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

Chenxi Duan, Chongshuang Hu, Minghao Li, Jiang JiangSyst 2026 · DOI

TL;DR

This paper tackles the complex challenge of assigning tasks to multiple drones (multi-agent systems) during disaster response, specifically when the amount of resources needed is uncertain. They introduce a novel two-stage robust optimization model that balances upfront costs with potential penalties for unmet demand, and a fast algorithm (LE-C&CG) to solve it efficiently, making it practical for real-time emergency situations.

What Problem Does This Paper Address?

Disaster response scenarios are dynamic and unpredictable. Unmanned Aerial Vehicles (UAVs), acting as multi-agent systems (MASs), are increasingly used for tasks like observation and intervention. However, allocating these tasks efficiently is difficult due to uncertainties, particularly in the demand for intervention resources. Existing approaches often simplify this by using deterministic models or focusing only on time uncertainty, ignoring the critical impact of fluctuating resource needs caused by environmental factors and incident complexity. This can lead to either overly conservative (and thus costly) plans or insufficient resource allocation, jeopardizing the mission's success. This paper aims to bridge this gap by developing a robust task allocation framework that explicitly accounts for demand uncertainty.

Methods

The core of this paper is a two-stage robust optimization model.

  • Stage 1 (Master Problem): This stage plans the initial task allocation, minimizing operational costs based on baseline demands. It aims to find a robust initial plan before the actual demands are known.
  • Stage 2 (Recourse Problem): Once the actual, uncertain demands are revealed, this stage calculates the penalty cost incurred by any shortfall between available resources and actual needs. The model then seeks to minimize the sum of Stage 1 costs and the worst-case Stage 2 penalties.

To handle the computational complexity of this robust optimization approach, especially for large-scale problems, the authors propose a Learning-Enhanced Column and Constraint Generation (LE-C&CG) algorithm. This algorithm leverages a key property: the recourse function (penalty cost) is monotonically non-decreasing with respect to uncertainty. This allows them to replace a computationally expensive Mixed-Integer Programming (MIP) subproblem with a fast, greedy heuristic separation oracle. This oracle efficiently identifies the worst-case scenarios by ranking and selecting the most impactful uncertain demands, significantly speeding up convergence.

A Post-Processing Dynamic Routing and Scheduling algorithm is also used to translate the optimal allocation into concrete flight paths and schedules, ensuring temporal feasibility (e.g., observation before intervention).

Datasets

Not discussed in the paper. The paper describes a simulation environment and parameter settings for experiments, but does not refer to specific pre-existing datasets for training or evaluation.

Key Insights and Ideas

  • Demand Uncertainty is Crucial: The paper strongly emphasizes that ignoring demand uncertainty in disaster response task allocation is a significant oversight, leading to suboptimal or risky plans.
  • Two-Stage Robustness Balances Risk and Cost: By separating the problem into two stages, the model effectively balances the upfront cost of preparedness against the potential penalties of worst-case scenarios, avoiding the extreme conservatism of single-stage robust methods.
  • Monotonicity is Key to Efficiency: The monotonic nature of the recourse function is a critical insight that enables the development of a much faster algorithm (LE-C&CG) by replacing complex MIP solvers with a heuristic oracle.
  • LE-C&CG is a Game-Changer for Speed: The proposed LE-C&CG algorithm demonstrates a dramatic speedup (orders of magnitude) compared to standard methods, making robust optimization practical for time-critical applications.
  • Heuristic Oracle Effectiveness: The greedy heuristic oracle, validated by the monotonicity property, effectively identifies worst-case scenarios, leading to rapid convergence and a near-zero optimality gap.

Key Results

  • Computational Speedup: The LE-C&CG algorithm achieved convergence orders of magnitude faster than standard Benders and C&CG algorithms, consistently reaching a 0% optimality gap within fractions of a second.
  • Reduced Real Cost: In simulations, the two-stage robust optimization model consistently showed lower average real costs compared to deterministic models, even though it might incur a slightly higher upfront cost.
  • Lower Violation Probability and Magnitude: The robust model significantly reduced the probability of insufficient demand and the average magnitude of the demand gap compared to deterministic approaches.
  • Low Price of Robustness: The additional cost incurred by the robust model (Price of Robustness) was generally less than 1%, indicating a highly efficient trade-off for improved reliability.
  • Scalability: The LE-C&CG algorithm demonstrated excellent scalability, with solution times increasing much more slowly than other methods as problem size grew.

Limitations and Future Work

  • Uncertainty Set Limitations: The current uncertainty set relies on estimated intervals and budgets, which may not fully capture complex, non-linear correlations in real-world disaster data.
  • Heuristic Oracle Dependency: The efficiency of the heuristic oracle depends on the monotonicity of the penalty function.
  • Future Work Suggestions:
    • Incorporating more realistic, data-driven uncertainty factors.
  • Investigating AI-assisted column generation techniques to handle non-monotonicity.
  • Developing robust compensation mechanisms for intermittent communication failures.
  • Integrating the model into live command-and-control infrastructures, addressing communication delays and dynamic updates.

Summary updated

BibTeX
@article{duan2026two,
  author = {Chenxi Duan and Chongshuang Hu and Minghao Li and Jiang Jiang},
  title = {{Two-Stage Robust Optimization for Coupled Multi-Agent Task Allocation in Disaster Response Under Demand Uncertainty}},
  journal = {Syst.},
  year = {2026},
  doi = {10.3390/systems14040405},
}
Figure