CSDO: Enhancing Efficiency and Success in Large-Scale Multi-Vehicle Trajectory Planning

Yang, Yibin; Xu, Shaobing; Yan, Xintao; Jiang, Junkai; Wang, Jianqiang; Huang, Heye · 2024 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2405.20858

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the challenge of Large-Scale Multi-Vehicle Trajectory Planning (MVTP), specifically the difficulty of efficiently finding feasible, collision-free trajectories for numerous agents in dense, unstructured environments. The core problem is the intractable growth of non-convex constraints as the number of agents increases, which complicates the exploration of different "homotopy classes" (distinct topological routes). Existing methods, such as coupled planning, distributed planning, sampling-based approaches, and tube construction, struggle with scalability, computational speed, or limited homotopy exploration in high-density scenarios. The authors aim to develop an algorithm that rapidly identifies feasible solutions with a high success rate by decoupling the search for homotopy classes from precise trajectory optimization. To solve this, the authors propose Centralized Searching and Decentralized Optimization (CSDO), a hierarchical framework. The method consists of two main stages. First, a centralized priority-based search phase utilizes an efficient Multi-Agent Path Finding (MAPF) algorithm, specifically Priority-Based Search (PBS), to explore various homotopy classes. This stage uses a large search step size to generate coarse initial guesses, implicitly encoding different homotopy classes without getting bogged down in precise kinematic details. The PBS algorithm resolves conflicts by establishing priority orders between agents, treating higher-priority agents as dynamic obstacles for lower-priority ones. Second, a decentralized Sequential Quadratic Programming (SQP) refinement phase takes the coarse initial guess and refines it into a kinematically feasible trajectory. This stage decomposes inter-vehicle constraints and solves them locally for each vehicle, resolving minor collisions and ensuring adherence to non-holonomic kinematic constraints (Ackermann-steering model). Experimental results demonstrate that CSDO significantly outperforms existing MVTP algorithms in large-scale, high-density scenarios. In random scenarios within a 50 m × 50 m workspace, CSDO achieved a success rate of up to 95% with computation times around one second. The method effectively handles the trade-off between solution quality and computational efficiency, overcoming the limitations of coupled methods (poor scalability) and distributed methods (low success rates in dense spaces). The separation of homotopy exploration via MAPF and precise optimization via SQP allows the algorithm to quickly navigate the complex solution space. The significance of this work lies in its practical applicability to real-world systems such as warehouse automation and cooperative parking, where rapid, reliable trajectory planning for many vehicles is essential. By leveraging efficient MAPF solvers for homotopy exploration and decentralized optimization for refinement, CSDO provides a scalable solution to a traditionally intractable problem. The authors also release source code, facilitating further research and application in multi-robot systems. This approach highlights the potential of integrating discrete search methods with continuous optimization to address the complexities of large-scale multi-agent motion planning.

Key finding

The proposed CSDO algorithm achieves a 95% success rate in large-scale, high-density multi-vehicle trajectory planning scenarios within approximately one second, outperforming existing methods.

Methodology

simulation_modeling

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed. Discovered via author_sweep_intake on 2026-05-28.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-10; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• traffic density