DTG-Plan
Ruoyun Huang, Yixin Chen, Weixiong Zhang,


Introduction

Most planning problems are of hierachically structured, in which case we are supposed to be able to retrieve a solution by doing causal analysis in a greedy fashion. However, simply applying this technique assumes that all the goals are interleaving/disjoint, which is typically not the truth. To take advantage of the structures, but in the meanwhile not be hampered by its limitation, we propose DTG-Plan.
It is an anytime algorithm planner consisted of two components. The higher level component uses the A* search algorithm which searches in an abstracted search space that expands each node during the search by one transition in a particular Domain Transition Grapha (DTG). The expanded transition might be of only one single action (if all preconditions are satisfied) or a sequnence of actions (if not all of the preconditions are satisfied). The corresponding sequence of actions for a transition is resolved by the lower level component, which is a greedy causal analysis based algorithm. It conducts causal analysis and retrieves a valid plan very fast. The upper level search component keeps increasing its scope (i.e. to a larger subset of the DTGs for the original problem), and incrementally increases the quality of the solution.




Software download: Source Code
Uncompress the src files.
Use the script 'build.sh' to compile the source code.
Use the script 'plan.sh' to run the solver.
      ./plan.sh domain.pddl problem.pddl


References


Acknowledgments
This research is supported by funds from Washington University in St Louis, National Science Foundation, Department of Energy, and Microsoft Research.

The parser for PDDL used in DTG-Plan is mostly based on the parser developed in Fast-Downward by Malte Helmert.


Any question, please contact: ruoyun.huang@wustl.edu
Last updated on Nov 05, 2008