A Simulation-Based Framework for Studying CDPS-Based Distributed Sensor Interpretation and Distributed Diagnosis

This project is now part of the NSF-funded project: Formalizing Distributed Search in Cooperative Distributed Problem-Solving Systems

Summary

The growth in computer networks has created the potential to harness a great deal of computing power, but new models of distributed computing are often required. Cooperative distributed problem solving (CDPS) is the subfield of multi-agent systems (MAS) that is concerned with how large-scale problems can be solved using a network of intelligent agents working together. Currently, it is difficult to build CDPS systems for real-world applications because the relationship between the characteristics of a domain, the strategies used by agents, and the performance of the distributed system is not well understood.

We have developed a simulation-based anaylsis system to help improve our understanding of these issues. Initially, research with this system is focusing on CDPS-based distributed sensor interpretation (DSI) and distributed diagnosis (DD). To demonstrate the kind of results that can be obtained, we have investigated the effect that the monotonicity of a domain has on the performance of a potentially very efficient strategy for CDPS-based DSI/DD. This strategy, which we have dubbed the consistent local solutions strategy, can limit communications among the agents because it focuses on the use of local agent solutions in arriving at global solutions. We had previously conjectured that the reason this type of strategy has performed well in previous systems was that many DSI/DD domains are what we termed nearly monotonic. Our initial work with the framework provides quantitative results that relate domain monotonicity to the performance of "local solutions strategies." A key finding is that the performance of these strategies is strongly dependent on the fraction of the data (relevant to its interpretation subproblem) that each agent receives---unless the domain is highly monotonic. This has important implications for the design of DSI/DD systems using local solutions strategies. While the work confirms that many DSI/DD domains are ``nearly monotonic'' according to our earlier definitions, it also shows other measures of domain monotonicity that correlate much better with system performance.

Relevant publications

"Domain Monotonicity and the Performance of Local Solutions Strategies for CDPS-based Distributed Sensor Interpretation and Distributed Diagnosis," N. Carver and V. Lesser, Technical Report 2000-01, Computer Science Dept., Southern Illinois University, April 2000 (also currently under review).
Available as: gzipped Postscript or PDF.

"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).

Norman Carver's home page.