| 1. |
- Jonsson, Anders, et al.
(author)
-
When Acyclicity is not Enough: Limitations of the Causal Graph
- 2013
-
In: Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling. - : AAAI Press. - 9781577356097 ; , s. 117-125
-
Conference paper (peer-reviewed)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.
|
|
| 2. |
- Nilsson, Mikael, et al.
(author)
-
Incremental Dynamic Controllability Revisited
- 2013
-
In: Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS). - : AAAI Press. - 9781577356097
-
Conference paper (peer-reviewed)abstract
- Simple Temporal Networks with Uncertainty (STNUs) allow the representation of temporal problems where some durations are determined by nature, as is often the case for actions in planning. As such networks are generated it is essential to verify that they are dynamically controllable – executable regardless of the outcomes of uncontrollable durations – and to convert them to a dispatchable form. The previously published FastIDC algorithm achieves this incrementally and can therefore be used efficiently during plan construction. In this paper we show that FastIDC is not sound when new constraints are added, sometimes labeling networks as dynamically controllable when they are not. We analyze the algorithm, pinpoint the cause, and show how the algorithm can be modified to correctly detect uncontrollable networks.
|
|
| 3. |
- Warnquist, Håkan, et al.
(author)
-
Exploiting Fully Observable and Deterministic Structures in Goal POMDPs
- 2013
-
In: Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS). - : AAAI Press. - 9781577356097 ; , s. 242-250
-
Conference paper (peer-reviewed)abstract
- When parts of the states in a goal POMDP are fully observable and some actions are deterministic it is possibleto take advantage of these properties to efficiently generate approximate solutions. Actions that deterministically affect the fully observable component of the world state can be abstracted away and combined into macro actions, permitting a planner to converge more quickly. This processing can be separated from the main search procedure, allowing us to leverage existing POMDP solvers. Theoretical results show how a POMDP can be analyzed to identify the exploitable properties and formal guarantees are provided showing that the use of macro actions preserves solvability. The efficiency of the method is demonstrated with examples when used in combination with existing POMDP solvers.
|
|
