Proceedings

Optimal Symbolic Planning with Action Costs and Preferences

Download BibTeX Cite

Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 1690-1694.

© 2009 International Joint Conferences on Artificial Intelligence

Abstract

This paper studies the solving of finite-domain action planning problems with discrete action costs and soft constraints. For sequential optimal planning, a symbolic perimeter database heuristic is addressed in a bucket implementation of A*. For computing net-benefits, we propose symbolic branch-and-bound search together with some search refinements. The net-benefit we optimize is the total benefit of satisfying the goals, minus the total action cost to achieve them. This results in an objective function to be minimized that is a linear expression over the violation of the preferences added to the action cost total.Stefan Edelkamp, Peter Kissmann

  1. [Ahuja et al., 1990] R. K. Ahuja, K. Mehlhorn, J. B. Orlin, and R. E. Tarjan. Faster algorithms for the shortest path problem. Journal of the ACM, 37(2):213-223, 1990.
  2. [Anderson et al., 2007] K. Anderson, R. Holte, and J. Schaeffer. Partial pattern databases. In SARA, Lecture Notes in Computer Science, pages 20-34. Springer, 2007.
  3. [Ball and Holte, 2008] M. Ball and R. C. Holte. The com- pression power of symbolic pattern databases. In ICAPS, pages 2-11, 2008.
  4. [Bartzis and Bultan, 2006] C. Bartzis and T. Bultan. Effi- cient BDDs for bounded arithmetic constraints. STTT, 8(1):26-36, 2006.
  5. [Bryant, 1986] R. E. Bryant. Graph based algorithms for boolean function manipulation. IEEE Transaction on Computing, 35(8):677-691, 1986.
  6. [Cimatti et al., 1997] A. Cimatti, E. Giunchiglia, F. Giunchi- glia, and P. Traverso. Planning via model checking: A de- cision procedure for AR. In ECP, Lecture Notes in Com- puter Science, pages 130-142. Springer, 1997.
  7. [Dial, 1969] R. B. Dial. Shortest-path forest with topological ordering. Communications of the ACM, 12(11):632-633, 1969.
  8. [Dijkstra, 1959] E. W. Dijkstra. A note on two problems in connection with graphs. Numerische Mathematik, 1:269- 271, 1959.
  9. [Dillenburg and Nelson, 1994] J. F. Dillenburg and P. C. Nel- son. Perimeter search. Artificial Intelligence, 65(1):165- 178, 1994.
  10. [Edelkamp and Helmert, 1999] S. Edelkamp and M. Hel- mert. Exhibiting knowledge in planning problems to min- imize state encoding length. In ECP, Lecture Notes in Computer Science, pages 135-147. Springer, 1999.
  11. [Edelkamp and Reffel, 1998] S. Edelkamp and F. Reffel. OBDDs in heuristic search. In KI, pages 81-92, 1998.
  12. [Edelkamp, 2002] S. Edelkamp. Symbolic pattern databa- ses in heuristic search planning. In AIPS, pages 274-293, 2002.
  13. [Edelkamp, 2006] S. Edelkamp. Cost-optimal symbolic planning with state trajectory and preference constraints. In ECAI, pages 841-842, 2006.
  14. [Gerevini et al., 2009] A. E. Gerevini, P. Haslum, D. Long, A. Saetti, and Y. Dimopoulos. Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners. Artificial Intelli- gence, 173(5-6):619-668, 2009.
  15. [Hansen et al., 2002] E. A. Hansen, R. Zhou, and Z. Feng. Symbolic heuristic search using decision diagrams. In SARA, Lecture Notes in Computer Science, pages 83-98. Springer, 2002.
  16. [Helmert, 2008] M. Helmert. Understanding Planning Tasks: Domain Complexity and Heuristic Decomposi- tion, volume 4929 of Lecture Notes in Computer Science. Springer, 2008.
  17. [Jensen et al., 2006] R. Jensen, E. Hansen, S. Richards, and R. Zhou. Memory-efficient symbolic heuristic search. In ICAPS, pages 304-313, 2006.
  18. [Jensen et al., 2008] R. M. Jensen, M. M. Veloso, and R. E. Bryant. State-set branching: Leveraging BDDs for heuris- tic search. Artificial Intelligence, 172(2-3):103-139, 2008.
  19. [Kautz and Selman, 1996] H. Kautz and B. Selman. Pushing the envelope: Planning propositional logic, and stochastic search. In AAAI, pages 1194-1201, 1996.
  20. [Smith, 2004] D. Smith. Choosing objectives in over- subscription planning. In ICAPS, pages 393-401, 2004.
  21. [van den Briel et al., 2004] M. van den Briel, R. Sanches, M. B. Do, and S. Kamphampati. Effective approaches for partial satisfaction (over-subscription) planning. In AAAI, pages 562-569, 2004.
  22. [Zhou and Hansen, 2004] R. Zhou and E. A. Hansen. Breadth-first heuristic search. In ICAPS, pages 92-100, 2004.

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

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