Fast Planning by Search in Domain Transition Graphs

Yixin Chen, Ruoyun Huang, Weixiong Zhang

Recent advances in classical planning have used the SAS+ formalism, and several effective heuristics have been developed based on the SAS+ formalism. Comparing to the traditional STRIPS/ADL formalism, SAS+ is capable of capturing vital information such as domain transition structures and causal dependencies. In this paper, we propose a new SAS+ based incomplete planning approach. Instead of using SAS+ to derive heuristics within a heuristic search planner, 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+ representation 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.

Subjects: 1.11 Planning; Please choose a second document classification

Submitted: Apr 10, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.