When Acyclicity is not Enough: Limitations of the Causal Graph

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.

Jonsson, PeterLinköpings universitet,Programvara och system,Tekniska högskolan(Swepub:liu)petjo00 (författare)
Lööw, TomasLinköpings universitet,Programvara och system,Tekniska högskolan(Swepub:liu)toman92 (författare)
Universitat Pompeu Fabra, Barcelona, SpainProgramvara och system (creator_code:org_t)

Ingår i:Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling: AAAI Press, s. 117-1259781577356097

Om ämnet

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.