一种面向地下管网环境的多机器人路径规划算法

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

多台机器人在地下管网执行任务时由于各通道只能允许一台机器人通过,可能因此出现大量的终点封堵和位置互锁问题,目前的路径规划算法无法有效解决此类问题。对此,本文提出一个具有中间点的动态优先级SIPP(安全间隔路径规划)算法,命名为DPiSIPP。首先引入确定性重新调度方法,使遭遇终点封堵问题的机器人能得到优先规划从而解除封堵。然后,对出现位置互锁问题的机器人添加一个中间点进行分段规划,以此直接解除互锁关系或将位置互锁问题转化为终点封堵问题来解决。实验结果表明,在地下管网场景下,DPiSIPP算法的求解成功率相较于Anytime SIPP算法、WSIPPd(具有重复状态的加权SIPP)算法和增强型CBS(基于冲突的搜索)算法最高分别可提升30%、30%和10%左右,这说明本文算法在求解能力上明显优于上述算法。

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,WSIPPd(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.