More Web Proxy on the site http://driver.im/

Article

Plan stability: replanning versus plan repair

Authors:

Alfonso Gerevini,

Ivan SerinaAuthors Info & Claims

ICAPS'06: Proceedings of the Sixteenth International Conference on International Conference on Automated Planning and Scheduling

Pages 212 - 221

Published: 06 June 2006 Publication History

Abstract

The ultimate objective in planning is to construct plans for execution. However, when a plan is executed in a real environment it can encounter differences between the expected and actual context of execution. These differences can manifest as divergences between the expected and observed states of the world, or as a change in the goals to be achieved by the plan. In both cases, the old plan must be replaced with a new one. In replacing the plan an important consideration is plan stability. We compare two alternative strategies for achieving the stable repair of a plan: one is simply to replan from scratch and the other is to adapt the existing plan to the new context.

We present arguments to support the claim that plan stability is a valuable property. We then propose an implementation, based on LPG, of a plan repair strategy that adapts a plan to its new context. We demonstrate empirically that our plan repair strategy achieves more stability than replanning and can produce repaired plans more efficiently than replanning.

References

[1]

Bacchus, F., and Kabanza, F. 2000. Using temporal logic to express search control knowledge for planning. Artificial Intelligence 116(1-2):123-191.

Digital Library

[2]

Boutilier, C.; Dean, T.; and Hanks, S. 1999. Decision-theoretic planning: Structural assumptions and computational leverage. J. AI Res. 11:1-94.

Digital Library

[3]

Cushing, W., and Kambhampati, S. 2005. Replanning: a new perspective. In Proc. of ICAPS.

[4]

Drummond, M.; Bresina, J.; and Swanson, K. 1994. Just-in-case scheduling. In Proc. 12th Nat. Conf. on AI (AAAI), 1098-1004.

Digital Library

[5]

Frank, J.; Gross, M. A. K.; and Kürklü, E. 2004. SOFIA's choice: An AI approach to scheduling airborne astronomy observations. In Proc. of AAAI, 828-835.

Digital Library

[6]

