A Weighted Distance-Time Algorithm for Large-Scale Task Allocation with Time Window Constraints in Multi-Robot Systems

This paper proposes a weighted distance-time algorithm to address the problem of reliably and efficiently allocating large-scale tasks with time window constraints in multi-robot systems. Such problems typically encounter the following challenges: with the task scale increases, the communication frequency within the robotic system grows exponentially, the number of unassigned tasks and idle robots increases significantly, and solution efficiency decreases markedly. To address these reliability and performance concerns, this paper proposes a task clustering algorithm, Weighted Distance-Time Clustering (WDT- Clustering), which is based on the principles of the K-means++ algorithm. By utilizing a priority function that incorporates task time window information, the algorithm clusters the task set into multiple subsets, grouping tasks with similar spatial and temporal characteristics. Subsequently, the CBBA is applied independently to each task subset to solve the task allocation problem. Finally, simulation experiments are conducted to validate the effectiveness of the proposed algorithm. Simulation experiments demonstrate that the proposed approach effectively addresses the challenges associated with large-scale task allocation under time constraints, reducing the number of unassigned tasks and idle robots while enhancing the overall reliability and operational performance of the robotic system.