A Formal Analysis of Required Cooperation in Multi-agent Planning

Yu Zhang, Subbarao KambhampatiarXiv 2014 · arXiv

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.
Taxonomy of Required Cooperation (RC) in Multi-Agent Planning.

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.

Causal graph for the Diamond Heist example, showing dependencies between agent location, the diamond, and door locks.

Key Conditions for Cooperation

The research identifies five sufficient conditions that force cooperation:

  1. Domain Heterogeneity: Agents are restricted to different parts of the state space.
  2. Variable Heterogeneity: Agents control different sets of state variables.
  3. Capability Heterogeneity: Agents have different sets of available actions.
  4. Non-traversable State Space: The environment prevents a single agent from visiting all necessary states to complete the plan.
  5. 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

Abstract

Research on multi-agent planning has been popular in recent years. While previous research has been motivated by the understanding that, through cooperation, multi-agent systems can achieve tasks that are unachievable by single-agent systems, there are no formal characterizations of situations where cooperation is required to achieve a goal, thus warranting the application of multi-agent systems. In this paper, we provide such a formal discussion from the planning aspect. We first show that determining whether there is required cooperation (RC) is intractable is general. Then, by dividing the problems that require cooperation (referred to as RC problems) into two classes -- problems with heterogeneous and homogeneous agents, we aim to identify all the conditions that can cause RC in these two classes. We establish that when none of these identified conditions hold, the problem is single-agent solvable. Furthermore, with a few assumptions, we provide an upper bound on the minimum number of agents required for RC problems with homogeneous agents. This study not only provides new insights into multi-agent planning, but also has many applications. For example, in human-robot teaming, when a robot cannot achieve a task, it may be due to RC. In such cases, the human teammate should be informed and, consequently, coordinate with other available robots for a solution.
BibTeX
@misc{zhang2014formal,
  author = {Yu Zhang and Subbarao Kambhampati},
  title = {{A Formal Analysis of Required Cooperation in Multi-agent Planning}},
  year = {2014},
  eprint = {1404.5643},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1404.5643},
}
Figure