Using State-Based Planning Heuristics for Partial-Order Causal-Link Planning

详细信息    查看全文

• 作者：Pascal Bercher (21)
  Thomas Geier (21)
  Susanne Biundo (21)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：8077
• 期：1
• 页码：13-24
• 全文大小：221KB
• 参考文献：1. Bercher, P., Biundo, S.: Encoding partial plans for heuristic search. In: Proceedings of the 4th Workshop on Knowledge Engineering for Planning and Scheduling (KEPS 2013), pp. 11鈥?5 (2013)
  2. Blum, A.L., Furst, M.L.: Fast planning through planning graph analysis. Artificial Intelligence聽90, 281鈥?00 (1997) CrossRef
  3. Coles, A., Coles, A., Fox, M., Long, D.: Forward-chaining partial-order planning. In: Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), pp. 42鈥?9. AAAI Press (2010)
  4. Dr盲ger, K., Finkbeiner, B., Podelski, A.: Directed model checking with distance-preserving abstractions. In: Valmari, A. (ed.) SPIN 2006. LNCS, vol.聽3925, pp. 19鈥?4. Springer, Heidelberg (2006) CrossRef
  5. Fikes, R.E., Nilsson, N.J.: STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence聽2, 189鈥?08 (1971) CrossRef
  6. Haslum, P., Geffner, H.: Admissible heuristics for optimal planning. In: Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems (AIPS 2000), pp. 140鈥?49. AAAI Press (2000)
  7. Helmert, M.: The fast downward planning system. Journal of Artificial Intelligence Research (JAIR)聽26, 191鈥?46 (2006) CrossRef
  8. Helmert, M., Domshlak, C.: Landmarks, critical paths and abstractions: Whats the difference anyway? In: Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009), vol.聽9, pp. 162鈥?69 (2009)
  9. Helmert, M., Haslum, P., Hoffmann, J.: Flexible abstraction heuristics for optimal sequential planning. In: Proceedings of the 17th International Conference on Automated Planning and Scheduling (ICAPS 2007), pp. 176鈥?83 (2007)
  10. Hoffmann, J., Nebel, B.: The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research (JAIR)聽14, 253鈥?02 (2001)
  11. Joslin, D., Pollack, M.E.: Least-cost flaw repair: A plan refinement strategy for partial-order planning. In: Proceedings of the 12th National Conference on Artificial Intelligence (AAAI 1994), pp. 1004鈥?009. AAAI Press (1994)
  12. Kambhampati, S.: Refinement planning as a unifying framework for plan synthesis. AI Magazine聽18(2), 67鈥?8 (1997)
  13. McAllester, D., Rosenblitt, D.: Systematic nonlinear planning. In: Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI 1991), pp. 634鈥?39. AAAI Press (1991)
  14. Muise, C., McIlraith, S.A., Beck, J.C.: Monitoring the execution of partial-order plans via regression. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), pp. 1975鈥?982. AAAI Press (2011)
  15. Nebel, B., B盲ckstr枚m, C.: On the computational complexity of temporal projection, planning, and plan validation. Artificial Intelligence聽66(1), 125鈥?60 (1994) CrossRef
  16. Nguyen, X., Kambhampati, S.: Reviving partial order planning. In: Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI 2001), pp. 459鈥?66. Morgan Kaufmann (2001)
  17. Penberthy, J.S., Weld, D.S.: UCPOP: A sound, complete, partial order planner for ADL. In: Proceedings of the third International Conference on Knowledge Representation and Reasoning, pp. 103鈥?14. Morgan Kaufmann (1992)
  18. Ram铆rez, M., Geffner, H.: Plan recognition as planning. In: Boutilier, C. (ed.) Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI 2009), pp. 1778鈥?783. AAAI Press (July 2009)
  19. Seegebarth, B., M眉ller, F., Schattenberg, B., Biundo, S.: Making hybrid plans more clear to human users 鈥?a formal approach for generating sound explanations. In: Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS 2012), pp. 225鈥?33. AAAI Press (June 2012)
  20. Vidal, V., Geffner, H.: Branching and pruning: An optimal temporal POCL planner based on constraint programming. Artificial Intelligence聽170(3), 298鈥?35 (2006) CrossRef
  21. Weld, D.S.: Systematic nonlinear planning: A commentary. AI Magazine聽32(1), 101鈥?03 (2011)
  22. Younes, H.L.S., Simmons, R.G.: VHPOP: Versatile heuristic partial order planner. Journal of Artificial Intelligence Research (JAIR)聽20, 405鈥?30 (2003)
  
• 作者单位：Pascal Bercher (21)
  Thomas Geier (21)
  Susanne Biundo (21)
  
  21. Institute of Artificial Intelligence, Ulm University, D-89069, Ulm, Germany
  

文摘

We present a technique which allows partial-order causal-link (POCL) planning systems to use heuristics known from state-based planning to guide their search. The technique encodes a given partially ordered partial plan as a new classical planning problem that yields the same set of solutions reachable from the given partial plan. As heuristic estimate of the given partial plan a state-based heuristic can be used estimating the goal distance of the initial state in the encoded problem. This technique also provides the first admissible heuristics for POCL planning, simply by using admissible heuristics from state-based planning. To show the potential of our technique, we conducted experiments where we compared two of the currently strongest heuristics from state-based planning with two of the currently best-informed heuristics from POCL planning.