Elamur Research⌕
☰
home / papers / 2006 / The Fast Downward Planning System

The Fast Downward Planning System

Paper · 2006 · M. Helmert

Summary

Classical planners such as HSP and FF search directly over propositional PDDL encodings. In those encodings the dependencies between facts are usually tangled, so the hierarchical reasoning people apply naturally is hard to automate. In a logistics task, for example, a person would plan parcel routing separately from vehicle movement. Helmert presents Fast Downward, a forward-search heuristic planner that first rewrites PDDL2.2 tasks, including ADL constructs and derived predicates, into multi-valued planning tasks. In this form, the relations between state variables become explicit as causal graphs and domain transition graphs. A knowledge-compilation stage builds these structures along with fast successor generators and axiom evaluators. The search stage relies on the causal graph heuristic, which drops some preconditions to remove causal cycles and then solves small subproblems centred on one variable and its causal predecessors. Several new search-control techniques support it. Fast Downward won the classical track of IPC-4 and also did well on benchmarks from earlier competitions. The work shows that multi-valued encodings and hierarchical decomposition can power competitive domain-independent planning.

Key points

  • The architecture has three stages: translation (PDDL to a multi-valued task), knowledge compilation, and search. The translator is reusable and has been adopted by other planners, e.g. van den Briel et al. (2005).
  • The search enhancements are:
    • preferred operators, which bring FF's helpful-actions idea into global best-first search;
    • deferred heuristic evaluation, which reduces the cost of large branching factors;
    • multi-heuristic best-first search, which combines the causal graph heuristic with the FF heuristic.
  • The paper also introduces focused iterative-broadening search, a non-heuristic algorithm that uses causal-graph information to prune the operators it considers.
  • In experiments, adding preferred operators (going from M to M+P) helped in fifteen domains and hurt in two. In each of those two domains, the loss was only one solved task.
  • At the 4th International Planning Competition (ICAPS 2004), Fast Downward took first place in the propositional track for planners not required to optimise plan quality. The paper appeared in JAIR 26 (2006), pp. 191–246.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of FreiburgFreiburg im Breisgau · Germany8 works · 1,661 citations

 Fields, topics and concepts

📚 Shelves 3The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksComputer Networks and Communications · 115 works

Cite

Cite as M. Helmert. 2006. The Fast Downward Planning System. Journal of Artificial Intelligence Research.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1613/jair.1705

