Efficient Plan Adaptation through Replanning Windows and Heuristic Goals

• Autorzy: Gerevini A.E. , Serina I.
• Języki publikacji: EN

Abstrakty

EN

Fast plan adaptation is important in many AI applications. From a theoretical point of view, in the worst case adapting an existing plan to solve a new problem is no more efficient than a complete regeneration of the plan. However, in practice plan adaptation can be much more efficient than plan generation, especially when the adapted plan can be obtained by performing a limited amount of changes to the original plan. In this paper, we investigate a domain-independent method for plan adaptation that modifies the original plan by replanning within limited temporal windows containing portions of the plan that need to be revised. Each window is associated with a particular replanning subproblem that contains some "heuristic goals" facilitating the plan adaptation, and that can be solved using different planning methods. An experimental analysis shows that, in practice, adapting a given plan for solving a new problem using our techniques can be much more efficient than replanning from scratch.

Słowa kluczowe

EN

plan adaptation and reuse; graphplan-based algorithms; plan efficiency; mixedinitiative planning

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 102, nr 3/4
• Strony: 287--323
• Opis fizyczny: Bibliogr. 34 poz., wykr.

Twórcy

autor

Gerevini A.E.

autor

Serina I.

• Dipartimento di Ingegneria dell'Informazione, Universita degli Studi di Brescia, via Branze 38, 25123 Brescia, Italy,

Bibliografia

