Targeted Parallelization of Conflict-Based Search for Multi-Robot Path Planning
<|reference_start|>Targeted Parallelization of Conflict-Based Search for Multi-Robot Path Planning: Multi-Robot Path Planning (MRPP) on graphs, equivalently known as Multi-Agent Path Finding (MAPF), is a well-established NP-hard problem with critically important applications. As serial computation in (near)-optimally solving MRPP approaches the computation efficiency limit, parallelization offers a promising route to push the limit further, especially in handling hard or large MRPP instances. In this study, we initiated a \emph{targeted} parallelization effort to boost the performance of conflict-based search for MRPP. Specifically, when instances are relatively small but robots are densely packed with strong interactions, we apply a decentralized parallel algorithm that concurrently explores multiple branches that leads to markedly enhanced solution discovery. On the other hand, when instances are large with sparse robot-robot interactions, we prioritize node expansion and conflict resolution. Our innovative multi-threaded approach to parallelizing bounded-suboptimal conflict search-based algorithms demonstrates significant improvements over baseline serial methods in success rate or runtime. Our contribution further pushes the understanding of MRPP and charts a promising path for elevating solution quality and computational efficiency through parallel algorithmic strategies.<|reference_end|>
@article{guo2024targeted,
    title={Targeted Parallelization of Conflict-Based Search for Multi-Robot Path
  Planning},
    author={Teng Guo, Jingjin Yu},
    journal={arXiv preprint arXiv:2402.11768},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.11768},
    primaryClass={cs.RO}
}