7 August 2024 in IEEE Robotics and Automation Letters
This paper presents an efficient algorithm, naming Centralized Searching and Decentralized Optimization (CSDO), to find feasible solution for large-scale Multi-Vehicle Trajectory Planning (MVTP) problem. Due to the intractable growth of non-convex constraints with the number of agents, exploring various homotopy classes that imply different convex domains, is crucial for finding a feasible solution. However, existing methods struggle to explore various homotopy classes efficiently due to combining it with time-consuming, precise trajectory solution finding. CSDO, addresses this limitation by separating them into different levels and integrating an efficient Multi- Agent Path Finding (MAPF) algorithm to search homotopy classes. It first searches for a coarse initial guess using a large search step, identifying a specific homotopy class. Subsequent decentralized Sequential Quadratic Programming (SQP) refinement processes this guess, resolving minor collisions efficiently. Experimental results demonstrate that CSDO outperforms existing MVTP algorithms in large-scale, high-density scenarios, achieving up to a 95% success rate in 50 m × 50 m random scenarios around one second. Source codes are released in https://github.com/YangSVM/CSDOTrajectoryPlanning .
2 September 2025 in IEEE Robotics and Automation Letters
The Collaborative Task Sequencing and Multi-Agent Path Finding (CTS-MAPF) problem involves planning collision-free paths for multiple agents while determining the sequence of intermediate tasks. This problem is particularly challenging due to its combinatorial complexity, as it combines both task sequencing and pathfinding. This letter introduces CTS-PIBT, a novel and efficient algorithm designed to address the CTS-MAPF problem. CTS-PIBT adopts a hierarchical framework with three key components: task sequencing, solution finding following the sequence, and a low-level search using an extended version of PIBT. This framework effectively leverages the advantages of the configuration-based approach, enabling the rapid generation of feasible solutions within a short period. To further enhance performance, we incorporate an anytime refinement mechanism and a quick task sequencing technique (called greedy insertion with 2-opt) to improve solution quality and solving efficiency. Extensive simulations demonstrate that CTS-PIBT significantly outperforms existing methods in success rate and runtime, particularly in large-scale and complex scenarios. Furthermore, physical robot experiments validate its practical applicability in real-world environments.
11 February 2026 in IEEE Internet of Things Journal
This article addresses a generalization problem of multiagent pathfinding (MAPF), called collaborative task sequencing—MAPF (CTS-MAPF), where agents must plan collision-free paths and visit a series of intermediate task locations in an optimized order before reaching their final destinations. To address this problem, we propose a new approach, collaborative task sequencing—conflict-based search (CTS-CBS), which conducts a two-level search. At the high level, it generates a search forest, where each tree corresponds to a joint task sequence derived from the joint-traveling salesman problem (jTSP) solution. At the low level, CTS-CBS performs constrained single-agent path planning to generate paths for each agent while adhering to high-level constraints. Furthermore, we integrate explicit estimation search (EES) into CTS-CBS to enhance the search efficiency. We also provide theoretical guarantees of its solution completeness and optimality (or suboptimality with a bounded parameter). To evaluate the performance of CTS-CBS, we utilize three datasets with different map sizes, map difficulty, and agent/task numbers, and conduct comprehensive experiments. The results show that our algorithms demonstrate significant improvements in success rate and runtime, while maintaining competitive solution quality. Finally, practical robot simulation and tests demonstrate the algorithm’s applicability in real-world scenarios.
7 April 2026 in Unmanned Systems