Goal allocation and cooperative path finding for multiple UGVs
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.
NETL
NSTL
万方数据
