# An accurate and efficient approach to probabilistic conflict prediction

Christian E. Roelofse<EMAIL_ADDRESS>Corné E. van Daalen
<EMAIL_ADDRESS>Department of Electrical and Electronic Engineering,
Stellenbosch University, Stellenbosch 7600

###### Abstract

Conflict prediction is a vital component of path planning for autonomous
vehicles. Prediction methods must be accurate for reliable navigation, but
also computationally efficient to enable online path planning. Efficient
prediction methods are especially crucial when testing large sets of candidate
trajectories. We present a prediction method that has the same accuracy as
existing methods, but up to an order of magnitude faster. This is achieved by
rewriting the conflict prediction problem in terms of the first-passage time
distribution using a dimension-reduction transform. First-passage time
distributions are analytically derived for a subset of Gaussian processes
describing vehicle motion. The proposed method is applicable to 2-D stochastic
processes where the mean can be approximated by line segments, and the
conflict boundary can be approximated by piece-wise straight lines. The
proposed method was tested in simulation and compared to two probability flow
methods, as well as a recent instantaneous conflict probability method. The
results demonstrate a significant decrease of computation time.

###### keywords:

conflict prediction, probabilistic methods, first-passage time, dimension
reduction, autonomous navigation

, ,

##  1 Introduction

Autonomous navigation is the process whereby a vehicle traverses an
environment without human intervention. This process can be construed as a
combination of mapping, localisation, and motion planning. The vehicle
localises itself in a map of its environment, and should plan a safe
trajectory through the map. However, this process is complicated by the
influence of uncertainty: unknown disturbances, measurement error, and
prediction uncertainty. Reliable conflict (or collision) prediction is
therefore an essential component of a motion planning subsystem.

A motion planner typically generates a large set of candidate trajectories for
the vehicle [1], which needs to be inspected for conflict to ensure safe
navigation. Conflict predictions need to be accurate to be reliable for the
purpose of navigation. However, since the computational cost associated with
conflict predication accumulates for each path tested, it needs to be
computationally efficient to allow for online autonomous navigation. Conflict
prediction methods can be divided into _deterministic_ and _probabilistic_
methods [2]. Deterministic methods produce a binary result and do not account
for uncertainty [3]. In contrast, probabilistic methods calculate the
probability of conflict, which accounts for uncertainty and allow for more
sophisticated risk reasoning [4]. The characteristics of two deterministic
methods (nominal and worst-case) and the probabilistic method are compared and
summarised in Table 1 [3]. Probabilistic methods are therefore preferable [2]
due to their ability to handle uncertainty; however, they are usually
computationally expensive.

Probabilistic conflict prediction is typically solved using either a sampling-
based, analytical or numerical approach. Sampling-based approaches (Monte
Carlo methods) allow for nonparametric distributions and nonlinear motion
models [4]. However, such methods tend to be expensive, even when using
techniques such as importance sampling [5]. Analytical approaches can result
in a closed-form solution, typically made possible by strict modelling
assumptions, or certain kinds of vehicle encounter conditions [6]. These
limitations are necessary to produce a closed-form expression, but are often
too restrictive to be used for most applications. Numerical approaches are
based on less strict assumptions, and use numerical techniques where needed
[7]. In general, the assumptions made by numerical approaches are not as
restrictive as those made by analytical approaches. Numerical approaches also
take advantage of specific choices of motion and noise models, unlike sampling
methods. Therefore, the cost of numerical techniques is not typically as
expensive as sampling. Three probabilistic solution approaches are summarised
in Table 1.

Table 1: Qualitative summary of conflict prediction methods and probabilistic
solution approaches. Descriptions are meant to be interpreted relative to the
descriptions of competitors. Prediction methods
---
Nominal |  Worst-case |  Probabilistic
Lower cost |  Moderate cost |  Higher cost
Disregards uncertainty |  Deterministically accounts for uncertainty |  Accounts for uncertainty
Uses nominal path |  Uses worst-case path envelope |  Uses sample paths
Optimistic |  Pessimistic |  More realistic
Probabilistic solution approaches
Analytical |  Sampling |  Numerical
Restrictive assumptions |  Minimal assumptions |  Moderate assumptions
Lower cost |  Higher cost |  Moderate cost
Accuracy varies111Varies depending on the degree to which the assumptions conform to the application. |  Accurate |  Accuracy varies111Varies depending on the degree to which the assumptions conform to the application.

Two examples of probabilistic prediction methods, which both use a numerical
solution, are probability flow (PF) and instantaneous conflict probability
(ICP). The PF method of van Daalen and Jones [2] is a fast, upper bound method
that numerically integrates the rate of probability mass flowing over the
conflict boundary (CB). Park and Kim devised a new method that separates PF
into drift and diffusion components, which are likewise integrated over the CB
[8]. ICP methods calculate the instantaneous overlap of probability mass and
the conflict region over time, which is used to calculate conflict
probability. The rectangular region approximation method of Pour et al. [9] is
a recent example of an ICP method.

The focus of this article is the derivation of an efficient, probabilistic
prediction method. The envisioned application is general autonomous
navigation, which requires efficient conflict prediction to avoid a
computational bottleneck in the motion planner. However, the proposed method
can also be used in other contexts, such as advisory systems for piloted
vehicles. The derivation presented uses a novel application of the first-
passage time (FPT) metric with a dimension-reduction approach, applied to a
subset of Gaussian processes. The proposed method is a numerical approach
where the conflict prediction problem is rewritten in terms of the FPT
distribution, which makes use of analytically derived FPT expressions. The
dimension-reduction is achieved by using line segments as conflict boundaries,
which can be used to construct an arbitrary boundary shape. The proposed
method is applicable to 2-D scenarios where the vehicle’s mean motion can be
approximated by line segments, and the conflict boundary can be approximated
by piece-wise line segments. The state distribution of the vehicle also needs
to drift or diffuse in the direction of the conflict boundary.

The rest of the article is organised as follows: Section 2 outlines the
problem formulation, then Section 3 gives an overview of the first-passage
time problem. Sections 4 and 5 presents the solution formulation and
derivation. Finally, Section 6 ends with a simulation comparison, highlighting
the performance of the proposed method.

##  2 Problem Formulation

Before the solution development is presented, some problem-specific
assumptions are stated along with a definition of the problem. The research
presented is intended to function in a _decentralised_ , non-cooperative
context [10]. All vehicles are assumed to behave _independently_ , which means
that the predicted states of other vehicles are the same for all possible
planned trajectories, and that the other vehicles do not react to the chosen
trajectory, or subsequent manoeuvring. The vehicle and environment are assumed
to be _state observable_ [5]: the states can be estimated from the available
information. Vehicle state estimates are chosen to be Gaussian distributed,
which is typical for problem definitions involving vehicle motion [2, 6, 11],
and the noise that models the influence of disturbances is white, uncorrelated
and zero-mean. The noise approximates the effects of disturbances such as wind
on the vehicle.

This research considers _conflict_ prediction: predicting the violation of a
user-defined, minimum separation, in contrast to _collision_ prediction [2].
This keep-out region defines a conflict region set $\bm{\mathcal{D}}$ in the
environment. Nevertheless, the solution presented in this article can be used
for collision prediction, since collision by definition entails conflict. The
desired output of conflict prediction is the probability $\mathbb{P}_{C}$ that
a vehicle will enter a conflict region $\bm{\mathcal{D}}$ over a finite
prediction period $t_{H}$. Starting from $t=0$, the conflict outcomes can be
expressed as a set [2]

