计算机辅助设计与图形学学报

作者：翟民, 章政, 黄卫华, 付亮亮, 罗文龙

关键词：多智能体取送货问题, 非固定送货位置, 任务分配, 多智能体路径规划

针对非固定送货位置的多智能体取送货(multi-agent pickup and delivery, MAPD)问题, 提出一种基于能源成本的启发式冲突搜索最优任务分配(energy-cost-based heuristic conflict-based search with optimal task assignment,ECB-HCBS-TA)算法, 旨在找到最优的任务分配结果及相应最短无冲突取送货路径, 最小化智能体完成所有任务的总成本. 首先通过耦合求解任务分配与多智能体路径规划, 保证非固定送货位置的 MAPD 问题解的最优性; 然后针对 CBS-TA 算法生成的搜索森林中存在冗余节点导致计算复杂度较高的问题, 设计基于能源成本的启发式代价函数指导约束树的搜索与生长, 以减少搜索空间; 最后针对取送货路径规划问题设计启发式双向 A*算法, 以加快路径搜索速度. 随机生成栅格地图和任务信息, 并将 ECB-HCBS-TA 算法与 CBS-TA 算法进行对比. 仿真实验结果表明, 在8×8 栅格地图执行 ECB-HCBS-TA 算法时, 4 个智能体完成任务的最大完工时间、平均时间成本、节点数量和算法的运行时间分别减少 9.3%, 5.4%, 23.2%和 50%, 证明了该算法的有效性; 当栅格地图进一步扩大时, ECB-HCBS-TA 算法仍能在较短时间内完成规划, 证明了该算法的可扩展性.

来源：2025年第9期

《计算机辅助设计与图形学学报》期刊编辑部

查看计算机辅助设计与图形学学报杂志2025年第9期