Causal graphs and structurally restricted planning
Hubie Chen, Omer Giménez · 2008
The causal graph is a directed graph that describes the vari-able dependencies present in a planning instance. A num-ber of papers have studied the causal graph in both practical and theoretical settings. In this work, we systematically study the complexity of planning restricted by the causal graph. In particular, any set of causal graphs gives rise to a subcase of the planning problem. We give a complete classification theorem on causal graphs, showing that a set of graphs is either polynomial-time tractable, or is not polynomial-time tractable unless an established complexity-theoretic assump-tion fails; our theorem describes which graph sets correspond to each of the two cases. We also give a classification theorem for the case of reversible planning, and discuss the general di-rection of structurally restricted planning.