$\displaystyle A_{t_{H}}=\\{\omega\in\Omega\ :\ \exists\ t_{C}\in[0,t_{H}],\
\mathbf{R}(t_{C},\omega)\in\bm{\mathcal{D}}\\},$ (1)

where $\omega\in\Omega$ represents a stochastic trajectory outcome and
$\mathbf{R}(t,\omega)$ denotes the position state of a vehicle. Therefore, the
probability of conflict can be expressed as

$\displaystyle\mathbb{P}_{C}(t_{H})=P[A_{t_{H}}].$ (2)

The vehicle is assumed to be a point mass with Gaussian state uncertainty. The
conflict region $\bm{\mathcal{D}}$ is assumed to have no uncertainty. The
problem description and assumptions can be related to a more realistic problem
definition by making appropriate transforms; the uncertainty of both the
vehicle position and the conflict region position can be combined into a
single equivalent source of uncertainty, centred on the vehicle. The volume of
the vehicle can be used to define a keep-out region centred on the vehicle. As
such, the keep-out region of the vehicle can likewise be combined with that of
the conflict region in the environment. These transforms result in an
equivalent problem description: calculating the conflict probability of a
point mass with uncertain state, with respect to a certain, combined conflict
region [12]. This region can be determined for arbitrary shapes using
Minkowski summation. Before the solution is formulated, the FPT problem is
discussed.

##  3 First-passage time

The conflict prediction solution presented in this article is inspired by the
_first-passage time (FPT) problem_ [13]. This problem can be expressed as:
given a point mass under the influence of noise – a stochastic process – when
will this point mass cross or hit a given boundary for the first time?
Historically, the problem is well known for its formulation in the context of
Brownian diffusion processes [13].

The FPT $\tau_{\bm{\mathcal{C}}}$, with reference to a conflict boundary (CB)
set $\bm{\mathcal{C}}$ which bounds a conflict region $\bm{\mathcal{D}}$,
$\bm{\mathcal{C}}\in\bm{\mathcal{D}}$, in $n$ dimensions, can be expressed as
[14]

$\displaystyle\tau_{\bm{\mathcal{C}}}(\omega)=\text{inf}\
\\{t\in\mathbb{R}^{+}\ |\ \mathbf{R}(t,\omega)\in\bm{\mathcal{C}}\\},$ (3)

where inf represents the _infimum function_ [14]. $\mathbf{R}$ is assumed to
be a continuous process without discontinuities, therefore the conflict region
$\bm{\mathcal{D}}$ cannot be entered without the vehicle touching the CB
$\bm{\mathcal{C}}$. The outcome $\omega\in\Omega$ can be thought of as an
indicator function for a given stochastically generated trajectory
$\mathbf{r}(t)$ [2]. The first-passage time is therefore a mapping of the
stochastic outcomes to a nonnegative time
$\tau_{\bm{\mathcal{C}}}\in\mathbb{R}^{+}$,
$\tau_{\bm{\mathcal{C}}}:\Omega\to[0,\ \infty)$.

###  3.1 First-passage time as a conflict metric

The FPT is a useful metric for conflict prediction because it can be used to
model the uncertainty of crossing a CB for the first time. The FPT can be used
to determine the probability of a conflict event $\mathbb{P}_{C}$ by
integrating the first-passage time distribution (FPTD). This probability, over
a prediction interval of $[0,t]$, can be expressed as

$\displaystyle\mathbb{P}_{C}(t)=\bigintssss_{0}^{t}f_{\tau}(s)\ ds,$ (4)

where $f_{\tau}(s)$ denotes the FPTD and $s$ is an integration variable.

###  3.2 Modelling first-passage time distribution

Modelling the FPTD for the purpose of conflict prediction can be difficult,
given that the distribution is a function of the vehicle motion model, as well
as the shape of the CB. As the CB shape becomes more arbitrary and higher
dimensional, the FPTD becomes more difficult to describe analytically. In the
field of stochastic processes, much effort has been put into 1-D cases [15],
where the CB is a 1-D point. However, for the purpose of autonomous
navigation, a 2-D problem definition (at minimum) is required in order to be
useful. FPTDs have been derived for 2-D cases [16], but they tend to not have
closed-form solutions [17]. A CB consisting of two perpendicular lines has
been used to produce an analytical solution [18], but only for specific
choices of correlation coefficients [19]. These CBs are also quite restrictive
and therefore not as useful in general. Given these challenges, a FPT
derivation that yields an analytical solution, while not being restrictive in
application, is desirable. The solution formulated in this article uses a FPT
derivation in the context of reduced-order dynamics (dimension-reduction),
that both has an analytical solution and is modular in application.

##  4 General solution formulation

In this section, we outline our approach and present our solution formulation,
which makes use of the FPT. Our solution follows a dimension-reduction
approach, illustrated by Fig. 1, resulting in significant computational
savings. Our dimension-reduction approach calculates the probability of
conflict for a straight line segment that forms a section of a CB in 2-D. If a
given 2-D CB can be approximated with a set of line segments, then the
conflict probability can be determined for each line segment. These results
can then be summed, yielding an approximation of the probability of conflict.

The stochastic process describing the vehicle’s motion can be reduced to a 1-D
process:

$\displaystyle R_{\mathbf{n}}(t,\omega)=\mathbf{R}(t,\omega)\cdot\mathbf{n},$
(5)

where $\mathbf{n}$ is defined as a unit vector normal to the CB. The dimension
reduction of Equation 5 represents the general case, whereas dimension
reduction results for a specific class of stochastic processes are presented
in Section 5. The resultant 1-D process is therefore normal to the conflict
line, and is treated as a FPT problem. This 1-D conflict problem is equivalent
to a 2-D conflict problem relative to an infinite line $\bm{\mathcal{C}}_{I}$.
However, integrating the FPTD $f_{\tau_{\bm{\mathcal{C}}_{I}}}$ does not yield
a useful result, since we are not interested in determining the probability of
crossing an infinite line $\bm{\mathcal{C}}_{I}$, but only a line segment
$\bm{\mathcal{C}}$. To solve this problem we use the product of the FPTD and
the state uncertainty, and integrate over the subset of interest
$\bm{\mathcal{C}}$, as described in the next subsection.

Figure 1: Illustration of dimension-reduction in 2-D, mapping the stochastic
process to 1-D. Shown is a sample trajectory, where the red dot is the point
of conflict on the trajectory at time $\tau_{\bm{\mathcal{C}}_{I}}$, and
$t_{H}$ denotes the prediction period (lookahead time). The stochastic process
is reduced to a 1-D process that is normal to the line $\bm{\mathcal{C}}_{I}$,
$\mathbf{n}$ being a unit vector normal to and pointing away from
$\bm{\mathcal{C}}_{I}$. This mapping is illustrated with dotted lines.
$\bm{\mathcal{C}}_{I}$ denotes an infinite line, represented by a dashed line,
while $\bm{\mathcal{C}}$ denotes the segment of interest,
$\bm{\mathcal{C}}\subset\bm{\mathcal{C}}_{I}$.

###  4.1 Derivation of probability of conflict using FPT and state uncertainty

This subsection presents the derivation of the proposed method to calculate
the conflict probability, which is used with the FPTD derivation in the next
section. The probability of conflict over the prediction period $t_{H}$,
relative to the CB $\bm{\mathcal{C}}_{I}$, can be expressed as

