A Multi-robot Path Planning Algorithm for Underground Pipeline Network Environment

Currently, path planning algorithms struggle to effectively address challenges in multi-robot tasks in underground pipeline networks due to the fact that each channel can only accommodate one robot, such as the issues of numerous endpoint blockages and position interlocking. Therefore, a dynamic priority SIPP (safe-interval path planning) algorithm with intermediate point is proposed, named DPiSIPP. Firstly, a deterministic re-scheduling method is proposed to prioritize the planning of robots that encounter endpoint blockages, thereby facilitating their removal. Then, an intermediate point is incorporated into the segmented planning process for robots experiencing position interlocking. This approach aims to either directly resolve the interlocking relationship or transform the position interlocking issue into an endpoint blocking problem for resolution. The experimental results demonstrate that the success rate of the proposed DPiSIPP algorithm can outperform Anytime SIPP, WSIPP_d (weighted SIPP with duplicate states), and enhanced CBS (conflict-based search) algorithms by up to 30%, 30%, and 10%, respectively, in the context of underground pipeline networks, indicating that the proposed algorithm has a clear advantage over the aforementioned algorithms in terms of solving performance.