Gerevini, A., and Serina, I. 2000. Fast plan adaptation through planning graphs: local and systematic search techniques. In Proc. of Int. Conf. on AI Planning and Scheduling (AIPS'00).

[7]

Gerevini, A.; Saetti, A.; and Serina, I. 2003. Planning through stochastic local search and temporal action graphs. J. AI Res. 20.

Digital Library

[8]

Hammond, K. 1990. Explaining and repairing plans that fail. Artificial Intelligence 45:173-228.

Digital Library

[9]

Hanks, S., and Weld, D. 1995. A domain-independent algorithm for plan adaptation. J. AI Res. 2:319-360.

Digital Library

[10]

Hoffmann, J. 2003. The Metric-FF planning system: Translating "ignoring delete lists" to numerical state variables. J. AI Res. 20.

Digital Library

[11]

Horty, J. F., and Pollack, M. E. 2001. Evaluating new options in the context of existing plans. Artificial Intelligence 127:199-220.

Digital Library

[12]

Kambhampati, S., and Hendler, J. 1992. A validation-structure-based theory of plan modification and reuse. Artificial Intelligence 55:193-258.

Digital Library

[13]

Kambhampati, S. 1990. Mapping and retrieval during plan reuse: a validation structure based approach. In Proc. of AAAI, 170-175.

Digital Library

[14]

Koenig, S.; Furcy, D.; and Bauer, C. 2002. Heuristic search-based replanning. In Proc. of Int. Conf. on AI Planning and Scheduling (AIPS'02), 310-317.

[15]

Kvarnström, J., and Magnusson, M. 2003. Talplanner in the 3rd international planning competition: Extensions and control rules. J. AI Research 20.

Digital Library

[16]

Nau, D.; Au, T.-C.; Ilghami, O.; Kuter, U.; Murdoch, J.; Wu, D.; and Yaman, F. 2003. An HTN planning environment. J. AI Res. 20.

[17]

Nebel, B., and Koehler, J. 1995. Plan reuse versus plan generation: A theoretical and empirical analysis. Artificial Intelligence 76(1-2):427-454.

Digital Library

[18]

Pryor, L., and Collins, G. 1996. Planning for contingencies: A decision-based approach. J. AI Res. 4:287-339.

Digital Library

[19]

Simmons, R. 1988. A theory of debugging plans and interpretations. In Proc. of AAAI, 94-99.

Digital Library

[20]

Stulp, F., and Beetz, M. 2005. Optimized execution of action chains using learned performance models of abstract actions. In Proc. of IJCAI, 1272-1278.

Digital Library

[21]

Traum, D., and Allen, J. 1994. Towards a formal theory of repair in plan execution and plan recognition. In Proc. UK PlanSIG.

[22]

van der Krogt, R., and de Weerdt, M. 2005. Plan repair as an extension of planning. In Proc. of the 15th Int. Conf. on Automated Planning and Scheduling (ICAPS-05), 161-170.

[23]

Veloso, M. 1994. Planning and learning by analogical reasoning. LNCS 886. Springer-Verlag.

Digital Library

Cited By

Krarup BKrivic SMagazzeni DLong DCashmore MSmith D(2022)Contrastive Explanations of Plans through Model RestrictionsJournal of Artificial Intelligence Research10.1613/jair.1.1281372(533-612)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1613/jair.1.12813
Maliah SKomarnitski RShani G(2022)Computing Contingent Plan Graphs using Online PlanningACM Transactions on Autonomous and Adaptive Systems10.1145/348890316:1(1-30)Online publication date: 23-Jan-2022
https://dl.acm.org/doi/10.1145/3488903
Borrajo DFernández S(2019)Efficient approaches for multi-agent planningKnowledge and Information Systems10.1007/s10115-018-1202-158:2(425-479)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s10115-018-1202-1
Show More Cited By

Recommendations

Continuing plan quality optimisation

Finding high quality plans for large planning problems is hard. Although some current anytime planners are often able to improve plans quickly, they tend to reach a limit at which the plans produced are still very far from the best possible, but these ...
HTN Plan Repair via Model Transformation
KI 2020: Advances in Artificial Intelligence
Abstract
To make planning feasible, planning models abstract from many details of the modeled system. When executing plans in the actual system, the model might be inaccurate in a critical point, and plan execution may fail. There are two options to handle ...
Plan reuse in conformant planning

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ICAPS'06: Proceedings of the Sixteenth International Conference on International Conference on Automated Planning and Scheduling

June 2006

449 pages

ISBN:9781577352709

Sponsors

NSF: National Science Foundation
Carnegie Mellon University: Carnegie Mellon University
Honeywell: Honeywell
DARPA: Defense Advanced Research Projects Agency
National ICT Australia

Publisher

AAAI Press

Publication History

Published: 06 June 2006

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Krarup BKrivic SMagazzeni DLong DCashmore MSmith D(2022)Contrastive Explanations of Plans through Model RestrictionsJournal of Artificial Intelligence Research10.1613/jair.1.1281372(533-612)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1613/jair.1.12813
Maliah SKomarnitski RShani G(2022)Computing Contingent Plan Graphs using Online PlanningACM Transactions on Autonomous and Adaptive Systems10.1145/348890316:1(1-30)Online publication date: 23-Jan-2022
https://dl.acm.org/doi/10.1145/3488903
Borrajo DFernández S(2019)Efficient approaches for multi-agent planningKnowledge and Information Systems10.1007/s10115-018-1202-158:2(425-479)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s10115-018-1202-1
Fickert MGnad DHoffmann J(2018)Unchaining the power of partial delete relaxation, part IIProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304652.3304669(4750-4756)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304652.3304669
Beal JUsbeck KLoyall JRowe MMetzler J(2018)Adaptive Opportunistic Airborne Sensor SharingACM Transactions on Autonomous and Adaptive Systems10.1145/317999413:1(1-29)Online publication date: 16-Apr-2018
https://dl.acm.org/doi/10.1145/3179994
(2017)Deliberation for autonomous robotsArtificial Intelligence10.1016/j.artint.2014.11.003247:C(10-44)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1016/j.artint.2014.11.003
Sohrabi SRiabov AUdrea OHassanzadeh O(2016)Finding diverse high-quality plans for hypothesis generationProceedings of the Twenty-second European Conference on Artificial Intelligence10.3233/978-1-61499-672-9-1581(1581-1582)Online publication date: 29-Aug-2016
https://dl.acm.org/doi/10.3233/978-1-61499-672-9-1581

View Options

View options

Media

Figures

Other

Tables

View Table of Contents