Abstract
Fast plan adaptation is important in many AI applications requiring a plan management module. From a theoretical point of view, in the worst case plan adaptation is no more efficient than a complete regeneration of the plan. However, in practice adapting an existing plan can be much more efficient than generating a new one from scratch, especially when the changes to the plan that are required concern only some circumscribed parts of the plan. In this paper we discuss a simple plan-adaptation method based on Blum and Furst’s Planning Graphs approach. The method is domain-independent and exploits the planning graph structure for a fast identification of the flaws that are present in the plan, and for fixing them by replanning limited portions of the plan. We present results from some experiments aimed at testing our method with several modifications of planning problems that are hard to solve for current planners based on planning graphs, such as IPP, Graphplan, and Blackbox. These results show that the method in practice is very efficient, especially when the plan can be adapted by changes that are localized in restricted parts of the original plan.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. Blum and M.L. Furst. Fast planning through planning graph analysis. In Proc. of IJCAI-95, pages 1636–1642. Morgan Kaufmann, 1995.
M. Fox and D. Long. The Detection and Exploitation of Symmetry in Planning Problems. In Proc. of IJCAI-99, Stockholm, 1999.
G. Ferguson and J. Allen. Arguing about Plans: Plan Representation and Reasoning for Mixed-Initiative Planning. In Proc. of AIPS-94, 1994.
G. Ferguson and J. Allen. Towards a Mixed-Initiative Planning Assistant. In Proc. of AIPS-96, AAAI press, 1996.
A. Gerevini, and I. Serina. Fast Planning through Greedy Action Graphs. In Proc. of AAAI-99, pages 503–510, AAAI/MIT Press, 1999.
A. Gerevini, and I. Serina. 1999. Fast Plan Adaptation through Planning Graphs: Local and Systematic Search Techniques. Technical Report R.T. 2000.01.20. DEA, Univ. di Brescia, Brescia, Italy.
H.A. Kautz and B. Selman. Pushing the envelope: Planning, propositional logic, and stochastic search. In Proc. of AAAI-96, AAAI Press, 1996.
H.A. Kautz and B. Selman. Unifying SAT-based and Graph-based Planning. In Proc. of IJCAI-99, Stockholm, 1999.
J. Koehler, B. Nebel, Hoffmann J., and Y. Dimopoulos. Extending planning graphs to an ADL subset. In Proc. of ECP’97, Springer Verlag, 1997.
B. Nebel and J. Koehler. Plan reuse versus plan generation: A complexity-theoretic perspective. Artificial Intelligence, 76:427–454, 1995.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gerevini, A., Serina, I. (2000). On Plan Adaptation through Planning Graph Analysis. In: Lamma, E., Mello, P. (eds) AI*IA 99: Advances in Artificial Intelligence. AI*IA 1999. Lecture Notes in Computer Science(), vol 1792. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46238-4_31
Download citation
DOI: https://doi.org/10.1007/3-540-46238-4_31
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67350-7
Online ISBN: 978-3-540-46238-5
eBook Packages: Springer Book Archive