Multi-Agent Cooperative Transportation: Optimal and Efficient Task Allocation and Path Finding
This work addresses a critical gap in multi-robot logistics by enabling true cooperation for tasks requiring multiple agents, providing a foundational framework and effective algorithms for a new class of cooperative multi-agent problems.
The paper formalizes the Cooperative Transportation Task Allocation and Path Finding (CT-TAPF) problem for multi-robot systems transporting large items, and proposes both an optimal solver (CT-TCBS) with a novel Incremental Expansion strategy and sub-optimal solvers using a global task-centric perspective. Empirical results show the incremental expansion strategy significantly prunes the search space, and the sub-optimal solvers establish a more efficient solution quality-runtime frontier.
Multi-robot systems are integral to modern logistics, but their capabilities are often limited to tasks executable by individual agents. This paper addresses a critical gap in existing frameworks like Multi-Agent Path Finding (MAPF) and Task Allocation and Path Finding (TAPF), which lack true cooperation for transporting large items that require multiple agents. To this end, we formalise the Cooperative Transportation Task Allocation and Path Finding (CT-TAPF) problem, which integrates team formation, task assignment, and collision-free pathfinding. We present an optimal solver, Cooperative Transportation Task Conflict-Based Search (CT-TCBS), which features a novel Incremental Expansion strategy to tackle the combinatorial explosion inherent in team formation. Recognising the computational cost of optimality, we also develop a family of sub-optimal solvers that employ a global, task-centric perspective, selecting the next task to assign based on a global difficulty metric (Best Task or Worst Task). Our comprehensive empirical evaluation demonstrates three key findings: (1) the incremental expansion strategy significantly outperforms the naive combinatorial approach by successfully pruning the dominant task-allocation search space; (2) we identify a task-conflict expansion dilemma, where sophisticated conflict resolvers effective for large-agent pathfinding subproblems can be detrimental in the integrated CT-TAPF setting; and (3) our proposed sub-optimal solvers establish a new, more efficient frontier on the solution quality-runtime spectrum compared to "nn-" agent-centric baselines. This work provides a foundational framework and a set of effective algorithms for a new, practical class of cooperative multi-agent problems.