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.
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.
- Goal Identification: Agent A0 wants to hold a block currently held by Agent A1.
- Constraint Reasoning: A0 recognizes it cannot physically take the block.
- Speech Act Planning: A0 plans to tell A1 it is ready and asks A1 to clear the block.
- Predictive Simulation: By simulating A1's reasoning, A0 predicts that A1 will put the block down once requested.
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