Research on Multi-Agent Pickup and Delivery Problem of Non-Fixed Delivery Locations

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.