  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.