$\displaystyle\mathbb{P}^{\bm{\mathcal{C}}_{I}}_{C}=\int_{0}^{t_{H}}f_{\tau_{\bm{\mathcal{C}}_{I}}}(t)\
dt.$ (6)

The FPTD $f_{\tau_{\bm{\mathcal{C}}_{I}}}$ in Equation 6 can be expressed as
the marginal of a joint distribution $f_{\mathbf{R}(t),\tau}$ over the vehicle
position and FPT as

$\displaystyle
f_{\tau_{\bm{\mathcal{C}}_{I}}}(t)=\int_{\mathbb{R}^{2}}f_{\mathbf{R}(t),\tau}\big{(}\mathbf{r}(t),t\big{)}\
d\mathbf{r}.$ (7)

Since $\tau=t$ means that the vehicle is on the CB,
$\mathbf{r}(t)\in\bm{\mathcal{C}}_{I}$, Equation 7 can be expressed as

$\displaystyle
f_{\tau_{\bm{\mathcal{C}}_{I}}}(t)=\int_{\mathbb{R}^{2}\in\bm{\mathcal{C}}_{I}}f_{\mathbf{R}(t),\tau}\big{(}\mathbf{r}(t),t\big{)}\
d\mathbf{r}.$ (8)

Equation 6 can therefore be expressed as

$\displaystyle\mathbb{P}^{\bm{\mathcal{C}}_{I}}_{C}$
$\displaystyle=\int_{0}^{t_{H}}f_{\tau_{\bm{\mathcal{C}}_{I}}}(t)\ dt$ (9)
$\displaystyle\mathbb{P}^{\bm{\mathcal{C}}_{I}}_{C}$
$\displaystyle=\int_{0}^{t_{H}}\int_{\mathbb{R}^{2}\in\bm{\mathcal{C}}}f_{\mathbf{R}(t),\tau}\big{(}\mathbf{r}(t),t\big{)}\
d\mathbf{r}\ dt$ $\displaystyle+\int_{0}^{t_{H}}\int_{\mathbb{R}^{2}\in\
\bm{\mathcal{C}}_{I}\backslash\bm{\mathcal{C}}}f_{\mathbf{R}(t),\tau}\big{(}\mathbf{r}(t),t\big{)}\
d\mathbf{r}\ dt.$ (10)

The spatial integral is separated over two mutually exclusive sets: the line
segment of interest $\bm{\mathcal{C}}$, and the remainder of the infinite line
$\bm{\mathcal{C}}_{I}\backslash\bm{\mathcal{C}}$. For the purpose of conflict
prediction, we are interested in counting the first crossings of
$\bm{\mathcal{C}}_{I}$ over the subset $\bm{\mathcal{C}}$, therefore we set

$\displaystyle\mathbb{P}^{\bm{\mathcal{C}}}_{C}=\int_{0}^{t_{H}}\int_{\mathbb{R}^{2}\in\bm{\mathcal{C}}}f_{\mathbf{R}(t),\tau}\big{(}\mathbf{r}(t),t\big{)}\
d\mathbf{r}\ dt.$ (11)

Using the definition of conditional probability distributions, Equation 11 can
be expressed as

$\displaystyle\mathbb{P}^{\bm{\mathcal{C}}}_{C}=\int_{0}^{t_{H}}\int_{\mathbb{R}^{2}\in\bm{\mathcal{C}}}f_{\mathbf{R}(t)}\big{(}\mathbf{r}(t)\
|\tau=t\big{)}f_{\tau_{\bm{\mathcal{C}}_{I}}}(t)\ d\mathbf{r}\ dt.$ (12)

The PDF $f_{\mathbf{R}(t)}\big{(}\mathbf{r}(t)\ |\tau=t\big{)}$ is called the
first-crossing distribution (FCD), denoted by $f_{\Phi}(\mathbf{r}(t))$. The
first crossing $\Phi$ is the position on $\bm{\mathcal{C}}_{I}$ where the
vehicle crosses the CB for the first time. We now introduce an important
approximation: the FCD is similar to the conditional state distribution,
conditioned on the CB. In most cases this approximation is accurate due to the
fact that at the FPT, the vehicle is on the CB by definition, assuming
absolutely continuous trajectories. However, this substitution is not exact,
given that the vehicle could be on the CB after the FPT (second crossings
etc.). However, we expect that it is unlikely for the vehicle to return to the
CB after the FPT in typical autonomous navigation applications. This
approximation can be expressed as

$\displaystyle\\!\\!\\!\\!f_{\Phi}(\mathbf{r}(t))$
$\displaystyle=f_{\mathbf{R}(t)}\big{(}\mathbf{r}(t)|\ \tau=t\big{)}$
$\displaystyle\approx f_{\mathbf{R}(t)}\big{(}\mathbf{r}(t)|\
\mathbf{r}(t)\in\bm{\mathcal{C}}_{I}\big{)}=f_{\Phi}(\mathbf{r}(t))^{*},$ (13)

for short and results in an approximation to the probability of conflict:

$\displaystyle\mathbb{P}^{\bm{\mathcal{C}}}_{C}$
$\displaystyle\approx\int_{0}^{t_{H}}\int_{\mathbb{R}^{2}\in\bm{\mathcal{C}}}f_{\mathbf{R}(t)}\big{(}\mathbf{r}(t)\
|\mathbf{r}(t)\in\bm{\mathcal{C}}_{I}\big{)}f_{\tau_{\bm{\mathcal{C}}_{I}}}(t)\
d\mathbf{r}\ dt$
$\displaystyle=\int_{0}^{t_{H}}f_{\tau_{\bm{\mathcal{C}}_{I}}}(t)\int_{\mathbb{R}^{2}\in\bm{\mathcal{C}}}f_{\Phi}(\mathbf{r}(t))^{*}\
d\mathbf{r}\ dt.$ (14)

At each moment $t$ in time, the conditional state distribution is conditioned
on and integrated over the CB. This result is then weighed by the likelihood
that $t$ is in fact the FPT. Therefore, the FPTD acts like a time-dependent
weighting function. Once the inner integral in Equation 4.1 is calculated, the
resultant expression consists of a single numerical integral over time.
Equation 4.1 uses a 1-D FPTD which is derived in Section 6. The inner integral
in Equation 4.1 can be calculated analytically using the conditional state
cumulative distribution function (CDF) for a specific class of models,
outlined in the next section.

##  5 State space models

We are interested in stochastic processes that will result in a closed-form
expression for the inner integral in Equation 4.1, as well as an analytical
result for the FPTD in Section 6. Useful models that satisfy these
requirements are a class of linear, Gaussian, time-invariant, continuous
models. We focus on these models for the rest of the article and refer to this
class of models as the vehicle motion model. These models are often used to
approximate vehicle motion [20, 21, 22]. Such a model can be expressed in
terms of a stochastic differential equation [23]

$\displaystyle\\!\\!\\!\mathbf{\dot{X}}(t,\omega)\\!=\\!\mathbf{A}(t)\mathbf{X}(t,\omega)+\mathbf{B}(t)\mathbf{u}(t)+\mathbf{B}_{\eta}(t)\boldsymbol{\eta}(t,\omega),$
(15)

where $\mathbf{X}(t,\ \omega)$ is a vector of stochastic processes.
$\boldsymbol{\eta}(t,\ \omega)$ is a vector of zero-mean, Gaussian, white
noise. $\mathbf{A}(t)$ denotes the state matrix, $\mathbf{u}(t)$ the control
input, $\mathbf{B}(t)$ the input matrix, and $\mathbf{B}_{\eta}(t)$ the noise
input matrix. The solution to Equation 15, starting from $t=0$, is [23, 24]

