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 assignment (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, 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 pathfinding. Then, 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. Finally, A heuristic bidirectional A* algorithm is designed to speed up the path search. The grid map and pickup and task information are generated randomly, and the ECB-HCBS-TA algorithm is compared with CBS-TA algorithm. The simulation results show that when the ECB-HCBS-TA algorithm is implemented on the 8×8 grid map, the maximum completion time, the average time cost, the number of nodes and the running time of the algorithm are reduced by 9.3%, 5.4%, 23.2% and 50% respectively, which proves the effectiveness of the algorithm. When the grid map is further expanded, the ECBHCBS-TA algorithm can still complete the planning in a short time, which proves the scalability of the algorithm.