Norman Carver and Victor Lesser
In the functionally-accurate, cooperative (FA/C) distributed problem-solving paradigm, agents produce tentative, partial results based on local information only, and then exploit the constraints among these local results to resolve uncertainties and global inconsistencies. However, there has never been any formal analysis of the quality of the solutions that are produced by the approach or of the conditions that are necessary for the approach to be successful. This paper represents a first step in formally analyzing the quality of solutions that can be produced by FA/C systems, within the context of distributed interpretation. Two theorems that compare the quality of solutions produced by a distributed system to those produced by an equivalent centralized system are presented. The theorems relate solution quality to agent problem-solving and coordination strategies. The analysis is based on an abstract model of the DRESUN system for distributed sensor interpretation. While the paper concentrates on sensor interpretation, we expect to extend the work to apply to FA/C systems in general.