$\displaystyle\mathbf{X}(t,\ \omega)$ $\displaystyle=\boldsymbol{\Psi}(t)\
\mathbf{X}(0,\ \omega)+\bigintssss_{0}^{t_{H}}\boldsymbol{\Psi}(t)\
\mathbf{B}(t)\ \mathbf{u}(t)\ dt$
$\displaystyle+\bigintssss_{0}^{t_{H}}\mathbf{B}_{\eta}(t)\ d\textbf{W}(t,\
\omega),$ (16)

where $\boldsymbol{\Psi}(t)$ denotes the state transition matrix. The final
integral $\bigintssss\cdot\ d\textbf{W}$ denotes an Ito-integral over a
differential increment in an extended Wiener process [24], with a diffusion
matrix $\textbf{Q}(t)$. The model consists of linear transforms and Gaussian
distributed noise; if the initial states are Gaussian distributed,
$\mathbf{X}(0,\ \omega)\sim\mathcal{N}\Big{(}\ \mathbf{m}(0)\ ,\
\textbf{C}(0)\Big{)}$, then all subsequent states are jointly Gaussian
distributed [12],

$\displaystyle\mathbf{X}(t,\ \omega)\sim\mathcal{N}\Big{(}\ \mathbf{m}(t)\ ,\
\textbf{C}(t)\Big{)}.$ (17)

The position $\mathbf{R}(t,\ \omega)=[R_{X}(t,\ \omega),\ R_{Y}(t,\
\omega)]^{T}$ and velocity states $\mathbf{V}(t,\ \omega)$ constitute the
state vector:

$\displaystyle\mathbf{X}(t,\ \omega)=\Big{[}\mathbf{R}(t,\ \omega)\ ,\
\mathbf{V}(t,\ \omega)\Big{]}^{T},$ (18)

and therefore

$\displaystyle\\!\\!\\!\\!\mathbf{X}(t,\ \omega)\sim\mathcal{N}\bigg{(}\
\\!\\!\begin{bmatrix}\mathbf{m}_{\mathbf{R}}(t,\omega)\\\
\mathbf{m}_{\mathbf{V}}(t,\omega)\end{bmatrix},\\!\begin{bmatrix}\textbf{C}_{\textbf{R}}(t)&\textbf{C}_{\textbf{RV}}(t)\\\
\textbf{C}^{T}_{\textbf{RV}}(t)&\textbf{C}_{\textbf{V}}(t)\end{bmatrix}\bigg{)}.$
(19)

Using the model in Equation 5, the state mean $\mathbf{m}(t)$ and covariance
$\textbf{C}(t)$ can be derived analytically. The mean and covariance can also
be calculated in a tractable manner if Equation 15 is discretised in terms of
$t$. The discrete equivalent model can be used to recursively calculate the
mean and covariance at sample times [23].

For a horizontal conflict boundary $\bm{\mathcal{C}}$ with end points
$(x_{\bm{\mathcal{C}}1,}y_{\bm{\mathcal{C}}})$ and
$(x_{\bm{\mathcal{C}}2},y_{\bm{\mathcal{C}}})$, the conditional state
distribution in Equation 4.1 can be expressed as a Gaussian distribution:

$\displaystyle f_{\Phi}$
$\displaystyle(\mathbf{r}(t))^{*}\sim\mathcal{N}\Big{(}\
m_{R_{X}|R_{Y}}(t),C_{R_{X}|R_{Y}}(t)\Big{)}\ $
$\displaystyle=\mathcal{N}\Big{(}\
m_{R_{X}}(t)+(y_{\bm{\mathcal{C}}}-m_{R_{Y}}(t))C_{R_{Y}R_{X}}(t)/C_{R_{Y}}(t),$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \
C_{R_{X}}(t)-C^{2}_{R_{Y}R_{X}}(t)/C_{R_{Y}}(t)\Big{)}.$ (20)

Any problem definition can be transformed so that that the conflict boundary
is horizontal, allowing for convenient conditional state mean and variance
calculations. Therefore, assuming a horizontal conflict boundary, and using
the Gaussian nature of the conditional state distribution, the inner integral
in Equation 4.1 can be calculated using error functions as

$\displaystyle\int_{\mathbb{R}^{2}\in\bm{\mathcal{C}}}f_{\Phi}(\mathbf{r}(t))^{*}\
d\mathbf{r}$
$\displaystyle=\frac{1}{2}\bigg{[}\text{erf}\Big{(}\frac{x_{\bm{\mathcal{C}}2}-m_{R_{X}|R_{Y}}(t)}{\sqrt{2C_{R_{X}|R_{Y}}(t)}}\Big{)}$
$\displaystyle-\text{erf}\Big{(}\frac{x_{\bm{\mathcal{C}}1}-m_{R_{X}|R_{Y}}(t)}{\sqrt{2C_{R_{X}|R_{Y}}(t)}}\Big{)}\bigg{]}.$
(21)

Using dimension reduction (Equation 5), and the dot product formulation of the
affine transformation of a normal random variable, the resultant Gaussian
process (Equation 17) can be shown to reduce to

$\displaystyle R_{\mathbf{n}}(t,\ \omega)\sim\mathcal{N}\Big{(}\
\mathbf{m}_{\mathbf{R}}(t)\cdot\mathbf{n}\ ,\
\mathbf{n}^{T}\textbf{C}_{\textbf{R}}(t)\mathbf{n}\Big{)},\text{ and}$ (22)
$\displaystyle V_{\mathbf{n}}(t,\ \omega)\sim\mathcal{N}\Big{(}\
\mathbf{m}_{\mathbf{V}}(t)\cdot\mathbf{n}\ ,\
\mathbf{n}^{T}\textbf{C}_{\textbf{V}}(t)\mathbf{n}\Big{)}.$ (23)

In this way the vehicle’s state uncertainty can be modelled in 1-D and used
for the FPTD. The derivation of the FPTD in the next section uses the motion
model reduced to 1-D (Equations 22 and 23), as described by Equation 5.

##  6 FPTD for state space models

This section derives the FPTD for linear, Gaussian, 1-D motion models used to
characterise $f_{\tau_{\bm{\mathcal{C}}_{I}}}(t)$ in Equation 4.1. Additional
assumptions are made that the mean of the velocity is constant, and that the
mean position of the vehicle relative to the conflict boundary is a linear
function of time. The constant mean velocity makes the model applicable for
vehicles that are not accelerating in the mean; instances of acceleration
induced by noise do not invalidate this assumption. The mean position being a
linear function of time makes the model applicable for any mean motion that
can be modelled or approximated as piece-wise straight line segments. The 1-D
stochastic process was obtained by reducing the full state stochastic process
(Equation 19) using dimension-reduction (Equations 22 and 23). The resultant
linear dynamics, with Gaussian distributed noise and additional assumptions,
can be expressed as a Gaussian process with time-dependent mean and variance
as

$\displaystyle R_{\mathbf{n}}(t,\omega)$
$\displaystyle\sim\mathcal{N}\Big{(}m(t)\ ,\ c(t)\Big{)}$
$\displaystyle=\mathcal{N}\Big{(}\mu t+r_{\mathbf{n}}(0)\ ,\
c(t)\Big{)}=f_{R_{\mathbf{n}}}(r_{\mathbf{n}}(t)).$ (24)

