A practical approach to error recovery for multiagent planning systems

ABSTRACT

A practical approach to error recovery strategy for real-time multiagent environments is presented. In a dynamic domain, when things do not happen as a pre-generated plan has expected, parts of the plan should be recovered to cope with any unexpected situations rather than abandoning the original plan and replanning from scratch. In order to deal with such situations, domain heuristics are used to order and classify conditions, and a resource management scheme is developed. Two tables, Wedge Table and Action Table, are introduced for prompt location of the contaminated plan parts. Plan rationale and wedge structure of a plan tree are recorded in these two tables. In order to solve the truth maintenance problem, action dependency calculation is established. This error recovery approach for multiagent planning environments not only promises successful achievement of a goal but also secures the safety of facilities in a domain. It enhances system performance and flexibility due to the versatility in real-time plan execution.

REFERENCES

• 1: Chang, K. H. and Edhala, M., "Execution Error ecovery for Planning Systems", IEEE Trans. on Systems, Men, and Cybernetics, Vol. 19, No. 1, 1989 pp. 130-134
• 2: Cheeseman, P,., 'A Reoresent, ation of Time for Automatic Planning , Proe. IEEE, Intl Conf. on Robotics, Atlanta, GA, Mar., 1984
• 3: Fikes, R. E. and Nilsson, hi. J., "STRIPS: A New pproach to the ApNication of Theorem Proving to Problem Sorving", Artificiar'intelligence, Vol. 2, 1971, pp. 189-208
• 4: Fikes, R. E., Hart, P. E., and Nilsson, N.J., "Learning and Executing Generalized Robot Plans, Artificial Intelligence, Vol. 3, 1972, pp 251-288
• 5: Les Gasser, The 1985 Workshop on Distributed Artificial Intelligence, AI Magazine, v.8 n.2, p.91-97, Summer 1987
• 6: M. P. Georgeff, Communication and interaction in multi-agent planning, Distributed Artificial Intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 7: Hyungoo Han, Error recovery for multiagent planning systems, Auburn University, Auburn, AL, 1992
• 8: Lansk~,, A. L., "A Representation of Parallel A/~tivity based on Events, Structure, and Causali~, Reasoning about Actions & Plans: Proc of 1986 Workshop Timberline, OR, June, 1986,pp. 123-159 , Editted by (;eorgeff, M. and Lansky, A., Mdrgan Kaufm,,~ Pub. Inc., Los Altos, CA
• 9: Jeffrey S. Rosenschein, Synchronization of multi-agent plans, Distributed Artificial Intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 10: Sacerdoti, E. D., 'A Structure for Plans and Behavior, Elsevier, North-HoUand New York, NY 1977
• 11: C. Stuart, An implementation of a multi-agent plan synchronizer, Distributed Artificial Intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 12: Tate, A., "Generating t'rolect Networks, IICAI-77, Cambridge, MA, Aug.,197"F, pp. 888-893
• 13: Wi}kins, D. E., "Recovering from Execution Errors in SIPE, Computational Intelligence, Vol. 1, 1985, pp. 33-45

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies; Plan execution, formation, and generation

General Terms:
Reliability, Theory