Prediction-Based Dual-Stage Distributed Task Allocation for Maximizing Assignments in Search and Rescue Scenarios

Multi-robot systems provide an effective solution for executing complex tasks in dynamic environments; however, achieving efficient task allocation–optimizing the division of labor among robots for satisfactory performance–poses a significant challenge. This study introduces a prediction-based dual-stage distributed task allocation (PDTA) method for distributed multi-robot systems, with a particular focus on search and rescue (SAR) scenarios. In the first stage, the method utilizes a performance impact algorithm framework to generate an initial solution. It incorporates a task bid prediction mechanism during the task removal process to reduce invalid bids and expedite the convergence rate of the algorithm. The cost function also integrates task deadlines, enabling robots to allocate time more effectively and complete additional tasks within fuel constraints. In the second stage, a local search mechanism refines the initial solution to improve the quality of task allocation and the number of completed tasks. Monte Carlo simulations in SAR scenarios, considering task deadlines and fuel limitations, validate the effectiveness of this approach. The results demonstrate significant advantages over existing distributed task allocation methods, particularly in iteration efficiency and the number of rescued survivors.