Artificial intelligence-informed planning for the rapid response of hazard-impacted road networks

Li Sun, John Shawe‐Taylor, Dina D’AyalaScientific 2022 · DOI

TL;DR

Researchers have developed an AI-driven framework to optimize how we repair road networks after a disaster. By combining lookahead search algorithms with deep reinforcement learning, the system identifies repair sequences that restore network connectivity significantly faster than traditional "rule-of-thumb" heuristics, effectively navigating a search space of billions of possible permutations.

What Problem Does This Paper Address?

When a major earthquake hits, road networks (RNs) often suffer widespread damage, particularly to bridges. Restoring these Critical Infrastructure Systems (CISs) is a race against time: delayed repairs hinder emergency services and stall the recovery of other vital utilities like power and water.

The challenge lies in the "sequencing problem." If you have 20 severely damaged bridges, there are $20!$ (over 2 quintillion) possible orders in which to repair them. Simple heuristics—like repairing the easiest bridges first or the ones that seem most central—often fail because they don't account for the dynamic state of the network. For example, a repair crew might be blocked from reaching a critical bridge because another bridge on the path hasn't been fixed yet. Finding the "optimal" path through this massive, interdependent search space is computationally impossible for standard optimization routines in real-time.

Methods

The authors propose a "toolkit" of strategies, moving from simple to highly sophisticated:

  1. Agent-Based Model (ABM): The foundation is a simulation involving two types of agents: Agent A (performing rapid, partial repairs on severely damaged bridges) and Agent B (performing full repairs on moderately damaged bridges).
  2. Heuristic-Based Strategies: They tested two baselines: Span-based (prioritizing shorter, easier-to-fix bridges) and Betweenness-based (prioritizing bridges that are mathematically central to the network's connectivity).
  3. Lookahead-Based Strategy: This introduces a "virtual" one-step lookahead. Before choosing the next bridge, the agent simulates the immediate outcome of fixing bridge i and then "rolls out" the rest of the campaign using a simple heuristic to estimate the total remaining loss.
  4. Learning-Based Strategy (The Core Innovation): To avoid the high computational cost of recursive simulations, the authors trained a Deep Neural Network (DNN) to "foresee" the expected future losses from any given network state. They used an iterative "self-learning" approach:
  5. 1st Generation: Trained on experiences from the simple span-based heuristic.
  6. Subsequent Generations: Each new DNN was trained using the previous generation's "knowledge" to guide a lookahead search, creating a virtuous cycle of improvement until performance "saturated."

Datasets

  • Real-World Topology: The road network of Luchon, France, featuring 118 bridges with varying seismic fragilities and spans.
  • Synthetic Scenarios: 8,000 hypothetical earthquake scenarios (Magnitude 7) with epicenters distributed across the region were used to generate a training dataset of approximately 112,000 "experience batches" for the neural networks.
  • Evaluation: 1,000 Monte Carlo simulations were used to benchmark each strategy against the others.

Key Insights and Ideas

  • The "Low-Hanging Fruit" Fallacy: The AI learned to avoid the "span-based" trap. While fixing short bridges is fast, it often leaves the network disconnected for longer. The AI sometimes chooses a harder, longer repair early on because it "unlocks" access to the rest of the network.
  • Interdependence is Key: The study highlights that the rapid response (Agent A) and full repair (Agent B) campaigns are deeply intertwined. A smart strategy for Agent A significantly speeds up Agent B by clearing the paths Agent B needs to travel.
  • Saturation of Learning: Performance gains were massive between the 1st and 2nd generations of the DNN, but leveled off by the 3rd and 4th. This suggests that for a given network, there is a "ceiling" of efficiency that AI can reach relatively quickly without needing infinite training.
  • Heuristic vs. Lookahead: Even a single step of lookahead can make a "bad" heuristic (like the span-based one) outperform a "good" one (betweenness), proving that adaptivity is more important than the initial ranking criteria.

Key Results

  • Duration Reduction: The learning-based strategy (2nd Gen DNN) completed the rapid response campaign in roughly 75 days, compared to 107 days for the betweenness baseline and a staggering 212 days for the span-based heuristic.
  • Loss Mitigation: Using Gross Weighted Losses (GWL)—a metric aggregating connectivity loss over time—the AI-informed strategy achieved a 57.7% reduction in median losses compared to the span-based approach.
  • Extreme Case Performance: In the worst-case scenarios (95th percentile), the AI's advantage was even more pronounced, showing it is robust against highly destructive, "unlucky" damage distributions.

Limitations and Future Work

  • Agent Assumptions: The model assumes uniform distributions for agent speed and efficiency. Real-world logistics (fuel, materials, labor strikes) are more chaotic.
  • Scalability: While tested on a regional network of 118 bridges, applying this to a massive metropolitan network (thousands of bridges) would significantly increase the state space and training requirements.
  • Multi-Agent Coordination: The current model uses one "squad" per agent type. Future work could explore coordinating multiple repair crews (multi-agent reinforcement learning) to further optimize recovery.
  • Static Roads: The study assumes road segments themselves are intact, focusing only on bridges. In reality, landslides or surface ruptures would add another layer of complexity.

Summary updated

Abstract

Abstract Post-hazard rapid response has emerged as a promising pathway towards resilient critical infrastructure systems ( CISs ). Nevertheless, it is challenging to scheme the optimal plan for those rapid responses, given the enormous search space and the hardship of assessment on the spatiotemporal status of CISs . We now present a new approach to post-shock rapid responses of road networks ( RNs ), based upon lookahead searches supported by machine learning. Following this approach, we examined the resilience-oriented rapid response of a real-world RN across Luchon , France , under destructive earthquake scenarios. Our results show that the introduction of one-step lookahead searches can effectively offset the lack of adaptivity due to the deficient heuristic of rapid responses. Furthermore, the performance of rapid responses following such a strategy is far surpassed, when a series of deep neural networks trained based solely on machine learning, without human interventions, are employed to replace the heuristic and guide the searches.
BibTeX
@inproceedings{sun2022artificial,
  author = {Li Sun and John Shawe‐Taylor and Dina D’Ayala},
  title = {{Artificial intelligence-informed planning for the rapid response of hazard-impacted road networks}},
  booktitle = {Scientific},
  year = {2022},
  doi = {10.1038/s41598-022-19637-z},
}
Figure