A resource based framework for planning and replanning

ABSTRACT

The aim of this paper is to combine standard planning and replanning methods into a rigorous unifying framework, extending an existing logic-based approach to resource-based planning. In this Action Resource Framework (ARF), actions and resources are the primitive concepts. Actions consume and produce resources. Plans are structured objects composed of actions and resource schemes and an explicit dependency function specifying their interrelationships.Previous plans can be used both for creating new plans and for modifying plans. Since we are often interested in reusing only a part of these previous plans, we extend the Action Resource Formalism with incomplete plans. To efficiently represent such incomplete plans we use the notion of a gap. We maintain a library of incomplete plans (with gaps), and we present operators to insert plan parts from this plan library into the current plan. We prove this set of plan operators to be complete.Generalizing the refinement planning approach, we present a template algorithm for both planning and replanning using the ARF and its plan library and plan operators. Finally, we show that existing (re)planning methods and heuristics nicely fit into this framework.

REFERENCES

• 1: Peter van Beek , Xinguang Chen, CPlan: a constraint programming approach to planning, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.585-590, July 18-22, 1999, Orlando, Florida, United States
• 2: Avrim L. Blum , Merrick L. Furst, Fast planning through planning graph analysis, Artificial Intelligence, v.90 n.1-2, p.281-300, Feb. 1997 [doi>10.1016/S0004-3702(96)00047-1]
• 3: {3} B. Bonet and H. Geffner, Planning as heuristic search, Artificial Intelligence. Special issue on Heuristic Search, 2000.
• 4: {4} B. Bonet and H. Geffner, Heuristic search planner 2.0, AI Magazine22(3) (2001), 77-80.
• 5: {5} M.M. de Weerdt, A. Bos, J. Tonino and C. Witteveen, A resource logic for multi-agent plan merging. Annals of Mathematics and Artificial Intelligence, special issue on Computational Logic on Multi-Agent Systems37(1-2) (2003), 93-130.
• 6: {6} K.S. Decker and V.R. Lesser, Generalizing the partial global planning algorithm. International Journal of Intelligent and Cooperative Information Systems1(2) (1992), 319-346.
• 7: {7} M.E. DesJardins, E.H. Durfee, C.L. Ortiz and M.J. Wolverton, A survey of research in distributed, continual planning. AI Magazine4 (2000), 13-22.
• 8: {8} B. Drabble, J. Dalton and A. Tate, Repairing plans on the fly, in: Proc. of the NASA Workshop on Planning and Scheduling for Space, Oxnard, CA, 1997.
• 9: Edmund H. Durfee , Victor R. Lesser, Planning Coordinated Actions in Dynamic Domains, University of Massachusetts, Amherst, MA, 1987
• 10: {10} E.H. Durfee and V.R. Lesser, Planning coordinated actions in dynamic domains, in: Proceedings of the DARPA Knowledge-Based Planning Workshop, 1987, pp. 18.1-18.10.
• 11: Gabriel John Ferrer , Worthy N. Martin, Anytime replanning using local subplan replacement, 2002
• 12: {12} R.E. Fikes and N. Nilsson, STRIPS: A new approach to the application of theorem proving to problem solving, Artificial Intelligence5(2) (1991), 189-208.
• 13: {13} S. Fox and D. Leake, Modeling case-based planning for repairing reasoning failures, in: Proceedings of the 1995 AAAI Spring Symposium on Representing Mental States and Mechanisms , 1995, pp. 31-38, AAAI Press, Menlo Park, CA.
• 14: {14} A. Gerevini and I. Serina, Fast plan adaptation through planning graphs: Local and systematic search techniques, in: Proceedings of the Fifth International Conference on Artificial Intelligence Planning Systems (AIPS-00), 2000, pp. 112-121, AAAI Press, Menlo Park, CA.
• 15: {15} J. Gratch, Reasoning about multiple plans in dynamic multi-agent environments, in: AAAI Fall Symposium on Distributed Continual Planning, 1998.
• 16: {16} K.J. Hammond, Case-based planning: A framework for planning from experience, Cognitive Science14(3) (1990), 385-443.
• 17: {17} S. Hanks and D. Weld, A domain-independent algorithm for plan adaptation, Journal of AI Research2 (1995), 319-360.
• 18: {18} J. Hoffmann and B. Nebel, The FF planning system: Fast plan generation through heuristic search, Journal of AI Research14 (2001), 253-302.
• 19: Subbarao Kambhampati, A comparative analysis of partial order planning and task reduction planning, ACM SIGART Bulletin, v.6 n.1, p.16-25, Jan. 1995 [doi>10.1145/202187.202192]
• 20: {20} S. Kambhampati, Refinement planning as a unifying framework for plan synthesis, AI Magazine18(2) (1997), 67-97.
• 21: {21} J. Koehler, An application of terminological logics to case based reasoning, in: KR'94: Principles of Knowledge Representation and Reasoning, J. Doyle, E. Sandewall and P. Torasso, eds, 1994, pp. 351-362, Morgan Kaufmann Publishers, San Mateo, CA.
• 22: {22} D. McDermott, PDDL - the planning domain definition language , Technical Report TR-98-003, Yale Center for Computational Vision and Control, 1998.
• 23: {23} S. Miksch and A. Seyfang, Continual planning with time-oriented, skeletal plans, in: Proceedings of the Fourteenth European Conference on Artificial Intelligence (ECAI-00), 2000, pp. 511-515.
• 24: {24} J. Tonino, A. Bos, M.M. de Weerdt and C. Witteveen, Plan coordination by revision in collective agent-based systems, Artificial Intelligence142(2) (2002), 121-145.
• 25: {25} R.P. van der Krogt, M.M. de Weerdt, L.R. Planken and A. Biesheuvel, Cabs planner, http://www.pds.twi.tudelft.nl/ ~mathijs/, 2003.
• 26: {26} M. Veloso, J. Carbonell, A. Pérez, D. Borrajo, E. Fink and J. Blythe, Integrating planning and learning: The PRODIGY architecture. Journal of Experimental and Theoretical Artificial Intelligence7(1) (1995), 81-120.
• 27: {27} X. Wang and S. Chien, Replanning using hierarchical task network and operator-based planning, Technical report, Jet Propulsion Laboratory Nasa, 1997.
• 28: {28} D.S. Weld, An introduction to least-commitment planning, AI Magazine15(4) (1994), 27-61.
• 29: {29} M.P. Wellman, A general-equilibrium approach to distributed transportation planning, in: Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92), 1992, pp. 282-289, AAAI Press, Menlo Park, CA.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents; Coherence and coordination

General Terms:
Algorithms, Design