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
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.
"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).
gzipped Postscript or
"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
Norman Carver's home page.