Multi-Agent Planning (MAP)

MAP inherently involves decentralized computation and partial observability. Unlike a single, omniscient planner, each agent typically has:

• A local view of the global state.
• Private goals or a partial understanding of the shared objective.
• Limited communication bandwidth with other agents.

This distribution necessitates algorithms for plan merging, conflict detection, and information sharing to build a coherent global plan from local contributions. Frameworks like Decentralized POMDPs (Dec-POMDPs) formally model these challenges.

A defining challenge in MAP is managing action dependencies and resource conflicts. Agents' plans are not independent; an action by one agent may:

• Enable or disable an action for another (positive/negative interactions).
• Require a shared resource (e.g., a unique tool, a spatial location).
• Need to be synchronized in time.

Coordination mechanisms like the Contract Net Protocol, auction-based systems, and coordination graphs are used to detect and resolve these interdependencies, ensuring the joint plan is temporally and causally consistent.

MAP requires structured inter-agent communication to exchange proposals, constraints, and commitments. This is governed by:

• Agent Communication Languages (ACLs): Formal languages like FIPA ACL with defined semantics for speech acts (e.g., request, inform, propose).
• Interaction Protocols: Pre-defined conversation patterns, such as negotiation or auction protocols, that specify valid message sequences.
• Negotiation Mechanisms: Processes like argumentation-based negotiation or bargaining where agents exchange offers and justifications to reconcile differing preferences or costs.

The nature of agent goals fundamentally shapes the planning approach:

• Collaborative (Cooperative) MAP: All agents share a common global utility function. The focus is on finding the joint plan that maximizes collective payoff, though computational complexity is high. Techniques include centralized planning for decentralized execution or distributed optimization.
• Self-Interested (Strategic) MAP: Agents have private, potentially conflicting utilities. Planning involves game-theoretic concepts and mechanisms to reach stable agreements, such as forming coalitions and distributing payoff via concepts like the Shapley Value. Trust and social commitments become critical.

MAP must account for a dynamic environment where the world state changes during planning and execution. This requires:

• Online and Replanning Capabilities: Agents must be able to adjust the joint plan in real-time in response to failures, new agents joining, or unexpected events.
• Execution Monitoring: Agents need to observe the execution of the plan and communicate deviations. Approaches like Partial Global Planning (PGP) involve the continuous exchange and merging of local plan states.
• Commitment Management: Agents must decide when to publicly commit to an action and under what conditions to drop a commitment, balancing flexibility with predictability for other agents.

MAP is computationally complex, often falling into the NEXP-complete or PSPACE-hard complexity classes for general cases (e.g., Dec-POMDPs). This intractability drives the development of scalable approximations:

• Hierarchical Abstraction: Using Hierarchical Task Networks (HTNs) to decompose problems.
• Locality of Interaction: Exploiting sparse agent interactions, as modeled in Distributed Constraint Optimization Problems (DCOPs) and coordination graphs.
• Emergent & Stigmergic Coordination: Forgoing explicit planning in favor of simple local rules that lead to emergent coordination, as seen in ant colony optimization or flocking models, which scale to very large numbers of agents.

A decentralized task allocation mechanism where a manager agent broadcasts a task announcement. Potential contractor agents evaluate the announcement against their capabilities and submit bids. The manager then evaluates the bids and awards the contract to the most suitable bidder, formalizing the agreement. This protocol is foundational for dynamic, market-like coordination in open systems.

• Key Mechanism: Announcement-Bid-Award sequence.
• Use Case: Distributed sensor networks, supply chain logistics, and dynamic manufacturing job scheduling.

A shared workspace coordination architecture where multiple specialized agents, known as knowledge sources, asynchronously read from and write to a common data structure called the blackboard. Agents work independently toward a solution, with the state of the blackboard triggering their contributions. This pattern is effective for problems that require integrating expertise from different domains, such as speech recognition or complex diagnostic systems.

• Key Mechanism: Opportunistic, data-driven triggering of knowledge sources.
• Analogy: A group of experts contributing to a shared whiteboard to solve a puzzle.

A formal sequential decision-making framework for modeling multi-agent systems operating under uncertainty and partial observability. Each agent has a local observation of the global state and must choose actions based on its local policy. The challenge is to optimize a joint reward function without centralized control or communication of full state information. It provides a rigorous mathematical model for the complexity inherent in collaborative MAP.

• Core Challenge: The non-stationarity of the environment from any single agent's perspective.
• Application: Autonomous vehicle fleets, cooperative robotics, and networked sensor teams.

A framework for modeling problems where a set of agents must assign values to their local variables to optimize a global objective function, subject to constraints that involve variables of multiple agents. Computation and decision-making are distributed. Algorithms like DPOP (Distributed Pseudotree Optimization Protocol) or MGM (Maximum Gain Message) are used to find optimal or near-optimal solutions through local message passing.

• Key Concept: Decomposing a global utility function into a sum of constraint utilities.
• Use Case: Distributed scheduling, smart grid load balancing, and wireless channel allocation.

A plan merging and coordination approach where agents develop local plans and then exchange summaries to form a Partial Global Plan (PGP). This PGP represents a non-centralized, incomplete view of the collective activity. Agents use it to detect and resolve potential interactions—such as resource conflicts, synergies, or redundancies—and then refine their local plans accordingly. It balances local autonomy with the need for coherent joint action.

• Key Process: Plan exchange, interaction detection, and local plan modification.
• Origin: Developed for distributed sensor networks and cooperative robotics.

A graphical model that represents the structure of a multi-agent coordination problem. The global payoff function for a joint action is decomposed into a sum of local payoff functions, each dependent on only a small subset of agents. The graph's nodes represent agents, and edges connect agents whose actions directly interact. This structure enables efficient computation of optimal joint actions using message-passing algorithms like Max-Sum.

• Core Benefit: Exploits locality of interaction to avoid the exponential complexity of full joint action spaces.
• Application: Multi-robot coordination, team strategy in games, and distributed resource management.