Multimodal Prescriptive Analytics for Rapid Post-Disaster
Inspection Operations
Bastián Bahamondesa , Mathieu Dahana , Andrew Leeb , and Saurabh Aminca School of Industrial & Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA

bastian.bahamondes@gatech.edu, mathieu.dahan@isye.gatech.edu
b Department of Mathematical Sciences, United States Military Academy, West Point, NY, USA

andrew.lee@westpoint.edu
c Laboratory for Information and Decision Systems, Department of Civil and Environment

Engineering, Massachusetts Institute of Technology, Cambridge, MA, USA
amins@mit.edu
Keywords: Disaster Response; Multimodal Inspection; Failure Identification; PrescriptiveAnalytics; Bayesian Update

1INTRODUCTION

Critical infrastructure networks, such as electricity, water, oil and gas distribution networks,
regularly face risks of service disruptions due to component failures caused by disaster events(e.g., hurricanes, earthquakes). These failures often result in significant societal and economic
losses: The 2017 hurricane season resulted in a record $306.2 billion in damages (NOAA, 2022).
Following a disaster event, the primary role of a utility company is to inspect its network topromptly identify failures and subsequently restore its service. However, inspection operations
are hindered by the uncertainty pertaining to the failures’ locations, resulting in an increase inresponse time and cost. Thus, a significant amount of stochastic routing models have been developed in the literature for response operations (de la Torre et al., 2012). In addition, researchers
have leveraged new data analytics to improve post-disaster failure predictions and reduce diagnostic uncertainty (Nateghi et al., 2011). Finally, unmanned aerial sensors (UASs) provide newtechnological opportunities to improve network inspections for post-disaster assessment (Ezequielet al., 2014). Our goal is to leverage these three research areas to develop a multimodal analytics
approach for post-disaster network inspection.
In this work, we formulate a prescriptive analytics model for network inspection operations. We
first develop a predictive model that provides spatial estimates and uncertainty bounds on thenumber of failures throughout an infrastructure network after a disaster event. Then, we leveragethese predictions to prioritize network inspection involving UAS-equipped ground crews. Aftereach day of inspection, we integrate the information from partially inspected regions to schedule
inspections in subsequent days. To solve this large-scale problem, we propose a solution approachbased on a certainty equivalent mixed-integer program (MIP) that (i) decomposes the inspectionof UASs over subnetworks and the routing of inspection crews between access points from whereUASs can be launched; and (ii) integrates failure information from current inspections to refine
the uncertainty bounds on the remaining number of failures. We evaluate our solution approachon Houston’s drainage network using debris data identified after Hurricane Harvey in 2017.

2PROBLEM DESCRIPTION

We consider a utility company that seeks to dispatch inspection crews equipped with UASs toidentify failures within a critical infrastructure network caused by a natural disaster. After thenatural disaster occurs, the utility has access to local information on the critical network (fromowned sensors or crowdsourced data). We use this information to partition the network intoTRISTAN XI Symposium

Original abstract submittal

Bahamondes, Dahan, Lee, and Amin

2N directed subnetworks Gn := (Vn , En ) and predict – with a Machine Learning algorithm – thenumber of failures within each subnetwork. For every n ∈ [N ], we let Dn1 denote the randomvariable representing the number of failures in subnetwork Gn .
To identify the failures’ locations and/or reduce the uncertainty regarding the number of failuresin each subnetwork, m inspection crews, each equipped with U UASs, originate at a service
station s and travel in vehicles along the road network to reach access points an from where they
operate the UASs to (partially) explore the corresponding subnetworks Gn . Each inspection crew
then retrieves their UASs and travels by vehicle to another subnetwork’s access point for anotherinspection. They repeat this process until the end of their shift, which lasts H time units, andthen return to the service station. At the end of each day, we gather the newly acquired data
and update the estimate of the number of failures that remain in each subnetwork.
Let A := {an , n ∈ [N ]}, with [N ] := {1, . . . , N }, denote the set of access points. For every
ordered pair of locations (i, j) ∈ (A ∪ {s})2 , we denote µij the vehicle travel time between iand j. For every subnetwork n ∈ [N ] and every edge (i, j) ∈ En , we denote its length by ℓij .
When flying over an edge of a subnetwork, a UAS can either travel at a nominal speed 1/ν −that enables the identification of failures along that edge, or it can travel at a faster speed 1/ν + ,which reduces the travel time but does not permit the identification of failures along that edge.
This feature is useful to permit the coordination of multiple UASs and avoid redundancy of effort.
We can then model the set of feasible dispatches using mixed-integer linear constraints. For every
ordered pair of locations (i, j) ∈ (A ∪ {s})2 with i ̸= j, we denote xij the binary variable equal
to 1 if an inspection crew travels from i to j, and we denote vij ∈ R≥0 the variable representing
the time at which the inspection crew traveling along (i, j) arrives at location j. Next, for every
subnetwork n ∈ [N ], every directed edge (i, j) ∈ En , and every UAS u ∈ [U ], we consider theu (resp. z u ) equal to 1 if UAS u travels from i to j at nominal speed (resp.
binary variable yijij
u representing the time (since takeoff
faster speed). We also consider the nonnegative variable wij
at an ) it takes for UAS u to arrive at location j. Since the inspection crew needs to retrieve
all dispatched UASs before traveling to the next subnetwork (or back to the service station),
we consider for each subnetwork n ∈ [N ] a variable ran representing the time spent at that
subnetwork, characterized by the longest flight time of the U UASs. We can now formulate themixed-integer linear constraints to model the feasible crew dispatches and UAS flight plans:
Xxsj ≤ m,
(1)
j∈AXX

∀i ∈ A(2)∀i ∈ A(3)∀ n ∈ [N ], ∀ u ∈ [U ](4)∀ n ∈ [N ], ∀ u ∈ [U ], ∀ i ∈ Vn \ {an }(5)∀ n ∈ [N ], ∀ u ∈ [U ], ∀ (i, j) ∈ En

(6)

∀ n ∈ [N ], ∀ (i, j) ∈ En

(7)

uuu
0 ≤ wij≤ M (yij+ zij),∀ n ∈ [N ], ∀ u ∈ [U ], ∀ (i, j) ∈ En

(8)waun j = ν − ℓan j yaun j + ν + ℓan j zaun j ,∀ n ∈ [N ], ∀ u ∈ [U ], ∀ j ∈ Vn

(9)xij =j∈A∪{s}

Xxji ,j∈A∪{s}xij ≤ 1,j∈A∪{s}

Xi∈Vn

X

xan j ,j∈A∪{s}uu(yij+ zij)=j∈Vnuu
yij+ zij≤ 1,UX

X(yaun i + zaun i ) ≤Xuu(yji+ zji),j∈Vnuyij≤ 1,u=1

TRISTAN XI Symposium

Original abstract submittal

Bahamondes, Dahan, Lee, and Amin

Xu
wij=j∈Vnran ≥Xuwji+j∈VnXX3uu(ν − ℓij yij+ ν + ℓij zij), ∀ n ∈ [N ], ∀ u ∈ [U ], ∀ i ∈ Vn \ {an }(10)j∈Vnuwia,n∀ n ∈ [N ], ∀ u ∈ [U ](11)∀j ∈ A(12)

i∈Vnvsj = µsj xsj ,0 ≤ vij ≤ Hxij ,XXvij =j∈A∪{s}

2

Xvji + ri +j∈A∪{s}µij xij ,∀ (i, j) ∈ A(13)∀ i ∈ A.

(14)

