Ruoyun Huang, Yixin Chen, Weixiong Zhang,


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


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