Limitations of acyclic causal graphs for planning

Jonsson, Peter (author): Linköpings universitet,Programvara och system,Tekniska högskolan

Lööw, Tomas (author): Linköpings universitet,Programvara och system,Tekniska högskolan

(creator_code:org_t)

Elsevier, 2014
2014
English.
In: Artificial Intelligence. - : Elsevier. - 0004-3702 .- 1872-7921. ; 210, s. 36-55

Related links:: https://doi.org/10.1...; show more...; https://urn.kb.se/re...; https://doi.org/10.1...; show less...

Abstract Subject headings

Causal graphs are widely used in planning to capture the internal structure of planning instances. Researchers have paid special attention to the subclass of planning instances with acyclic causal graphs, which in the past have been exploited to generate hierarchical plans, to compute heuristics, and to identify classes of planning instances that are easy to solve. This naturally raises the question of whether planning is easier when the causal graph is acyclic. In this article we show that the answer to this question is no, proving that in the worst case, 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 preconditions. We show that the reduction still holds if we restrict actions to have at most two preconditions. Having established that planning is hard for acyclic causal graphs, we study two subclasses of planning instances with acyclic causal graphs. One such subclass is described by propositional variables that are either irreversible or symmetrically reversible. Another subclass is described by variables with strongly connected domain transition graphs. In both cases, plan existence is bounded away from PSPACE, but in the latter case, the problem of bounded plan existence is hard, implying that optimal planning is significantly harder than satisficing planning for this class.

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.