The mean $m(t)$ is also assumed to be a linear function of time, where $\mu$
denotes the drift factor, which corresponds to the mean of the velocity. The
variance is left generic, since its form depends on whether the model uses
feedback control (closed-loop), or not (open-loop)

The FPTD derivation starts by creating an unnormalised distribution
$f_{R_{\mathbf{n}}}^{*}(r_{\mathbf{n}}(t)\ |\ \alpha,\ r_{\mathbf{n}}(0))$
that matches the 1-D position-state distribution $f_{R_{\mathbf{n}}}$, but
also satisfies an absorbing boundary condition:
$f_{R_{\mathbf{n}}}^{*}(r_{\mathbf{n}}=\alpha)=0$. $\alpha$ denotes the CB
point in 1-D. $f_{R_{\mathbf{n}}}^{*}$ models the distribution of position
states that have not experienced conflict, in contrast to
$f_{R_{\mathbf{n}}}$, which does not account for prior conflict. The
distribution $f_{R_{\mathbf{n}}}^{*}$ is zero at the CB $\alpha$, also
referred to as the _absorbing level_ in stochastic process literature [25].
This distribution will be used to calculate the survival CDF $F_{S}$, which
will be used to calculate the FPTD. Fig. 2. illustrates the approach, which is
known as the _method of imaging_ [19, 25]. A negative distribution, which is
also spaced a distance of $|\alpha-r_{\mathbf{n}}(0)|$ from the absorbing
point $\alpha$, is used to ensure that the absorbing condition
$f_{R_{\mathbf{n}}}^{*}(\alpha)=0$ is met. As the positive distribution state
distribution drifts toward the absorbing point from the left, the negative
distribution drifts at the same mean rate $|\mu|$ from the right, causing
$f_{R_{\mathbf{n}}}^{*}(\alpha)=0\text{,}\ \forall\ t$.

Figure 2: Illustration of the imaging method [19], which satisfies the
boundary condition. $\alpha$ denotes the CB and $r_{\mathbf{n}}(0)$ denotes
the initial condition. Both means of the Gaussian distributions start at a
distance $|\alpha-r_{\mathbf{n}}(0)|$ from the CB $\alpha$.

The resultant distribution can be expressed as [25]

$\displaystyle f_{R_{\mathbf{n}}}^{*}(r_{\mathbf{n}}|\ \alpha,\
r_{\mathbf{n}}(0))=\frac{1}{\sqrt{2\pi
c(t)}}\Bigg{[}\text{exp}\Bigg{(}\frac{-\big{(}r_{\mathbf{n}}-m(t)\big{)}^{2}}{2c(t)}\Bigg{)}$
$\displaystyle\ \ \ \ \ \ \ \
-\text{exp}\Bigg{(}\frac{-\big{(}r_{\mathbf{n}}-(2\alpha-m(t))\big{)}^{2}}{2c(t)}\Bigg{)}\Bigg{]}\text{,}\
r_{\mathbf{n}}\leq\alpha,$ (25) $\displaystyle\text{or}\ \
f_{R_{\mathbf{n}}}^{*}(r_{\mathbf{n}}|\ \alpha,\ r_{\mathbf{n}}(0))=0,\
r_{\mathbf{n}}>\alpha.$

Note that the variances are the same, but the means are defined in such as way
as to cause the mirrored distributions to move toward each other. As they
move, their means maintain the same distance from the CB, on both sides of
$\alpha$. The distribution $f_{R_{\mathbf{n}}}^{*}$ is approximately
normalised if the Gaussian images are far away from the absorbing point or
have a small variance. As the Gaussian images move toward the absorbing point,
the distribution $f_{R_{\mathbf{n}}}^{*}$ becomes less normalised. The rate at
which it deviates from being normalised is a function of the mean and variance
of of the vehicle. Therefore, Equation 6 is a poor approximation for problem
definitions with large uncertainty, with means close to the absorbing point.

###  6.1 Survival cumulative distribution

The next step is to relate the distribution to the survival metric, survival
being defined as not yet having reached the CB $\alpha$. The survival CDF
$F_{S}(t)$, which is related to the FPTD, can be derived as [25]

$\displaystyle
F_{S}(t)=\mathbb{P}[R_{\mathbf{n}}<\alpha]=\int_{-\infty}^{\alpha}f_{R_{\mathbf{n}}}^{*}(r_{\mathbf{n}}|\
\alpha,\ r_{\mathbf{n}}(0))\ dr_{\mathbf{n}}$ (26)
$\displaystyle=\frac{1}{\sqrt{2\pi
c(t)}}\Bigg{[}\bigintssss_{-\infty}^{\alpha}\text{exp}\Bigg{(}\frac{-\big{(}r_{\mathbf{n}}-m(t)\big{)}^{2}}{2c(t)}\Bigg{)}dr_{\mathbf{n}}$
$\displaystyle\ \ \ \ \ \
-\bigintssss_{-\infty}^{\alpha}\text{exp}\Bigg{(}\frac{-\big{(}r_{\mathbf{n}}-(2\alpha-m(t))\big{)}^{2}}{2c(t)}\Bigg{)}dr_{\mathbf{n}}\Bigg{]}.$
(27)

The probability mass of $f_{R_{\mathbf{n}}}^{*}$ corresponds to the portion of
$f_{R_{\mathbf{n}}}$ that has not yet experienced conflict prior to the
current moment $t$, and therefore represents the survival probability. Using
variable substitutions $u=(r_{\mathbf{n}}-m(t))/\sqrt{2c(t)}$ and
$v=(r_{\mathbf{n}}-2\alpha+m(t))/\sqrt{2c(t)}$, $c(t)\neq 0,\ \forall\ t$, and
dividing both of the integration bounds at zero, both integrals over
$[-\infty,0]$ cancel out, and Equation 27 reduces to

$\displaystyle F_{S}($ $\displaystyle
t)=\frac{1}{\sqrt{\pi}}\Bigg{[}\int_{0}^{u(\alpha)}e^{-u^{2}}du-\int_{0}^{v(\alpha)}e^{-v^{2}}dv\Bigg{]}.$
(28)

Equation 28 can now be expressed as

$\displaystyle\\!\\!F_{S}$
$\displaystyle(t)\\!\\!=\\!\\!\frac{1}{2}\Bigg{[}\text{erf}\bigg{(}\frac{\alpha-m(t)}{\sqrt{2c(t)}}\bigg{)}-\text{erf}\bigg{(}\frac{-(\alpha-m(t))}{\sqrt{2c(t)}}\bigg{)}\Bigg{]}.$
(29)

Given that the error function is an uneven function,
$\text{erf}(-x)=-\text{erf}(x)$, the survival CDF reduces to

$F_{S}(t)=\text{erf}\bigg{(}\frac{\alpha-m(t)}{\sqrt{2c(t)}}\bigg{)}\text{,}\
\alpha-m(t)>0.$ (30)

The survival CDF can be related to the FPTD $f_{\tau}(t)$ as [25]

$f_{\tau}(\ t)=-\frac{dF_{S}(t)}{dt}.$ (31)

Using the expression for the survival CDF, Equation 30, the FPTD $f_{\tau}(\
t)$ can be derived using the chain rule as

$\displaystyle f_{\tau}(t)$
$\displaystyle=-\frac{dF_{S}(t)}{dt}=\sqrt{\frac{2}{c(t)\pi}}\text{exp}\Bigg{(}\frac{-\Big{(}\alpha-m(t)\Big{)}^{2}}{2c(t)}\Bigg{)}\times$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\Bigg{(}\frac{(\alpha-m(t))\dot{c}(t)}{2c(t)}+\mu\Bigg{)},$ (32)

