| 1. |
- Bäckström, Christer, et al.
(författare)
-
From Macro Plans to Automata Plans
- 2012
-
Ingår i: ECAI 2012. 20th European Conference on Artificial Intelligence, 27-31 2012, August, Montpellier, France. - 9781614990970 - 9781614990987 ; , s. 91-96
-
Konferensbidrag (refereegranskat)abstract
- Macros have a long-standing role in planning as a tool for representing repeating subsequences of operators. Macros are useful both for guiding search towards a solution and for representing plans compactly. In this paper we introduce automata plans which consist of hierarchies of finite state automata. Automata plans can be viewed as an extension of macros that enables parametrization and branching. We provide several examples of the utility of automata plans, and prove that automata plans are strictly more expressive than macro plans. We also prove that automata plans admit polynomialtime sequential access of the operators in the underlying “flat” plan, and identify a subset of automata plans that admit polynomial-time random access. Finally, we compare automata plans with other representations allowing polynomial-time sequential access.
|
|
| 2. |
- Bäckström, Christer, et al.
(författare)
-
Macros, Reactive Plans and Compact Representations
- 2012
-
Ingår i: ECAI 2012. 20th European Conference on Artificial Intelligence 27-31 August 2+12, Montpellier, France. - 9781614990970 - 9781614990987 ; , s. 85-90
-
Konferensbidrag (refereegranskat)abstract
- The use and study of compact representations of objects is widespread in computer science. AI planning can be viewed as the problem of finding a path in a graph that is implicitly described by a compact representation in a planning language. However, compact representations of the path itself (the plan) have not received much attention in the literature. Although both macro plans and reactive plans can be considered as such compact representations, little emphasis has been placed on this aspect in earlier work. There are also compact plan representations that are defined by their access properties, for instance, that they have efficient random access or efficient sequential access. We formally compare two such concepts with macro plans and reactive plans, viewed as compact representations, and provide a complete map of the relationships between them.
|
|
| 3. |
- Jonsson, Anders, et al.
(författare)
-
When Acyclicity is not Enough: Limitations of the Causal Graph
- 2013
-
Ingår i: Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling. - : AAAI Press. - 9781577356097 ; , s. 117-125
-
Konferensbidrag (refereegranskat)abstract
- Causal graphs are widely used in planning to capture the internal structure of planning instances. In the past, causal graphs have been exploited to generate hierarchical plans, to compute heuristics, and to identify classes of planning instances that are easy to solve. It is generally believed that planning is easier when the causal graph is acyclic. In this paper we show that this is not true in the worst case, proving that the problem of plan existence is PSPACE-complete even when the causal graph is acyclic. Since the variables of the planning instances in our reduction are propositional, this result applies to STRIPS planning with negative pre-conditions. Having established that planning is hard for acyclic causal graphs, we study a subclass of planning instances with acyclic causal graphs whose variables have strongly connected domain transition graphs. For this class, we show that plan existence is easy, but that bounded plan existence is hard, implying that optimal planning is significantly harder than satisficing planning for this class.
|
|
