基于三维时空地图和运动分解的多机器人路径规划算法

作者：屈立成; 吕娇; 赵明^*; 王海飞; 屈艺华

来源：计算机应用, 2020, 40(12): 3499-3507.

• 多机器人路径规划
• 分布式
• 三维时空
• 深度优先搜索
• *算法" name="keyword">A*算法
• 蚁群算法

针对当前多机器人路径规划策略中存在的路径耦合性高、总路径长、避碰等待时间长等缺点,以及由此导致的系统鲁棒性低、机器人利用率低等问题,提出了基于三维时空地图和运动分解的多机器人路径规划算法。首先,根据已有路径集和当前机器人的位置生成时间维度上的动态临时障碍物,将其与静态障碍物一并拓展为三维搜索空间;其次,在三维搜索空间内,将路径运动总时间拆分为运动时间、转向时间和原地停留时间这三个参数,并使用条件深度优先搜索策略计算出从起始节点到达目标节点的所有符合参数要求的路径集合;最后,遍历路径集合中的所有路径,对于每条路径,计算其实际总耗时。如果某一路径的实际总耗时和理论总耗时之间的差距小于规定的最大误差,则可认为该路径为最短路径,否则,继续遍历剩下的其余路径;而如果路径集合中所有路径的实际总耗时和理论总耗时之差全都大于最大误差,则需要动态调整参数,然后继续执行算法的初始步骤。实验结果表明,所提算法规划的路径具有总长短、运行时间少、系统无碰撞、鲁棒性高等优点,解决了多机器人系统完成持续随机任务的问题。