Task Allocation and Path Planning for Multiple Destinations Oriented Towards Task Updates

This study addresses the complexities of orchestrating multi-target transportation tasks within multi-agent systems, constrained by load capacity. The primary objective is to engineer an advanced path planning framework that assures collision avoidance and optimal load distribution. Diverging from conventional single-path strategies, this research incorporates load factors and requires continuous dynamic multi-target point and path planning to ensure agents can efficiently navigate through a series of predetermined key points. To address this complex requirement, a two-stage multi-agent task allocation and path planning method is proposed. First, an initial solution is obtained using a suboptimal algorithm, followed by optimization iterations using the large neighborhood search algorithm to improve task allocation. In the second stage, an accelerated algorithm based on priority search is used to plan optimal paths for each agent in a predetermined order. The proposed algorithm's effectiveness is comprehensively evaluated through a series of experimental evaluations and comparisons with the commercial solver Gurobi within a limited time. The results show that the proposed method achieves optimality in both running time and minimum path cost while ensuring the load balance of agents.