非固定送货位置的多智能体取送货问题研究
Research on Multi-Agent Pickup and Delivery Problem of Non-Fixed Delivery Locations
-
摘要: 针对非固定送货位置的多智能体取送货(Multi-Agent Pickup and Delivery, MAPD)问题, 提出了一种基于能源成本的启发式CBS-TA(Energy-Cost-Based Heuristic Conflict-Based Search with Optimal Task Assignmen, ECB-HCBS-TA)算法, 旨在找到最优的任务分配结果及相应最短无冲突取送货路径, 从而最小化智能体完成所有任务的总成本. 首先, 通过耦合求解任务分配与多智能体路径规划, 以保证非固定送货位置的MAPD问题解的最优性; 其次, 针对CBS-TA算法生成的搜索森林中存在冗余节点导致计算复杂度较高的问题, 设计了基于能源成本的启发式代价函数指导约束树的搜索与生长, 以减少搜索空间; 然后, 针对取送货路径规划问题设计了启发式双向A*算法以加快路径搜索速度; 最后, 仿真实验结果表明本文所提出算法解决非固定送货位置的MAPD问题时能有效减少成本并降低算法计算量, 证明了该算法的有效性和可扩展性.Abstract: For the Multi-Agent Pickup and Delivery (MAPD) problem with non-fixed delivery locations, an Energy-Cost-Based Heuristic Conflict-Based Search with Optimal Task Assignmen (ECB-HCBS-TA) algorithm is proposed. The aim is to find the optimal task assignment result and the corresponding shortest conflict-free pickup and delivery path, so as to minimize the total cost of completing all tasks. Firstly, the optimization of MAPD solution for non-fixed delivery location is ensured by coupling the task assignment and multi-agent path finding. Secondly, to solve the problem of high computational complexity caused by redundant nodes in the search forest generated by CBS-TA algorithm, a heuristic cost function based on energy cost is designed to guide the search and growth of the constraint tree to reduce the search space. Then, A heuristic bidirectional A* algorithm is designed to speed up the path search. Finally, the simulation results show that the proposed algorithm can effectively reduce the cost and computation amount when solving the MAPD problem of non-fixed delivery locations, which proves the effectiveness and scalability of the algorithm.