CSDO: Enhancing Efficiency and Success in Large-Scale Multi-Vehicle Trajectory Planning
<|reference_start|>CSDO: Enhancing Efficiency and Success in Large-Scale Multi-Vehicle Trajectory Planning: 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 Quadratic Programming (QP) 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 95% success rate in 50m $\times$ 50m random scenarios around one second. Source codes are released in https://github.com/YangSVM/CSDOTrajectoryPlanning.<|reference_end|>
@article{yang2024csdo:,
    title={CSDO: Enhancing Efficiency and Success in Large-Scale Multi-Vehicle
  Trajectory Planning},
    author={Yibin Yang, Shaobing Xu, Xintao Yan, Junkai Jiang, Jianqiang Wang,
  Heye Huang},
    journal={arXiv preprint arXiv:2405.20858},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.20858},
    primaryClass={cs.RO}
}