Dynamic Task Allocation with Dialogue

Matthew Groholski, Weiwei Gu, Nakul GopalanarXiv 2026 · arXiv

TL;DR

Researchers at Arizona State University have developed a communication-augmented Bayesian framework that allows AI agents to coordinate tasks in "messy," dynamic environments where they can't see everything. By treating natural language dialogue as probabilistic evidence to update internal belief states, their agent significantly outperforms vanilla Large Language Model (LLM) agents and non-communicating baselines in partially observable settings.

What Problem Does This Paper Address?

Imagine a busy restaurant kitchen. Orders arrive at random, chefs can’t always see what their colleagues are doing behind the counter, and responsibilities must shift on the fly to prevent bottlenecks. This is dynamic task allocation under partial observability.

Most existing AI frameworks for multi-agent collaboration struggle here. They often assume "static goals" (the menu never changes) or "full observability" (everyone sees everything). While LLMs are great at conversation, they often lack explicit, verifiable "beliefs" about what needs to be done, making them unreliable long-horizon planners. The authors aim to bridge this gap by combining the structured reasoning of Bayesian inference with the flexible communication of LLMs.

Methods

The authors introduce a language-lifted agent that operates within a decentralized partially observable Markov decision process (Dec-POMDP). Key components include:

  • Bayesian Task Inference: Building on "Bayesian Delegation," the agent maintains a probability distribution over possible task allocations. It updates this "belief" based on observed actions and—crucially—dialogue.
  • Dialogue as Evidence: Instead of letting an LLM take the wheel entirely, the agent uses an LLM to calculate the likelihood of a specific utterance given a hypothesized task allocation. This allows natural language to function as formal evidence in a Bayesian update.
  • Latent Propositional Beliefs: In partially observable modes, the agent maintains beliefs about "latent propositions"—for example, "Does a chopped tomato exist in the area I can't see?" These beliefs are updated recursively based on environmental logic and teammate communication.
  • Entropy-Based Communication: To avoid constant "chatter," agents only broadcast messages when their uncertainty (measured via Shannon entropy) about the current task allocation exceeds a specific threshold.
Fig. 2: (a) An example of utterances between two agents. The agent circled in blue communicates its belief that both agents are currently collaborating to chop the lettuce. The agent circled in purple communicates its belief that it is cooking the potato while the other agent is chopping the lettuce. (b) Example of an agent’s beliefs over the unobserved state space. In this example, the agent’s latent propositions include object existence and object creation.

Datasets

The framework was evaluated using a modified version of the Overcooked environment, a popular benchmark for multi-agent coordination. The authors introduced two critical extensions:

  1. Dynamic Goal Setting: Tasks (recipes) arrive incrementally during execution rather than being fixed at the start.
  2. Partial Object-Space Observability: Agents are restricted to seeing only their local partition and a shared counter space, forcing them to reason about the "fog of war."

They tested these on both Symmetric (even capabilities) and Asymmetric (uneven capabilities/access) layouts.

Key Insights and Ideas

  • Communication as a "Gap Filler": The value of dialogue is inversely proportional to observability. Under full observability, agents can often infer intent just by watching their partner. In partial observability, communication becomes the primary tool to "close the information gap."
  • LLMs as Interpreters, Not Planners: The study reinforces that while LLMs struggle with autonomous long-horizon planning, they are excellent at interpreting intent from dialogue, which can then be fed into more robust, explicit planning procedures.
  • Explicit Beliefs Matter: The vanilla LLM baseline failed to complete any configuration in the study. This suggests that for complex, multi-step collaboration, agents need an explicit, verifiable model of the world and their partners' intents, rather than relying on the "black box" of a neural network's internal state.

Key Results

The communication-augmented agent was compared against a vanilla LLM agent and a non-communicating Bayesian baseline.

  • vs. Vanilla LLM: The proposed agent consistently outperformed the LLM agent in all settings.
  • vs. Non-Communicating Baseline: Under full observability, the performance was comparable. However, under partial observability, the communication agent showed a massive advantage. As task complexity increased, it achieved an average speedup of 0.585 and completed tasks an average of 18 timesteps faster.
Performance metrics showing the clear advantage of the communication agent under partial observability.

Limitations and Future Work

The authors acknowledge several limitations that pave the way for future research:

  • Narrow Dialogue: Currently, utterances only convey task-allocation intent. They do not yet support richer interactions like negotiation, asking questions, or error repair.
  • Communication Costs: The model assumes reliable, cost-free communication. In many real-world robotics applications, bandwidth is limited or noisy.
  • Scale: The experiments were limited to two-agent scenarios with a small set of task types. Scaling to larger teams and more diverse environments remains a challenge.

By grounding LLM-based dialogue in explicit probabilistic reasoning, this work provides a promising blueprint for robots that can truly "talk through" complex problems in environments where they can't see the whole picture.

Summary updated

Abstract

Effective multi-agent collaboration requires agents to adapt task allocation as goals and responsibilities evolve. Prior task-allocation frameworks often assume static goals, full observability, or rely on large language models (LLMs) without explicit, verifiable beliefs about task allocation or intent. These assumptions limit their applicability to real-world collaboration, where agents often lack full information about each other's actions, progress, or local environment. To support dynamic task allocation under partial observability, we introduce a communication-augmented Bayesian task-allocation framework. Our agent uses dialogue to reduce uncertainty about the environment and collaborators, while keeping decisions grounded in explicit probabilistic beliefs. We evaluate our framework in an Overcooked domain extended with dynamically arriving tasks under both full and partial object-space observability. Our communication agent consistently outperforms a vanilla LLM agent in both settings. Additionally, our framework performs comparably to a non-communicating task-allocation baseline under full observability, but substantially outperforms it under partial observability as task complexity increases by an average speed up of 0.585 and completes on average 18 timesteps faster. These results indicate that our agent is more efficient in dynamic task allocation than baselines in partially observable environments, and that communication is important as available information decreases.
BibTeX
@misc{groholski2026dynamic,
  author = {Matthew Groholski and Weiwei Gu and Nakul Gopalan},
  title = {{Dynamic Task Allocation with Dialogue}},
  year = {2026},
  eprint = {2611.23119},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.23119},
}
Figure