Introduction
In Multi-Agent Planning (MAP), research typically focuses on how to coordinate multiple agents to solve a task efficiently. However, the fundamental question of whether multiple agents are strictly necessary—termed "Required Cooperation" (RC)—has received little formal attention. This paper provides the first formal characterization of RC, moving beyond the assumption that more agents are always better. It identifies specific conditions, such as agent heterogeneity and environmental structural constraints, that make cooperation mandatory.
Complexity and Taxonomy
The authors prove that determining if a planning problem requires cooperation is PSPACE-complete, establishing that identifying RC is just as hard as solving the planning problem itself. To facilitate analysis, the paper introduces a taxonomy of RC problems:
- Type-1 (Heterogeneous): Cooperation is necessitated by differences in agent capabilities, domains, or variables (DVC). For example, a logistics task might require both a truck to drive and a plane to fly. Many Type-1 problems are solvable by a hypothetical "Super Agent" possessing the union of all capabilities.
- Type-2 (Homogeneous): Cooperation is required due to the environmental structure, even when agents are identical (N-DVC). In these cases, the difficulty lies in the environment's constraints rather than the agents' individual limitations.
Structural Bottlenecks: Causal Loops
A primary cause of RC for identical agents is the "Causal Loop." This occurs when an agent's necessary actions to reach a goal state inadvertently destroy the preconditions for other required actions, creating a logical deadlock. This is often a result of a non-traversable state space, where an agent can reach a state but cannot return or move to a subsequent necessary state.
The authors illustrate this with a "Diamond Heist" example. To steal a diamond, an agent must enter a room, which triggers a security lock. Once the door is locked, the agent is trapped and cannot exit to flip an override switch. Thus, two agents are required: one to retrieve the diamond and another to remain outside at the switch to manage the door state.
Key Conditions for Cooperation
The research identifies five sufficient conditions that force cooperation:
- Domain Heterogeneity: Agents are restricted to different parts of the state space.
- Variable Heterogeneity: Agents control different sets of state variables.
- Capability Heterogeneity: Agents have different sets of available actions.
- Non-traversable State Space: The environment prevents a single agent from visiting all necessary states to complete the plan.
- Causal Loops: Interdependencies between variables create deadlocks for a single actor.
The authors prove a Theorem of Sufficiency: if none of these conditions exist (i.e., agents are homogeneous, the state space is traversable, and there are no causal loops), then any solvable MAP problem is guaranteed to be solvable by a single agent.
Conclusion and Future Work
This formal framework provides a rigorous basis for determining minimum agent requirements in complex tasks. While the paper establishes mathematical upper bounds for the number of agents needed, it acknowledges these may not be tight. Future work includes refining these bounds and extending the analysis to temporal planning, where non-instantaneous actions and synchronization requirements are likely to increase the necessity for cooperation. Additionally, this framework could assist in human-robot teaming by allowing robots to explain failures as structural requirements for human intervention.
Summary updated