面向多无人车的目标点分配和协同路径规划算法  

Goal allocation and cooperative path finding for multiple UGVs

作　　者：谷依田 张涛[1,2] 张亮[1,2] 杨泰泓 Gu Yitian;Zhang Tao;Zhang Liang;Yang Taihong(School of Instrument Science&Engineering,Southeast University,Nanjing 210096,China;Key Laboratory of Micro-inertial Instrument and Advanced Navigation Technology of Ministry of Education,Nanjing 210096,China)

机构地区：[1]东南大学仪器科学与工程学院,南京210096 [2]微惯性仪表与先进导航技术教育部重点实验室,南京210096

出　　处：《仪器仪表学报》2024年第3期263-274,共12页Chinese Journal of Scientific Instrument

摘　　要：针对多智能体路径搜索算法在非指定式多车协同路径规划问题中路径冗长,计算效率低等缺陷,提出协同目标点分配路径规划算法Nutcracker-CBS。首先构建紧耦合目标点分配MAPF框架,实现目标点分配和路径构建的联合寻优;针对目标点分配模块,提出改进的星鸦优化算法,增量式求解分配问题,缩短模块用时;针对路径构建模块,提出改进的MAPF算法,通过回退式约束构建机制,引入避碰路径估计的绕道机制和数据共享底层路径规划机制,提升效率和路径质量。数据集实验中,Nutcracker-CBS时耗相比SOTA算法减少90.37%;目标点分配模块求解耗时减少86.76%;MAPF模块6 s内构建100辆无人车路径,平均路径长度缩短6.058%。实际实验中路径总和与系统运行时长分别减少55.26%和61.29%,提升了多机器人系统的效率,降低了路径长度。Aiming at the shortcomings of MAPF in the scenarios of anonymous cooperative path finding for multiple carlike robots,including long path and poor efficiency,a cooperative goal allocation and path finding algorithm for multiple unmanned ground vehicles,Nutcracker-CBS,is proposed.Firstly,a tightly coupled MAPF framework with goal allocation is constructed to optimize goal allocation and path finding jointly.In goal allocation module,an improved nutcracker optimization algorithm is proposed to solve goal allocation incrementally,which can shorten the duration of the module.In path finding module,an improved MAPF algorithm is proposed with traceback constraint construction mechanism,bypass mechanism for the length estimation of collision-free path,and low-level path planning mechanism for data sharing,to enhance efficiency and quality of path finding.In benchmark experiments,time cost of Nutcracker-CBS is reduced by 90.37%compared to SOTA algorithm.Time consumption of goal allocation module is reduced by 86.76%compared to the original algorithm.MAPF module completes the path construction of 100 unmanned ground vehicles within 6 seconds,with the reduction of average path length by 6.058%.Filed test shows that the total path length is reduced by 55.26%and the total time consumption of the system is reduced by 61.29%,which boost the efficiency of multi-robot system and decrease path length.

关 键 词：协同路径规划 多智能体路径搜索 基于冲突的搜索 目标点分配 

分 类 号：TP242.6[自动化与计算机技术—检测技术与自动化装置] TH39[自动化与计算机技术—控制科学与工程]