Standard Multi-Agent Path Finding asks multiple agents to move from specified starts to specified goals without collisions in a shared environment. The paper considers a generalization called CTS-MAPF, where agents must also visit intermediate task locations in a prescribed order before reaching their final destinations. The task order and assignment are collaborative because the sequence selected for one agent can affect the planning results of the others. The optimization objective is to minimize an overall movement cost, such as total time or distance, including waiting actions, while satisfying collision, assignment, ordering, and destination requirements.
The main contribution is Collaborative Task Sequencing Conflict-Based Search, or CTS-CBS, a method designed for CTS-MAPF. It extends the conflict-based-search perspective from fixed goals to joint task sequencing and path planning. At the high level, it builds a search forest whose trees correspond to joint task sequences derived from a jTSP solution; at the low level, it computes constrained paths for individual agents. The paper states theoretical guarantees of completeness and optimality in the exact setting, and bounded suboptimality when a bounded parameter is used. It also introduces two evaluation datasets, CTS-MAPF and MG-MAPF, and evaluates the method in simulation and on physical robots.
CTS-CBS uses a two-level search architecture. The high level maintains multiple search trees, each associated with a candidate joint task sequence, rather than committing to one sequence in advance; new root nodes can be generated when necessary. The low level plans a path for each agent subject to the selected task sequence and the current collision constraints, then returns a joint-path cost to guide the high-level search. When a conflict is detected, the search branches by imposing a constraint on one side or the other of the conflict and replans under the new constraints. This makes task-order decisions and collision resolution interact within the same search process. The implementation uses SIPP for low-level planning, although the paper notes that A*-like methods could also be used.
The experiments adapt Moving AI MAPF benchmarks because, according to the supplied excerpt, no public dataset specifically designed for CTS-MAPF was available. Each map provides 50 scenarios with about 100 pieces of agent data; the first 20 are used as agent data and the remaining start positions are converted into task data. The implementation is in C++, with a three-minute limit per instance, on a Linux computer with an Intel Core i7-12700KF CPU, an NVIDIA GeForce RTX 3080 GPU, and 32 GB of RAM. The evaluation compares CTS-CBS adaptations with several baselines; the excerpt explicitly names HCBS and MGCBS but does not identify every baseline. It measures success rate, runtime, and solution quality, studies the effect of the suboptimality parameter, and includes physical-robot demonstrations.
For MG-MAPF, the paper reports that CTS-CBS adaptations substantially outperform the baselines: success rate is up to 20 times larger and runtime up to 100 times faster, with less than a 10 percent sacrifice in solution quality. These are maximum improvements reported in the supplied excerpt, not complete per-map or per-setting results; the excerpt does not provide the underlying values, variability, statistical tests, or the full list of baseline names. The adjustable suboptimality bound provides an operational trade-off between solution quality and computational efficiency, which may be useful when applications impose different latency requirements. The stated experiments and robot tests support practical applicability, but the method is evaluated primarily under static, discrete-motion assumptions. The paper identifies dynamic and lifelong scenarios, agent kinematic constraints, and further efficiency strategies as future work, while the excerpt does not establish how computation scales in every larger or more difficult regime.
MAPF is a foundational problem in which multiple agents must obtain collision-free paths in a shared workspace, with applications in robotics, warehouses, and autonomous vehicles. Simple methods such as prioritized planning, PUSH AND SWAP, and Hierarchical Cooperative A* are described as easy to deploy but generally non-complete and non-optimal. Conflict-Based Search is presented as a complete and optimal MAPF framework based on high-level conflict constraints and low-level single-agent planning. CTS-MAPF adds collaborative intermediate-task sequencing to that setting.
A CTS-MAPF instance includes agents moving on an undirected workspace graph with vertices, edges, positive edge costs, static obstacles, starts, destinations, and task positions. Each agent may wait or move one step in one of the four cardinal directions, must visit its assigned tasks in the required order, and must then reach its destination. The cost of waiting must be included in the objective. A feasible solution must avoid conflicts and satisfy task assignment, ordering, movement, and arrival constraints while minimizing the total cost.
The high level organizes a search forest around joint task sequences obtained from a jTSP solver. The low level replans single-agent paths under both sequence requirements and collision constraints, using SIPP in the reported implementation. A necessity check for new root nodes and a tunable suboptimality parameter are key components when bounded suboptimal solutions are preferred. The parameter allows users to exchange solution quality for efficiency, while the paper claims exact behavior in the non-bounded setting.
The authors create CTS-MAPF and MG-MAPF datasets, although the supplied excerpt does not give the complete construction procedure or all dataset statistics. Their adaptation of MAPF benchmarks contains 50 scenarios per map; the first 20 agent records are used as agents and the remaining starts as task locations. Each instance has a three-minute cutoff, and the study compares against existing methods, examines the suboptimality-parameter effect, and deploys the algorithm on physical robots. The excerpt names HCBS and MGCBS among the baselines but does not list every comparator or every experimental condition.
The reported MG-MAPF adaptations achieve up to a 20-fold improvement in success rate and up to a 100-fold improvement in runtime relative to the baselines. The reported reduction in solution quality is below 10 percent. Physical robots successfully navigate along their designated paths, which the paper uses as evidence of real-world applicability. The supplied evidence does not establish the exact values for individual maps, agent counts, task counts, or parameter settings.
CTS-CBS integrates collaborative task sequencing with collision-free multi-agent path planning instead of treating sequencing as an independent preliminary step. The paper claims completeness and optimality in its exact setting and bounded suboptimality when a bound parameter is supplied. Its simulation results and physical-robot demonstrations indicate practical benefits, especially for MG-MAPF, in success rate and runtime.
The excerpt does not provide the algorithm's detailed complexity analysis, complete baseline list, map names, per-condition measurements, variance, or statistical significance. The described model is centered on static environments and discrete actions, so continuous kinematics, dynamic obstacles, and lifelong streams of tasks remain outside the demonstrated scope. The reported gains concern MG-MAPF adaptations and should not be assumed to transfer unchanged to every MAPF formulation. The excerpt also does not establish the failure modes or scalability limits of the search forest as the number of agents and tasks grows.
The work is important because it treats task assignment, task order, and path conflicts as coupled decisions. Its search structure offers a principled way to reuse conflict-based reasoning when agents have multiple intermediate obligations rather than only one goal. The adjustable quality-efficiency trade-off may be useful in warehouse and multi-robot systems where exact optimality and response time have different operational priorities.
This paper is suitable for researchers studying MAPF, multi-robot coordination, integrated task assignment and path planning, or extensions of Conflict-Based Search. It is also relevant to readers interested in joint traveling-salesperson formulations and physical-robot validation. Readers whose primary focus is dynamic environments, continuous control, or rigorous benchmark statistics should consult the full paper because those details are not established by the supplied excerpt.