Predictability Versus Responsiveness: Coordinating Problem Solvers in Dynamic Domains

Edmund H. Durfee, Victor R. LesserAAAI 1988

In distributed artificial intelligence, a fundamental challenge is maintaining coordination among autonomous agents in a rapidly changing environment. This classic 1988 paper from the AAAI proceedings explores the inherent tension between an agent's need to be predictable to its peers and its need to be responsive to new local data.

The Coordination Trap

In a distributed problem-solving network, agents typically possess only a limited, local view of the world. Effective collaboration requires predictability: agents must commit to specific plans so that others can rely on their expected outputs. However, in dynamic domains, new information arrives continuously. If agents are too rigid in their commitments, they fail to be responsive to critical updates, potentially pursuing obsolete goals.

The authors identify a "coordination trap." If agents communicate every minor adjustment to their local plans, the network becomes paralyzed by the computational and communication overhead of constant re-coordination. Conversely, if they rarely update their shared plans, they risk working on stale information, leading to redundant efforts or missed opportunities.

Partial Global Planning (PGP)

To address this, the authors propose the Partial Global Planning (PGP) framework. PGP allows agents to coordinate by sharing summaries of their local intentions rather than exhaustive detail. Key components include:

  • Node-Plans: High-level summaries of an agent’s local goals and the estimated time required to achieve them.
  • Partial Global Plans (PGPs): These are broader coordination structures created by a "PGPlanner" that analyzes multiple node-plans to identify common goals. A PGP includes a plan-activity-map for representing concurrent activities and a solution-construction-graph to designate which agents should integrate results and when.

The Time-Cushion: Balancing Stability and Agility

The core innovation of PGP is the time-cushion. This user-defined threshold represents a "negligible" amount of time. If an agent’s local plan slips by a duration less than the time-cushion, it does not notify the rest of the network.

This mechanism acts as a low-pass filter for plan updates, preventing "chain reactions" where a minor delay in one node forces every other node in the network to re-calculate its plans. By building these cushions into the solution-construction-graph, the system creates robust plans that tolerate minor, inevitable delays without sacrificing overall coordination.

Experimental Evaluation

The framework was tested using the Distributed Vehicle Monitoring Testbed (DVMT), which simulates a network of acoustic sensors tracking vehicles in a 2D space. Two primary environments were used:

  • Environment A: Included a faulty sensor generating noise, testing the system's ability to use predictive information to filter out false signals.
  • Environment B: Featured two vehicles moving in parallel with significant data overlap between sensors, testing the system's ability to minimize redundant work.
Environment B in the DVMT, featuring two vehicles moving in parallel with overlapping sensor coverage.

Key Results and Insights

The experiments compared several configurations: no planning, local planning only, and PGP with various time-cushions (TC = 0, 1, or 2). Coordination styles included Broadcast (bc), where all agents share plans, and Centralized (cn), where plans are sent to a designated coordinator.

Experimental results comparing different coordination strategies and time-cushion (TC) values across Environments A and B.

As shown in the results table, PGP significantly reduced the simulated time (ST) required to find solutions compared to local planning alone. However, this came at the cost of increased communication (T-r).

A critical finding was the existence of a "sweet spot" for the time-cushion. In Environment B, a time-cushion of 1 was optimal. A cushion of 0 (maximum responsiveness) led to excessive re-planning overhead, while a cushion of 2 (maximum predictability) caused agents to wait too long for results or duplicate work because they were unaware of their peers' progress.

Conclusion

The PGP framework demonstrates that "optimal" coordination is often impractical due to the overhead costs. Instead, systems should aim for a balance between predictability and responsiveness. The time-cushion provides a powerful tool for damping oscillations in distributed plans, allowing agents to maintain a "public" version of their intentions that remains stable despite minor local fluctuations.

Future work suggests moving toward dynamic time-cushions that adapt to network traffic and task urgency, as well as developing meta-level reasoning to determine when the effort of coordination itself is justified.

Summary updated

BibTeX
@inproceedings{durfee1988predictability,
  author = {Edmund H. Durfee and Victor R. Lesser},
  title = {{Predictability Versus Responsiveness: Coordinating Problem Solvers in Dynamic Domains}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure