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

针对多智能体路径搜索算法在非指定式多车协同路径规划问题中路径冗长,计算效率低等缺陷,提出协同目标点分配路径规划算法 Nutcracker-CBS。 首先构建紧耦合目标点分配 MAPF 框架,实现目标点分配和路径构建的联合寻优;针对目标点分配模块,提出改进的星鸦优化算法,增量式求解分配问题,缩短模块用时;针对路径构建模块,提出改进的 MAPF 算法,通过回退式约束构建机制,引入避碰路径估计的绕道机制和数据共享底层路径规划机制,提升效率和路径质量。 数据集实验中,Nutcracker-CBS 时耗相比 SOTA 算法减少 90. 37% ;目标点分配模块求解耗时减少 86. 76% ;MAPF 模块 6 s 内构建 100 辆无人车路径,平均路径长度缩短 6. 058% 。 实际实验中路径总和与系统运行时长分别减少 55. 26% 和 61. 29% ,提升了多机器人系统的效率,降低了路径长度。

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 allocationand path finding jointly. In goal allocation module, an improved nutcracker optimization algorithm is proposed to solve goal allocationincrementally, which can shorten the duration of the module. In path finding module, an improved MAPF algorithm is proposed withtraceback constraint construction mechanism, bypass mechanism for the length estimation of collision-free path, and low-level pathplanning mechanism for data sharing, to enhance efficiency and quality of path finding. In benchmark experiments, time cost ofNutcracker-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 timeconsumption of the system is reduced by 61. 29% , which boost the efficiency of multi-robot system and decrease path length.