China
Africa
Explore chapters and articles related to this topic
Methodological and Tool Projects
Published in Peter Hoschka, Computers as Assistants, 2021
That looks pretty easy, but a “real” representation of the graphic domain would have to list a tremendous number of different operators, and draft graphics usually consist of more than just two objects, both facts causing the search space for a planner to grow to a considerable size. It has in fact been shown (Bylander, 1991) that even much-restricted instances of classical planning problems are PSPACE complete in terms of the problem size, which involves the number of objects and operators in the domain—that is, planning, even if it is decidable, falls into one of the nastiest complexity categories.
An optimal and a heuristic algorithm for the single-item retrieval problem in puzzle-based storage systems with multiple escorts
Published in International Journal of Production Research, 2019
Altan Yalcin, Achim Koberstein, Kai-Oliver Schocke
The problem treated in this paper is also related to the domain of robot motion planning problems (Latombe 1991), in particular to motion planning problems with movable obstacles. A well-studied instance of this problem class is the sliding block game Rush Hour (Flake and Baum 20020. Flake and Baum showed that the Rush Hour problem is PSPACE-complete. Tromp and Cilibrasi (2005) strengthened the result of Flake and Baum (2002) and showed that even the restricted case when all sliding blocks have size is PSPACE-complete. The complexity of the case when all blocks have size but may only move horizontally or only vertically remained an open question (Tromp and Cilibrasi 2005; Hearn and Demaine 2005. DePuy and Don Taylor (2007) provided an integer program formulation for the Rush Hour problem. The SRPME considered in this paper differs from the Rush Hour problem in that we have blocks which may move in any of the four directions.
Expectations for agents with goal-driven autonomy
Published in Journal of Experimental & Theoretical Artificial Intelligence, 2021
Dustin Dannenhauer, Héctor Muñoz-Avila, Michael T. Cox
One conclusion from this analysis is that the guiding sensing problem is at least PSPACE-hard since we show how to transform the problem, PLANMIN (Bylander, 1994), of generating a plan with at mist actions as a guiding sensing problem, PLANSENSE (defined below). Furthermore, we show that this transformation can be done in polynomial time on , so we proved that PLANMIN PLANSENSE. Since PLANMIN is PSPACE-complete (Bylander, 1994), then PLANSENSE must be at least PSPACE-hard. For completeness, we define both of these problems below: Definition. (PLANMIN) Given and a STRIPS planning problem , is there a solution plan for such that has at most steps?Definition. (PLANSENSE) Given and a guiding sensing problem , is there a solution plan for such that ?
Defeasible linear temporal logic
Published in Journal of Applied Non-Classical Logics, 2023
Anasse Chafik, Fahima Cheikh-Alili, Jean-François Condotta, Ivan Varzinczak
Sistla and Clarke (1985) proved that the satisfiability in to be a PSPACE-complete problem. Moreover, the satisfiability checking of many fragments of the language were investigated (Demri & Schnoebelen, 2002; Sistla & Clarke, 1985). Table 1 contains the complexity of some notable fragments. The notation denotes that the language of is restricted to the temporal operators between parenthesis. indicates that the negation is allowed on the atomic propositions only.