Abstract
A planning process formulates action assignments for various agents to accomplish a goal statement. In a real situation, unexpected environmental changes (called failures) may invalidate the preformulated plan. When a failure occurs, effective and efficient handling procedures must be taken to prevent irreversible damages. A failure-handling mechanism is a key component in a fault-tolerant system, which makes autonomous operation possible. There are two basic approaches to failure handling—replanning and recovery. In the replanning approach, the currently failure-encountered state is treated as a new initial state, and a brand-new plan is derived from scratch. On the other hand, the recovery approach preserves the applicable components of the original plan and makes necessary adjustments to the preserved plan components to fit the new state. This article presents a method of achieving recovery and compares its performance with replanning. In general, the recovery approach provides a better response time, and the replanning approach sometimes provides a better plan quality.
Similar content being viewed by others
References
E. D. Sacerdoti,A Structure for Plans and Behavior Elsevier (North-Holland): New York, 1977.
M. J. Stefik, “Planning and meta-planning,”Artif. Intell. vol. 16, pp. 141–169, 1981.
A. Tate, “Generating project networks,” inProc. Int. Joint Conf. Artif. Intell.-77, 1977, pp. 888–893.
P. R. Cohen and E. A. Feigenbaum,The Handbook of Artificial Intelligence, Vol. 3, Heuritech Press: Stanford, CA, 1982.
P. Cheeseman, “A representation of time for automatic planning,” inProc. IEEE Int. Conf. Robotics, Atlanta, GA, 1984, pp. 513–518.
M. Georgeff, “Communication and interaction in multiagent planning,” inReadings in Distributed Artificial Intelligence edited by A. H. Bond and L. Gasser, Morgan Kaufmann: San Mateo, CA, pp. 216–219, 1988.
A. L. Lansky, “A representation of parallel activity based on events, structure, and causality,” inReasoning about Actions & Plans edited by M. Georgeff and A. Lansky, Morgan Kaufmann: Los Altos, CA, pp. 123–159, 1986.
K. H. Chang and W. G. Wee, “A planning model with problem analysis and operator hierarchy,”IEEE Trans. Pattern Anal. Machine Intell. vol. 10, no. 5, pp. 672–675, September 1988.
J. H. Muson, “Robot planning, execution, and monitoring in an uncertain environment,” inProc. Int. Joint Conf. Artif. Intell.-71, London, England, 1971, pp. 338–349.
R. E. Fikes and N. J. Nilsson, “STRIPS: A new approach to the application of theorem proving to problem solving,”Artif. Intell. vol. 2, pp. 189–208, 1971.
P. J. Hayes, “A representation for robot plan,” inProc. Int. Joint Conf. Artif. Intell.-75, Tbilisi, USSR, 1975, pp. 181–188.
B. R. Fox and K. G. Kempf, “Opportunistic scheduling for robotics assembly,”IEEE Int. Conf. Robot. Automat., St. Louis, MO, 1985, pp. 880–889.
D. E. Wilkins, “Recovery from execution errors in SIPE,”Comput. Intell. vol. 1, pp. 33–45, 1985.
P. S. Ow, S. F. Smith, and A. Thiriez, “Reaction plan revision,” inProc. Natl. Conf. Artif. Intell., St. Paul, MN, 1988, pp. 77–82.
R. J. Firby, “An investigation into reactive planning in complex domains,” inProc. Natl. Conf. Artif. Intell., Seattle, WA, 1987, pp. 202–206.
L. P. Kaelbling, “An architecture for intelligent reactive systems,” inReasoning about Actions & Plans edited by M. Georgeff and A. Lansky, Morgan Kaufmann: Los Altos, CA, pp. 395–410, 1986.
D. Chapman, “Penguins can make cake,”AI Mag. vol. 10, no. 4, pp. 45–50, 1989.
M. J. Schoppers, “In defense of reaction plans as caches,”AI Mag. vol. 10, no. 4, pp. 51–60, 1989.
M. L. Ginsberg, “Universal planning: An (almost) universally bad idea,”AI Mag. vol. 10, no. 4, pp. 40–44, 1989.
M. L. Ginsberg, “Ginsberg replies to Chapman and Schoppers—Universal planning research: A good or bad idea?,”AI Mag. vol. 10, no. 4, pp. 61–62, 1989.
J. Hendler, A. Tate, and M. Drummond, “AI planning systems and techniques,”AI Mag. vol. 11, no. 2, pp. 61–77, 1990.
R. Alterman, “An adaptive planner,” inProc. Natl. Conf. Artif. Intell., Philadelphia, PA, 1986, pp. 65–69.
C. A. Broverman and W. B. Croft, “Reasoning about exceptions during plan execution monitoring,” inProc. Natl. Conf. Artif. Intell., Seattle, WA, 1987, pp. 190–195.
M. Drummond and J. Bresina, “Anytime synthetic projection: Maximizing the probability of goal satisfaction,” inProc. Natl. Conf. Artif. Intell., Boston, MA, 1990, pp. 138–144.
T. Dean and M. Boddy, “An analysis of time-dependent planning,” inProc. Natl. Conf. Artif. Intell., St. Paul, MN, 1988, pp. 49–54.
H. Han,Error Recovery for Multiagent Planning Systems Ph.D. dissertation, Computer Science and Engineering, Auburn University, Auburn, AL, December 1990.
M. Georgeff, “Reactive reasoning and planning,” inProc. Natl. Conf. Artif. Intell., Seattle, WA, 1987, pp. 677–682.
B. Hayes-Roth and M. Hewett, “BB1: An implementation of the Blackboard control architecture,” inBlackboard Systems edited by R. Engelmore and T. Morgan, Addison-Wesley: Reading, MA, pp. 297–313, 1988.
D. E. Wilkins, “Can AI planners solve practical problems?” Stanford Res. Inst., Stanford, CA, SRI Int. Tech. Report No. 468R, 1989.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Chang, KH., Han, H. & Day, W.B. A comparison of failure-handling approaches for planning systems—Replanning vs. recovery. Appl Intell 3, 275–300 (1993). https://doi.org/10.1007/BF00872133
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00872133