When Acyclicity is not Enough: Limitations of the Causal Graph

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)

AAAI Press, 2013
2013
English.
In: Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling. - : AAAI Press. - 9781577356097 ; , s. 117-125

Related links:: http://www.aaai.org/...; show more...; https://urn.kb.se/re...; show less...

Abstract Subject headings

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.

About the subject

NATURAL SCIENCES: NATURAL SCIENCES; and Computer and Inf ...; and Computer Science ...

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.