Assignment-Preserving Replanning for Dynamic Task Allocation in Multi-UAV Systems

Dynamic events, such as new task arrivals, UAV failures, and changes in task time windows, require timely updates to task allocation plans in multi-UAV systems. Global replanning provides broad flexibility for feasibility recovery, but it may also modify assignments and route structures that remain valid after an event. This study proposes Assignment-Preserving Replanning (APR), which inherits the operational state at a common event time, partitions unfinished tasks into directly affected and initially unaffected sets, and explicitly protects valid assignments and relative route structure during repair. When feasibility cannot be recovered within this protected scope, APR selectively releases protected tasks associated with constraint conflicts to expand the modifiable scope. APR was evaluated against constructive repair, partial replanning with a fixed or localized scope, and two global adaptive large neighborhood search methods. Among 116 primary scenarios feasible for all five methods, APR achieved the lowest reassignment rate of 17.71%. It preserved 100.00% of initially unaffected task assignments in 103 scenarios and 100.00% of comparable induced route structure in 91 scenarios. These structural gains were accompanied by a higher mission cost. Across the broader primary evaluation set, APR showed lower feasibility than global replanning but substantially shorter computation time. A stochastic robustness analysis using 10 independent random seeds reproduced the overall trends. Overall, APR provides a complementary replanning strategy that trades some search flexibility and mission efficiency for stronger structural continuity of valid portions of the existing plan. Whether these gains reduce energy consumption, control effort, communication burden, operator workload, or execution risk remains to be validated.