Norman Carver

JAAMAS Journal 2026 Journal Article

Domain Monotonicity and the Performance of Local Solutions Strategies for CDPS-based Distributed Sensor Interpretation and Distributed Diagnosis

• Norman Carver
• Victor Lesser

Abstract 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. Building CDPS systems for real-world applications is still very difficult, however, in large part because the effects that domain and strategy characteristics have on the performance of CDPS systems are not well understood. This paper reports on the first results from a new simulation-based analysis system that has been created to study the performance of CDPS-based distributed sensor interpretation (DSI) and distributed diagnosis (DD). To demonstrate the kind of results that can be obtained, we have investigated how the monotonicity of a domain affects the performance of a potentially very efficient class of strategies for CDPS-based DSI/DD. Local solutions strategies attempt to limit communications among the agents by focusing on using the agents' local solutions to produce global solutions. While these strategies have been described as being important for effective CDPS-based DSI/DD, they need not perform well if a domain is nonmonotonic. We had previously suggested that the reason they have performed well in several research systems was that many DSI/DD domains are what we termed nearly monotonic. In this paper, we will provide quantitative results that relate the performance of local solutions strategies to the monotonicity of a domain. The experiments confirm that domain monotonicity can be important to consider, but they also show that it is possible for these strategies to be effective even when domains are relatively nonmonotonic. What is required is that the agents receive a significant fraction of the data that is relevant to their subproblems. This has important implications for the design of DSI/DD systems using local solutions strategies. In addition, while the work indicates that many DSI/DD domains are likely to be “nearly monotonic” according to our original definitions, it also shows that these measures are not as predictive of performance as other measures we define. This means that near monotonicity alone does not explain why local solutions strategies have performed well in previous systems. Instead, a likely explanation is that these systems typically involved only a small number of agents.

AAMAS Conference 2008 Conference Paper

Efficient Approximate Inference in Distributed Bayesian Networks for MAS-based Sensor Interpretation

• Norman Carver

The multiply sectioned Bayesian network (MSBN) framework is the most studied approach for distributed Bayesian Network inference in an MAS setting. This paper describes a new framework that supports efficient approximate MASbased sensor interpretation, more autonomy and asynchrony among the agents, and more focused, situation-specific communication patterns. Its use can lead to significant improvements in agent utilization and time-to-solution.

AAMAS Conference 2003 Conference Paper

Analyzing the Efficiency of Strategies for MAS-based Sensor Interpretation and Diagnosis

• Norman Carver
• Ruj Akavipat

AAMAS Conference 2003 Conference Paper

Minimizing Communication Cost in a Distributed Bayesian Network Using a Decentralized MDP

• Jiaying Shen
• Victor Lesser
• Norman Carver

AAAI Conference 1996 Conference Paper

Nearly Monotonic Problems: A Key to Effective FA/C Distributed Sensor Interpretation?

• Norman Carver

The fesractioncslly-Qcczdrrcate, cooperative (FA/C) distributed problem-solving paradigm is one approach for organizing distributed problem solving among homogeneous, cooperating agents. A key assumption of the FA/C model has been that the agents’ local solutions can substitute for the raw data in determining the global solutions. This is not the case in general, however. Does this mean that researchers’ intuitions have been wrong and/or that FA/C problem solving is not likely to be effective? We suggest that some domains have a characteristic that can account for the success of exchanging mainly local solutions. We call such problems nearly monotonic. This concept is discussed in the context of FA/C-based distributed sensor interpretation.

AAAI Conference 1991 Conference Paper

A New Framework for Sensor Interpretation: Planning to Resolve Sources of Uncertainty

• Norman Carver

Sensor interpretation involves the determination of high-level explanations of sensor data. Blackboardbased interpretation systems have usually been limited to incre, mental hypothesize and test strategies for resolving uncertainty. We have developed a new interpretation framework that supports the use of more sophisticated strategies like differential diagnosis. The RESUN framework has two key components: an evidential representation that includes explicit, symbolic encodings of the sources of uncertainty (SOUs) in the evidence for hypotheses and a script-based, incremental control planner. Interpretation is viewed as an incremental process of gathering evidence to resolve particular sources of uncertainty. Control plans invoke actions that examine the symbolic SOUs associated with hypotheses and use the resulting information to post goals to resolve uncertainty. These goals direct the system to expand methods appropriate for resolving the current sources of uncertainty in the hypotheses. The planner’ s refocusing mechanism makes it possible to postpone focusing decisions when there is insufficient information to make decisions and provides opportunistic control capabilities, The RESUN framework has been implemented and experimentally verified using a simulated aircraft monitoring application.

AAAI Conference 1991 Conference Paper

Sophisticated Cooperation in FA/C Distributed Problem Solving Systems

• Norman Carver

In the functionally accurate, cooperative (FA/C) distributed problem solving paradigm, agents exchange tentative and partial results in order to converge on correct solutions. The key questions for FA/C problem solving are: how should cooperation among agents be structured and what capabilities are required in the agents to support the desired cooperation. To date, the FA/C paradigm has been explored with agents that did not have sophisticated evidential reasoning capabilities. We have implemented a new framework in which agents maintain explicit representations of the reasons why their hypotheses are uncertain and explicit representations of the state of the actions being taken to meet their goals. In this paper, we will show that agents with more sophisticated models of their evidence and their problem solving states can support the complex, dynamic interactions between agents that are necessary to fully implement the FA/C paradigm. Our framework makes it possible for agents to have directed dialogues among agents for distributed differential diagnosis, make use of a variety of problem solving methods in response to changing situations, transmit information at different levels of detail, and drive local and global problem solving using the notion of the global consistency of local solutions. These capabilities have not been part of previous implementations of the FA/C paradigm.