TLDR: A new study explores how Large Language Models (LLMs) can effectively manage decentralized goal assignment for multiple autonomous agents in path planning. By providing LLMs like GPT-4.1 with structured prompts and explicit environmental data, researchers found they could achieve near-optimal task completion times, outperforming traditional greedy methods. This highlights the potential of LLMs in complex multi-agent coordination by enabling agents to reason about global objectives and resolve conflicts efficiently.
A recent study delves into a critical challenge in robotics and artificial intelligence: how to coordinate multiple autonomous agents in shared environments without relying on a single, central controller. This problem, known as decentralized goal assignment for multi-agent path planning, is addressed by allowing agents to independently decide which goals to pursue, share their preferences, and then use a fixed rule to resolve any conflicts that arise.
The researchers systematically compared various strategies for this decentralized goal assignment. These included traditional greedy methods, an optimal assignment solver (which provides a benchmark for the best possible outcome), and agents powered by advanced large language models (LLMs) such as GPT-4.1 and LLaVA. The experiments were conducted in simulated grid-world environments, where agents navigate a grid containing obstacles and specific goals. Each agent’s task is to select a unique goal, plan its movements, and avoid collisions with both static obstacles and other agents.
A significant finding from this research is the exceptional performance of LLM-based agents. When provided with carefully designed prompts and relevant quantitative information—such as explicit tables detailing agent-goal distances—these agents achieved near-optimal makespans. The makespan represents the total time required for all agents to successfully reach their assigned goals. This level of performance consistently surpassed that of traditional greedy heuristics, underscoring the crucial role of how information is structured and presented to the LLMs for their effectiveness.
The Proposed Decentralized Solution
The study proposes a decentralized goal assignment protocol where each agent receives a structured representation of its environment. This includes a labeled grid image, the precise positions of all agents, goals, and obstacles, and, in some experimental conditions, a table of agent-to-goal distances. Based on this comprehensive input, each agent independently generates a ranked list of goals according to its preferences. These ranked preferences are then simultaneously announced to other agents. Assignment conflicts are resolved using a predefined agent index order, meaning the agent with the lowest index receives priority in case of a tie.
Prompt engineering was a pivotal factor in the success of the LLM agents. Prompts were meticulously constructed to include detailed scenario descriptions, explicit instructions, and even “chain-of-thought” (CoT) prompting. CoT prompting encourages LLMs to articulate their intermediate reasoning steps before arriving at a final decision. This structured approach enabled the LLMs to make more globally informed choices, considering overall team objectives and potential conflicts rather than simply selecting locally optimal options for themselves. For example, a team-level reasoning checklist was integrated into the prompts to guide the LLMs in drafting assignments, computing the makespan, and exploring alternative assignments to identify the one with the smallest maximum path length.
Experimental Setup and Key Outcomes
The experiments involved 100 randomly generated grid-world scenarios, each featuring a 20×20 grid with 2 to 6 agents and goals, and between 15 and 30 uniformly placed obstacles. The optimal assignment, determined through brute-force centralized search, served as a ground-truth lower bound for comparison. Performance was primarily evaluated using the makespan and the performance gap relative to this optimum.
The results clearly demonstrated the superiority of the GPT-4.1 agents. Specifically, GPT-4.1 agents that re-ranked goals at each step and received explicit agent-goal distances achieved an impressive mean makespan of 15.12. This was remarkably close to the optimal makespan of 13.93. This performance significantly outperformed the greedy assignment (17.93) and random assignment (20.54) baselines. However, when explicit distance information was removed from the prompt, GPT-4.1’s performance declined to 17.67, becoming comparable to the greedy baseline. This highlights the critical importance of providing explicit, quantitative data to LLMs for effective decentralized assignment.
Conversely, the LLaVA-based agent performed substantially worse than all other methods, often yielding makespans exceeding even the random assignment baseline, especially as the team size grew. This poor performance was attributed to LLaVA’s tendency to frequently change its assignment strategy, leading to unstable and inconsistent plans, unlike GPT-4.1’s more stable and coherent rankings.
Also Read:
- Coordinating Robot Teams with Natural Language: A Hierarchical Planning Approach
- How Structured Communication Boosts AI Teamwork
Conclusion and Future Directions
The study concludes that large language models, when equipped with well-designed prompts and access to explicit quantitative information, can serve as highly effective decentralized agents for goal assignment in multi-agent grid environments. GPT-4.1-based agents, in particular, achieved makespans close to the optimal solution without requiring centralized planning and consistently outperformed traditional greedy and random assignment strategies, especially as the complexity of the problem increased. This work provides new benchmarks for language-model-driven coordination and suggests promising avenues for integrating LLM-based agents into scalable, decentralized multi-agent systems. For more details, you can read the full research paper here.
