VHPOP: Versatile Heuristic Partial Order Planner

Håkan L. S. Younes Reid G. Simmons

Abstract
VHPOP is a partial order causal link (POCL) planner loosely based on UCPOP. It draws from the experience gained in the early to mid 1990's on flaw selection strategies for POCL planning, and combines this with more recent developments in the field of domain independent planning such as distance based heuristics and reachability analysis. We present an adaptation of the additive heuristic for plan space planning, and modify it to account for possible reuse of existing actions in a plan. We also propose a large set of novel flaw selection strategies, and show how these can help us solve more problems than previously possible by POCL planners. VHPOP also supports planning with durative actions by incorporating standard techniques for temporal constraint reasoning. We demonstrate that the same heuristic techniques used to boost the performance of classical POCL planning can be effective in domains with durative actions as well. The result is a versatile heuristic POCL planner competitive with established CSP-based and heuristic state space planners.

Full paper: PDF (26 pages, 33 references)
©2003 AI Access Foundation. All rights reserved.

Citings

  1. Nilufer Onder, Garrett C. Whelan, and Li Li. 2006. Engineering a conformant probabilistic planner. Journal of Artificial Intelligence Research 25:1–15.

  2. Vincent Vidal and Héctor Geffner. 2006. Branching and pruning: An optimal temporal POCL planner based on constraint programming. Artificial Intelligence 170(3):298–335.

  3. Daniel Bryce, Subbarao Kambhampati, and David E. Smith. 2006. Sequential Monte Carlo in probabilistic planning reachability heuristics. In Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling, 233–242. AAAI Press.

  4. William Cushing and Danel Bryce. 2005. State agnostic planning graphs and the application to belief-space planning. In Proceedings of the Twentieth National Conference on Artificial Intelligence, 1131–1138. AAAI Press.

  5. Joachim Peer. 2005. A POP-based replanning agent for automatic web service composition. In Proceedings of the Second European Semantic Web Conference, 47–61. Springer.

  6. Roman van der Krogt and Mathijs de Weerdt. 2005. Plan repair as an extension of planning. In Proceedings of the Fifteenth International Conference on Automated Planning and Scheduling, 161–170. AAAI Press.

  7. Roman van der Krogt, Nico Roos, Mathijs de Weerdt, and Cees Witteveen. 2005. Multiagent planning through plan repair. In Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems, 1337–1338. ACM Press.

  8. Roman van der Krogt and Mathijs de Weerdt. 2004. The two faces of plan repair. In Proceedings of the 16th Belgium-Netherlands Conference on Artificial Intelligence, 147–154. University of Groningen.

  9. Joachim Peer. 2004. A PDDL based tool for automatic Web service composition. In Proceedings of the Second International Workshop on Principles and Practice of Semantic Web Reasoning, 149–163. Springer.

  10. Oscar Sapena and Eva Onaindía. 2004. Handling numeric criteria in relaxed planning graphs. In Proceedings of the 9th Ibero-American Conference on Artificial Intelligence, 114–123. Springer.

  11. Vincent Vidal and Héctor Geffner. 2004. Branching and pruning: An optimal temporal POCL planner based on constraint programming. In Proceedings of the Nineteenth National Conference on Artificial Intelligence, 570–577. AAAI Press.

  12. Minh B. Do and Subbarao Kambhampati. 2003. Sapa: A multi-objective metric temporal planner. Journal of Artificial Intelligence Research 20:155–194.

  13. Derek Long and Maria Fox. 2003. The 3rd international planning competition: Results and analysis. Journal of Artificial Intelligence 20:1–59.


Håkan L. S. Younes Valid CSS! Valid XHTML 1.0!
Last modified: Fri Sep 28 15:23:36 EDT 2007