• [1] Blum, A., Furst, M.: Fast planning through planning graph analysis, Artificial Intelligence, 90, 1997, 281-300.
• [2] Bonet, B., Geffner, H.: Planning as heuristic search, Artificial Intelligence, 129(1-2), 2001, 5-33.
• [3] Cushing, W., Kambhampati, S.: Replanning: a new perspective, Proc. of ICAPS, 2005.
• [4] Drabble, B.: Excalibur - A program for planning and reasoning with processes, Artificial Intelligence, 62(1), 1993, 1-40.
• [5] Ferguson, G., Allen, J.: Towards a Mixed-Initiative Planning Assistant., In Proceedings of the 3rd InternationalConference on Artificial Intelligence Planning Systems (AIPS-96), 1996.
• [6] Fox, M., Gerevini, A., Long, D., Serina, I.: Plan Stability: Replanning versus Plan Repair, Proceedings of International Conference on AI Planning and Scheduling (ICAPS), AAAI Press, 2006.
• [7] Fox, M., Long, D.: The Detection and Exploitation of Symmetry in Planning Problems, Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI-99), 1999, 956-961.
• [8] Gerevini, A., Saetti, A., Serina, I.: Planning through Stochastic Local Search and Temporal Action Graphs, Journal of Artificial Intelligence Research (JAIR), 20, 2003, pp. 239-290.
• [9] Gerevini, A., Schubert, L.: Inferring State Constraints in DISCOPLAN: Some New Results, Proceedings of the 17th National Conference of the American Association for Artificial Intelligence (AAAI-00), AAAI press/The MIT Press, 2000, 761-767.
• [10] Gerevini, A., Serina, I.: Fast Planning through Greedy Action Graphs, Proceedings of the 16th National Conference of the American Association for Artificial Intelligence (AAAI-99), AAAI Press/MIT Press, July 1999, 503-510.
• [11] Gerevini, A., Serina, I.: Fast Plan Adaptation through Planning Graphs: Local and Systematic Search Techniques, Proceedings of the 5th International Conference on Artificial Intelligence Planning and Scheduling (AIPS-00), AAAI Press/MIT Press, 2000, 112-121.
• [12] Gerevini, A. E., Long, D., Haslum, P., Saetti, A., Dimopoulos, Y.: Deterministic Planning in the Fifth International Planning Competition: PDDL3 and Experimental Evaluation of the Planners, Artificial Intelligence., 173(5-6), 2009, 619-668.
• [13] Hanks, S., Weld, D.: A domain-independent algorithm for plan adaptation., Journal of Artificial Intelligence Research (JAIR), 2, 1995, 319-360.
• [14] Helmert, M.: The Fast Downward Planning System, Journal of Artificial Intelligence Research, 26, 2006, 191-246.
• [15] Hoffmann, J.: FF: The Fast-Forward Planning System, AI Magazine, 22(3), 2001, 57-62.
• [16] Hoffmann, J., Nebel, B.: The FF Planning System: Fast Plan Generation Through Heuristic Search, Journal of Artificial Intelligence Research (JAIR), 14, 2001, 253-302.
• [17] Hsu, C. W., Wah, B. W., Huang, R., Chen, Y. X.: New Features in SGPlan for Handling Soft Constraints and Goal Preferences in PDDL3.0, Proc. Fifth International Planning Competition, International Conf. On Automated Planning and Scheduling, AAAI Press/MIT Press, 2006.
• [18] Kambhampati, S.: Refinement Planning as a Unifying Framework for Plan Synthesis, AI Magazine, 18(2), 1997, 67-97.
• [19] Kambhampati, S., Hendler, J. A.: A validation-structure-based theory of plan modification and reuse, Artificial Intelligence, 55, 1992, 193-258.
• [20] Kautz, H., Selman, B.: Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search, Proceedings of the Thirteenth National Conference of the American Association for Artificial Intelligence (AAAI-96) (H. Shrobe, T. Senator, Eds.), AAAI Press, 1996, 1194-1201.
• [21] Koehler, J., Nebel, B., Hoffmann, J., Dimopoulos, Y.: Extending Planning Graphs to an ADL Subset, Fourth European Conference on Planning (ECP'97), Springer Verlag, 1997, 273-285.
• [22] van der Krogt, R., de Weerdt, M.: Plan Repair as an Extension of Planning, ICAPS (S. Biundo, K. L. Myers, K. Rajan, Eds.), AAAI, 2005, ISBN 1-57735-220-3, 161-170.
• [23] Long, D., Fox, M.: The 3rd International Planning Competition: Results and Analysis, Journal of Artificial Intelligence Research (JAIR), 2003.
• [24] McAllester, D., Rosenblitt, D.: Systematic nonlinear planning, Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI-91), July 1991, 634-639.
• [25] McDermott, D.: An Heuristic Estimator for Means-Ends Analysis in Planning, Proceedings of the Third International Conference on Artificial Intelligence Planning Systems, AAAI Press, Menlo PArk, CA., USA, May 1996, 142-149.
• [26] Mcdermott, D.: The 1998 AI planning systems competition, AI Magazine, 21, 2000, 35-55.
• [27] Nebel, B., Koehler, J.: Plan reuse versus plan generation: A complexity-theoretic perspective, Artificial Intelligence- Special Issue on Planning and Scheduling, 76, 1995, 427-454.
• [28] Penberthy, J., Weld, D.: UCPOP: A sound, complete, partial order planner for ADL, Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning (KR'92), Morgan Kaufmann, Boston, MA, 1992, 103-114.
• [29] Thangarajah, J., Harland, J., Morley, D., Yorke-Smith, N.: Suspending and resuming tasks in BDI agents, AAMAS '08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2008, ISBN 978-0-9817381-0-9, 405-412.
• [30] Tonidandel, F., Rillo, M.: The FAR-OFF System: A Heuristic Search Case-Based Planning, AIPS (M. Ghallab, J. Hertzberg, P. Traverso, Eds.), AAAI, 2002, ISBN 1-57735-142-8, 302-311.
• [31] Traum, D. R., Allen, J. F., Ferguson, G., Heeman, P. A., Hwang, C.-H., Kato, T., Martin, N., Poesio, M., Schubert, L. K.: Integrating Natural Language Understanding and Plan Reasoning in the TRAINS-93 Conversation System, Working Notes of the AAAI Spring Symposium on Active NLP, Stanford, CA, 21-23 March 1994, 63-67.
• [32] Veloso, M.: Planning and learning by analogical reasoning, vol. 886 of Lecture Notes in Artificial Intelligence and Lecture Notes in Computer Science, Springer-Verlag Inc., New York, NY, USA, 1994, ISBN 3-540-58811-6 (Berlin), 0-387-58811-6 (New York).
• [33] Younes, H. L. S., Simmons, R. G.: VHPOP: Versatile Heuristic Partial Order Planner, J. Artif. Intell. Res. (JAIR), 20, 2003, 405-430.
• [34] Zhang, J. F., Nguyen, X. T., Kowalczyk, R.: Graph-based multiagent replanning algorithm, AAMAS '07: Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, ACM, New York, NY, USA, 2007, ISBN 978-81-904262-7-5, 1-8.