Abstract
We consider a model-based diagnosis approach to the diagnosis of plans. Here, a plan performed by some agent(s) is considered as a system to be diagnosed. We introduce a simple formal model of plans and plan execution where it is assumed that the execution of a plan can be monitored by making partial observations of plan states. These observed states are used to compare them with states predicted based on (normal) plan execution. Deviations between observed and predicted states can be explained by qualifying some plan steps in the plan as behaving abnormally. A diagnosis is a subset of plan steps qualified as abnormal that can be used to restore the compatibility between the predicted and the observed partial state. Besides minimum and subset minimal diagnoses, we argue that in plan-based diagnosis maximum informative diagnoses should be considered as preferred diagnoses, too. The latter ones are diagnoses that make the strongest predictions with respect to partial states to be observed in the future. We show that in contrast to minimum diagnoses, finding a (subset minimal) maximum informative diagnosis can be achieved in polynomial time. Finally, we show how these diagnoses can be found efficiently if the plan is distributed over a number of agents.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bertoli, P., Cimatti, A., Pistore, M., & Traverso, P. (2002). Plan validation for extended goals under partial observability (preliminary report). In Proceedings of the AIPS 2002 Workshop on Planning via Model Checking, pp. 14–22, Toulouse, France.
Birnbaum, L., Collins, G., Freed, M., & Krulwich, B. (1990). Model-based diagnosis of planning failures. In AAAI 90, pp. 318–323.
Carver N., Lesser V.R. (2003). Domain monotonicity and the performance of local solutions strategies for cdps-based distributed sensor interpretation and distributed diagnosis. Autonomous Agents and Multi-Agent Systems 6(1):35–76
Console L., Torasso P. (1990). Hypothetical reasoning in causal models. International Journal of Intelligence Systems 5:83–124
Console L., Torasso P. (1991). A spectrum of logical definitions of model-based diagnosis. Computational Intelligence 7:133–141
Cox, J. S., Durfee, E. H., & Bartold, Th. (2005). A distributed framework for solving the multiagent plan coordination problem. In AAMAS ’05: Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, pp. 821–827, New York, NY, USA, 2005. ACM Press.
Debouk R., Lafortune S., Teneketzis D. (2000). Coordinated decentralized protocols for failure diagnosis of discrete-event systems. Journal of Discrete Event Dynamical Systems: Theory and Application 10:33–86
Eiter, T., Erdem, E., & Faber, W. (2004). Diagnosing plan execution discrepancies in a logic-based action framework. Technical report INFSYS RR-1843-04-03, TU-Wien.
Fikes R.E., Nilsson N. (1971). Strips: A new approach to the application of theorem proving to problem solving. Artificial Intelligence 5:189–208
Gierz, G., Hofmann, K. H., Keimel, K., Lawson, J. D., Mislove, M., & Scott, D. S. (2003). Continuous Lattices and Domains. In Encyclopedia of Mathematics and its Applications, Vol. 93, Cambridge University Press.
Horling, B., Benyo, B., & Lesser, V. (2001). Using self-diagnosis to adapt organizational structures. In Proceedings of the 5th International Conference on Autonomous Agents, pp. 529–536. ACM Press.
Jensen R.M., Veloso M.M. (1999). OBDD-based universal planning: Specifying and solving planning problems for synchronized agents in non-deterministic domains. Lecture Notes in Computer Science 1600:213–228
de Jonge, F., & Roos, N. (2004). Plan-execution health repair in a multi-agent system. In Proceedings of the 23rd Workshop of the UK Planning and Scheduling Special Interest Group (PLANSIG 2004), pp. 33–44, Cork, Ireland.
Kalech, M., & Kaminka, G. A. (2003). On the design of social diagnosis algorithms for multi-agent teams. In IJCAI-03, pp. 370–375.
Kalech, M., & Kaminka, G. A. (2005). Diagnosing a team of agents: Scaling-up. In Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-05), pp. 249–255, ACM Press.
Pencolé, Y., Cordier, M., & Rozé, L. (2001). Incremental decentralized diagnosis approach for the supervision of a telecommunication network. In Twelfth International Workshop on Principles of Diagnosis Đ DXÕ01. San Sicario, Italy, pp. 151–158.
Reiter R. (1987). A theory of diagnosis from first principles. Artificial Intelligence 32:57–95
Witteveen, C., Roos, N., van der Krogt, R. P. J., & de Weerdt, M. M. (2005). Diagnosis of single and multi-agent plans. In Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-05), pp. 805–812, ACM Press.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License ( https://creativecommons.org/licenses/by-nc/2.0 ), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Roos, N., Witteveen, C. Models and methods for plan diagnosis. Auton Agent Multi-Agent Syst 19, 30–52 (2009). https://doi.org/10.1007/s10458-007-9017-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10458-007-9017-6