noting that $\dot{m}(t)=\mu$; the mean changes linearly as defined by Equation
6. The limitation of the method can be seen in Equation 6.1: the FPTD
collapses if both $\mu$ and $\dot{c}$ are zero, or is invalid if the second
factor is negative. After more specific models are explored next, the negative
factor is only an issue if the vehicle is not moving toward the conflict
boundary. A conflict prediction algorithm could inspect the mean movement
(relative to the CB) to determine if the method is useful, bearing in mind
that moving away from the CB poses minimal risk in most encounter scenarios.

###  6.2 Closed-loop scenario

The result in Equation 6.1 can be further refined by choosing appropriate
expressions for the variance $c(t)$. For a closed-loop system using a time-
invariant controller, the variance is regulated by means of feedback control,
causing it to settle at a steady-state value $c_{ss}$ after a while. From this
point the derivative is zero $\dot{c}(t)=0$. For typical applications the
variance would settle quickly; taking advantage of a constant (zero) variance
reduces Equation 6.1 to

$f_{\tau}(t)=\frac{2\mu}{\sqrt{2\pi
c_{ss}}}\text{exp}\Bigg{(}\frac{-\Big{(}\alpha-m(t)\Big{)}^{2}}{2c_{ss}}\Bigg{)},$
(33)

for closed-loop systems. Integrating $f_{\tau}(t)$ over all time
$0\rightarrow\infty$ results in

$\int_{0}^{\infty}f_{\tau}(t)dt=2,$ (34)

due to the choice of $f_{R_{\mathbf{n}}}^{*}$ in Equation 6. The FPTD is
normalised, resulting in

$f_{\tau}(t)=\frac{\mu}{\sqrt{2\pi
c_{ss}}}\text{exp}\Bigg{(}\frac{-\Big{(}\alpha-m(t)\Big{)}^{2}}{2c_{ss}}\Bigg{)}.$
(35)

Following the same derivation, but changing the illustration in Fig. 2 to a
$\alpha<r_{\mathbf{n}}(0)$ and $\mu<0$ scenario produces

$f_{\tau}(t)=\frac{-\mu}{\sqrt{2\pi
c_{ss}}}\text{exp}\Bigg{(}\frac{-\Big{(}\alpha-m(t)\Big{)}^{2}}{2c_{ss}}\Bigg{)}$
(36)

after normalisation. These two results can be put together as

$f_{\tau}(t)=\frac{|\mu|}{\sqrt{2\pi
c_{ss}}}\text{exp}\Bigg{(}\frac{-\Big{(}\alpha-m(t)\Big{)}^{2}}{2c_{ss}}\Bigg{)},$
(37)

which is the final form of the FPTD of closed-loop dynamics, with a linear
mean as defined by Equation 6.

###  6.3 Open-loop scenario

An open-loop model can be used to model dynamics that do not have any feedback
corrections. For example, Yang et al. [26] used an open-loop model to
represent the timing uncertainty of a flight manoeuvre used by a pilot
changing their flight path. For an open-loop system, the state distribution
can be defined as

$\displaystyle R_{\mathbf{n}}(t,\omega)$
$\displaystyle\sim\mathcal{N}\Big{(}m(t)\ ,\ c(t)\Big{)}$
$\displaystyle=\mathcal{N}\Big{(}\mu t+r_{\mathbf{n}}(0)\ ,\
\frac{1}{3}\sigma^{2}t^{3}\Big{)},$ (38)

where the variance is the closed-form solution of a linear state space model
with zero-mean Gaussian noise, with a constant mean velocity and an initial
zero covariance. $\sigma$ denotes the white noise strength. The expression
given in Equation 6.3 is a useful starting point; however, the work that
follows is without loss of generality, since the third order time $t^{3}$ is
the governing factor in the derivation. The FPTD can be determined from the
result in Equation 6.1:

$\displaystyle f_{\tau}(t)=-\frac{dF_{S}(t)}{dt}$
$\displaystyle=\frac{-2}{\sqrt{\pi}}\text{exp}\Bigg{(}\frac{-\big{(}\alpha-m(t)\big{)}^{2}}{2c(t)}\Bigg{)}\frac{d}{dt}\Bigg{(}\frac{(\alpha-m(t))}{\sqrt{(2c(t))}}\Bigg{)}.$
(39)

Using the model as defined by Equation 6.3 results in

$\displaystyle f_{\tau}(t)$
$\displaystyle=\text{exp}\Bigg{(}\frac{-\big{(}\alpha-m(t)\big{)}^{2}}{2c(t)}\Bigg{)}\frac{\sqrt{3t}(3a-\mu
t)}{\sqrt{2\pi}\sigma t^{3}},$ (40)

where $a=\alpha-r_{\mathbf{n}}(0)$. The distribution is only valid for
$t<\frac{3a}{\mu}$; outside this range the CDF is no longer monotonically
increasing. Equation 40 needs to be slightly altered in two ways; First,
Equation 40 needs to be altered to work for encounter scenarios where $a$ and
$\mu$ are negative $a<0$, $\mu<0$. This alteration can be done with an
absolute value function. Second, the expression needs a normalisation factor
so that the CDF tends to unity. This factor is the same as the closed-loop
case. Equation 6.3 can be expressed in its final form as

$\displaystyle f_{\tau}(t)$
$\displaystyle=\text{exp}\Bigg{(}\frac{-\big{(}\alpha-m(t)\big{)}^{2}}{2c(t)}\Bigg{)}\times\frac{\sqrt{3t}\
|3a-\mu t|}{2\sqrt{2\pi}\sigma t^{3}},$ (41)

for $t<\frac{3a}{\mu}$.Having derived the FPTD for open- and closed-loop
motion models as defined by Equation 6, Equation 4.1 can be used to
approximate the probability of conflict.

##  7 Simulation experiments

This section contains simulations of open-loop and closed-loop scenarios
illustrating the advantage of the proposed method. The proposed method is
compared to three existing methods: a probability flow (PF) method by van
Daalen and Jones [2], a more recent PF variation by Park and Kim [8], and an
instantaneous conflict probability (ICP) method by Pour et al. [9]. These
methods were chosen for their applicability to the testing scenarios and their
execution speed.

The PF method of Park and Kim was slightly altered due to their Wiener process
motion model (Equations 1 and 2 in [8]). The drift contribution to PF is not
defined so as to constrain its contribution to only drift directed toward the
CB, which consequently allows for negative drift PF contributions. Negative PF
is ill defined in a conflict predication framework since a vehicle cannot
recover after experiencing conflict. The published method uses the constant
velocity (Wiener drift) normal to the CB $(\mathbf{v}\cdot\mathbf{n})$ to
calculate the drift contribution (Equation 10 of [8]), regardless of
direction. Given these discrepancies, the velocity normal to the CB
$(\mathbf{v}\cdot\mathbf{n})$ in Equation 10 of [8] is replaced by the
unconditional velocity mean normal to the CB ($\beta$), calculated using
velocities oriented toward the CB:

$\displaystyle\beta=\int_{-\infty}^{0}f_{V_{\mathbf{n}}}(v_{\mathbf{n}})v_{\mathbf{n}}\
dv_{\mathbf{n}}.$ (42)

