Heuristics for Domain-Independent Planning: A Survey

Abstract:

Increasing interest has been devoted to Planning as Heuristic Search over the years. Intense research has focused on deriving fast and accurate heuristics for domain-independent planning. This paper reports on an extensive survey and analysis of research work related to heuristic derivation techniques for state space search. Survey results reveal that heuristic techniques have been extensively applied in many efficient planners and result in impressive performances. We extend the survey analysis to suggest promising avenues for future research in heuristic derivation and heuristic search techniques.

• Periodical: Applied Mechanics and Materials (Volumes 135-136)
• Pages: 573-577
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.135-136.573
• Online since: October 2011
• Authors: Rui Shi Liang, Min Huang
• Keywords: AI Planning, Heuristic Derivation, Heuristic Search

References

[1] Helmert M. 2003. Complexity results for standard benchmark domains in planning. Artificial Intelligence 143(2): 219~262.

DOI: 10.1016/s0004-3702(02)00364-8

[2] Fikes, R. Nilsson, N. 1971. STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence 2: 189-208.

DOI: 10.1016/0004-3702(71)90010-5

[3] International Planning Competition Archives official website: http: /ipc. icaps-conference. org.

[4] Bonet, B., Geffner, H. Planning as Heuristic Search. 2001. Artificial Intelligence 129: 5-33.

DOI: 10.1016/s0004-3702(01)00108-4

[5] Hoffmann, J. and Nebel, B. 2001. The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research 14: 253-302.

DOI: 10.1613/jair.855

[6] Helmert, M. 2006. The fast downward planning system. Journal of Artificial Intelligence Research, 26: 191-246.

DOI: 10.1613/jair.1705

[7] Richter, S. and Westphal, M. The LAMA planner: Guiding cost-based anytime planning with landmarks. Journal of Artificial Intelligence Research, 2010, 39: 127-177.

DOI: 10.1613/jair.2972

[8] Haslum, P.; Bonet, B.; and Geffner, H. 2005. New admissible heuristics for domain-independent planning. In Proc. AAAI 2005, 1163–1168.

[9] Edelkamp, S. 2001. Planning with pattern databases. In Proc. ECP 2001, 13–24.

[10] Karpas, E., & Domshlak, C. 2009. Cost-optimal planning with landmarks. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI 2009), p.1728–1733.

[11] Helmert, M.; Haslum, P.; and Hoffmann, J. 2007. Flexible abstraction heuristics for optimal sequential planning. In Proc. ICAPS 2007, 176–183.

[12] Katz, M., and Domshlak, C. 2009. Structural-pattern databases. In Proc ICAPS 2009, 186–193.

DOI: 10.1609/icaps.v19i1.13351

[13] Katz, M., and Domshlak, C. Implicit Abstraction Heuristics. Journal of Artificial Intelligence Research, 2010, 39: 51-126.

DOI: 10.1613/jair.3063

[14] Katz, M., & Domshlak, C. (2010). Optimal admissible composition of abstraction heuristics. Artificial Intelligence, 174, 767–798.

DOI: 10.1016/j.artint.2010.04.021

[15] Hoffmann J and Porteous J and Sebastia L. Ordered landmarks in planning. Journal of Artificial Intelligence Research, 2004, 22: 215-278.

DOI: 10.1613/jair.1492

[16] Karpas, E., & Domshlak, C. (2009). Cost-optimal planning with landmarks. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-09), p.1728–1733, Pasadena, CA, USA.

[17] Domshlak, C., Katz, M., & Lefler, S. 2010. When abstractions met landmarks. In Proc ICAPS 2010, p.50–56.

DOI: 10.1609/icaps.v20i1.13409