# Proactive Distributed Constraint Optimization of Heterogeneous Incident
Vehicle Teams ††thanks:  Preprint. under review.

Justice Darko
Computational Science and Engineering
North Carolina A&T State University
1601 E. Market Street, Greensboro, NC 27411
<EMAIL_ADDRESS>
&Hyoshin (John) Park
Computational Science and Engineering
North Carolina A&T State University
1601 E. Market Street, Greensboro, NC 27411
<EMAIL_ADDRESS>

###### Abstract

Traditionally, traffic incident management (TIM) programs coordinate the
deployment of emergency resources to immediate incident requests without
accommodating the interdependencies on incident evolutions in the environment.
However, ignoring inherent interdependencies on the evolution of incidents in
the environment while making current deployment decisions is shortsighted, and
the resulting naive deployment strategy can significantly worsen the overall
incident delay impact on the network. The interdependencies on incident
evolution in the environment, including those between incident occurrences,
and those between resource availability in near-future requests and the
anticipated duration of the immediate incident request, should be considered
through a look-ahead model when making current-stage deployment decisions.
This study develops a new proactive framework based on the distributed
constraint optimization problem (DCOP) to address the above limitations,
overcoming conventional TIM models that cannot accommodate the dependencies in
the TIM problem. Furthermore, the optimization objective is formulated to
incorporate Unmanned Aerial Vehicles (UAVs). The UAVs’ role in TIM includes
exploring uncertain traffic conditions, detecting unexpected events, and
augmenting information from roadway traffic sensors. Robustness analysis of
our model for multiple TIM scenarios shows satisfactory performance using
local search exploration heuristics. Overall, our model reports a significant
reduction in total incident delay compared to conventional TIM models. With
UAV support, we demonstrate a further decrease in the overall incident delay
through the shorter response time of emergency vehicles, and a reduction in
uncertainties associated with the estimated incident delay impact.

_K_ eywords Incident management $\cdot$ Emergency response $\cdot$ Distributed
constraint optimization $\cdot$ Unmanned aerial vehicles $\cdot$ Look-ahead

##  1 Introduction

Traffic incident management (TIM) programs have traditionally focused on
reducing congestion and enhancing highway safety mainly through its Full-
Function Service Patrols (FFSP)s program [1]. Under the FFSP program, service
patrol vehicles such as Emergency Response Vehicles (ERV)s are dispatched to
perform tasks including traffic incident clearance, traffic control and scene
management, and incident detection and verification. In this study, we assume
a trained FFSP operator uses a fully equipped ERV, capable of rapidly removing
incident-involved automobiles or light trucks to a safe location without
waiting for a wrecker.

One of the main challenges facing the TIM program is the efficient deployment
of the limited resources (i.e., ERVs) in response to a sequence of incident
requests. A typical deployment goal is to minimize the overall response time
of all ERVs to incident locations and, therefore, minimize the travel time
delay to commuters in the network. To achieve this goal, TIM programs have
conventionally deployed the closest available ERV to an incident location and
returned to the depot after completing the assignment [2].

However, this approach overlooks several key components that can improve the
overall response time of ERVs to incident requests. First, to deploy an ERV to
a current incident request, the dispatcher at the Traffic Operations Center
(TOC) may consider interdependencies between past, current and possible near-
future incident occurrences [3, 4] and allocate another ERV instead of the
closest one to the current request. The closest available ERV not served in
the current request could be closer to the location of the anticipated near-
future emergency, possibly resulting in a lower overall response time of the
ERVs to the sequence of incident requests and thus significantly decreasing
the overall incident impact on the network.

Second, suppose a busy ERV is available earlier than the anticipated
occurrence time of the next incident. Then, we can consider the ERV in the
next deployment solution search. Conversely, if the anticipated availability
time of a busy ERV is later than the occurrence time of the next incident, we
exclude that ERV in the next deployment solution search. By considering the
availability of the ERVs based on the anticipated incident duration, we avoid
making shortsighted ERV assignments.

While considering the aforementioned components will improve the deployments
of ERVs in TIM, emerging technologies such as Unmanned Aerial Vehicles (UAVs)
are providing new opportunities to enhance operations in TIM. In particular,
the Next-Generation (NextGen) TIM seeks to integrate new and emerging
technology (e.g., UAVs), tools, and training to improve incident detection and
safety response and reduce clearance times at roadway crashes [5]. Under
revised Federal Aviation Authority (FAA) regulations that accommodate UAVs’
advanced operations, UAVs and ERVs can coordinate their deployments in
response to an incident request to provide more benefits in TIM programs. The
role of UAVs in a heterogeneous vehicle team yields three key enhancements.
First, aerial view of the possible route of ERVs to the incident location can
update the availability status of the route and allow a safer and faster
response to the incident location. Second, sparse freeway sensor networks
cannot accurately estimate the location and speed of non-recurring congestion
(e.g., shockwave). Aerial monitoring of moving shockwaves can help estimate
the true impact of an incident. Third, real-time information about an incident
location can be gathered by monitoring the clearance progress from UAVs.

Coordinating the deployment of a heterogeneous emergency vehicle team (i.e.,
ERVs and UAVs) to improve TIM is challenging. Previously, the distributed
constraint optimization problem (DCOP), a generic modeling approach for
multiagent systems and coordination, has been applied to problems such as the
mobile sensor team, among other applications [6, 7]. This framework is an
attractive problem-solving approach for coordinating the heterogeneous vehicle
team in TIM for many reasons.

First, the distributed constraint optimization framework is flexible in
modeling the objectives of multiagent coordination problems through
cost/utility constraints, overcoming the rigidity of models such as the
constraint satisfaction model that defines a set of hard constraints and
cannot easily model the dynamics in the TIM problem. The dynamics in TIM
include varying numbers of available resources as they are deployed or busy
serving other requests and the detection of new incidents when solving the
current time problem. Second, the distributed framework for TIM can utilize
the onboard computing units on the emergency vehicles and, with little
communication overhead, find an acceptable deployment scheme eliminating the
need for a central computing station. Third, because the problem-solving
activities are distributed among the agents (vehicles), the possibility of a
single point of failure is eliminated. Specifically, since knowledge of cost
constraints are inherently distributed among the agents, each agent in the
deployment fleet can autonomously decide the best solution by sharing minimum
information. Lastly, the distributed framework can exploit potential
parallelism in constraint networks that define the coordination between the
two sub-teams of ERVs and UAVs in TIM. For example, by carefully connecting
the problem of deploying ERVs and UAVs, the ERVs can use route-to-incident
information from UAVs for a safe and fast response to incident scenes.

This paper develops the distributed constraint optimization framework for
allocating ERVs and UAVs developed in a multi-agent TIM. We develop the
distributed allocation of aerial and ground emergency resources by proactively
responding to dynamic changes in the freeway network. The model’s cost
constraints directly consider the dispatch decision based on current incident
requests in parallel with relocation of free ERVs based on the anticipated
location of near-future emergencies. This unified approach will improve the
overall benefit of deploying emergency resources by finding a solution that
minimizes the sum of our developed cost constraints. The motivating domain is
modeled as the Proactive Dynamic Routing Of uNmanned-aerial and Emergency Team
Incident Management (P-DRONETIM). We highlight the contributions of this paper
as follows:

  * •

A distributed constraint decision-making framework for deploying emergency
resources in TIM to minimize the delay impact of incidents on the network;

  * •

A unified approach to dispatch ERVs based on current incident requests in
parallel with relocation policies for free ERVs based on the anticipated
location of near-future emergencies;

  * •

The benefit of coordination between UAVs and ERVs is developed as a percentage
reduction in response time of the ERV to the incident location based on the
level of hazard on the ERV’s route to the incident location;

  * •

UAV aerial monitoring of moving shortwaves in the vicinity of an incident
updates the estimate of the true impact of the incident by combining the
estimates of the delay impact from the UAV observations and traditional road
sensors in a data assimilation approach.

To the best of our knowledge, this is the first study that develops a
proactive and dynamic model for the heterogeneous incident vehicle team in
traffic incident management based on the DCOP approach.

##  2 Literature Review

