Source-linked AI summary
Too many cooks: Bayesian inference for coordinating multi-agent collaboration
Rose E. Wang, Sarah A. Wu, James A. Evans, Joshua B. Tenenbaum, David C. Parkes, Max Kleiman-Weiner
TL;DR
Agents must coordinate on the fly despite uncertainty about one another’s intentions. Bayesian Delegation infers sub-tasks from observed actions and plans for shared or separate work; evaluations report strong collaboration outcomes and human-aligned inferences.
Problem
Agents need to coordinate high-level sub-tasks and low-level actions while inferring others’ intentions from actions that may be ambiguous.
Source: §1 · pp. 1–2Method
Results
Bayesian Delegation outperforms alternatives in self-play, collaborates with unfamiliar agent types, and produces sub-task inferences aligned with many fine-grained variations in human judgments.
Source: §4 · pp. 7–8Takeaways & Limitations
The results show that decentralized agents can coordinate across shared and separate sub-tasks while making sparse-data inferences consistent with human judgments.
Source: §5 · p. 8The agents lack communication to resolve conflicts, which the authors identify as a risk for sensitive applications.
Source: Broader Impact · p. 10
Abstract
from arXiv · showhide
Collaboration requires agents to coordinate their behavior on the fly, sometimes cooperating to solve a single task together and other times dividing it up into sub-tasks to work on in parallel. Underlying the human ability to collaborate is theory-of-mind, the ability to infer the hidden mental states that drive others to act. Here, we develop Bayesian Delegation, a decentralized multi-agent learning mechanism with these abilities. Bayesian Delegation enables agents to rapidly infer the hidden intentions of others by inverse planning. We test Bayesian Delegation in a suite of multi-agent Markov decision processes inspired by cooking problems. On these tasks, agents with Bayesian Delegation coordinate both their high-level plans (e.g. what sub-task they should work on) and their low-level actions (e.g. avoiding getting in each other's way). In a self-play evaluation, Bayesian Delegation outperforms alternative algorithms. Bayesian Delegation is also a capable ad-hoc collaborator and successfully coordinates with other agent types even in the absence of prior experience. Finally, in a behavioral experiment, we show that Bayesian Delegation makes inferences similar to human observers about the intent of others. Together, these results demonstrate the power of Bayesian Delegation for decentralized multi-agent collaboration.
1 Introduction
Collaboration requires agents to coordinate their actions and infer others’ unobserved intentions, especially when actions are ambiguous. Bayesian Delegation uses inverse planning to infer sub-tasks and coordinate decentralized agents, with evaluations spanning self-play, ad-hoc collaboration, and human judgments.
1 Introduction
- Agents must infer hidden intentions from actions, which can be ambiguous because multiple intentions may produce the same action.The paper describes this capacity as theory-of-mind and aims to use it for collaboration in novel situations.Source: §1 · pp. 1–2
- The cooking tasks test parallel work on separate sub-tasks, cooperation on shared sub-tasks, and movement that avoids interference.The tasks are inspired by Overcooked and share features with object-oriented construction and assembly tasks.Source: §1 · p. 2
- Prior Overcooked studies often train agents with self-play or human data, while this approach learns during interaction and targets coordination across and within sub-tasks.The paper situates its approach in ad-hoc coordination and decentralized Bayesian theory-of-mind.Source: §1 · p. 2
- Bayesian Delegation infers others’ sub-tasks through inverse planning, enabling agents to delegate effort and coordinate without centralized control.The paper reports better self-play performance than alternatives, successful ad-hoc collaboration, and inferences aligned with fine-grained variations in human judgments.Source: §1 · p. 3
2 Multi-Agent MDPs with Sub-Tasks
These MMDPs make sub-tasks explicit while leaving agents to coordinate who does what and how to carry it out. The Overcooked-inspired test suite combines partially ordered recipes with simultaneous movement in grid-world kitchens.
2 Multi-Agent MDPs with Sub-Tasks
- The MMDP has shared rewards and independently chosen actions, while agents observe the environment state but not one another’s policies or internal representations.States encode locations, status, and types of objects and agents.Source: §2 · p. 3
- Sub-tasks form a partial order, with preconditions and postconditions; each Merge(X,Y) task brings two objects to the same location, which need not be predetermined when both can move.The recipe is represented by the partial order of sub-tasks.Source: §2 · p. 3
- Partial ordering creates choices about which agent implements each Merge and the order of eligible tasks, so agents must align their plans.For the Salad recipe, the chopped ingredients can be combined before plating, or either ingredient can be plated first.Source: §2 · p. 3
2.1 Coordination Test Suite
- The test suite uses 2D grid-world kitchens with movable foods and plates, immovable stations, and simultaneous agent movement constrained by counters and other agents.Agents can pick up objects, carry one at a time, chop food at knife stations, and merge food with plates; they cannot pass objects directly to each other.Source: §2.1 · pp. 3–4
- Each kitchen task is to finish the recipe and deliver the dish to the star square as quickly as possible, with a 100-step episode limit.The environments vary kitchens and recipes for evaluation.Source: §2.1 · p. 4
3 Bayesian Delegation
Bayesian Delegation infers a shared task-allocation hypothesis from observed actions, then plans actions according to the most likely allocation. Its decentralized planners support both separate and shared sub-tasks.
3 Bayesian Delegation
- Bayesian Delegation uses inverse planning to infer which sub-tasks other agents are pursuing, then chooses whether to divide work or cooperate on a shared task.Agents plan and learn independently without access to one another’s internal representations.Source: §3 · p. 4
- Each agent maintains a probability distribution over allocations assigning every agent to a sub-task, including both separate-task and shared-task assignments.Agents cannot communicate before or during execution, so the allocation remains uncertain.Source: §3 · p. 4
- The posterior over allocations uses the prior and the likelihood of all agents’ actions given the state and allocation; updates use commonly observed history, not each agent’s private intention.The likelihood models whether each agent follows its assigned sub-task.Source: §3 · p. 4
- Action likelihoods come from planned sub-task policies, with a soft-max parameter β modeling beliefs about whether other agents act optimally or randomly.As β approaches 0, others are believed to act randomly; as β approaches infinity, they are believed to maximize.Source: §3 · p. 4
- Allocation priors exclude tasks whose preconditions are unmet and favor allocations estimated to take less time; priors reset as tasks become available or are completed.The paper says these dynamics help agents align beliefs about who is doing what.Source: §3 · pp. 4–5
- For separate sub-tasks, agents model others’ movements to avoid interference; for shared tasks, joint policies let agents plan cooperative actions such as passing objects across counters.Joint plans are not guaranteed to coordinate perfectly because planning is stochastic.Source: §3 · p. 5
4 Results
Across self-play, ad-hoc pairings, and human-inference tests, Bayesian Delegation performs well against alternative agents and aligns most closely with human judgments. Its advantages are especially apparent in more complex tasks that require flexible plans or coordination on shared sub-tasks.
Self-play
- Bayesian Delegation outperforms all baselines in self-play across nine environments, completing recipes in fewer time steps with fewer shuffles.Its performance does not suffer with three agents, while most other agents perform worse; Figure 2 breaks down two-agent results by kitchen and recipe.Source: Figure 2 · p. 6, §4 · p. 7
- In complex Salad tasks on Full-Divider, agents without learning struggle to coordinate a shared completion order, while Bayesian Delegation can yield to others to break action cycles.Salad allows three completion orders, and neither agent can perform every sub-task alone.Source: §4 · p. 7
Ad-hoc
- Bayesian Delegation performs well with unfamiliar agent types; pairings with UP, D&C, and Greedy outperform those agents’ respective self-play pairings.None of the agents had prior experience with their partners.Source: §4 · p. 7, Figure 3 · p. 8
Human inferences
- Bayesian Delegation is more aligned with human judgments than all four baseline models.The study compared model predictions with judgments from 45 participants observing agent interactions.Source: §4 · pp. 7–8, Figure 4 · p. 8
- Without training on human behavior, Bayesian Delegation captures fine-grained sub-task inferences, including how ambiguous actions become clearer as interaction unfolds.The authors suggest it may help build better models of human theory of mind for cooperation with people.Source: §4 · p. 8
5 Discussion
Bayesian Delegation supports ad-hoc coordination by inferring others’ sub-tasks and aligning beliefs, in ways consistent with human judgments. The authors identify limits in tracking individual contributions to joint tasks and coordinating larger, longer-term groups.
5 Discussion
- Bayesian Delegation infers others’ sub-tasks from sparse data and aligns agents’ beliefs about who is doing what, consistent with human judgments.It supports both helping on a shared sub-task and dividing work for efficiency.Source: §5 · p. 8
- Agents cannot tell when they have completed their individual contribution to a jointly planned sub-task.For example, an agent passing ingredients across a divider cannot know when its role in the joint effort is finished.Source: §5 · p. 8
- Recognizing when an agent’s role is finished could let it plan for later sub-tasks before their preconditions are satisfied.Source: §5 · pp. 8–9
- As groups grow, hierarchies, norms, and conventions may help coordinate longer-term collaborations beyond a single short interaction.The authors also identify partnering with human teams as a future capability.Source: §5 · p. 9
Broader Impact
The authors identify possible uses for coordination without a shared communication channel, including assistive technologies, and note that beliefs make agent decisions interpretable. They also flag open questions about human-value alignment and resolving conflicts without communication.
Broader Impact
- Belief alignment without communication could support assistive technologies where a common channel is not feasible.The authors give virtual assistants and household robots for older adults as possible examples.Source: Broader Impact · p. 10
- Reviewing agents’ beliefs can make their decisions interpretable, unlike many end-to-end trained deep reinforcement learning policies.Source: Broader Impact · p. 10
- Open questions include which sub-tasks agents should infer, who chooses them, and how to align them with human values.Source: Broader Impact · p. 10
- Without communication, agents lack a way to resolve conflicts, a concern the authors raise for sensitive applications.They mention surveillance, law enforcement, and military settings.Source: Broader Impact · p. 10
A Analysis of Agent Behavior
The behavior analysis illustrates agents aligning beliefs about sub-task assignments and shows shuffles as a coordination failure that Bayesian Delegation and Joint Planning help prevent.
A Analysis of Agent Behavior
- The paper’s project page provides videos of two- and three-agent behavior across environments.Source: A Analysis of Agent Behavior · p. 13
- Beliefs converge both on sub-task ordering and on which agent should handle a sub-task, despite no communication or prior agreement.On Salad, agents shift to tomato plating followed by adding chopped lettuce to the plate.Source: Figure 5 · p. 13
- Bayesian Delegation and Joint Planning help prevent shuffles, a repeated back-and-forth that keeps agents from passing each other.The example involves no collision; the figure reports average shuffles per agent in Open- and Partial-Divider environments.Source: Figure 6 · p. 14
B Environment Details
The appendix describes how recipe sub-tasks and kitchen states are represented, and presents figures covering ordering frequencies and agent performance across kitchen-recipe compositions.
B Environment Details
- Figure 7 reports the frequency of three Salad orderings in Open- and Partial-Divider environments.Source: Figure 7 · p. 14
- Recipe sub-tasks are generated from STRIPS instances by searching for shortest paths from the initial state to a goal and collecting actions on those paths.Actions have preconditions and postconditions; the resulting set of sub-tasks can be partially ordered.Source: B Environment Details · p. 14
- The full agent completes more sub-tasks and does so more quickly than the alternatives across the kitchen-recipe compositions shown.Figure 8 organizes compositions by kitchen rows and recipe columns; its left graphs show time steps and right graphs show sub-task completion over time.Source: Figure 8 · p. 15
- The state representation allows objects to hold other objects; combined objects share coordinates and movement, with interactions occurring at the same location.Food items can be chopped or unchopped, and the table lists object interactions and transitions.Source: Table 2 · p. 15, B Environment Details · p. 15
C Behavioral Experiment
The experiment asked participants to infer agents’ tasks and whether they were collaborating from trajectories. Its setup used cooking tasks and kitchens that varied in counter layout.
C Behavioral Experiment
- Participants judged what tasks agents were doing and whether they were working together based on the scenes shown in Figure 12.The 60 recruited participants completed the experiment in 10–15 minutes and were paid $0.80.Source: C Behavioral Experiment · p. 15
- Most kitchen-recipe compositions showed better ad-hoc coordination as models became more Bayesian Delegation-like.Figure 9 breaks aggregate performance down by kitchen and recipe; lower performance is better.Source: Figure 9 · p. 16
- The kitchens varied only in counter placement: agents could cross freely, pass through a bottleneck, or remain on one side.Source: Figure 10 · p. 16
- After practice and filtering for instruction comprehension, 45 participants completed 15 trajectory-judgment questions.Sixty participants were recruited initially; the final analysis used N = 45.Source: C Behavioral Experiment · pp. 15–16
D Computational Experiments
The computational experiments used cooking recipes and kitchen layouts to evaluate models and generate behavioral-experiment predictions. The appendix describes the planning implementation, experimental compute, and code availability.
D Computational Experiments
- The recipes ranged from tomato preparation to adding lettuce and combining chopped foods into a salad, with example plans showing possible task orderings.Source: Figure 11 · p. 17
- Two-agent simulations and behavioral-trajectory predictions ran on one CPU core per simulation, taking roughly three hours and up to 15 GB of memory.The reported batch covered 3 recipes, 3 environments, 5 models, and 20 seeds.Source: D Computational Experiments · pp. 16–17
- BRTDP used a cost structure penalizing each time step by 1 and movement by an additional 0.1, with bounds and stopping criteria specified for planning.The lower bound used Manhattan distance; the upper bound summed shortest paths. Runs stopped at bound convergence (α = 0.01, τ = 2) or after 100 trajectories of up to 75 roll-outs.Source: D Computational Experiments · pp. 17–18
- The behavioral stimuli included agent trajectories and feasible-task likelihood judgments, alongside recipe and environment-state information.Figure 12 shows model and participant inferences; Figure 13 depicts the question format.Source: Figure 12 · p. 17, Figure 13 · p. 18
- When agents had no valid sub-task, random movement or staying in place improved alternative-model performance but did not affect Bayesian Delegation.Without this noise, alternative agents often got stuck and blocked each other from completing the recipe.Source: D Computational Experiments · p. 18
- The environment and model code was included in the supplemental materials and made available on GitHub.Source: D Computational Experiments · p. 18
E Pseudocode
The pseudocode maintains beliefs over feasible task allocations, infers others’ intentions from action likelihoods, and then chooses a task and plans accordingly.
E Pseudocode
- At initialization or when feasible allocations change, the algorithm initializes allocation beliefs using the task values estimated by BRTDP.Source: E Pseudocode · p. 19
- When allocations remain unchanged, it updates their beliefs using observed-action likelihoods, then normalizes the posterior and selects the maximum a posteriori allocation.Source: E Pseudocode · p. 19
- After selecting its own task, an agent plans jointly when another agent shares that task; otherwise, it plans a best response to other agents’ models.Source: E Pseudocode · p. 19