Communication and Interaction in Multi-Agent Planning

Michael P. GeorgeffAAAI 1983

Abstract

In multi-agent environments, the coordination of independent plans is essential to prevent resource conflicts and ensure goal achievement. This paper, originally published in 1983, introduces a formal method for merging single-agent plans into a synchronized multi-agent framework. By representing actions as sequences of states and identifying "critical regions" through commutativity analysis, the system generates minimal communication primitives to maintain safety without exhaustive state-space searching.

Introduction

In the early development of artificial intelligence, planning was primarily treated as a single-agent problem in a static world. However, as systems evolved to include multiple autonomous actors, the limitations of traditional planning became apparent. A plan that is optimal for one agent may be rendered impossible if another agent occupies a required resource or alters the environment mid-action. Michael Georgeff’s "Communication and Interaction in Multi-Agent Planning" addresses the challenge of coordinating these agents without falling into the "combinatorial explosion" that typically occurs when trying to account for every possible interleaving of agent actions.

The Problem: Beyond Atomic Actions

Traditional AI planners, such as STRIPS, modeled actions as atomic transitions—simple "before and after" snapshots. While effective for single-agent scenarios, this model fails in multi-agent environments because it ignores the state of the world during the execution of an action. For example, if two robots both require a specific tool for the duration of their respective tasks, a model that only checks start and end states might erroneously conclude that their plans are compatible.

Checking every possible interleaving of actions is computationally prohibitive. For two agents with ten steps each, there are over 180,000 possible sequences to evaluate. Georgeff’s objective was to develop a method that ensures safety and cooperation by analyzing action interactions more intelligently.

Methodology

Actions as Sequences

To capture the temporal nature of tasks, Georgeff defines actions as sequences of state sets rather than atomic jumps. This allows for the specification of "during" conditions—properties that must remain true throughout the action's execution.

Action definition for puton(x,y) showing pre, during, and post conditions.

As shown in the figure above, the puton(x,y) action is defined not just by its preconditions and postconditions, but by a during clause. This clause ensures that the agent maintains its hold on object x and that the destination y remains clear while the action is in progress.

Interaction Analysis and Commutativity

The core of the proposed method is the Commutativity Theorem. The system analyzes pairs of action sequences to determine if they commute—meaning they can be executed in any order or in parallel without conflict. Georgeff proves that if two sequences commute, the planner only needs to verify safety at the "boundary" states (the entry and exit points). If these boundaries are safe, the entire sequence is guaranteed to be safe, drastically pruning the search space.

Critical Regions and Synchronization

When actions do not commute, the system identifies "critical regions" where conflicts may occur. To manage these, the planner utilizes Communicating Sequential Processes (CSP) primitives. It generates a "supervisor" process that acts as a traffic controller, using simple send and receive commands to ensure mutual exclusion. Communication is thus used as a minimalist synchronization tool rather than a complex negotiation platform.

Evaluation and Results

The approach was validated using classic symbolic AI benchmarks, most notably the Blocks World and the Lathe Example. In the Lathe Example, two robots must share a single machine to manufacture different parts. The system successfully:

  1. Identified the lathe as a shared resource causing a conflict.
  2. Simplified the plans to focus on the conflicting segments.
  3. Automatically generated a synchronizer process to manage access via status variables.
  4. Produced a multi-agent plan guaranteed to be deadlock-free and safe from harmful interactions.

Conclusion and Future Work

Georgeff’s work demonstrated that multi-agent coordination can be achieved efficiently by exploiting the independence of agent actions. By focusing on boundary states and critical regions, the system avoids the computational burden of exhaustive interleaving analysis.

While foundational, the method assumes that single-agent plans are pre-generated and relies on the "STRIPS assumption" (that the environment only changes through explicit agent actions). Future research directions suggested by the paper include handling conditional plans, where agent behavior depends on real-time sensor data, and developing hierarchical planning structures to manage even greater complexity in multi-agent systems.

Summary updated

BibTeX
@inproceedings{georgeff1983communication,
  author = {Michael P. Georgeff},
  title = {{Communication and Interaction in Multi-Agent Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1983},
}
Figure