Multiple-Agent Planning Systems

Kurt Konolige, Nils J. NilssonAAAI 1980

Abstract

This 1980 paper by Kurt Konolige and Nils Nilsson is a foundational text in Distributed Artificial Intelligence (DAI). It addresses the limitations of early AI planning systems, which were designed for single agents in static environments. The authors propose a formal framework that allows multiple autonomous agents to cooperate by reasoning about each other's internal states, including beliefs, goals, and plans. By employing meta-languages and "semantic attachment" for procedural simulation, the system enables agents to plan communicative acts and delegate tasks effectively.

Introduction: Beyond the "Lone Wolf" Planner

In the late 1970s, AI planning was dominated by systems like STRIPS and NOAH. These "single-player" models assumed a world that only changed through the actions of a lone agent. However, real-world scenarios are often distributed and dynamic. The core challenge identified by Konolige and Nilsson is that in a multi-agent environment, an agent cannot plan in a vacuum; it must account for the knowledge, intentions, and likely actions of others.

Methodology: A Formalism for Multi-Agent Reasoning

The authors develop a multi-agent formalism based on first-order theories and metatheories. Each agent is modeled as an independent entity with its own "theory" comprising a language, facts, goals, and a deductive system.

Internal Modeling and Meta-Predicates

To represent the mental state of another agent, the system uses meta-level predicates such as FACT(agent, 'proposition') and GOAL(agent, 'goal'). This allows Agent A to maintain a symbolic model of Agent B’s beliefs without falling into infinite recursive loops.

Semantic Attachment and Simulation

A key innovation is "semantic attachment." Rather than relying solely on slow logical proofs to predict a peer's behavior, an agent can "attach" a procedural model of that peer's planner. This allows for a simulation of the other agent's reasoning process.

Agent A1's internal planning tree to achieve the goal of holding block B.

Spontaneous Operators and Communication

The framework introduces "spontaneous operators" that trigger automatically when preconditions are met, modeling the independent agency of others. Furthermore, communication is treated as a planning action. "Telling" or "asking" has specific preconditions (e.g., the speaker must believe the information) and effects (e.g., the listener acquires a new belief).

Key Results: Coordinating via Communication

The paper demonstrates the effectiveness of this formalism through a coordinated trace in a "blocks-world" scenario involving two agents, A0 and A1.

  1. Goal Identification: Agent A0 wants to hold a block currently held by Agent A1.
  2. Constraint Reasoning: A0 recognizes it cannot physically take the block.
  3. Speech Act Planning: A0 plans to tell A1 it is ready and asks A1 to clear the block.
  4. Predictive Simulation: By simulating A1's reasoning, A0 predicts that A1 will put the block down once requested.
A complex planning trace showing coordination between agents A0 and A1 through communication and plan simulation.

The resulting plan successfully coordinates the two agents through shared belief and strategic communication, demonstrating that delegation is a valid planning step rather than a failure.

Discussion and Limitations

While foundational, the paper acknowledges several limitations. The system was in an early stage of development, focusing on "loosely coupled" cooperative agents rather than competitive or hierarchical social structures. Additionally, the computational overhead of modeling entire belief systems poses scaling challenges for more complex environments. Future work would need to address the heuristics for when an agent should choose simulation over simple logical axioms.

Conclusion

Konolige and Nilsson’s work laid the groundwork for modern multi-agent systems. By treating other agents as dynamic entities with internal logic, they moved AI planning toward more realistic, collaborative environments where communication and mutual modeling are central to success.

Summary updated

BibTeX
@inproceedings{konolige1980multiple,
  author = {Kurt Konolige and Nils J. Nilsson},
  title = {{Multiple-Agent Planning Systems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1980},
}
Figure