The Majority of research on highway incident management have focused on
allocating a team of emergency vehicles by considering only the immediate
incident request [8, 9, 10, 11], without considering the interdependencies on
the evolution of incidents in transportation networks. However, considering
only the immediate request when deploying emergency vehicles is myopic and
fails to accommodate the benefits of knowledge of the interdependencies on the
evolution of incidents and its impact on improving the immediate request’s
decisions, thereby minimizing the overall incident impact on the network.

A few studies have attempted to address the above limitations. A notable
example is the online optimization model that considers the stochastic nature
of event occurrences [12]. The model receives a sequence of emergency calls
and performs a dispatch decision responding to each request. However, there is
no direct framework for relocation of free emergency vehicles that can be made
parallel with dispatch decisions. Other studies have developed the relocation,
and dispatch decisions as separate models without considering the
interdependencies between the two decisions [12, 13]. However, developing a
connection between these two decisions will provide an efficient relocation
decision to improve the overall response time during dispatch. The relocation
of free emergency resources based on expected near-future emergencies can
significantly improve the response time in TIM.

A key performance measure for TIM considering incident occurrences is the
response time of emergency vehicles to the incident requests. Most studies
have therefore proposed models that minimize the total response time for the
team of emergency vehicles to the sequence of incident requests [8, 9, 10, 11,
12, 13]. However, using just the response time as a performance measure is
inadequate for assessing the true benefits of a deployment policy defined by
the total delay impact on the network. Aside from the response time, the
traffic characteristics at each incident location, including traffic flow
rate, should be considered when making deployment decisions. In this study, we
directly model and utilize the expected total delay impact on the network as
the measure of performance for assigning a vehicle to an incident.

To enhance the existing incident management programs, federal programs such as
the NextGen TIM are integrating new and emerging technologies such as UAVs
with the ground vehicles [5]. However, there has been a lack of focus on
developing a framework to integrate UAVs to support the operations of ground
vehicles in highway incident management. Under revised FAA regulations that
accommodate UAVs’ advanced operations [14], a significant opportunity is
presented for policy improvement in highway incident management. UAVs can
provide enhanced information about the incident scene and aid the emergency
vehicles in arriving at the incident location at full speed [15, 16, 17].

Previous DCOP [6, 7, 18, 19], for multiagent systems and coordination, applied
to problems such as the mobile sensor team, among others, has been proposed
for modeling the heterogeneous vehicle team in TIM. However, the previous
studies assumed a static environment, simplifying dynamic traffic behaviors
and events changing over time [13]. A myopic resource allocation decision that
does not consider the sequence of dependent events can not proactively adapt
to changes in the environment over multiple time stages. Also, the
availability of emergency resources for near-future emergencies was not
considered that could be estimated based on the service time of the current
request. The predictions of the environment and the resource availability in a
future time should be considered when making decisions in response to the
current request. Research on DCOP under stochastic uncertainty shows that
network uncertainty can be reduced through multi-agent collaborative sampling
[20]. Multi-agent coordination has been successfully used to efficiently
explore unknown environments using the probabilistic multi-hypothesis tracker
(PMHT) technique [21]. Using the Adopt polynomial-space algorithm, DCOP has
been shown to achieve globally optimal solutions under asynchronous task
execution while achieving high computational efficiency [6, 22].

To accommodate the dynamically changing environment and the dependencies at
different stages, this study model the resource allocation in the traffic
incident management problem as the Proactive Dynamic Routing Of uNmanned-
aerial and Emergency Team Incident Management (P-DRONETIM). P-DRONETIMs
directly model interdependencies and the possible changes in the future stage
when making current stage decisions. Compared to previous studies, we consider
a heterogeneous vehicle fleet under a unified framework for dispatch and
relocation decisions to accurately capture interdependencies in the decisions.
The probability of incident occurrences at a location for different times of
the day is achieved using incident characteristics of the given area. A look-
ahead model considers the near-future availability of emergency vehicles and
anticipates future events.

DCOP solution approaches such as complete algorithms that find the optimal
solutions have been proposed in literature [23, 24, 25, 26, 27]. However,
complete algorithms are not practical for dynamic problems like TIM with large
constraint density. On the other hand, incomplete algorithms such as the
Maximum Gain Method (MGM) and the Distributed Stochastic Algorithm (DSA)
provide high-quality solutions, especially for systems with large constraints
density [28, 29, 30]. This study focuses on applying the incomplete algorithms
MGM and DSA to P-DRONETIM.

##  3 Emergency Vehicle Team (EVT) in TIM

We first describe the problem of the emergency vehicle team (EVT) in TIM. The
EVT represented by the finite set of vehicles
$\mathbb{A}=\\{A_{1},A_{2},\dots,A_{n}\\}$ are physically located in the
transportation network. The network is modeled as a metric space on a grid
with a function $d$ that defines the distance between two locations in the
grid. The current location $cloc_{i}$ of each vehicle $A_{i}$ is assumed to be
known. Considering the grid network, a finite set of locations defined by the
grid cells represents the locations where a vehicle can assume a position or
where an incident can occur. These locations represent a discretization of the
overall underlying space on the transportation network.

Figure 1: Emergency vehicle team in TIM with three agents and two incidents.
Grid cells represent the possible locations an emergency vehicle can visit,
and stars represent the incidents, characterized by their expected total delay
on the network for each time step.

As shown in Figure 1 the cells in the grid network represent the possible
locations for vehicles or incidents. We assume time is discretized so that the
vehicles can estimate travel time between possible locations. The occurrence
of an incident results in travel time delays for commuters at that location.
We model the incident-induced delays on the network by a delay function
$\mathrm{TD}$ that estimates the expected total delay impact on the network
due to that incident. Indirectly we define incident locations $l$ as those
whose $\mathrm{TD}_{l}$ is greater than zero. This definition can be
strengthened by setting a threshold for $\mathrm{TD}_{l}$ since delays in the
network can also be from non-incident events such as rush hours and social
events. Because incidents may occur and be cleared by the EVT,
$\mathrm{TD}_{l}$ changes dynamically as the EVT becomes aware of new
incidents from the TOC. In the example presented in Figure 1 there are two
incidents shown as star symbols, with estimated $\mathrm{TD}$ at the location.
Given a set of incidents $l\in L$, the goal of the EVT is to be assigned in a
way that minimizes the total delay impact of all the incidents in the network.
In addition to the emergency vehicle response time to and clearance time of an
incident, $\mathrm{TD}$ is a function of several other traffic parameters
(e.g., traffic flow rate) defined in the vicinity of the incident location. We
provide additional details of the delay function $\mathrm{TD}$ in a later
section. Depending on the number of incidents and available vehicles, the goal
of the proactive and dynamic EVT in the TIM is to position themselves to
minimize the total delay impact for all incidents considering the dynamics of
vehicles and incidents and also predicting near-future incident occurrences.

##  4 Proactive-DRONETIM Model

###  4.1 Approach overview

Our model for the proactive and dynamic EVT in TIM is based on the DCOP
framework. DCOP is defined by a tuple
$\left\langle\mathbb{A},\mathbb{X},\mathbb{D},\mathbb{F}\right\rangle$ where
$\mathbb{A}=\left\\{A_{1},A_{2},\ldots,A_{n}\right\\}$ is a finite set of
agents (emergency vehicles),
$\mathbb{X}=\left\\{X_{1},X_{2},\ldots,X_{m}\right\\}$ is a finite set of
variables, $\mathbb{D}=\left\\{D_{1},D_{2},\ldots,D_{m}\right\\}$ is a finite
set of domain values for each variable, $\mathbb{F}$ is a finite set of
constraints between variables. Each variable $X_{i}$ is held by an agent who
chooses a value to assign it from the finite set of values in domain $D_{i}$;
Each constraint $\mathcal{C}\in\mathbb{F}$ is a function $C:D_{i_{1}}\times
D_{i_{2}}\times\ldots\times D_{i_{k}}\rightarrow\mathbb{R}_{+}\cup\\{0\\}$
that maps assignments of a subset of the variables to a non-negative cost. The
cost of a complete assignment of values to all variables is computed by
aggregating the costs of all constraints. The agents have control over the
assignment of values to their variables, and they are assumed to know only the
constraints involving their variables, thus the distributed knowledge
structure of DCOP. Agents coordinate by passing messages with other agents who
hold variables constrained by their own variables called their neighbors. The
goal of the DCOP is to find a sequence of assignments to variables with a
minimum total cost.

