💻 computer science

DISPATCH -- Decentralized Informed Spatial Planning and Assignment of Tasks for Cooperative Heterogeneous Agents

This paper introduces DISPATCH, a framework that bridges the Eisenberg-Gale equilibrium with decentralized multi-agent learning to achieve fair and efficient spatial task allocation for heterogeneous agents under partial observability, validated through both simulation and real-world robotic experiments.

Original authors: Yao Liu, Sampad Mohanty, Elizabeth Ondula, Bhaskar Krishnamachari

Published 2026-01-23

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yao Liu, Sampad Mohanty, Elizabeth Ondula, Bhaskar Krishnamachari

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a busy warehouse or a disaster zone where a team of different robots needs to find and fix various problems scattered around. Some robots are strong but slow (like a forklift), some are small and agile (like a mouse), and some are good at delicate work (like a surgeon). The problems they need to fix also vary: some are urgent and heavy, while others are light and less critical.

The big challenge is: How do you tell each robot which job to do so that everything gets done quickly, but no single job is left waiting forever?

If you just tell every robot to grab the "easiest" or "closest" job first (a greedy approach), the strong robots might hog all the easy jobs, leaving the difficult, urgent ones to sit untouched for a long time. This is unfair and inefficient.

This paper, titled DISPATCH, proposes two new ways to solve this "who does what" problem using a concept from economics called the Eisenberg-Gale (EG) equilibrium. Think of this as a "fair market" where jobs have a price tag based on their importance, and robots bid for them based on their skills and distance. The goal is to find a balance where everyone is happy, and the system works well.

Here are the two main solutions the authors developed:

1. The "Smart Student" Approach (EG-MARL)

Imagine you have a class of robots that need to learn how to work together, but they can only see what's right in front of them (they have "partial observability"). They can't see the whole map.

How it works: The authors created a "teacher" (a central computer) that can see the whole map. This teacher solves the perfect "fair market" problem first to figure out the ideal assignment.
The Lesson: The teacher then guides the robots during their training. It doesn't just tell them where to go; it shapes their "rewards" (like giving them candy) to encourage them to act like the teacher's perfect plan.
The Result: Once trained, the robots go out on their own. They don't need the teacher anymore. They use their local sensors and a bit of communication with neighbors to make decisions that are almost as good as the perfect plan, balancing speed and fairness without needing to see the whole world.

2. The "Scout and Assign" Approach (Stochastic Online Assignment)

Imagine a team of explorers entering a dark cave. They don't know where the treasures (tasks) are hidden.

How it works: The robots split up to explore the cave. As soon as they find a few new treasures, they stop and hold a quick "meeting" (using a central connection).
The Meeting: They look at the treasures they just found and the robots that are currently free. They run a quick calculation to decide which free robots should take which new treasures to be the fairest and most efficient.
The Cycle: The assigned robots go to work immediately, while the unassigned robots keep exploring for more treasures. This cycle repeats until everything is done.
The Result: This method is great for real-time situations where tasks appear one by one. It ensures that as soon as a job is found, it gets assigned fairly, rather than waiting for the whole map to be known.

What Did They Find?

The authors tested these ideas in computer simulations (like a video game for robots) and even in a real-world warehouse with different types of physical robots.

Fairness Wins: Their methods were much better at ensuring that every job got attention, not just the easy ones. They used a "fairness score" to prove that their approach treated all tasks more equally than older methods.
Speed is Kept: Even though they were being fair, they didn't sacrifice speed. The robots finished their work almost as fast as if a super-computer had controlled every single move from the start.
The Trade-off: The "Smart Student" (EG-MARL) was the fastest at finishing tasks, while the "Scout and Assign" method was excellent at maintaining fairness in dynamic, changing environments.

The Bottom Line

The paper shows that you don't need a super-computer watching every robot to get a fair and efficient team. By using economic principles (like a fair market) to guide how robots learn or how they make quick decisions, you can create a team that works together smoothly, treats every job with the respect it deserves, and gets the job done quickly—even when the robots can't see the whole picture.

Technical Summary: DISPATCH - Decentralized Informed Spatial Planning and Assignment of Tasks for Cooperative Heterogeneous Agents

Problem Statement

The paper addresses the challenge of spatial task allocation in heterogeneous multi-agent systems, specifically within domains such as multi-robot delivery, search and rescue, and environmental monitoring. The core problem involves coordinating $N$ heterogeneous agents to service $m$ spatially distributed tasks under partial observability.

Key constraints and characteristics include:

Heterogeneity: Agents possess different service capabilities (skill levels), and tasks have varying workloads, importance weights, and urgency. Compatibility is modeled via preference vectors.
Spatial Costs: Agents must navigate complex 2D environments with obstacles, incurring travel costs and time delays.
Fairness vs. Efficiency Trade-off: Greedy or purely efficiency-driven policies (e.g., minimizing total distance) often lead to inequitable service, where some tasks receive rapid, high-quality service while others face long delays or poor matches.
Partial Observability: Agents do not have access to global state information; they only perceive entities within a local sensing radius.