Negative velocities are considered since positive velocities denotes PF away
from the CB. A second method was also implemented that corresponds to the
publication version; the velocity mean was used as the publication Wiener
drift counterpart, since the velocity mean of a Wiener process is equal to its
drift. Both the implementation results of Park and Kim’s published version and
the altered version are presented. However, both are altered to ensure that
the drift contribution’s velocity points toward the CB; in the publication
version the normal velocity is limited using an if statement, while the
altered version uses Equation 42.

In a recent paper, Pour et al. proposed a method to calculate the ICP by
approximating the conflict region with rectangular elements, after
transforming the state space to achieve an uncoupled joint distribution [9].
In a follow-up paper the authors adapted their conflict region approximation
by using a spatial multi-resolution scheme [27]. The new adaptation
dynamically changes the conflict region approximation as a function of the
relative position uncertainty. This article focusses on the first paper
(original method) in order to control and manually vary the region
approximation accuracy.

ICP is not synonymous with conflict probability and requires further
processing to produce a conflict probability result. Three conflict
probability results are derived from the published ICP algorithm: the maximum
ICP (lower-bound estimate) [6], and two forms of ICP accumulation [11]. The
first assumes no prior conflict before the last discrete accumulation, and can
be expressed using discrete notation, with $\mathbb{P}_{C}[0]=0$ and $k\geq
0$, as

$\displaystyle\mathbb{P}_{C}[k+1]=\mathbb{P}_{C}[k]+\text{ICP}[k+1](1-\mathbb{P}_{C}[k]).$
(43)

The second includes all ICP from the beginning, with $\mathbb{P}_{C}[0]=0$ and
$k\geq 0$, expressed as

$\displaystyle\mathbb{P}_{C}[k+1]=\mathbb{P}_{C}[k]+\text{ICP}[k+1]\prod_{i=0}^{k}(1-\mathbb{P}_{C}[i]).$
(44)

Note the method of Pour et al. is only used for the first simulation since the
method is only defined for circular or elliptical conflict regions.

The actual conflict probability for each scenario is calculated using Monte
Carlo simulations, which are used to evaluate each method’s accuracy. For each
simulation, normal vectors on the CB and pointing away from the conflict
region are used to determine whether the vehicle is moving toward the CB. All
tests were executed on a Linux Mint 64-bit operating system, with 16 GB RAM
and an Intel Core i5-4590 CPU @ 3.30 GHz$\times$4\. Conflict probability
algorithms were implemented in C and called in Python by means of wrappers.

###  7.1 Open-loop experiment

In the experiment for the open-loop scenario, the vehicle starts at
$\mathbf{r}=(100\ \text{m},-20\ \text{m})$, as depicted by Fig. 3, with an
initial covariance of zero. The vehicle has a constant mean velocity of $(-10\
\text{m/s},1\ \text{m/s})$, and its acceleration is stimulated by noise with a
diffusion matrix of $\textbf{Q}=\text{diag}(2.2^{2},1.58^{2})$. The total
prediction period $t_{H}$ is $15$ seconds, with a sampling period of $15$ ms.

Figure 3: 2-D open-loop simulation. The CB (red) is a circle at the origin
with radius of 5. Six straight line segments (blue) can used to represent the
CB on the right side. The nominal trajectory (green) corresponds to the mean
path of a Gaussian process. Sample trajectories (black) are also displayed.

PF involves numerical integration along the CB in state space, therefore a
partition interval for the circle circumference must be chosen. Since PF
involves spatial numerical integration, and the proposed method does not, two
results are presented for PF for comparison. In the first case, the circle is
partitioned into 20 intervals, while the second is partitioned into 15
intervals. These two partitions are used for all PF methods. The ICP method of
Pour et al. involves partitioning the conflict region using rectangular
elements, likewise two results are presented for comparison; the region is
partitioned using 15 elements for the first case and 20 elements for the
second case. Note that partitioning the CB is distinct from partitioning the
conflict region into rectangular elements. For all methods, smaller partition
intervals are likely to yield more accurate answer at the cost of additional
computation. Table 2 summarises the simulation results.

Table 2: Collation of open-loop simulation results. The partition sizes are shown in brackets; the corresponding results coincide with the partition size order. The published version of Park and Kim’s method is indicated with “(P)”, and the altered version is indicated with “(A)”. “Accumulation” has been shortened to “Acc.”.  Methods |  Average444Average calculated with 10,000 simulation runs. run time (ms) |  Probability of conflict (%)
---|---|---
Monte Carlo333Simulation performed with 4,414,427 sample trajectories. |  N/A |  11.344
Proposed method |  1.212 |  11.359
van Daalen and Jones [2] (20/15) |  2.675/2.022 |  11.402/11.396
Park and Kim (P) [8] (20/15) |  2.493/1.909 |  9.939/9.931
Park and Kim (A) [8] (20/15) |  3.540/2.714 |  11.480/11.480
Max. ICP, Pour et al. [9] (20/15) |  0.284/0.217 |  1.375/1.366
ICP Acc. Eq. 43, Pour et al. [9] (20/15) |  0.284/0.217 |  37.927/37.735
ICP Acc. Eq. 44, Pour et al. [9] (20/15) |  0.284/0.217 |  14.743/14.697
|  |

The execution time of the proposed method is faster than most PF results by a
factor of 2. This is largely due to the computational cost of numerical
integration; the proposed method requires the calculation of a single,
temporal numerical integral, while PF requires both temporal and spatial
numerical integrals. The ICP calculations were faster than the proposed
method, but at the cost of accuracy. The ICP accumulation results were
obtained by calculating and accumulating the ICP every 150 ms. The lower
accumulation rate is used to ensure that the accumulated result does not
drastically compound and saturate over time. The ICP accumulation tends to
saturate over time due to the assumption that the vehicle state distribution
is unchanged by previous conflict; the impact of this assumption becomes more
pronounced if the accumulation points are within close proximity in time.
These problems can be regarded as a short-coming of ICP methods: they do not
directly translate to a calculation of total vehicle conflict probability
without limiting assumptions, like the maximum ICP, or further data processing
decisions such as a lower accumulation rate. The absolute error of all the PF
simulation results are relatively small, with the largest absolute error being
1.413% and smallest absolute error being 0.052%. The proposed method resulted
in an absolute error of 0.015%.

###  7.2 Closed-loop experiment

In the closed-loop experiment scenario, the vehicle starts at
$\mathbf{r}=(-1.5\ \text{m},9.15\ \text{m})$, as depicted by Fig. 4, with an
initial covariance of zero. The vehicle moves in two stages; first, with a
constant mean velocity magnitude of $1$ m/s to position $(9\ \text{m},9.45\
\text{m})$. Second, from $(9\ \text{m},9.45\ \text{m})$ the vehicle moves with
a constant mean velocity magnitude of $1.6$ m/s to position $(12.5\
\text{m},8.94\ \text{m})$. Two straight-line manoeuvres are followed, with
feedback control tracking the planned path. The total prediction period is
$13.73$ seconds, with a sampling period of $10$ ms. During both manoeuvres the
acceleration is stimulated by noise with a diffusion matrix of
$\textbf{Q}=\text{diag}(7.5^{2},2.4^{2})$. The proposed method calculates the
steady-state covariance using the feedback gains and noise variances.
Therefore, an approximation is introduced that there are no transient
dynamics. The simulation results are shown in Table 3.

Figure 4: 2-D closed-loop simulation. The CB (red) consists of three line
segments. The nominal trajectory (green) corresponds to the mean path of a
Gaussian process. Sample trajectories (black) are also displayed.