@article{helmert2006fast,
  title = {{The Fast Downward Planning System}},
  author = {M. Helmert},
  journal = {Journal of Artificial Intelligence Research},
  year = {2006},
  doi = {10.1613/jair.1705},
  url = {https://doi.org/10.1613/jair.1705}
}

References

34 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Bacchus, F., & Yang, Q. (1994). Downward refinement and the efficiency of hierarchical problem solving. Artificial Intelligence, 71(1), 43–100. find
  2. Bäckström, C., & Nebel, B. (1995). Complexity results for SAS + planning. Computational Intelligence, 11(4), 625–655. find
  3. Bonet, B., & Geffner, H. (2001). Planning as heuristic search. Artificial Intelligence, 129(1), 5–33. find
  4. Brafman, R. I., & Domshlak, C. (2003). Structure and complexity in planning with unary operators. Journal of Artificial Intelligence Research, 18, 315–349. find
  5. Bylander, T. (1994). The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69(1–2), 165–204. find
  6. Domshlak, C., & Brafman, R. I. (2002). Structure and complexity in planning with unary operators. In Ghallab, M., Hertzberg, J., & Traverso, P. (Eds.), Proceedings of the Sixth International Conference on Artificial Intelligence Planning and Scheduling (AIPS 2002), pp. 34–43. AAAI Press. find
  7. Domshlak, C., & Dinitz, Y. (2001). Multi-agent off-line coordination: Structure and complexity. In Cesta, A., & Borrajo, D. (Eds.), Pre-proceedings of the Sixth European Conference on Planning (ECP’01), pp. 277–288, Toledo, Spain. find
  8. Dowling, W. F., & Gallier, J. H. (1984). Linear-time algorithms for testing the satisfiability of propositional Horn formulae. Journal of Logic Programming, 1(3), 367–383. find
  9. Edelkamp, S., & Helmert, M. (1999). Exhibiting knowledge in planning problems to minimize state encoding length. In Fox, M., & Biundo, S. (Eds.), Recent Advances in AI Planning. 5th European Conference on Planning (ECP’99), Vol. 1809 of Lecture Notes in Artificial Intelligence, pp. 135–147, New York… find
  10. Edelkamp, S., & Hoffmann, J. (2004). PDDL2.2: The language for the classical part of the 4th International Planning Competition. Tech. rep. 195, Albert-Ludwigs-Universität Freiburg, Institut für Informatik. find
  11. Fox, M., & Long, D. (2003). PDDL2.1: An extension to PDDL for expressing temporal planning domains. Journal of Artificial Intelligence Research, 20, 61–124. find
  12. Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability — A Guide to the Theory of NP-Completeness. Freeman. find
  13. Gerevini, A., Saetti, A., & Serina, I. (2003). Planning through stochastic local search and temporal action graphs in LPG. Journal of Artificial Intelligence Research, 20, 239–290. find
  14. Ginsberg, M. L., & Harvey, W. D. (1992). Iterative broadening. Artificial Intelligence, 55, 367–383. find
  15. Helmert, M. (2004). A planning heuristic based on causal graph analysis. In Zilberstein, S., Koehler, J., & Koenig, S. (Eds.), Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling (ICAPS 2004), pp. 161–170. AAAI Press. find
  16. Hoffmann, J. (2001). Local search topology in planning benchmarks: An empirical analysis. In Nebel, B. (Ed.), Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI’01), pp. 453–458. Morgan Kaufmann. find
  17. Hoffmann, J. (2002). Local search topology in planning benchmarks: A theoretical analysis. In Ghallab, M., Hertzberg, J., & Traverso, P. (Eds.), Proceedings of the Sixth International Conference on Artificial Intelligence Planning and Scheduling (AIPS 2002), pp. 92–100. AAAI Press. find
  18. Hoffmann, J. (2005). Where ‘ignoring delete lists’ works: Local search topology in planning benchmarks. Journal of Artificial Intelligence Research, 24, 685–758. find
  19. Hoffmann, J., & Edelkamp, S. (2005). The deterministic part of IPC-4: An overview. Journal of Artificial Intelligence Research, 24, 519–579. find
  20. Hoffmann, J., & Nebel, B. (2001). The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research, 14, 253–302. find
  21. Jonsson, P., & Bäckström, C. (1995). Incremental planning. In Ghallab, M., & Milani, A. (Eds.), New Directions in AI Planning: EWSP ’95 — 3rd European Workshop on Planning, Vol. 31 of Frontiers in Artificial Intelligence and Applications, pp. 79–90, Amsterdam. IOS Press. find
  22. Jonsson, P., & Bäckström, C. (1998a). State-variable planning under structural restrictions: Algorithms and complexity. Artificial Intelligence, 100(1–2), 125–176. find
  23. Jonsson, P., & Bäckström, C. (1998b). Tractable plan existence does not imply tractable plan generation. Annals of Mathematics and Artificial Intelligence, 22(3), 281–296. find
  24. Joslin, D., & Roach, J. (1989). A theoretical analysis of conjunctive-goal problems. Artificial Intelligence, 41(1), 97–106. Research Note. find
  25. Knoblock, C. A. (1994). Automatically generating abstractions for planning. Artificial Intelligence, 68(2), 243–302. find
  26. Korf, R. E. (1987). Planning as search: A quantitative approach. Artificial Intelligence, 33(1), 65–88. find
  27. Lowerre, B. T. (1976). The HARPY Speech Recognition System. Ph.D. thesis, Computer Science Department, Carnegie-Mellon University, Pittsburgh, Pennsylvania. find
  28. Newell, A., & Simon, H. A. (1963). GPS: A program that simulates human thought. In Feigenbaum, E. A., & Feldman, J. (Eds.), Computers and Thought, pp. 279–293. Oldenbourg. find
  29. Russell, S., & Norvig, P. (2003). Artificial Intelligence — A Modern Approach. Prentice Hall. find
  30. Sacerdoti, E. D. (1974). Planning in a hierarchy of abstraction spaces. Artificial Intelligence, 5, 115–135. find
  31. Tenenberg, J. D. (1991). Abstraction in planning. In Allen, J. F., Kautz, H. A., Pelavin, R. N., & Tenenberg, J. D., Reasoning About Plans, chap. 4, pp. 213–283. find
  32. Morgan Kaufmann, San Mateo. van den Briel, M., Vossen, T., & Kambhampati, S. (2005). Reviving integer programming approaches for AI planning: A branch-and-cut framework. In Biundo, S., Myers, K., & Rajan, K. (Eds.), Proceedings of the Fifteenth International Conference on Automated Planning and Sche… find
  33. Williams, B. C., & Nayak, P. P. (1997). A reactive planner for a model-based executive. In Pollack, M. E. (Ed.), Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI’97), pp. 1178–1195. Morgan Kaufmann. find
  34. Yoshizumi, T., Miura, T., & Ishida, T. (2000). A ∗ with partial expansion for large branching factor problems. In Kautz, H., & Porter, B. (Eds.), Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI-2000), pp. 923–929. AAAI Press. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/helmert-2006-fast-downward-planning-system/