###  4.2  Proactive Dynamic EVT in TIM as DCOP

The proactive and dynamic EVT in TIM problem is formulated as DCOP as follows;
each vehicle holds a single variable for its position with a domain that
includes all possible locations in the transportation network. A vehicle can
be assigned to an incident in the current stage if it is not busy serving
other incident locations. The total travel time required by the vehicle to
reach the incident location and the clearance time for the incident determines
the vehicles availability for a next assignment. Considering each incident
location $l\in L$, a constraint $C_{l}$ relates the vehicles’ current location
to the delay impact $\mathrm{TD}_{l}$ of the incident in the network. The set
of constraints $\mathbb{F}$ changes over time as incidents occur (TOC
surveillance system discovers new incidents) and are cleared. In addition, the
constraints cost can change over time due to changing impact of the incident
on the network due to new and more accurate estimates of the impact from
superior UAV surveillance systems. As discussed earlier, the $\mathrm{TD}$
function models the delay impact of incidents in the network. Realistically,
the vehicles’ knowledge of the number of incidents and their impact on the
network will be dynamic, reflecting the inherent dynamism in the TIM problem.
We assume these inherent changes in the network are reported by the TOC.
Vehicles that are free after the current stage assignment can be relocated to
other locations in the network in anticipation of near-future changes in the
$\mathrm{TD}$ function at those locations. We model the relocation decision by
considering the dependencies in incident occurrences. Since we are only
anticipating an incident at a given location, the benefits of such decisions
are discounted to ensure that vehicles are first dispatched to known incident
locations before the relocation of the free vehicles, if any, in anticipation
of a near-future incidents.

####  4.2.1 Probability of incident occurrences.

The relocation of free emergency vehicles are based on expected probability of
near-future incident occurrences. For the set of possible locations $j\in J$,
we define $\mathrm{Pr}_{j,r}$ as the probability of incident occurring at
location $j$ in the next future stage $r$. The incident occurrence includes
accumulated probabilities of secondary incidents in future stages, in which
the impact of primary incidents overlaps. In general, a secondary incident may
occur during the clearance or recovery of a primary incident. Therefore, we
look-ahead two future stages. For example, the conditional probability of a
secondary incident at site 2 at the first future-stage may depend on the
probability of a primary incident at site 1 during the past and site 3 during
the current stage; at the second-future stage may depend on the probability of
a primary incident at site 1 and site 3 during the current stage (Figure 2).

Figure 2: Dependency in incident occurrences.[31]

In this study the expected probability of incidents in the near-future stages
is developed as [31]: Let $\tau(j,r)$ be the normalized probability of
incidents (probability of incidents at site $j$ over all locations $J$ in one
stage) for each stage $r$. The expected probability of incidents
$\mathbb{E}[\tau(j,r)]$ for each location $(j=k)$ and stage $(r=u)$ is a sum
of $\mathrm{Pr}^{p}_{j,r}$ and $\mathrm{Pr}^{s}_{k,u}$.

$\mathbb{E}[\tau(j,r)]=\operatorname{Pr}_{j,r}^{p}+\operatorname{Pr}_{k,u}^{s}\quad\text{for}\quad
j=k,r=u$ (1)

$\mathrm{Pr}^{p}_{j,r}$ is the probability of primary and independent
incidents at site $j$ during stage $r$, and $\mathrm{Pr}^{s}_{k,u}$ is the
probability of secondary incident occurrences at location $k$ during stage
$u$. The expected probability of incident at each location in the near-future
stages is written as:

$\mathbb{E}[\tau(j,r)]=\operatorname{Pr}_{(j,r)}^{p}+\sum_{j}\delta(\Omega,\Delta)_{(j,r-1)(k,u)}\operatorname{Pr}_{j,r-1}^{p}\\\
+\sum_{j}\delta(\Omega,\Delta)_{(j,r-2)(k,u)}\operatorname{Pr}_{j,r-2}^{p},$
(2)

where the second and third terms is the explicit model for the probability of
secondary incidents. The primary incident density ratio
$\delta(\Omega,\Delta)_{(j,r)(k,u)}$ is defined to measure relative difference
ratio and is not 0 only when an interrelation between incidents exists.
P-DRONETIM estimates the expected probability of incident occurrence at all
locations in the network in the first and second future stages using Equation
2.

####  4.2.2 Total delay impact on network due to incident.

The total delay, $\mathrm{TD}_{l}$, at incident location $l$ can be estimated
using variables considered in the Highway Capacity Manual 2010 [32]. The
deterministic incident delay model have underestimated the variance of actual
delay and therefore the true impact of an incident in the freeway. In this
study, the stochastic incident delay model is used to estimate the expected
delay at incident location $l$ as [33]:

$\mathbb{E}\left[\mathrm{TD}_{l}\left(t,r,s_{1}\right)\right]=\\\
\frac{\left[\left(\bar{s}_{1}^{2}+\sigma_{s_{1}}^{2}\right)-(s+q)\cdot\bar{s}_{1}+s\cdot
q\right]\cdot\left(\bar{r}^{2}+\sigma_{r}^{2}\right)}{2\cdot(s-q)},$ (3)

where the parameters in the model is defined as follows:

$s$ = freeway capacity, which is also the departure rate after the incident
[vehicles per hour (vph)];

$\bar{s}_{1}$ = mean reduced freeway capacity during the incident (vph);

$\sigma_{s_{1}}$ = standard deviation of reduced freeway capacity;

$q$ = traffic flow rate (vph);

$\bar{r}$ = mean incident duration and;

$\sigma_{r}$ = standard deviation of incident duration

The incident duration $r$ is the sum of the response time to and clearance
time of the incident. The current location of the emergency vehicle is an
important parameter for determining the response time and, therefore, the
incident delay impact. Therefore considering multiple available vehicles, it
is more reasonable to dispatch the closest available emergency vehicle to
mitigate the delay impact. However, considering the global goal of minimizing
the impact of all incidents, this may not always be the case. P-DRONETIM model
considers the predictions of incident occurrences in future stages when making
the current stage decisions. While this study assumes random values for
clearance time for each incident, more benefits will be achieved by accurately
predicting the clearance time for the incident. Accurately predicting the
clearance time for the incident improves the estimation of the incident delay
impact on the network. Several approaches, including statistical and machine
learning models, have predicted the expected clearance time of an incident
which will be adopted for future study [34]. We assume that the above-listed
traffic parameters are known for each incident location (e.g., from roadside
sensors).

###  4.3 TIM with UAV Active Sensing

The role of a UAV sub-team in TIM is to explore unknown traffic conditions,
unexpected situations on roads, and enhance prior information from loop
detectors, automatic vehicle identification detectors, probe vehicle data, and
other sensors (see Figure 3).

Figure 3: TIM with UAV active sensing.

P-DRONETIM makes the following assumptions to ensure our model satisfies
potential operational requirements and scenarios:

  * •

UAVs have superior imaging technology (e.g., HD camera) and sensor payloads
(e.g., infrared, LIDAR, etc.) and can perform high accuracy real-time
surveillance by capturing video and images at higher elevations (within FAA
regulations). In addition, the UAVs have a wider field of view (sensing range)
and can provide enhanced information about an incident several miles ahead of
ERV;

  * •

UAVs are launched from vehicles (e.g., trucks), serving as ground stations
that have installed navigational computers and control stations for the UAVs.
The trucks can be placed at strategic locations and moved when needed;

  * •

Depending on battery life, operators can bring UAVs back to the truck for
battery exchange and relaunch;

  * •

The UAV ground stations have a two-way communication setup that allows
communication with the TOC.

The developed model deploys the UAVs by considering factors that enhance the
operation of the EVT in TIM. Particularly to improve the response time to and
clearance of incidents and assess the true impact (e.g., delays) of the
incidents on the transportation network.

####  4.3.1 Uncertainty of incident delay impact.

