MT-SIPP: An Efficient Collision-Free Multi-chain Robot Path Planning Algorithm

Compared to traditional multi-robot path planning problems, multi-chain robot path planning (MCRPP) is more challenging because it must account for collisions between robot units and between the bodies of a chain and the leading unit during towing. To address MCRPP more efficiently, we propose a novel algorithm called Multi-Train Safe Interval Path Planning (MT-SIPP). Based on safe interval path planning principles, we categorize conflicts in the multi-train planning process into three types: travel conflicts, waiting conflicts, and station conflicts. To handle travel conflicts, we use an improved k-robust method to ensure trains avoid collisions with other trains during movement. To resolve waiting conflicts, we apply a time correction method to ensure the safety of positions occupied by trains during waiting periods. To address station conflicts, we introduce node constraints to prevent other trains from occupying the station positions of trains that have reached their target stations and are stopped. Experimental results on three benchmark maps show that the MT-SIPP algorithm achieves about a 30% improvement in solution success rate and nearly a 50% increase in the maximum number of solvable instances compared to existing methods. These results confirm the effectiveness of MT-SIPP in addressing the challenges of MCRPP.