Multi-Agent Cooperative Transportation: Optimal and Efficient Task Allocation and Path Finding

Technical Summary: Multi-Agent Cooperative Transportation: Optimal and Efficient Task Allocation and Path Finding

Problem Definition: CT-TAPF
This paper addresses a critical gap in existing Multi-Agent Path Finding (MAPF) and Task Allocation and Path Finding (TAPF) frameworks: the inability to handle cooperative transportation tasks requiring multiple agents to move a single large object. The authors formalize the Cooperative Transportation Task Allocation and Path Finding (CT-TAPF) problem. In this setting, a set of $n$ agents must be assigned to a set of $m$ cooperative tasks. Each task $\tau_i$ requires a specific team size $k_i$ and involves two phases:

1. Assembly Phase: Agents travel independently to designated "slots" (start configuration vertices) to form a team.
2. Convoy Phase: Once all assigned agents arrive and synchronize, they move as a single rigid entity (a "Convoy") to the goal configuration.

The problem is NP-hard, generalizing TAPF. A valid solution must minimize the Sum of Costs (SoC) while ensuring collision-free paths. Crucially, the paper introduces a geometric conflict definition where collisions occur if the footprints of agents or convoys overlap, even if their reference positions are distinct.

Methodology
The authors propose a two-level search architecture to solve CT-TAPF, introducing both an optimal solver and a family of sub-optimal variants.

1. Optimal Solver: CT-TCBS
   The Cooperative Transportation Task Conflict-Based Search (CT-TCBS) is a two-level algorithm based on the Conflict-Based Search (CBS) framework:

   • High-Level Search: Performs an A* search on a constraint tree. Each node represents a partial solution defined by task assignments and spatio-temporal constraints. The algorithm prioritizes resolving path conflicts before assigning new tasks.
   • Low-Level Planner: Uses a Unified A* to compute optimal paths for individual agents and multi-agent convoys. It handles the synchronization of agents arriving at assembly slots and plans the joint movement of the convoy.
   • Incremental Expansion Strategy: A core contribution is the replacement of "Combinatorial Expansion" (which generates all possible team permutations at once) with Incremental Expansion. Instead of assigning a full team immediately, the algorithm assigns agents to task slots one by one. This creates intermediate, partially assigned nodes, drastically reducing the branching factor and managing the combinatorial explosion inherent in team formation.
   • Heuristic Function: The heuristic $H$ is the sum of two admissible components: $H_1$ (committed transport cost for partially assigned agents) and $H_2$ (estimated assignment cost for unassigned slots). The authors explicitly exclude a synchronisation wait-time component ($H_3$) because calculating an admissible lower bound for it is computationally intractable (equivalent to the Generalised Assignment Problem).

2. Sub-Optimal Solvers: Task-Centric Selectors
   To address scalability, the authors develop sub-optimal variants that introduce a global, task-centric perspective. Unlike agent-centric "nearest neighbor" approaches (which can lead to inefficient team formation), these solvers select the next task to assign based on a global difficulty metric:

   • Best Task (BT): Selects the task with the lowest estimated completion cost (greedy approach).
   • Worst Task (WT): Selects the task with the highest estimated completion cost (fail-fast approach), aiming to form complex teams early to avoid deadlocks.
     These solvers use the Hungarian algorithm to estimate task difficulty based on agent availability and travel times.

Key Findings and Results
Through comprehensive empirical evaluation on grid maps with varying densities and task distributions, the paper reports three primary findings:

1. Superiority of Incremental Expansion: The Incremental Expansion strategy significantly outperforms the naive Combinatorial approach. Statistical analysis confirms that the combinatorial burden of task allocation is the dominant computational bottleneck, not pathfinding conflicts. By pruning the task-allocation search space, the Incremental strategy achieves significantly higher success rates.
2. The Task-Conflict Expansion Dilemma: The paper identifies a counter-intuitive phenomenon where sophisticated conflict resolution strategies (specifically MAX-d, which is effective for Large-Agent MAPF) perform worse in the integrated CT-TAPF setting. The authors attribute this to the "Task-Conflict Dilemma": MAX-d's strategy of increasing node costs to prune conflict trees forces the high-level search to explore more task-allocation branches prematurely, leading to larger search spaces and lower success rates within time limits.
3. New Efficiency Frontier: The proposed sub-optimal solvers (particularly the Worst-Task variant) establish a new trade-off frontier between solution quality and runtime. While the Optimal CT-TCBS provides the best solutions, it is computationally expensive. The sub-optimal solvers outperform agent-centric baselines (like -nn1/-nn2) by finding higher-quality solutions faster, while being more robust than simple greedy heuristics. Specifically, the WT selector generally produces solutions closer to optimal than BT, as it prioritizes forming complex teams early, preventing agents from being scattered.

Significance and Claims
The paper claims to provide a foundational framework for a new class of cooperative multi-agent problems. Its significance lies in:

• Formalizing CT-TAPF: Moving beyond individualistic task execution to model sustained, physically coupled cooperative actions.
• Algorithmic Innovation: Introducing the Incremental Expansion strategy to manage the specific combinatorial explosion of team formation, which standard TAPF solvers cannot handle efficiently.
• Practical Scalability: Offering a suite of algorithms (from optimal to sub-optimal) that allow practitioners to navigate the trade-off between solution optimality and computational feasibility in real-world logistics scenarios involving large or irregular goods.

The authors conclude that while their current framework is discrete, future work will extend these concepts to continuous domains and heterogeneous agents, but the current contribution establishes the necessary theoretical and algorithmic groundwork for cooperative transportation.