Formal Analysis of the FA/C Distributed Problem-Solving Paradigm


Summary

The functionally-accurate, cooperative (FA/C) distributed problem-solving paradigm is one approach for organizing distributed problem solving among homogeneous, cooperating agents. The idea behind the FA/C model is that agents should produce tentative, partial results based on only local information and then exchange these results, exploiting the constraints that exist among their local subproblems to resolve the uncertainties and global inconsistencies that result from the use of incomplete information.

While several FA/C systems have been implemented, there has been little formal analysis of the quality of the solutions that can be produced using the approach or of the conditions that are necessary for the approach to be effective. In this line of research we have been working to formally analyze the FA/C model in the context of distributed sensor interpretation (SI). There are two basic directions in which we are proceeding: 1.) characterizing the quality of solutions that can be produced by FA/C systems and 2.) understanding the domain characteristics necessary for the FA/C approach to be effective.

Relevant publications

"A Formal Analysis of Solution Quality in FA/C Distributed Sensor Interpretation Systems," N. Carver and V. Lesser, Proceedings of the International Conference on Multiagent Systems (ICMAS96), December 1996.

"Nearly Monotonic Problems: A Key to Effective FA/C Distributed Sensor Interpretation?" N. Carver, V. Lesser, and R. Whitehair, Proceedings of AAAI-96, August 1996 (Copyright AAAI).

"Evidence Reliability in Nonmonotonic Domains and Nearly Monotonic Problems," N. Carver, Proceedings of the Midwest Artificial Intelligence and Cognitive Science Society Conference, April 1996.

"A Formal Analysis of Solution Quality in FA/C Distributed Sensor Interpretation Systems," N. Carver and V. Lesser, Technical Report 95-05, Computer Science Department, Southern Illinois University, July 1995.

"Examining Some Assumptions of the FA/C Distributed Problem-Solving Paradigm," N. Carver, Proceedings of the Midwest Artificial Intelligence and Cognitive Science Society Conference, April, 1995.

"A First Step Toward the Formal Analysis of Solution Quality in Distributed Interpretation Systems," N. Carver and V. Lesser, Proceedings of the 13th International Workshop on Distributed Artificial Intelligence, July, 1994 (also available as Technical Report 94-37, Department of Computer Science, University of Massachusetts).


Norman Carver's home page.