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