International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 5, No. 12, 8 Nov. 2013
Cover page and Table of Contents: PDF (size: 851KB)
Author(s)
Mohamed Elkawkagy
1,*
Heba Elbeh
1
Index Terms
Landmarks, Planning, Hybrid Planning
Abstract
Although planning techniques achieved a significant progress during recent years, solving many planning problem still difficult even for modern planners. In this paper, we will adopt landmark concept to hybrid planning setting - a method that combines reasoning about procedural knowledge and causalities. Landmarks are a well-known concept in the realm of classical planning. Recently, they have been adapted to hierarchical approaches. Such landmarks can be extracted in a pre-processing step from a declarative hierarchical planning domain and problem description. It was shown how this technique allows for a considerable reduction of the search space by eliminating futile plan development options before the actual planning. Therefore, we will present a new approach to integrate landmark pre-processing technique in the context of hierarchical planning with landmark technique in the classical planning. This integration allows to incorporate the ability of using extracted landmark tasks from hierarchical domain knowledge in the form of HTN and using landmark literals from classical planning. To this end, we will construct a transformation technique to transform the hybrid planning domain into a classical domain model. The methodologies in this paper have been implemented successfully, and we will present some experimental results that give evidence for the consid-erable performance increase gained through planning system.
Cite This Paper
Mohamed Elkawkagy, Heba Elbeh, "Landmarks in Hybrid Planning", International Journal of Intelligent Systems and Applications(IJISA), vol.5, no.12, pp.23-33, 2013. DOI:10.5815/ijisa.2013.12.02
Reference
[1]Dana S. Nau, Malik Ghallab, and Paolo Traverso, Automated Planning: Theory & Practice, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2004.
[2]Richard E. Fikes and Nils J. Nilsson, ‘STRIPS: a new approach to the application of theorem proving to problem solving’, Artificial Intelligence, 2, 189–208, (1971).
[3]Kutluhan Erol, James Hendler, and Dana S. Nau, ‘UMCP: A sound and complete procedure for hierarchical task-network planning’, in Proc. of AIPS 1994, pp. 249–254, (1994).
[4]Qiang Yang, Intelligent Planning. A Decomposition and Abstraction Based Approach, Springer, 1998.
[5]Avrim L. Blum and Merrick L. Furst, ‘Fast planning through planning graph analysis’, Artificial Intelligence, 90(1-2), 281–300, (1997).
[6]Drew McDermott, ‘The 1998 AI planning systems competition’, AI Magazine, 21(2), 35–55, (2000).
[7]Blai Bonet and Hctor Geffner, ‘Planning as heuristic search’, Artificial Intelligence, 129, 5–33, (2001).
[8]Jrg Hoffmann and Berhard Nebel, ‘The FF planning system: Fast plan generation through heuristic search’, Journal of Artificial Intelligence Research, 14, 253–302, (2001).
[9]Patrik Haslum, Blai Bonet, and Hctor Geffner, ‘New admissible heuristics for domain-independent planning’, in Proc. of AAAI-05, pp. 1163–1168, (2005).
[10]Julie Porteous, Laura Sebastia, and Jrg Hoffmann, ‘On the extraction, ordering, and usage of landmarks in planning’, in Proc. of ECP 2001, pp. 37–48, (2001).
[11]Jrg Hoffmann, Julie Porteous, and Laura Sebastia, ‘Ordered landmarks in planning’, Journal of Artificial Intelligence Research, 22, 215–278, (2004).
[12]Lin Zhu and Robert Givan, ‘Landmark extraction via planning graph propagation’, in Proc. of the ICAPS 2003 Doctoral Consortium, pp.156–160, (2003).
[13]Laura Sebastia, Eva Onaindia, and Eliseo Marzal, ‘Decomposition of planning problems’, AI Communications, 19(1), 49–81, (2006).
[14]Peter Gregory, Stephen Cresswell, Derek Long, and Julie Porteous, ‘On the extraction of disjunctive landmarks from planning problems via symmetry reduction’, in Proc. of SymCon 2004, pp. 34–41, (2004).
[15]Julie Porteous and Stephen Cresswell, ‘Extending landmarks analysis to reason about resources and repetition’, in Proc. of PLANSIG 2002, pp. 45–54, (2002).
[16]Erez Karpas and Carmel Domshlak, ‘Cost-optimal planning with landmarks’, in Proc. of IJCAI 2009, pp. 1728–1733, (2009).
[17]Vincent Vidal and Hctor Geffner, ‘Branching and pruning: An optimal temporal POCL planner based on constraint programming’, Artificial Intelligence, 170, 298–335, (2006).
[18]Silvia Richter, Malte Helmert, and Matthias Westphal, ‘Landmarks revisited’, in Proc. of AAAI 2008, pp. 975–982, (2008).
[19]Malte Helmert and Carmen Domshlak, ‘Landmarks, critical paths and abstractions: What’s the difference anyway?’, in Proc. of ICAPS 2009, pp. 162–169, (2009).
[20]Carmel Domshlak, Michael Katz, and Sagi Lefler, ‘When abstractions met landmarks’, in Proc. of ICAPS 2010, pp. 50–56, (2010).
[21]Blai Bonet and Malte Helmert, ‘Strengthening landmark heuristics via hitting sets’, in Proc. of ECAI 2010, pp. 329–334, (2010).
[22]Emil Keyder, Silvia Richter, and Malte Helmert, ‘Sound and complete landmarks for and/or graphs’, in Proc. of ECAI 2010, pp. 335–340, (2010).
[23]Mohamed Elkawkagy, Bernd Schattenberg, and Susanne Biundo, ‘Landmarks in hierarchical planning’, in Proc. of ECAI 2010, (2010).
[24]Susanne Biundo and Bernd Schattenberg, ‘From abstract crisis to concrete relief (a preliminary report on combining state abstraction and HTN planning)’, in Proc. of ECP 2001, pp. 157–168, (2001).
[25]Thomas Geier and Pascal Bercher, ‘On the decidability of HTN planning with task insertion’, in Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), pp. 1955–1961, (2011).
[26]Scott Penberthy and Daniel Weld, ‘Ucpop: A sound, complete, partial order planner for adl’, in Proceedings of the Third International Conference on the principles of knowledge representation, pp. 103–114, (1992).
[27]Edwin P.D. Pednault, ‘ADL: Exploring the middle ground between STRIPS and the situation calculus’, in Proc. of KR-89, pp. 324–332, (1989).
[28]Bernd Schattenberg, Julien Bidot, and Susanne Biundo, ‘On the construction and evaluation of flexible plan-refinement strategies’, in Proc. of KI 2007, pp. 367–381, (2007).
[29]Dana S. Nau, Yue Cao, Ammon Lotem, and Hctor Muoz-Avila, ‘SHOP: Simple hierarchical ordered planner’, in Proc. of IJCAI 1999, pp. 968–975, (1999).