j∈A∪{s}Constraints (1)-(3) model the tours taken by the m inspection crews. Constraints (4) permit
the exploration of a subnetwork by UASs only if a crew reaches its access point. Constraints (5)ensure conservation of the flow of UASs within Gn . Constraints (6) ensure that one speed isselected (nominal or faster) for each edge traversed by a UAS. Constraints (7) ensure that eachedge is inspected for failure identification by at most one UAS. Constraints (8)-(10) monitor theflying time of each UAS and eliminate subtours. Constraints (11) determine the time spent by
an inspection crew at each subnetwork. Finally, the remaining constraints (12)-(14) determine
the total working time of each inspection crew and eliminate subtours.
Let X denote the set of feasible solutions to the set of constraints (1)-(14). Let T denote anupper bound on the number of days required to explore all subnetworks. Then, each day t ∈ [T ],we select a feasible dispatch and flight plan X t ∈ X . After each day of inspection, we process thedata gathered by UASs and update our estimate of the number of failures in the subnetworks
that have been partially explored. The distribution of the number of failures within each subnetwork is updated using Bayes’ rule. In deriving the computations, we assume that the failures areuniformly spread throughout each subnetwork. Thus, conditional on the total number of failuresdtn ∼ Dnt within a subnetwork and the fraction γnt of the subnetwork that is explored on dayt, the number of failures identified by the UASs fnt follows a binomial distribution Fnt = B(dtn , γnt ).
Every day t ∈ [T ], the state of the system is characterized by Rt = (Rt1 , . . . , RtN ) and D t =t ), which respectively represent the set of unexplored edges and the distribution of(D1t , . . . , DN
the number of remaining failures in each subnetwork at the beginning of day t. The objective
is to maximize the number of failures identified each day. Then, the decision problem can beformulated using the following multi-stage stochastic optimization problem:∀ t ∈ [T ],NhhXii∗∗
q t (Rt , Dt ) = max EDt EF t
fnt + δq t+1 (Rt+1 , D t+1 )X t ∈X

(15)

n=1UX
X
1tut
with γn = Pℓij yij,(i,j)∈Rtn ℓij u=1 (i,j)∈Rt∀ n ∈ [N ](16)nFnt = B(dtn , γnt ),∀ n ∈ [N ]Rt+1
= Rtn \ {(i, j) ∈ En |n(17)

UXutyij≥ 1},∀ n ∈ [N ]

(18)

u=1

Dnt+1 = π t (Dnt , Rtn , X t , fnt ),∀ n ∈ [N ],(19)

where δ ∈ (0, 1) is a discount factor to model the importance of identifying failures as earlyas possible. Equations (16) determine the fraction of previously unexplored edges in each subnetwork that are inspected on day t, which in turn impact the distributions of the numbers ofidentified failures given in equations (17). Equations (18) update the sets of unexplored edges ineach subnetwork for the following day, and equations (19) update the distribution of the numberof failures remaining in each subnetwork using Bayes’ rule.
TRISTAN XI Symposium

Original abstract submittal

Bahamondes, Dahan, Lee, and Amin

34

CURRENT RESULTS

Proportion of Total Failures FoundTo solve the multi-stage stochastic routing problem (15)-(19), we propose a certainty equivalent
MIP that is solved on a rolling horizon. To scale this approach, we replace the set of constraints(4)-(11) by the selection of likely UAS flight plan options that are precomputed by solving aMIP that generalizes the minmax k-Chinese postman problem (Frederickson et al., 1978). We
evaluate our solution approach using the data from the inspection operations in Houston, TX,
after Hurricane Harvey in 2017. Specifically, the flood control district was tasked with finding
debris along its drainage network that led to important and costly floods throughout the city. To
estimate the distribution of the number of failures on the first day after the hurricane, we trained
a multivariate Poisson regression model using environmental data and readings from a networkof fixed gauge sensors. Figure 1 shows the location of the debris on the drainage network, as wellas the performance of our solution approach in comparison with a greedy heuristic – with simpler
data analytics and no UAS capabilities – designed to represent the 2017 inspection operations.
1.2
10.8
0.6
0.4
0.2
0MIP
Greedy0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
DayFigure 1 – Houston’s drainage network with failures (left) and evaluation of our solution (right).
From Figure 1, we observe a significant improvement in the inspection operations compared to
the greedy heuristic. This improvement is due to (i) the added speed provided by UASs, (ii) thesmarter coordination of resources from the MIP, and (iii) the reduced diagnostic uncertainty,
obtained from the initial regression model and the daily Bayesian updates using the informationfrom partially inspected subnetworks. Next, we aim to improve our solution approach with more
complex decomposition methods for dynamically computing near-optimal UAS flight plans andby directly accounting for the failure uncertainty bounds in the certainty equivalent MIP.

Referencesde la Torre, Luis E., Dolinskaya, Irina S., & Smilowitz, Karen R. 2012. Disaster Relief Routing: Integrating
Research and Practice. Socio-Economic Planning Sciences, 46(1), 88 – 97.
Ezequiel, Carlos Alphonso F., Cua, Matthew, Libatique, Nathaniel C., Tangonan, Gregory L., Alampay,Raphael, Labuguen, Rollyn T., Favila, Chrisandro M., Honrado, Jaime Luis E., Caños, Vinni, Devaney,Charles, Loreto, Alan B., Bacusmo, Jose, & Palma, Benny. 2014. UAV aerial imaging applications forpost-disaster assessment, environmental management and infrastructure development. Pages 274–283
of: 2014 International Conference on Unmanned Aircraft Systems (ICUAS).
Frederickson, Greg N., Hecht, Matthew S., & Kim, Chul E. 1978. Approximation Algorithms for SomeRouting Problems. SIAM Journal on Computing, 7(2), 178–193.
Nateghi, Roshanak, Guikema, Seth D, & Quiring, Steven M. 2011. Comparison and Validation of Statistical Methods for Predicting Power Outage Durations in the Event of Hurricanes. Risk Analysis: AnInternational Journal, 31(12), 1897–1906.
Office for Coastal Management, National Oceanic and Atmospheric Administration. 2022 (November).
Hurricane Costs. https://coast.noaa.gov/states/fast-facts/hurricane-costs.html.

TRISTAN XI Symposium

Original abstract submittal