The Collaborative Task Sequencing and Multi-Agent Path Finding (CTS-MAPF) problem requires agents to accomplish sequences of tasks while avoiding collisions, posing significant challenges due to its combinatorial complexity. This work introduces CTS-PLL, a hierarchical framework that extends the configuration-based CTS-MAPF planning paradigm with two key enhancements: a lock agents detection and release mechanism leveraging a complete planning method for local re-planning, and an anytime refinement procedure based on Large Neighborhood Search (LNS). These additions ensure robustness in dense environments and enable continuous improvement of solution quality. Extensive evaluations across sparse and dense benchmarks demonstrate that CTS-PLL achieves higher success rates and solution quality compared with existing methods, while maintaining competitive runtime efficiency. Real-world robot experiments further demonstrate the feasibility of the approach in practice.
Figures & tables
Fig. 1: Examples of deadlock and livelock cases in CTS-PIBT. (a) Deadlock: agent a1 attempts to execute task vt1 , but agent a2 has no alternative position to yield, blocking the move. (b) Livelock: agents a1 and a2 repeatedly oscillate around each other’s goals, preventing convergence.
Fig. 2: The main process of CTS-PLL, which has four key components: joint task sequencing, path finding using Extended-PIBT, lock detection and release module and solution quality enhancement via LNS.
Scenario type
Maps
Agents N
Tasks M
Instances
Sparse
four maps
5,10,20
10,20,30,40,50
50
Dense
maze
50
60,90,120,150,180
50
TABLE I: Experimental settings for sparse and dense scenarios.
Fig. 3: Benchmark maps adopted for evaluation, including four representative scenarios: empty, random, room, and maze. These maps are used to construct sparse and dense experimental settings.
Fig. 4: Performance of CTS-PLL and baseline methods under different difficulty levels (map types, agent numbers, and task numbers). For clarity, we omit the x-axis labels in each subfigure since they share the same contents. The x-axis represents the pairs of (N,M) (agent number, task number), ranging from (5,10) to (5,50), (10,10) to (10,50), and (20,10) to (20,50). Here, CTS-PLL-v2 denotes the variant without anytime optimization, while CTS-PLL-v3 refers to the full method with anytime mechanism and LNS refinement.
Method
Success Rate ↑
# Tasks
60
90
120
150
180
CTS-PIBT
76%
68%
66%
50%
38%
CTS-PLL-v1
98%
92%
96%
92%
72%
Improvement Rate
28.95%
35.29%
45.45%
84.00%
89.47%
TABLE II: Success rate results of denser configurations on maze map.
Method
Solution Quality (Flowtime) ↓
# Tasks
60
90
120
150
180
CTS-PIBT-anytime
196.35
253.21
316.93
389.62
457.04
CTS-PLL-v3
162.00
221.89
301.85
357.99
451.34
Improvement Rate
17.49%
12.37%
4.76%
8.12%
1.25%
TABLE III: Solution quality results of denser configurations on maze map.
Fig. 5: Physical robot experiment using toio robots to validate CTS-PLL. Robots are shown as purple, cyan, and yellow squares. The corresponding colored stars indicate their goal locations, while red triangles represent task points. Black numbers above each task denote the robots assigned to it, and red numbers below show the robots that have already completed it. The top subfigure illustrates the real-world robot experiment, while the bottom subfigure shows the corresponding simulation process. The figure depicts the trajectories of the robots during the experiment.
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.
The concurrent target assignment and pathfinding (TAPF) problem extends multi-agent pathfinding (MAPF) by asking planners to allocate distinct targets and collision-free paths to agents. Prior work on TAPF has relied exclusively on Conflict-Based Search (CBS), which tightly couples target assignment and pathfinding, resulting in compute-intensive, non-scalable solutions. In contrast, we propose an iterative refinement framework that decouples target assignment from pathfinding. Our framework builds on modern, fast, suboptimal MAPF solvers, such as LaCAM. Specifically, within a given time budget, it repeatedly solves MAPF for the current target assignment, identifies bottleneck agents via MAPF feedback, and refines the assignment. Empirical results show that feedback-driven reassignment loop is effective, enabling our framework to scale well beyond the reach of the state-of-the-art CBS-based solver while maintaining decent solution quality. This represents a solid step toward practical, large scale TAPF suitable for real-world setups.
Yu Kumagai, Keisuke Okumura
1Hitotsubashi University, Japan · 2National Institute of Advanced Industrial Science and Technology (AIST), Japan
Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective start locations to their respective goal locations while minimizing path costs. Most existing MAPF algorithms rely on a common assumption of synchronized actions, where the actions of all agents start at the same time and always take a time unit, which may limit the use of MAPF planners in practice. To get rid of this assumption, Continuous-time Conflict-Based Search (CCBS) is a popular approach that can find optimal solutions for MAPF with asynchronous actions (MAPF-AA). However, CCBS has recently been identified to be incomplete due to an uncountably infinite state space created by continuous wait durations. This paper proposes a new method, Conflict-Based Search with Asynchronous Actions (CBS-AA), which bypasses this theoretical issue and can solve MAPF-AA with completeness and solution optimality guarantees. Based on CBS-AA, we also develop conflict resolution techniques to improve the scalability of CBS-AA further. Our test results show that our method can reduce the number of branches by up to 90%.