Formalizing Distributed Search in Cooperative Distributed Problem-Solving Systems

This is a collaborative research project funded by the Computation and Social Systems (CSS) program of the National Science Foundation.
The PIs are: Prof. Norman Carver (NSF Grant No. IIS-0084135) and Prof. Victor Lesser (NSF Grant No. IIS-0004112).

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Project Summary

The explosive growth of computer networks and networking capabilities has created the potential to access a great deal of computing power and information, but also the need for new models of distributed computing. This has led to increasing interest in intelligent agents and multi-agent systems (MAS). Cooperative distributed problem solving (CDPS) is the subfield of MAS that is concerned with how large-scale problems can be solved using systems of agents, distributed among a set of networked computers, working cooperatively. There are a wide variety of potential applications for CDPS techniques, including: sensor interpretation in distributed sensor networks; vehicle traffic monitoring and control; detection and diagnosis of faults in computer and telecommunications networks; information retrieval from distributed information sources; computer-supported cooperative work, and various kinds of situation assessment. CDPS approaches can potentially offer increased processing power, flexibility, and reliability, and reduced hardware costs.

Despite the promise of CDPS techniques, the current state of the field makes it difficult to build CDPS systems for real-world applications. There are not yet any formal modeling techniques that are fully adequate for predicting how a particular CDPS design will perform in a potential application domain. Furthermore, relatively little research has been done to develop a broad understanding of how system and domain characteristics interact to affect the performance of CDPS systems, or to identify strategies that perform well under particular conditions. As a result, there is very limited information available to guide the selection of appropriate strategies when designing a CDPS system. This is a critical issue if there is to be significant further application of this important field.

The research being proposed will address this issue by: (1) developing formalisms for modeling CDPS systems; (2) implementing software tools that can use these models to predict the performance of CDPS systems; and (3) performing a broad range of experiments in order to build up a suite of effective abstract CDPS strategies. The PIs are well prepared to accomplish these tasks. They have extensive research backgrounds in CDPS and have carried out previous research that can be built upon to meet the above goals. One of these projects involved the development of a grammar-based framework for representing and analyzing sophisticated sensor interpretation systems. The grammar representation formalism and basic tool design from that project will be the basis for a new CDPS modeling formalism and associated analysis framework for general, search-based CDPS. The other project that is particularly relevant to this research is a recently developed simulation framework for studying CDPS-based distributed sensor interpretation (DSI) and distributed diagnosis (DD). This framework uses abstract models of agents, domains, and strategies to run the large numbers of experiments that are required to develop information about the performance of CDPS strategies. This framework will be extended and used both to develop a better understanding of CDPS-base DSI/DD and to identify domain and strategy characteristics to be explored with the grammar-based framework.

The main elements of the proposed research are:

Relevant publications

"Minimizing Communication Cost in a Distributed Bayesian Network using a Decentralized MDP," J. Shen, V. Lesser, and N. Carver, Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems, 2003.
Available as: gzipped Postscript or PDF.

"Analyzing the Efficiency of Strategies for MAS-based Sensor Interpretation and Diagnosis," N. Carver and R. Akavipat, Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems (poster session), 2003.
Published (short) version available as: gzipped Postscript or PDF.

"Domain Monotonicity and the Performance of Local Solutions Strategies for CDPS-based Distributed Sensor Interpretation and Distributed Diagnosis," N. Carver and V. Lesser, International Journal of Autonomous Agents and Multi-Agent Systems, Vol. 6, 35--76, 2003.
Available as: gzipped Postscript or PDF.

"Reasoning about Remote Data in CDPS with Distributed Bayesian Network," J. Shen, V. Lesser, and N. Carver, Proceedings of Multi-Agent Systems and Applications -- ACAI, July 2001.
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).
Available as: gzipped Postscript.

Simulation System Software

An important component of the outreach aspects of this project will be making the simulation system software publicly available. A version of this software is now available. It can be used to produce the kind of information that appears in the JAAMAS paper listed above. Contact Prof. Carver ( for information about obtaining the system. Note that the software is written in Common Lisp, and has been run under Franz's Allegro Common Lisp for Linux.


Principal Investigators:
Prof. Norman Carver (Southern Illinois University, Carbondale)
Prof. Victor Lesser (University of Massachusetts, Amherst)

Research Assistants:
Ruj Akavipat (SIUC)
Muralidar Chakravarthi (SIUC)
Jonathan Koren (SIUC)
Jiaying Shen (UMass)

Norman Carver's home page.
Victor Lesser's Multi-Agent Systems Laboratory page.