Existing approaches often assume centralized coordination with full global information or rely on reward shaping without a rigorous equilibrium-based fairness reference. This paper seeks to bridge the gap between Eisenberg–Gale (EG) equilibrium theory (which guarantees Pareto efficiency and envy-freeness) and decentralized, partially observable multi-agent learning.

Methodology

The authors propose two complementary algorithms that integrate fairness and efficiency:

1. EG-MARL (Centralized Training, Decentralized Execution)

This framework utilizes a CTDE (Centralized Training with Decentralized Execution) architecture.

Training Phase: A centralized critic has access to the global state and solves a spatially modified Eisenberg–Gale (EG) convex program. This program maximizes the weighted sum of logarithmic utilities, where utility is defined as a function of agent-task preference and a distance-discounted factor ( $uji = (\alpha d_{ij}) \cdot \text{preference}_{ji}$ ). The solution to this program serves as a "teacher" or supervisory signal.
Execution Phase: Agents operate independently using only local observations. They utilize a Graph Neural Network (GNN) to process local agent-entity graphs (representing neighbors, tasks, and obstacles) to learn decentralized policies.
Reward Shaping: The learning process is guided by a composite reward that includes exploration bonuses, workload progress, completion bonuses, and a specific fairness shaping term derived from the EG assignment targets.

2. Stochastic Online Assignment

This is a cooperative explore-and-assign mechanism designed for settings with centralized communication (serving as a strong online baseline).

Mechanism: Agents cooperatively explore the environment using a grid-based sampling strategy. When a threshold $k$ of new tasks is discovered, the algorithm performs a subset-based assignment.
Process: It enumerates subsets of currently free agents, solves the EG optimization problem for each subset against the discovered tasks, and selects the subset that maximizes the equilibrium objective. Assigned agents immediately service their targets while others continue exploring.
Purpose: While computationally expensive due to combinatorial enumeration ( $O(\binom{N}{k})$ ), it provides a benchmark for how close decentralized policies can get to an online, centrally coordinated EG solution.

Key Contributions

Spatial-Aware Eisenberg–Gale Framework: The authors extend the classical EG framework by incorporating spatial travel costs into the utility formulation, effectively bridging equilibrium theory with embodied multi-agent task allocation.
EG-MARL Algorithm: A novel CTDE framework that integrates graph-based policies with spatially aware EG assignments. This allows agents to learn decentralized policies that jointly optimize fairness and travel efficiency under partial observability, guided by the EG equilibrium.
Stochastic Online Assignment: A cooperative mechanism that performs guided exploration and subset-based fair assignment in real-time as tasks are discovered, establishing a centralized baseline for online fairness-efficiency trade-offs.
Empirical Validation: The approach is validated in Multi-Agent Particle Environment (MPE) simulations across varying team sizes (3 to 15 agents) and a Webots-based warehouse proof-of-concept using heterogeneous robots (e.g., Summit-XL, TurtleBot3, Pioneer).

Experimental Results

The evaluation compares EG-MARL and the Stochastic Online method against centralized baselines: Centralized EG, Hungarian Algorithm (utilitarian optimum), and Min-Max Distance (equity-focused).

Regret: EG-MARL achieves low regret (gap between decentralized and centralized EG objectives), particularly for smaller teams. As team size increases, regret grows but remains competitive.
Fairness: Both EG-MARL and the Online method consistently outperform Hungarian and Min-Max baselines in fairness metrics (Coefficient of Variation and Jain's Fairness Index). The EG-based methods achieve more balanced task outcomes, clustering in the "upper-left" region of the fairness-efficiency trade-off curve (high fairness, low completion time).
Efficiency: EG-MARL achieves the fastest completion times in most configurations (N=7, 10), often outperforming the centralized EG solution in speed, though sometimes at the cost of slightly higher total travel distance.
Ablation Studies: Removing the EG fairness-shaping reward or the exploration reward leads to degraded fairness and increased completion times, confirming the necessity of the equilibrium-guided reward structure.
Webots Validation: In a realistic warehouse scenario with heterogeneous robots, the centralized EG assignment demonstrated the strongest overall balance, achieving the highest fairness scores while maintaining competitive completion times compared to Hungarian and Min-Max methods.

Significance and Claims

The paper claims that spatially aware EG formulations can effectively guide decentralized coordination in agents with heterogeneous capabilities.

Theoretical Bridge: The work establishes a connection between the EG equilibrium convex program and decentralized, partially observable multi-agent learning, demonstrating that equilibrium concepts can serve as effective supervisory signals for learning.
Practical Balance: The results suggest that decentralized agents can approximate Pareto-efficient and fairness-aware outcomes without relying on global state information.
Limitations: The authors modestly note that the Stochastic Online Assignment is computationally intensive for large teams due to combinatorial enumeration and is intended primarily as a baseline rather than a scalable deployment solution. They also acknowledge that the EG-MARL framework is an empirically guided learning approach rather than a theoretical approximation algorithm for the underlying Dec-POMDP.

The study concludes that while pure efficiency often creates inequities, integrating equilibrium-based fairness into decentralized learning allows multi-agent systems to achieve a robust balance between service quality and operational efficiency in dynamic, spatial environments.