Fast Planning by Search in Domain Transition Graphs

Recent advances in classical planning have used the SAS+ formalism, and several effective heuristics have been devel-oped based on the SAS+ formalism. Comparing to the tra-ditional STRIPS/ADL formalism, SAS+ is capable of cap-turing vital information such as domain transition structures and causal dependencies. In this paper, we propose a new SAS+ based incomplete planning approach. Instead of us-ing SAS+ to derive heuristics within a heuristic search plan-ner, we directly search in domain transition graphs (DTGs) and causal graphs (CGs) derived from the SAS+ formalism. The new method is efficient because the SAS+ representa-tion is often much more compact than STRIPS. The CGs and DTGs provide rich information of domain structures that can effectively guide the search towards solutions. Experimental results show strong performance of the proposed planner on recent international planning competition domains