Increasing Coherence in a Distributed Problem-Solving Network

Edmund H. Durfee, Victor R. Lesser, Daniel D. Corkill

Abstract

Achieving global coherence in Distributed Problem-Solving Networks (DPSNs) remains a significant challenge, often requiring a trade-off between rigid pre-planning and excessive communication overhead. This paper introduces a framework that utilizes "abstracted blackboards" and multi-step planning to allow autonomous nodes to reason about their future actions and coordinate via high-level intentions. Experimental results in the Distributed Vehicle Monitoring Testbed (DVMT) demonstrate that these mechanisms significantly boost problem-solving speed and reduce redundant communication.

Introduction

In a DPSN, multiple semi-autonomous agents must collaborate to solve large-scale problems, such as tracking vehicles across a distributed sensor grid. The primary hurdle is ensuring global coherence—where nodes work together sensibly—without saturating the network with low-level data updates. Traditional approaches either rely on brittle, pre-defined plans or suffer from high latency and bandwidth consumption due to constant synchronization. This research seeks a middle ground: providing nodes with enough "self-awareness" and "neighbor-awareness" to coordinate through high-level summaries.

Architectural Methodology

The authors enhance the standard Hearsay-II blackboard architecture with three key components designed to improve local and global coordination:

  1. The Abstracted Blackboard: Nodes group related hypotheses into higher-level representations based on spatial and temporal proximity. This acts as a "smoothing operator," allowing nodes to focus on long-term trends rather than noisy, individual data points.
  2. Multi-step Planning: Unlike standard nodes that execute single Knowledge Source Instantiations (KSIs), "plan-based" nodes use the abstracted blackboard to formulate sequences of actions, allowing them to predict their own future behavior.
  3. Meta-level Communication (MLC): Nodes exchange these high-level plans. By understanding a neighbor's intent, a node can avoid redundant tasks and focus on complementary activities that the neighbor is not covering.
Internal node architecture featuring the Abstracted Blackboard and Planner components.

Experimental Evaluation

The proposed methods were tested using the Distributed Vehicle Monitoring Testbed (DVMT), which simulates acoustic sensor data of vehicles moving through a 2D space cluttered with noise ("ghost tracks"). The evaluation covered various configurations:

  • E1 & E2: 4-node networks with varying sensor overlaps and noise levels.
  • E3: A larger 10-node network with 18 sensed time-steps designed to test scalability.

Results and Discussion

The quantitative improvements were most pronounced in "distracted" environments where noise typically leads nodes astray. For instance, in a centralized scenario with high noise, a standard KSI-based node took 213 time units to find a solution, while a plan-based node finished in just 58 units.

Performance comparison across different environments (E1-E3) and node types.

As shown in the table above, plan-based nodes consistently outperformed standard KSI-based nodes across all environments. In E1, the plan-based approach reached a solution in 36 units compared to 49 for the standard approach. Furthermore, the addition of Meta-level Communication (MLC) further optimized performance, particularly in the complex E3 environment, where it reduced transmissions from 279 to 166 without sacrificing accuracy or speed.

Conclusion

This research demonstrates that local abstraction is the key to effective global planning. By treating intentions as primary data for coordination, DPSNs can achieve high levels of coherence with minimal communication. Future work will focus on richer plan structures and more dynamic negotiation of organizational roles in volatile environments.

Summary updated

BibTeX
@inproceedings{durfee1985increasing,
  author = {Edmund H. Durfee and Victor R. Lesser and Daniel D. Corkill},
  title = {{Increasing Coherence in a Distributed Problem-Solving Network}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1985},
}
Figure