Too Many Cooks: Coordinating Multi-agent Collaboration Through Inverse Planning

Summary

Wang et al. present Bayesian Delegation, a decentralized coordination mechanism for cooking-style multi-agent tasks where agents must infer what subtasks other agents are pursuing and decide whether to divide labor or jointly solve a subtask. The model uses inverse planning to maintain a posterior over task allocations, then uses bounded real-time dynamic programming for low-level action planning and collision avoidance.

This is a partial ingest based on the extended abstract text.

Key Claims

• Flexible collaboration requires agents to switch between divide-and-conquer behavior and joint subtask execution without assuming explicit communication or pre-coordination.
• Inferring another agent’s subtask by inverse planning can support decentralized coordination in hierarchical tasks.
• Including joint subtasks in the prior matters: some tasks cannot be completed by either agent alone, so a purely independent subtask allocation misses required cooperation.
• Both Bayesian subtask inference and joint planning are needed; lesioned models produce slower completions and spatial miscoordination.

Methods / Formalism

• The tasks are modeled as decentralized MDPs with a partial order over object-object interaction subtasks, instantiated as kitchen/cooking tasks.
• Let ta denote a high-level assignment of agents to subtasks. At each time step, the agent selects

$$t{a}^{\ast }=\arg \underset{ta}{\max }P(ta\mid H_{0:T}),$$

where H_{0:T} = [(s_0,a_0), ..., (s_T,a_T)] is the public interaction history.

• The posterior is updated by Bayesian inference:

$$P(ta\mid H_{0:T})\propto P(ta)\prod _{t=0}^{T}P(a_t\mid s_t,ta).$$

• The likelihood is computed by inverse planning with a softmax model of approximately rational action:

$$P(a_t\mid s_t,ta)\propto \exp (\beta Q_{ta}^{\ast }(s_t,a_t)).$$

• Low-level planning uses bounded real-time dynamic programming (BRTDP) for the MDP induced by the chosen subtask, plus partner models for collision avoidance and role allocation in joint subtasks.
• See Bayesian Delegation for the reusable inference and planning schema.

Evidence / Experiments

• The authors test the model in nine cooking tasks formed from three kitchens and three nonlinear recipes.
• The full Bayesian Delegation model is compared against two lesions: one without joint planning, and one without both Bayesian Delegation and joint planning.
• The full model finishes recipes in fewer time steps, especially in more complex layouts/recipes that demand high-level subtask coordination and low-level spatial coordination.
• Lesioned systems often create deadlocks or bottleneck conflicts, such as both agents waiting for the same corridor.

Connections

• Grounds Multi-Agent Coordination in a compact inverse-planning mechanism rather than learned value decomposition alone.
• Fits Ad Hoc Teamwork because agents coordinate without prior task assignment or communication.
• Complements Rother2023 - Disentangling Interaction using Maximum Entropy Reinforcement Learning in Multi-Agent Systems: Wang et al. infer collaborator intent over subtasks, while Rother et al. learn impact-aware policies for coexistence.
• Connects to Cooperative Multi-Agent Reinforcement Learning as a structured-planning alternative to pure shared-reward policy learning.
• Useful for Strategic Reasoning because coordination is treated as belief update over other agents’ latent plans.

Open Questions

• How does Bayesian Delegation scale when the subtask graph, number of agents, or possible role assignments becomes large?
• How robust is the model when partner behavior is not approximately optimal under the assumed Q^*_{ta}?
• Can learned policies recover the same role-allocation structure without explicit inverse-planning machinery?
• What safety failures arise when the posterior confidently misclassifies another agent’s subtask?

Citation

Wang, Rose E., Sarah A. Wu, James A. Evans, Joshua B. Tenenbaum, David C. Parkes, and Max Kleiman-Weiner. 2020. “Too Many Cooks: Coordinating Multi-agent Collaboration Through Inverse Planning.” Extended Abstract, AAMAS 2020.