Proceedings

A Heuristic Search Approach to Planning with Temporally Extended Preferences

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 1808-1814.

© 2007 International Joint Conferences on Artificial Intelligence

Abstract

In this paper we propose a suite of techniques for planning with temporally extended preferences (TEPs). To this end, we propose a method for compiling TEP planning problems into simpler domains containing only final-state (simple) preferences and metric functions. With this simplified problem in hand, we propose a variety of heuristic functions for planning with final-state preferences, together with an incremental best-first planning algorithm. A key feature of the planning algorithm is its ability to prune the search space. We identify conditions under which our planning algorithm will generate optimal plans. We implemented our algorithm as an extension to the lplan ~planning system and report on extensive testing performed to evaluate the effectiveness of our heuristics and algorithm. Our planner, hplanp{}, competed in the 5th International Planning Competition, achieving distinguished performance in the emph{qualitative preferences} track.

  1. [Bacchus and Kabanza, 1998] F. Bacchus and F. Kabanza. Plan- ning for temporally extended goals. Annals of Mathematics and Artificial Intelligence, 22(1-2):5-27, 1998.
  2. [Baier and McIlraith, 2006] J. A. Baier and S. A. McIlraith. Plan- ning with first-order temporally extended goals using heuristic search. In Proc. of the 21st National Conference on Artificial Intelligence (AAAI-06), pp. 788-795, Boston, MA, 2006.
  3. [Benton et al., 2006] J. Benton, S. Kambhampati, and M. B. Do. YochanPS: PDDL3 simple preferences and partial satisfaction planning. In 5th International Planning Competition Booklet (IPC-2006), pp. 54-57, Lake District, England, July 2006.
  4. [Bienvenu et al., 2006] M. Bienvenu, C. Fritz, and S. McIlraith. Planning with qualitative temporal preferences. In Proc. of the 10th Int'l Conference on Knowledge Representation and Reason- ing (KR-06), pp. 134-144, Lake District, England, 2006.
  5. [Brafman and Chernyavsky, 2005] R. Brafman and Y. Chernyavsky. Planning with goal preferences and con- straints. In Proc. of the 15th Int'l Conference on Automated Planning and Scheduling (ICAPS-05), pp. 182-191, June 2005.
  6. [Delgrande et al., 2004] J. P. Delgrande, T. Schaub, and H. Tom- pits. Domain-specific preferences for causal reasoning and plan- ning. In Proc. of the 14th Int'l Conference on Automated Plan- ning and Scheduling (ICAPS-04), pp. 63-72, Whistler, Canada, June 2004.
  7. [Edelkamp et al., 2006] S. Edelkamp, S. Jabbar, and M. Naizih. Large-scale optimal PDDL3 planning with MIPS-XXL. In 5th International Planning Competition Booklet (IPC-2006), pp. 28- 30, Lake District, England, July 2006.
  8. [Edelkamp, 2006] S. Edelkamp. Optimal symbolic PDDL3 plan- ning with MIPS-BDD. In 5th International Planning Competi- tion Booklet (IPC-2006), pp. 31-33, Lake District, England, July 2006.
  9. [Gerevini and Long, 2005] A. Gerevini and D. Long. Plan con- straints and preferences for PDDL3. Technical Report 2005- 08-07, Department of Electronics for Automation, University of Brescia, Brescia, Italy, 2005.
  10. [Gerevini et al., 2006] A. Gerevini, Y. Dimopoulos, P. Haslum, and A. Saetti. 5th International Planning Competition, July 2006. http://zeus.ing.unibs.it/ipc-5/. Link
  11. [Hoffmann and Nebel, 2001] J. Hoffmann and B. Nebel. The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research, 14:253-302, 2001.
  12. [Hoffmann, 2003] J. Hoffmann. The Metric-FF planning system: Translating "ignoring delete lists" to numeric state variables. Journal of Artificial Intelligence Research, 20:291-341, 2003.
  13. [Hsu et al., 2007] C.-W. Hsu, B. Wah, R. Huang, and Y. Chen. Con- straint partitioning for solving planning problems with trajectory constraints and goal preferences. In Proc. of the 20th Int'l Joint Conference on Artificial Intelligence (IJCAI-07), Hyderabad, In- dia, January 2007. To appear. IJCAI
  14. [Son and Pontelli, 2004] T. C. Son and E. Pontelli. Planning with preferences using logic programming. In Proc. of the 7th Int'l Conference on Logic Programming and Nonmonotonic Reason- ing (LPNMR-04), number 2923 in LNCS, pp. 247-260. Springer, 2004.
  15. [Zhu and Givan, 2005] L. Zhu and R. Givan. Simultaneous heuris- tic search for conjunctive subgoals. In Proc. of the 20th National Conference on Artificial Intelligence (AAAI-05), pp. 1235-1241, Pittsburgh, Pennsylvania, USA, July 9-13 2005.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards