A Framework for Distributed Problem Solving

David McArthur, Randall Steeb, Stephanie J. CammarataAAAI 1982

Introduction

In the early 1980s, Artificial Intelligence research was primarily focused on single-agent systems operating within static, predictable environments. Classic planners like STRIPS or NOAH relied on a linear "sense-plan-act" cycle. However, this paradigm falters in distributed environments where multiple agents must interact, negotiate, and adapt to changes caused by others. This 1982 paper from the AAAI proceedings introduces a foundational framework for Distributed Artificial Intelligence (DAI), proposing a shift from rigid sequential planning toward a more flexible, "knowledge-based operating system" model for agents.

The Challenge of Multi-Agent Environments

The authors identify a fundamental limitation in traditional AI: the assumption of a static world. In a multi-agent system, an agent’s plan may become obsolete before it is even completed because another actor has altered the environment. To address this, the paper outlines five essential "competences" for a distributed agent:

  1. Continuous world-model updates: Maintaining an accurate view of the environment.
  2. Asynchronous information integration: Processing data received from other agents at any time.
  3. Dynamic plan modification: The ability to invalidate or alter plans during execution.
  4. Altruistic interruption: Pausing one's own planning to assist others.
  5. Resource recruitment: Enlisting other agents to help achieve personal or shared goals.

The Proposed Framework: A Knowledge-Based OS

The core of the proposed framework is implemented in a custom INTERLISP task language. Rather than viewing an agent as a single execution thread, the authors treat it as a collection of generic tasks—such as sensing, planning, and evaluation—managed as resumable coroutines.

Key Architectural Pillars

  • Task Interweaving: Tasks can be suspended and resumed without losing state. This allows an agent to interleave different cognitive processes, such as pausing a long-term planning task to handle an immediate sensory update.
  • Blackboard Architecture: Borrowing from the HEARSAY-II system, all tasks share a common knowledge base. This ensures that if a sensing task updates the world model, a suspended planning task will immediately have access to the most current data upon resumption.
  • Heuristic Scheduling: The agent functions like an operating system, using heuristic rules to prioritize task instances. This mechanism balances "goal-directed" behavior (pursuing a plan) with "data-directed" behavior (reacting to new conflicts or information).
  • Self-Knowledge and Validity: Each task instance includes "validity conditions." If the environment changes such that a task is no longer relevant, the scheduler can terminate it, preventing the waste of computational resources on obsolete goals.

Experimental Evaluation: Distributed Air-Traffic Control (DATC)

To test the framework, the authors developed a simulated Distributed Air-Traffic Control (DATC) environment. In this simulation, multiple aircraft act as independent agents within a 14 x 23 mile airspace. Each agent's goal is to navigate to a destination (an airport or boundary outfix) while maintaining a 3-mile horizontal and 1000-foot vertical separation from other aircraft. The agents operate under constraints of limited sensory horizons and restricted communication bandwidth, forcing them to rely on the framework's distributed problem-solving capabilities to avoid collisions and manage traffic flow.

Key Insights and Implications

The paper’s most significant contribution is the conceptualization of an agent as an operating system. By managing competing cognitive processes through heuristic scheduling, cooperation becomes an emergent property of the system rather than just a fixed protocol. For instance, a scheduling rule might dictate that an agent should stop its own planning and request help from another aircraft if a conflict persists for too long without resolution.

This approach successfully navigates the tension between currency (staying reactive to new data) and continuity (maintaining a stable plan). The use of coroutines and a shared blackboard allows the agent to remain responsive without abandoning complex strategies at every minor environmental shift.

Conclusion and Future Directions

While the paper serves primarily as a proof-of-concept, it demonstrates that complex multi-agent coordination can be effectively modeled as a set of triggered, modular sub-tasks. The authors acknowledge that the computational overhead of managing these processes was significant for 1982-era hardware. Furthermore, they view the framework as a laboratory for future "computational experiments" to discover the most robust cooperative strategies for increasingly crowded and complex environments, where the density of goal interactions requires more sophisticated negotiation tactics.

Summary updated

BibTeX
@inproceedings{mcarthur1982framework,
  author = {David McArthur and Randall Steeb and Stephanie J. Cammarata},
  title = {{A Framework for Distributed Problem Solving}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1982},
}
Figure