The uncertainty associated with the estimated incident delay impact is
developed as a factor for UAV deployment. With the UAVs’ superior surveillance
payload, real-time observation of queues and moving shockwaves will provide a
more accurate estimate of the delay impact at the incident location. To
incorporate the enhanced information from UAVs, we first assume the prior
estimated delay impact from the traditional sensor (e.g., loop detectors) has
some associated uncertainty defined by the variance
$\sigma^{2}_{\mathrm{TD,P},l}$. Previous study have estimated this uncertainty
as (parameters are defined as stated above) [33]:

$\sigma^{2}_{\mathrm{TD,P},l}=\operatorname{Var}\left[d\left(t,r,s_{1}\right)\right]=\frac{\left[\left(q-\bar{s}_{1}\right)^{2}+\sigma_{s_{1}}^{2}\right]\cdot\left(\sigma_{r}^{2}+\bar{r}^{2}\right)}{3\cdot
q^{2}}\\\ -\frac{\left(q-\bar{s}_{1}\right)^{2}\cdot\bar{r}^{2}}{4\cdot
q^{2}}.$ (4)

Assuming that the variance of delay impact estimated from UAV observation is
$\sigma^{2}_{\mathrm{TD,O},l}$, then the relative improvement achieved by
removing uncertainty through the enhanced UAV observation can be assessed
through a data assimilation technique. Data assimilation adjusts the estimates
of a variable (e.g., delay impact) directly during a period of observation for
which you want the estimates [35]. The variance of the delay impact after
combining the estimate from the prior evaluation from the traditional sensors
and UAV observation represents the posterior estimate of the uncertainty,
written as:

$\sigma_{\text{TD,
Posterior},l}^{2}=\left(1-\beta_{l}\right)\sigma^{2}_{\mathrm{TD,P},l}$ (5)

The weight parameter $\beta$ considers the variance of the estimate from
traditional sensors (prior), and the estimates from the UAV observation
written as:

$\beta_{l}=\frac{\sigma_{\mathrm{TD,P},l}^{2}}{\sigma_{\mathrm{TD,P},l}^{2}+\sigma_{\mathrm{TD,O},l}^{2}}$
(6)

Since the UAVs provide enhanced sensing capabilities than the traditional
sensors, $\sigma_{\mathrm{TD,O},l}^{2}$ is expected to be less than
$\sigma_{\mathrm{TD,P},l}^{2}$. Therefore, the posterior estimate of the
uncertainty after UAV observation is always less than the prior as seen in
Equation 5. To update the expected delay impact (Equation 3) after UAV
observations, let
$\mathrm{TD}_{\mathrm{P},l}=\mathbb{E}\left[\mathrm{TD}_{l}\left(t,r,s_{1}\right)\right]$
be the prior estimated total delay for incident location $l$ from traditional
sensors, and $\mathrm{TD}_{\mathrm{O},l}$ estimated total delay from UAV
observation, then the posterior estimate of the delay after UAV observation
can be written as:

$\mathrm{TD}_{\text{Posterior},l}=\left(1-\beta_{l}\right)\mathrm{TD}_{\mathrm{P},l}+\beta_{l}\mathrm{TD}_{\mathrm{O},l}$
(7)

After UAV observations, the new information is transmitted to the TOCs, who
can then update the TD function with the improved posterior estimate of the
expected total delay impact from the incident.

####  4.3.2 Status of ERVs route-to-incident.

Typically, the best route-to-incident location is communicated to the ERV by
the TOC. The UAV sub-team can provide accurate information about the status of
this route-to-incident and therefore reduce the response time of the ERVs to
the incident location. As in most TIM settings, this study assumes the freeway
shoulder as the main roadway used by ERVs to incident locations. In addition
to the uncertainty of incident delay impact, the UAV deployment model of
P-DRONETIM will consider how the information on the route-to-incident location
will impact the response time to the incident and, thus, the extent of the
reduction in the total delay from the incident. ERVs having such support
information can reach the incident locations at a higher speed and further
minimize the delay impact on the network. We make the following assumptions to
justify the different levels of reduction in ERV response time when a UAV
deploys to observe an ERV’s route-to-incident location:

  * •

The best recommended route-to-incident location has a hazard index (HI) based
on past or current reported obstacles (e.g., disabled vehicles, debris, etc.)
on the freeway shoulder.

  * •

The initial travel speed of the ERV is based on the hazard index for the
route. For example, at a high hazard index, ERVs’ are advised to travel at a
slower speed to accommodate enough stopping distance in case of an obstacle
and avoid a crash.

  * •

An ERV will decelerate and change lane from shoulder to main travel lane and
back to shoulder after passing the obstacle if there is one impeding the
freeway shoulder. A lane change process briefly reduces the speed of ERV and
thus the response time.

  * •

A UAV deployed to monitor the ERVs’ route-to-incident can confirm whether or
not there is an obstacle on the freeway shoulder and the exact location of the
obstacle if any.

This study assumes that the HI for a given route-to-incident location is
categorized into five levels for simulation purposes. Each category has an
assumed percentage reduction in response time with UAV support.

