Two-Stage Robust Optimization for Coupled Multi-Agent Task Allocation in Disaster Response Under Demand Uncertainty

Multi-agent systems (MASs), with unmanned aerial vehicles (UAVs) as a representative embodiment, have become increasingly vital in time-sensitive disaster response scenarios, where multiple agents must collaborate to execute “observe-and-intervene” emergency tasks and jointly cope with dynamic environmental uncertainties. Existing research on task allocation mostly eliminates uncertainty through deterministic models; the few studies that directly consider uncertainty focus primarily on time uncertainty, overlooking the critical importance of demand uncertainty. To this end, this study accounts for the impact of harsh environmental conditions and incident complexity factors on intervention resource demands. We establish an uncertainty set for these demands and construct a two-stage robust optimization model to solve the coupled multi-agent task allocation problem. Compared with deterministic models, this framework enhances risk resistance while simultaneously reducing the conservatism of decisions. Furthermore, to overcome the computational challenges of large-scale instances, a Learning-Enhanced Column and Constraint Generation (LE-C&CG) algorithm is proposed. Experimental results demonstrate that LE-C&CG converges over an order of magnitude faster than standard Benders and C&CG algorithms, consistently achieving a 0% optimality gap within fractions of a second, making it highly suitable for time-critical emergency applications.