A Hierarchical Goal-Based Formalism and Algorithm for Single-Agent Plannin

Plan generation is important in a number of agent applications, but such applications generally require elaborate domain models that include not only the definitions of the actions that an agent can perform in a given domain, but also information about the most effective ways to generate plans for the agent in that domain. Such models typically take a large amount of human effort to create.

To alleviate this problem, we have developed a hierarchical goalbased planning formalism and a planning algorithm, GDP (GoalDecomposition Planner), that combines some aspects of both HTN planning and domain-independent planning. For example, it allows the planning agent to use domain-independent heuristic functions to guide the application of both methods and actions.

This paper describes the formalism, planning algorithm, correctness theorems, and the results of a large experimental study. The experiments show that our planning algorithm works as well as the well-known SHOP2 HTN planner, using domain models only about half the size of SHOP2’s. 

PDF docuemnt is available at aamas-conference.org

Shivashankar, V., Kuter, U., Nau, D., and Alford, R. A Hierarchical Goal-Based Formalism and Algorithm for Single-Agent Planning. AAMAS-12: Proceedings of the Eleventh International Conference on Autonomous Agents and Multiagent Systems, Valencia, Spain (June 2012).