$\mathrm{HI}=\left\\{\begin{array}[]{ll}{\text{1: very low }}&\qquad{3\%}\\\
{\text{2: low }}&\qquad{5\%}\\\ {\text{3: average }}&\qquad{7\%}\\\ {\text{4:
high }}&\qquad{9\%}\\\ {\text{5: very high }}&\qquad{11\%}\end{array}\right.$

As an example, by confirming that there is no obstacle on the route-to-
incident (e.g., HI = 5) for an ERV, the ERV can increase its speed and
significantly decrease the response time to the incident location ($\approx
11\%$). The preferred coordination of location assignment is such that UAVs
and incident location are the same in order for the ERV to utilize information
from the UAV. Although each sub-team has its own task, they are both working
towards a common goal.

####  4.3.3 Priority matrix for UAV deployment.

The framework for determining which incident location to deploy a UAV is
developed as a priority matrix that considers the aforementioned parameters
and the severity of the incident to determine the benefit of deploying to an
incident location. We assume that route-to-incident information and the
enhanced information from the incident location will be accommodated once a
UAV is assigned to a specific incident. In summary, the factors considered
are: (1) The severity of the incident at location $l$. The severity is
proportional to the capacity reduction (i.e., the number of lanes closed
rising from the incident) [31]; (2) The uncertainty of the estimated delay at
incident location $l$, and; (3) The hazard index of the route-to-incident for
the ERV assigned to incident location $l$. P-DRONETIM decomposes the models
for ERVs and UAVs. However, ERVs benefits from cooperation (i.e., reduction in
response time) if the sub-teams are assigned to the same location.

The incident severity $\omega_{l}$ implicitly measures the impact of the
incident on the transportation network. In this study, we define four levels
of severity, where level one (low) indicates the lowest impact incident and
level four the highest impact incident based on standard incident management
definition [36, 37].

$\omega_{l}=\left\\{\begin{array}[]{ll}{\text{ low }}&\qquad{1}\\\ {\text{
moderate }}&\qquad{2}\\\ {\text{ high }}&\qquad{3}\\\ {\text{
critical}}&\qquad{4}\end{array}\right.$

Finally, we simplify the development of the priority matrix by categorizing
the prior uncertainty of the estimated delay based on the sparsity of the
freeway sensor network $SS_{l}$ at the incident location $l$ which cannot
accurately estimate the speed of non-recurring congestion. The higher the
sparsity of the sensor network at the incident location, the less accurate the
estimate of incident delay impact at the location. The levels are developed as
ranging from 1 to 5, where level 1 indicates a very low uncertainty and level
5 indicates a very high uncertainty corresponding to low and high sparsity of
sensor network at the incident location.

$SS_{l}=\left\\{\begin{array}[]{ll}{\text{very low}}&\qquad{1}\\\ {\text{ low
}}&\qquad{2}\\\ {\text{ average }}&\qquad{3}\\\ {\text{ high }}&\qquad{4}\\\
{\text{very high}}&\qquad{5}\end{array}\right.$

Figure 4: UAV deployment priority matrix based on hazard index of the ERVs
route-to-incident location $l$, delay impact uncertainty (sparsity of sensor
network at incident location), and incident type (severity).

P-DRONETIM quantifies the benefit for deploying a UAV to incident location $l$
as a mapping of the set of all ordered pair $\omega_{l}\times
SS_{l}\times\mathrm{HI}$ to the real number $\mathbb{R}$. This approach is
similar to the design of priority matrix for incident management that shows
the importance of each task pair. In our case, the values indicate how much
benefit the UAV will provide by deploying to a particular incident location
(see Figure 4).

###  4.4 Constraint relations

####  4.4.1 Ground emergency vehicle team.

ERV deployment in P-DRONETIM aims to find the best solution that minimizes the
sum of the defined constraint costs. Since each vehicle can communicate with
all other vehicles in the network, the constraint graph is complete in
structure. Specifically, each vehicle (node) is connected to every other
vehicle in the EVT in the constraint graph. Each constraint is a function
$C_{ij}:D_{i}\times D_{j}\rightarrow\mathbb{R}_{+}\cup\\{0\\}\text{ (binary
constraint) }$. The constraint relation between any two ERVs in P-DRONETIM is
developed as:

$C\left(X_{a},X_{b}\right)=\left\\{\begin{array}[]{cc}{\infty}&{\text{if
}X_{a}==X_{b}}\\\ {w_{j}c_{{X_{a}}}+w_{j}c_{{X_{b}}}}&{\text{otherwise }}\\\
\end{array}\right.$ (8)

where $X_{a}$ and $X_{b}$ are the variables held by ERVs $a$ and $b$.
Arbitrary values for weight $w_{j}$ is chosen dependent on whether or not an
incident has been reported at location $j$. Specifically, the weight
$w_{j}=w_{d}$ is applied on the function $c_{X_{i}}$ to discount the cost for
dispatch assignments if the value assignment of variable $X_{i}=j$ and
location $j$ has a reported incident ( i.e., $\mathrm{TD}_{j}>0$). On the
contrary, if location $j$ has no reported incident (i.e., $\mathrm{TD}_{j}\leq
0$), then weight $w_{j}=w_{r}$ is applied to the function $c_{{X_{i}}}$. In
this case, weight $w_{r}\texttt{>>}w_{d}$ is set to penalize relocation
decision. The values of the weight $w_{j}$ ensures that relocation of
emergency vehicles are carried out only after dispatch to reported incident
locations are completed.

Under limited resources, our developed constraint relations ensure that the
emergency vehicles coordinate their local decision-making so that only one
vehicle is assigned to a location at any time. Specifically, a partial or
complete assignment of vehicles where $X_{a}$ equals $X_{b}$ incurs a very
high cost ($\approx\infty$) to prevent or disincentivize such assignment. For
all other scenarios, two main criteria determine the cost for the constraint.
Firstly, for $X_{i}=j$ where location $j$ has a reported incident, then
$c_{{X_{i}}}$ is defined by Equation 3 (expected delay function). Secondly, if
location $j$ has no reported incident, then $c_{{X_{i}}}$ is defined by the
probability of an incident occurring at that location in the near-future stage
(Equation 2).

All locations with no reported incidents are candidates for relocation for
free emergency vehicles. In our formulation, because relocation decisions are
designed to achieve an anticipated goal in a future stage, it is always less
important than the goals of dispatching to true incidents in the current
stage. The goal of PDRONETIM model is to find a sequence of assignments
$\mathbf{X}^{*}$ for all the decision variables in $\mathbb{X}$. Agents need
to optimize a global objective function in a distributed fashion using local
communication.

$\mathbf{X}^{*}=\underset{\mathbf{x}\in\Sigma}{\operatorname{argmin}}\quad\mathcal{C}^{h}(\mathbf{X})$
(9)

where $\Sigma$ is the assignment space for the decision variables of the
P-DRONETIM.

$\displaystyle\mathcal{C}^{h}(\mathbf{X})=C_{a,b}\left(d_{a},d_{b}\right)+\sum_{t=1}^{h}C^{t}_{a,b}\left(d_{a}^{t},d_{b}^{t}\right)$
(10) $\displaystyle\quad X_{a}\leftarrow d_{a}\in D_{a},X_{b}\leftarrow
d_{b}\in D_{b}$

Our model considers a look-ahead of two future stages ($h$=2). The first term
$C_{a,b}\left(d_{a},d_{b}\right)$ is the sum of the cost functions over the
current stage. Looking at the reported incident set in the current time, our
formulation of the cost allows the model to find the configuration of
emergency vehicles for the incidents that will minimize the delay impact. The
second term $\sum_{t=1}^{h}C^{t}_{a,b}\left(d_{a}^{t},d_{b}^{t}\right)$ looks
ahead into future stages by evaluating the first and second future stage cost
according to probability of incident incident occurring in that stage.
Therefore, the configuration that minimizes the sum of the cost considering a
look-ahead of the two future stages is the best deployment in the current
stage.

####  4.4.2 Unmanned aerial vehicle team.

With the appropriate adjustment, the constraint relations developed for the
EVT are extended for the UAVs. The goal is to find the best deployments for
the UAVs to maximize their benefits for TIM. We define utility constraints
that are based on the UAV deployment priority matrix (Figure 4). Similar to
ERVs, the constraint relation for UAVs is developed as:

$U\left(X_{u},X_{v}\right)=\left\\{\begin{array}[]{cc}{-\infty}&{\text{if
}X_{v}==X_{v}}\\\ {u_{{X_{u}}}+u_{{X_{v}}}}&{\text{otherwise }}\\\
\end{array}\right.$ (11)

where $X_{u}$ and $X_{v}$ are the variables held by UAVs $u$ and $v$. Since
battery usage is a major limitation, UAV deployment is considered only for
locations with reported incidents. Nonetheless, we can extend the model for
surveillance to detect or monitor locations where incidents are anticipated by
applying weights similar to those developed for the relocation of EVT. The
utilities $u_{{X_{u}}}$ and $u_{{X_{v}}}$ for deployments of UAVs $u$ and $v$
are defined based on the priority matrix discounted by the distance of the UAV
to the incident location. Specifically, the travel distance of the UAV to
incident location is subtracted from the computed benefit from the priority
matrix. The goal of the UAV deployment model is to find the optimal assignment
to the incident locations as:

$\displaystyle\mathbf{U}^{*}=\operatorname{maximize}\sum
U_{u,v}\left(X_{u},X_{v}\right).$ (12)

The domain $X_{u}\leftarrow d_{u}\in D_{u},X_{v}\leftarrow d_{v}\in D_{v}$ for
the variables held by the UAVs comprise of only locations of reported
incidents. We have described two sub-teams performing tasks in the same
network separately. However, it is reasonable to assume that cooperation
between the sub-teams can lead to better results because although each sub-
team has its task, they are both working towards a common goal of minimizing
the delay impact of an incident in the network. For example, when an emergency
vehicle has UAV support (assigned to the same incident), the estimated delay
impact reduces since UAV support allows the ERV to reach the incident location
safely and faster. In addition, the uncertainty of estimated delay impact
improves (reduced), giving us a more accurate assessment of the impact of the
incident on the network.

##  5 SOLUTION APPROACH

The local search algorithms MGM and DSA are used for solving P-DRONETIM,
justified by the typical standards for choosing local over the complete
search. Specifically time constraints and the limit on the scale of problems
that complete algorithms can solve. Furthermore, P-DRONETIM also has unique
characteristics that support using a local search algorithm. First, as
required for a complete search, exploring the entire search space is not
practical for large transportation networks with a large fleet of emergency
resources. Second, the dynamic changes such as new incident requests while the
current requests are being evaluated limit the time agents have to perform a
complete algorithm because changes during the search for the best solution
make the computed solution outdated. In P-DRONETIM, the expected incident
duration, given by the sum of the expected response and clearance time, is
used to estimate the availability of the resource for future stage decisions.
Therefore, not all possible assignment combinations will be feasible. The
resource availability is directly considered for all sequences of value
assignments for any variable. Specifically, a vehicle that is assigned
multiple incidents in a sequence has already estimated its availability for
the next assignment and, thus, how that impacts the total delay of the
incidents in the network. The main steps developed for the MGM and DSA
solution approach are as follows:

Step-1: Make Initial random assignments for all vehicles. The vehicle
initializes its information of the other vehicles’ assignment in the network
(initial is null).

Step-2: Each vehicle updates their information about the neighboring vehicles’
assignment by receiving the current assignment of the neighbors.

Step-3: Each vehicle computes its cost (estimated incident delay) for the
current assignment while considering its information on the neighboring
vehicles.

Step-4: Each vehicle then calculates its gain by finding the difference
between the current assignment cost and the assignment that will result in the
minimum cost.

Step-5: Each vehicle sends and receives the neighbor’s gain. The vehicles then
update the locations of the current assignments if their gain is greater than
zero and maximum compared to the gain of the neighbors. In the case of the
DSA, the vehicle uses a stochastic strategy to decide whether or not to assign
a value. Specifically, a probability threshold is set, and the vehicle’s
assignment is only updated if a randomly generated number is less than the
threshold.

Step-6: Terminate if set number of iterations are performed else restart step
2 by sending a message that contains its new locations to its neighbors.

##  6 SCENARIOS AND EXPERIMENTS

The proposed P-DRONETIM model is evaluated in a prototype network abstracted
with an existing highway network’s traffic parameter data. The problem
scenarios are simulated in a 10-by-10 city block-like grid network, with 180
links representing the road segments and 100 points of intersections
representing the possible crash locations. The weight on each edge,
representing the average time to traverse the edge, is randomly drawn from a
uniform distribution between 0.1 and 1.5 (hr). The total delay for an incident
request is estimated based on Equation 3 with parameters described in Table 1
and the response time to the incident estimated from a distance function on
the grid network. Each incident is given a random severity number drawn from a
uniform distribution between 1 and 4, which determines the values for traffic
parameters used to estimate the total delay of the incident. For example,
looking at Table 1, an incident request of severity one will have parameters
drawn uniformly from the ranges defined for each of the variables in row one.
The incidents are randomly located in the network through a random draw from a
uniform distribution whose range is the size of the grid network. We assume
each ERV and UAV is given an initial random location following current
practice. The arbitrary weights are set at $w_{d}=1$ and
$w_{r}=100*\max{\\{c_{X}\\}}$ (i.e., hundred times the maximum delay possible
for all incidents in the current stage). We randomly generate probabilities of
incident occurrence at different locations for the near-future stages for
simulation purposes dependent on each current stage request. A highly
functional UAV that supports reliable communication over long distances with
the TOCs is assumed for this study. A typical example is the Autel DragonFish
Fixed Wing UAV, featuring Beyond Visual Line of Sight (BVLOS) UAV, Vertical
Takeoff and Landing (VTOL), 120 Minute Flight Time, 18.6 Mile Transmission
Range, and 50x Optical Zoom Capability. For simplicity, we assume that UAVs
maintain a fixed altitude during their flights and cover a given region in the
network once assigned to a given location. Vehicles can communicate with each
other using a low-bandwidth Radio frequency.

Table 1: Simulation parameters severity |  $s$ (vph) |  $\bar{s}_{1}$(vph) |  $\sigma_{s_{1}}$ (vph) |  $q$ (vph) |  $\sigma^{2}_{r}$ (h) |  clearance time (h)
---|---|---|---|---|---|---
1 | [750,800] | [600,800] | [100,200] | [600,720] | [0.1,0.2] | [0.2,0.3]
2 | [1130,1500] | [900,1900] | [100,300] | [960,1120] | [0.2,0.3] | [0.3,0.4]
3 | [1700,1900] | [1000,1200] | [100,300] | [1440,1644] | [0.2,0.4] | [0.5,0.7]
4 | [2200,2800] | [1000,1500] | [100,300] | [1824,2015] | [0.2,0.3] | [0.5,1]

##  7 RESULTS AND DISCUSSIONS

The results for different TIM scenarios are first presented for the MGM and
DSA approach to P-DRONETIM to assess its performance. The MGM algorithm is
highly exploitative, limiting the exploration of other possible solutions. On
the contrary, DSA uses a stochastic exploration technique to find other
solutions that might be optimal [38]. In DSA, a vehicle’s assignment to a
location is updated only if a specified probability threshold condition has
been satisfied, introducing randomness in selecting other feasible solutions.
In our assessments, each scenario is repeated in ten experiments, and each
solution point represents the mean and standard error values for that
scenario.

Figure 5: MGM and DSA (varying probability threshold) solution and convergence
for total delay impacting network (Incident requests = 5, ERVs = 3.)

Figure 5 shows the solution and convergence for MGM and DSA (considering
different probability thresholds) for total incident delay for a scenario with
five incident requests and three emergency vehicles. The MGM and DSA
approaches find better deployment for emergency vehicles as the number of
iterations increases. Performing more iterations forces the algorithm to find
better solutions than the previous since, in each iteration, the model
evaluates other potential solutions. In the DSA approach, the deployment
solution improves for higher probability threshold values. The probability
threshold determines the level of exploration, and the higher this level, the
more likely the algorithm escapes a local optimal to find a better solution.
Comparing MGM and DSA, we clearly show the benefit of incorporating
exploration over just exploitation. In the case of MGM, the best deployment
solution resulted in a total delay of approximately 40000 vehicle hours
compared to about 25000 vehicle hours for DSA at a probability threshold of
0.9. Arguably, while MGM got stuck in a local optimal solution, DSA escaped
the local optimal through the exploration to find a better deployment
solution.

Figure 6: MGM and DSA solutions for mean incident delay for 100 randomly
generated TIM scenarios.

To further assess the performance of the two solution approach, we conduct a
Monte Carlo simulation with 100 scenarios of randomly sampled vehicle numbers,
number of incident requests, incident type, and incident locations for MGM and
DSA. As seen in Figure 6, implementing the exploration heuristic (DSA)
improves the solution for the vehicle assignments, seen with a lower mean
total incident delay ($\approx$ 50000 at prob = 0.9) compared to the highly
exploitative solution approach (MGM, $\approx$ 78000). Furthermore, DSA finds
the best solution at higher probability thresholds. The higher the probability
threshold, the more exploration, allowing DSA to find better solutions.
Previous studies have confirmed the effect of the probability threshold on the
solution quality of DSA [39]. The remainder of the experiments in this study
is conducted using the DSA approach at a probability threshold of 0.9. We
investigate the performance of P-DRONETIM for different TIM scenarios.

Figure 7: DSA solution (prob=0.9) for total delay impacting network (ERVs = 3)
for different number of incident requests. Figure 8: DSA solution (prob = 0.9)
for total delay impacting network for different number of emergency vehicles
for scenario with 15 incident requests.

Figure 7 shows the performance of DSA (prob = 0.9) for three emergency
vehicles considering different number of incident request. Increasing the
number of incidents implies an increase in the total delay impacting the
network. Increasing the number of iterations improved the search for the best
deployment solution. For example, performing 45 iterations for fifteen
incident requests finds a deployment solution with a lower total incident
delay ($\approx$ 800000 vehicle hours) than 5 iterations ($\approx$ 1100000
vehicle hours).

Figure 8 shows the performance of DSA (prob = 0.9) for different number of
emergency vehicles for fifteen incident request. Increasing the number of
emergency vehicles implies more vehicles available to respond to incident
requests and minimize the delay impacting the network. In the case of three
emergency vehicles, the vehicles have to respond and clear the initially
assigned incidents before it is available to respond to the next incident. The
total delay on the network increases when incidents are not responded to
quickly. As expected, the higher the number of emergency vehicles, the lower
the total delay on the network. For example, considering fifteen incident
requests, a team of nine emergency vehicles results in a lower total delay
($\approx 200000$ vehicle hours) than a team with three emergency vehicles
($\approx 750000$ vehicle hours) for 45 iterations. Similar to our prior
observation, increasing the number of iterations performed improves the search
for the optimal deployment solution.

Similar to the ground emergency vehicles, two experiments are conducted to
assess our model’s performance for UAV deployment based on the utilities
defined by the priority matrix. The first experiment evaluates the effect of
varying the number of incidents considering three UAVs. The second experiment
evaluates the effect of varying the number of UAVs considering fifteen
incident requests.

Figure 9: DSA solution (prob = 0.9) for total utility for different number of
incident requests for scenario with 3 UAVs.

Figure 9 shows the performance of P-DRONETIM for three UAVs for different
number of incident requests. With three UAVs, increasing the number of
incidents implies more locations than number of UAVs required for immediate
observations. Therefore the UAVs coordinate and decide on a sequence of
assignments for each UAV. The results indicate that, as the number of incident
requests increases, the UAVs coordinate effectively to provide significant
benefits.

Figure 10: DSA solution (prob = 0.9) for total utility for different number of
UAVs for scenario with 15 incident requests.

Figure 10 shows the performance of P-DRONETIM for different numbers of UAVs
considering fifteen incident requests. Increasing the number of UAVs implies
more aerial vehicles are available to quickly support the incident tasks and
update the estimates of the delay in the network. Therefore, the total benefit
for the network increases when more UAVs are available to support the task of
ERVs in TIM. For example, considering fifteen incident requests, a fleet of
nine UAVs results in a higher total benefit ($\approx 850$) than a fleet with
three UAVs ($\approx 610$) for 45 iterations. Increasing the number of
iterations performed improves the search for the optimal deployment solution.

Figure 11: DSA solution (prob = 0.9) for total incident delay with and without
cooperation between ERVs and UAVs.

We further perform experiments that assess the effect of cooperation between
the two sub-teams of ERVs and UAVs on the total incident delay on the network.
Figure 11 shows the total incident delay in the network for the TIM scenario
with different numbers of incidents, with and without cooperation, between
three ERVs and UAVs. It is clear that when the ERVs have UAV support, there is
a lower incident delay compared to when there is no support. This is because
the ERVs with UAV support can use the information they receive from the UAVs
to improve their response time to incident locations and thus reduce the
incident delay impact. Depending on the hazard level on the route, the
percentage reduction in response time is estimated to calculate the expected
incident duration and delay.

Figure 12: Percentage reduction in uncertainty of posterior with UAV active
sensing of incident location.

Figure 12 assess the level of improvement in incident delay estimation by
evaluating the percentage reduction in uncertainty of the total delay when
there are observations of incident location by the UAVs. Considering three
UAVs, we observe a significant reduction in the estimated total delay ranging
between 5 and 45% for the different number of incidents. UAV actively sensing
the incident locations provides enhanced observations used to update the
posterior estimates of the expected delay impact as described in Equations 5
and 7.

Considering three emergency vehicles, we evaluate the performance of the
proposed model against the conventional model in multiple experiments. Each
experiment has different sequences of incident requests. We consider five
incident request stages for which new incident numbers are reported.

Table 2: Comparison of total incident delay (vehicle hours) for three models for different sequences of incident request Scenario | Conventional TIM | P-DRONETIM | OPT
---|---|---|---
3,2,2,2,1 | 72002 | 68200 | 62200
2,2,2,1,2 | 70330 | 60300 | 58211
4,2,1,3,3 | 75000 | 63200 | 60235
5,3,4,2,2 | 88430 | 78500 | 68112
1,3,5,2,1 | 73500 | 71500 | 65170
2,5,1,1,3 | 74340 | 70100 | 65981
3,3,3,2,1 | 73800 | 69501 | 63730

For example, in Table 2, scenario one (3,2,2,2,1) indicates that three
incidents were reported in the first stage, followed by two in the next stage,
in that order. The total incident delay for the deployment solution for three
models is presented. First, the conventional TIM model makes current stage
decisions without considering near-future stage decisions. Second, the
proposed P-DRONETIM considers the near-future stage decisions when making the
current stage decision. Finally, the optimal strategy model (OPT) assumes
knowledge of the exact dependencies and sequences of the incident and thus
makes the best deployment decision.

As shown in Table 2, P-DRONETIM showed significant improvement when compared
to the conventional TIM. Specifically, the three emergency vehicles
successfully coordinated to find the best sequences of assignments in each
current stage. On average, P-DRONETIM reduced the total delay impact by
approximately 8% than the conventional TIM. The minimum and maximum
improvements were estimated as 3% and 15%, respectively. Compared to OPT,
P-DRONETIMs percentage improvement decreased, ranging between 3% and 13%, but
much worse when OPT is compared to conventional TIM (11% and 22%). OPT finds
the best deployment solution since it assumes knowledge of the exact sequence
of incident requests.

Figure 13 shows the runtime example for a scenario with five incident requests
in sequence (1,1,1,1,1) with no concurrent emergencies at different times.
Incidents requests one to four have a severity of 1, and incident request five
has a severity of 4. The response time estimates for the conventional TIM
model ranges between 3.6 min and 17.4 min, with a total response time of 62.4
min and a total estimated incident delay of 50022 vehicle hours. ERV1 is
dispatched to incident requests one, two, four, and five, and ERV2 to incident
requests three and four. Similarly, P-DRONETIM dispatched ERV1 to incident
requests one, two, four, and five and ERV2 to incident three.

Figure 13: Runtime example for two ERVs and UAVs for five incidents with
different request times.

However, ERV2 was relocated twice based on the estimated probability of
incident occurrences at the request times of incidents one and two. With this
look-ahead to anticipate the near-future incident, ERV2’s response time to
incident request three is drastically reduced since it is already in the
vicinity of incident request three. The total response time for P-DRONETIM is
estimated as 59.1 min, with a total incident delay of 45200 vehicle hours
representing a 5.28% reduction in total response time and 9.64% reduction in
total incident delay compared to the traditional TIM as DCOP strategy.

In OPT, ERV1 is dispatched to incident requests one, two, and four, and ERV2
dispatches ERV2 to incident requests three and five. Since OPT assumes to know
precisely where the incident will happen, it makes the best relocation
decisions at the different request times. The total response time and incident
delay for OPT is estimated as 51.5 min and 40520 vehicle hours. Compared to
OPT, P-DRONETIM’s percentage improvement in response and incident delay fell
short by 12% and 10%, but much worse when OPT is compared to conventional TIM
(17% and 19%).

##  8 CONCLUSIONS

Traditionally, traffic incident management programs coordinate the deployment
of emergency resources to immediate incident requests without anticipating
near future requests and the associated interdependencies in the network. In
this work, a new proactive and dynamic framework, P-DRONETIM, based on the
distributed constraint optimization problem, provides a roadmap for practical
resource allocation for highway incident management by accommodating
interdependencies in network events. Furthermore, the optimization objective
is formulated to accommodate near future stage decisions when making current
stage decisions. In addition, we develop a new framework for allocating UAVs
and coordinating their benefits for emergency vehicles’ response time to
incident locations and improving the estimates of the total delay impact.

The proposed framework is solved with the DCOP local search algorithms MGM and
DSA. In multiple experiments, P-DRONETIM showed satisfactory performance.
P-DRONETIM model actively relocates emergency vehicles to anticipate future
incidents to improve the overall response time to incident requests and showed
significant performance improvement compared to the conventional TIM.
Furthermore, coordinating the benefit of UAV assignment for ERVs resulted in
further improvement in performance.

Future research can enhance the allocation process for UAVs by accommodating
its routing decisions. For example, the routing decision can be modeled to
maximize the reduction in entropy for observed traffic parameters such as link
travel time [40, 41, 42], shockwave parameters, and discharge rate resulting
from an incident while en-route to an assigned location. In addition, to
optimize the monitoring of locations by UAVs and manage the limited resources,
a coordination constraint that considers deployments having overlapping
surface areas can be investigated. Such a constraint will limit the assignment
of UAVs to the same neighborhood.

## Acknowledgments

Funding for this research was provided by the NSF RI #1910397, NASA JPL RSA
#1625294, and USDOT University Transportation Centers (Contract
69A3551747125).

## References

  * [1] FHWA FSP Handbook Full-Function Service Patrol Concept.  https://ops.fhwa.dot.gov/publications/fhwahop08031/fsp4_0.htm, 2022\.  Online; accessed 29 January 2022.
  * [2] Farzad Daneshgar, Stephen P Mattingly, and Ali Haghani.  Evaluating beat structure and truck allocation for the tarrant county, texas, courtesy patrol.  Transportation research record, 2334(1):40–49, 2013.
  * [3] Hyoshin Park and Ali Haghani.  Real-time prediction of secondary incident occurrences using vehicle probe data.  Transportation Research Part C: Emerging Technologies, 70:69–85, 2016.
  * [4] N Pugh and H Park.  Prediction of secondary crash likelihood considering incident duration using high order markov model.  IEEE SoutheastCon, Huntsville, AL, pages 11–14, 2019.
  * [5] Next-generation tim: Integrating technology, data, and training.  https://www.fhwa.dot.gov/innovation/everydaycounts/edc_6/nextgen_tim.cfm, author="U.S. Department of Transportation/Federal Highway Administration", note=Online; accessed 4 December 2021, year=2021,.
  * [6] Pragnesh Jay Modi, Wei-Min Shen, Milind Tambe, and Makoto Yokoo.  Adopt: Asynchronous distributed constraint optimization with quality guarantees.  Artificial Intelligence, 161(1-2):149–180, 2005.
  * [7] William Yeoh and Makoto Yokoo.  Distributed problem solving.  AI Magazine, 33(3):53–53, 2012.
  * [8] Huang Deqi, Chu Xiumin, and Mao Zhe.  A simulation framework for emergency response of highway traffic accident.  Procedia Engineering, 29:1075–1080, 2012.
  * [9] Yafeng Yin.  Optimal fleet allocation of freeway service patrols.  Networks and Spatial Economics, 6(3):221–234, 2006.
  * [10] Yafeng Yin.  A scenario-based model for fleet allocation of freeway service patrols.  Networks and Spatial Economics, 8(4):407–417, 2008.
  * [11] Ping Wang, Jingwen Yang, Yinli Jin, and Jun Wang.  Research on allocation and dispatching strategies of rescue vehicles in emergency situation on the freeway.  In 2020 16th International Conference on Control, Automation, Robotics and Vision (ICARCV), pages 130–135. IEEE, 2020.
  * [12] Hyoshin Park, Deion Waddell, and Ali Haghani.  Online optimization with look-ahead for freeway emergency vehicle dispatching considering availability.  Transportation research part C: emerging technologies, 109:95–116, 2019.
  * [13] Darko Justice, Larkin Folsom, Niharika Deshpande, and Hyoshin Park.  Distributed constraint optimization problem for coordinated response of unmanned aerial vehicles and ground vehicles.  In 2021 55th Annual Conference on Information Sciences and Systems (CISS), 2021.
  * [14] U.S. Department of Transportation/Federal Aviation Administration.  Unmanned aircraft systems (uas).  https://www.faa.gov/uas/, 2021.  Online; accessed 8 April 2021.
  * [15] Anuj Puri.  A survey of unmanned aerial vehicles (uav) for traffic surveillance.  Department of computer science and engineering, University of South Florida, pages 1–29, 2005.
  * [16] Fatma Outay, Hanan Abdullah Mengash, and Muhammad Adnan.  Applications of unmanned aerial vehicle (uav) in road safety, traffic and highway infrastructure management: Recent advances and challenges.  Transportation research part A: policy and practice, 141:116–129, 2020.
  * [17] Navid Ali Khan, NZ Jhanjhi, Sarfraz Nawaz Brohi, Raja Sher Afgun Usmani, and Anand Nayyar.  Smart traffic monitoring system using unmanned aerial vehicles (uavs).  Computer Communications, 157:434–443, 2020.
  * [18] Jeffrey S Cox, Edmund H Durfee, and Thomas Bartold.  A distributed framework for solving the multiagent plan coordination problem.  In Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, pages 821–827, 2005.
  * [19] Jonathan P Pearce, Milind Tambe, and Rajiv Maheswaran.  Solving multiagent networks using distributed constraint optimization.  AI Magazine, 29(3):47–47, 2008.
  * [20] Thomas Léauté and Boi Faltings.  Distributed constraint optimization under stochastic uncertainty.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 25, 2011.
  * [21] Brian Cheung, Samuel Davey, and Douglas Gray.  Comparison of the pmht path planning algorithm with the genetic algorithm for multiple platforms.  In 2010 13th International Conference on Information Fusion, pages 1–8. IEEE, 2010.
  * [22] Pragnesh Jay Modi.  Distributed constraint optimization for multiagent systems.  PhD thesis, University of Southern California, 2003.
  * [23] Marius C Silaghi and Makoto Yokoo.  Nogood based asynchronous distributed optimization (adopt ng).  In Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, pages 1389–1396, 2006.
  * [24] Adrian Petcu and Boi Faltings.  Dpop: A scalable method for multiagent constraint optimization.  In IJCAI 05, number CONF, pages 266–271, 2005.
  * [25] Pragnesh Jay Modi, Wei-Min Shen, Milind Tambe, and Makoto Yokoo.  An asynchronous complete method for distributed constraint optimization.  In AAMAS, volume 3, pages 161–168. Citeseer, 2003.
  * [26] Rajiv T Maheswaran, Jonathan P Pearce, Milind Tambe, et al.  Distributed algorithms for dcop: A graphical-game-based approach.  In PDCS, pages 432–439, 2004.
  * [27] Robert Junges and Ana LC Bazzan.  Evaluating the performance of dcop algorithms in a real world, dynamic problem.  In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 2, pages 599–606, 2008.
  * [28] Alessandro Farinelli, Alex Rogers, and Nick R Jennings.  Agent-based decentralised coordination for sensor networks using the max-sum algorithm.  Autonomous agents and multi-agent systems, 28(3):337–380, 2014\.
  * [29] Alon Grubshtein, Roie Zivan, Tal Grinshpoun, and Amnon Meisels.  Local search for distributed asymmetric optimization.  In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1-Volume 1, pages 1015–1022, 2010.
  * [30] Zhengyu Yin, Christopher Kiekintveld, Atul Kumar, and Milind Tambe.  Local optimal solutions for dcop: New criteria, bound, and algorithm.  In Proc. of 8th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2009). Citeseer, 2009.
  * [31] Hyoshin Park and Ali Haghani.  Stochastic capacity adjustment considering secondary incidents.  IEEE Transactions on Intelligent Transportation Systems, 17(10):2843–2853, 2016.
  * [32] Highway capacity manual, transportation research board, 2010.
  * [33] Jibing Li, Chang-Jen Lan, and Xiaojun Gu.  Estimation of incident delay and its uncertainty on freeway networks.  Transportation research record, 1959(1):37–45, 2006.
  * [34] Jinjun Tang, Lanlan Zheng, Chunyang Han, Weiqi Yin, Yue Zhang, Yajie Zou, and Helai Huang.  Statistical and machine-learning methods for clearance time prediction of road incidents: A methodology review.  Analytic Methods in Accident Research, 27:100123, 2020.
  * [35] Mark Asch, Marc Bocquet, and Maëlle Nodet.  Data assimilation: methods, algorithms, and applications.  SIAM, 2016.
  * [36] Manual on classification of motor vehicle traffic accidents.  ANSI, 16:1–2007, 2007.
  * [37] Peter T Martin, Piyali Chaudhuri, Ivana Tasic, Milan Zlatkovic, and Tristan Pedersen.  Traffic incident management state of the art review.  Civil and Environmental Engineering, 2011.
  * [38] Gerard Tel.  Introduction to distributed algorithms.  Cambridge university press, 2000.
  * [39] Weixiong Zhang, Guandong Wang, Zhao Xing, and Lars Wittenburg.  Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks.  Artificial Intelligence, 161(1-2):55–87, 2005.
  * [40] Larkin Folsom, Masahiro Ono, Kyohei Otsu, and Hyoshin Park.  Scalable information-theoretic path planning for a rover-helicopter team in uncertain environments.  International Journal of Advanced Robotic Systems, 18(2):1729881421999587, 2021.
  * [41] Justice Darko, Larkin Folsom, Hyoshin Park, Masashi Minamide, Masahiro Ono, and Hui Su.  A sampling-based path planning algorithm for improving observations in tropical cyclones.  Earth and Space Science Open Archive, page 17, 2020.
  * [42] Hyoshin Park, Justice Darko, Niharika Deshpande, Vankesh Pandley, Hui Sui, Masahiro Ono, Dedrick Barkely, Derek Posselt, and Steven Chien.  Temporal multimodal multivariate learning (tmml).  In The SIG Knowledge Discovery and Data Mining (SIGKDD 2022) Conference, 2022.