Three results are shown for each PF simulation; for the first result, each
line is partitioned into intervals of 0.05 m, for the second result each line
is partitioned into intervals of 0.1 m, and for the third result each line is
partitioned into intervals of 0.15 m. The proposed method makes an absolute
error of 1.3%. The largest PF result absolute error is 9.206% and the smallest
PF result absolute error is 0.149%. The most substantial advantage of the
proposed method is the computational savings: All PF results are at least an
order of magnitude more expensive. This is due to the large amount of CB
partitioning needed, inflating the spatial integral computational cost. The
total spatial integral cost accumulates drastically since the calculation is
performed for each time step.

Table 3: Collation of closed-loop simulation results. Partition interval lengths (m) are shown in brackets; the corresponding results coincide with the interval length order. The published version of Park and Kim’s method is indicated with “(P)”, and the altered version is indicated with “(A).”. Methods |  Average44footnotemark: 4 run time (ms) |  Probability of conflict (%)
---|---|---
Monte Carlo555Simulation performed with 6,676,360 sample trajectories. |  N/A |  10.231
Proposed method |  0.278 |  8.931
van Daalen and Jones [2] (0.05/0.1/0.15) |  107.561/ 26.491/ 17.640 |  12.021/ 13.343/ 18.202
Park and Kim (P) [8] (0.05/0.1/0.15) |  52.085/ 26.005/ 17.456 |  10.082/ 11.456/ 16.619
Park and Kim (A) [8] (0.05/0.1/0.15) |  68.914/ 34.558/ 22.946 |  13.224/ 14.554/ 19.437
|  |

##  8 Conclusions

This paper proposes a conflict prediction technique for 2-D scenarios where
vehicle motion can be described as a Gaussian process and the conflict
boundary can be approximated by a number of straight-line segments. The
proposed technique first reduces the dimensionality of the problem, and then
writes the expression for the probability of conflict in terms of the FPTD.
The final expression involves the computation of a single numerical integral,
which results in significant computational savings when compared to a known
fast method like probability flow. Simulation experiments were used to
demonstrate the computational efficiency of the proposed method, as well
demonstrating that the accuracy of the proposed method is of the same order as
the accuracy of existing methods. Two variants of probability flow were used
for comparison, as well as a recent ICP method. Increasing the number of line
segments by a factor of $N$ would increase the computational time by a factor
of $N$. However, since these calculations are completely independent of each
other they can be computed in parallel.

## References

  * [1] S.M. LaValle.  Planning Algorithms.  Cambridge University Press, USA, 2006.
  * [2] C.E. Van Daalen and T. Jones.  Fast Conflict Detection Using Probability Flow.  Automatica, 45(8):1903–1909, 2009.
  * [3] J.K. Kuchar and L.C. Yang.  A Review of Conflict Detection and Resolution Modeling Methods.  IEEE Transactions on Intelligent Transportation Systems, 1(4):179–189, Dec 2000.
  * [4] J. Jansson and F. Gustafsson.  A framework and automotive application of collision avoidance decision making.  Automatica, 44(9):2347–2351, 2008.
  * [5] J. Chryssanthacopoulos, M. Kochenderfer, and R. Williams.  Improved Monte Carlo sampling for conflict probability estimation.  AIAA Non-Deterministic Approaches Conference, 2010.
  * [6] R.A. Paielli and H. Erzberger.  Conflict Probability Estimation for Free Flight.  AIAA Journal of Guidance Control and Dynamics, 20:588–596, 1997\.
  * [7] T. A. Lauderdale.  Probabilistic conflict detection for robust detection and resolution.  Proc. AIAA Aviation Technol. Integr. Oper. Conf., 2012.
  * [8] J. Park and J. Kim.  Predictive Evaluation of Ship Collision Risk Using the Concept of Probability Flow.  IEEE Journal of Oceanic Engineering, 42(4):836–845, Oct 2017.
  * [9] S.S. Pour, H. Nobahari, and M. Prandini.  Probability estimation in aircraft conflict detection: a simple and computationally effective method with accuracy certificates.  In 2019 18th European Control Conference (ECC), pages 4319–4324. IEEE, 2019.
  * [10] D.V. Dimarogonas and K.J. Kyriakopoulos.  Inventory of Decentralized Conflict Detection and Resolution Systems in Air Traffic.  Deliverable D6, 1, 2002.
  * [11] T. Jones.  Tractable Conflict Risk Accumulation in Quadratic Space for Autonomous Vehicles.  Journal of Guidance, Control, and Dynamics, 29(1):39–48, 2006\.
  * [12] C.E. Van Daalen.  Conflict Detection and Resolution for Autonomous Vehicles.  PhD thesis, Stellenbosch: University of Stellenbosch, 2010.
  * [13] D.A. Darling and A.J.F. Siegert.  The first passage problem for a continuous Markov process.  Annals of Mathematical Statistics, 24(4):624–639, 12 1953.
  * [14] T. Ryznar, J. Byczkowski, and M. Małecki.  Hitting Times of Bessel Processes.  Potential Analysis, 38:735–786, 2013.
  * [15] Y. Hamana and H. Matsumoto.  The probability distributions of the first hitting times of Bessel processes.  Transactions of the American Mathematical Society, 365:5237–5257, 2013.
  * [16] S. Iyengar.  Hitting lines with two-dimensional Brownian motion.  SIAM Journal on Applied Mathematics, 45(6):983–989, 1985.
  * [17] A. Metzler.  On the first passage problem for correlated Brownian motion.  Statistics and Probability Letters, 80(5):277 – 284, 2010.
  * [18] P.G. Buckholtz and M.T. Wasan.  First passage probabilities of a two dimensional Brownian motion in an anisotropic medium.  Sankhyā: The Indian Journal of Statistics, Series A (1961-2002), 41(3/4):198–206, 1979.
  * [19] S. Haozhe, M. Rubén, and J. Drugowitsch.  Family of closed-form solutions for two-dimensional correlated diffusion processes.  Phys. Rev. E, 100:032132, Sep 2019.
  * [20] J.E. Stellet et al.  Estimating the process noise variance for vehicle motion models.  pages 1512–1519. IEEE, 2015.
  * [21] T. Jones.  Real-time Probabilistic Collision Avoidance for Autonomous Vehicles, Using Order Reductive Conflict Metrics.  PhD thesis, Massachusetts Institute of Technology, 2003.
  * [22] S. Song and J. Wu.  Motion state estimation of target vehicle under unknown time-varying noises based on improved square-root cubature kalman filter.  Sensors, 20(9):2620, 2020.
  * [23] M.J. Grimble and M.A. Johnson.  Optimal control and stochastic estimation: theory and applications, volume 1.  John Wiley & Sons, 1988.
  * [24] J.A. Borrie.  Stochastic Systems for Engineers: Modelling, Estimation and Control.  Prentice Hall, 1992.
  * [25] D.R. Cox and H. D. Miller.  The theory of stochastic processes.  Methuen London, 1965, p.203–251.
  * [26] L. Yang, J.H. Yang, J. Kuchar, and E. Feron.  A Real-time Monte Carlo Implementation for Computing Probability of Conflict.  In AIAA Guidance, Navigation, and Control Conference and Exhibit, page 4876, 2004.
  * [27] S. Seyedipour, , H. Nobahari, and M. Prandini.  An efficient aircraft conflict probability estimation method using a spatial multi-resolution scheme.  In 2021 European Control Conference (ECC), pages 29–34. IEEE, 2021\.