What Is The Collision Probability And How To Compute It

arXiv:1711.07060v2 [] 14 Jan 2018

Richard Altendorfer and Christoph Wilkmann

Abstract—We revisit the computation of probability of collision
in the context of automotive collision avoidance (the estimation
of a potential collision is also referred to as conflict detection
in other contexts). After reviewing existing approaches to the
definition and computation of collision probability we argue that
the fundamental quantity that is required to answer a question
like ”What is the probability of collision within the next three
seconds?” is a collision probability rate. We derive a general
expression for the distribution of the collision probability rate and
demonstrate that it exactly reproduces distributions obtained by
large-scale Monte-Carlo simulations. This expression is valid for
arbitrary prediction models including process noise. We derive
an approximation for the distribution of the collision probability
rate that can be computed on an embedded platform. In order to
efficiently sample this probability rate distribution for determination of its characteristic shape an adaptive method to obtain the
sampling points is proposed. The probability of collision is then
obtained by one-dimensional numerical integration over the time
period of interest. We also argue that temporal collision measures
such as time-to-collision should not be calculated as separate or
even prerequisite quantities but that they are properties of the
distribution of the collision probability rate.

we derive a general expression valid for arbitrary prediction
models including process noise. Inclusion of process noise
is crucial for collision avoidance systems since it allows to
encode the uncertainty in the relative motion of the host and
the colliding vehicle. This uncertainty is particularly relevant
for predictions over several seconds where it is unknown
whether the colliding vehicle keeps its motion, accelerates or
slows down, or whether the host vehicle driver perceives the
risk and slows down, for example.
The basis of our derivations are the distributions
pt (x, y, ẋ, ẏ, ẍ, ÿ), t ∈ ∆T of the predicted relative state ξ − (t)
of the colliding vehicle. The predicted state ξ − (t) is a nonstationary stochastic process. In the remainder of this paper the
time dependence of ξ − (t) and its elements will be suppressed,
however the temporal dependence of probability distributions
will be indicated by p → pt where appropriate.
In the next section Monte-Carlo simulations of two collision
scenarios are performed and it is shown that the result is
naturally represented by a collision probability rate.

I. INTRODUCTION

II. T HE COLLISION PROBABILITY GROUND TRUTH :
LARGE - SCALE M ONTE -C ARLO SIMULATIONS

The implementation of a collision mitigation or collision
avoidance system requires in general the computation of a
collision probability in order to assess the criticality of the
current traffic situation as well as its evolution in the shortterm future. Sometimes, in a separate calculation, see e. g.
[1],[2] an estimate of the time-to-collision (TTC) is computed.
There are two fundamentally different approaches to computing a collision probability that are known to the authors:
1) probability of the spatial overlap of the host vehicle with
the colliding vehicle’s probability distribution, see e. g.
[3], [4], and
2) probability of penetrating a boundary around the host
vehicle, see e. g. [5],[6].
There is currently no satisfying way to compute the collision
probability over a time period: there is a heuristic proposal to
pick the maximal collision probability over that period as the
collision probability for that time period [5],[1], and there is
a rather involved calculation valid only for piecewise linear
trajectories penetrating a line interval to directly compute the
collision probability over a time period while ignoring process
noise [6].
In the following we will derive an expression of the
probability of penetrating a boundary around the host vehicle
in a time period ∆T = [t1 , t2 ]. This will be the result of
the temporal integration of the probability rate for which
R. Altendorfer is with Driver Assistance Systems, ZF TRW, Germany

richard.altendorfer@zf.com
C.

Wilkmann

is

with

RWTH

Christoph.Wilkmann@rwth-aachen.de

Aachen,

Germany

In order to obtain ground truth data for the collision
probability Monte-Carlo simulations are performed. The target
vehicle on a possibly colliding path with the host vehicle is
modeled by the state vector ξ = (x y ẋ ẏ ẍ ÿ)> and the
dynamical system as specified in appendix B. Accelerations
are deliberately included in the state in order to demonstrate
that accelerated motions can be handled. The target vehicle
is chosen to be detected by a radar sensor mounted at the
middle of the front bumper of the host vehicle with standard
radar measurements also specified in app. B.
The starting point for an individual simulation is a sample
point in state space ξi− where the target vehicle is some
distance away from the host vehicle - either directly in front
or coming from the right side, see fig. 1. This sample point is
drawn from a multivariate Gaussian distribution characterized
by its mean vector and covariance matrix. The covariance
matrix is taken from steady state1 at this mean vector using
the discrete algebraic Riccati equation (25) as detailed in app.
B. An instance ξi− of an initial state of the target vehicle is
−
drawn as a sample of N (ξ − ; µ−
ξ , P∞ ). This state is predicted
using the stochastic state equation (22) until it crosses the host
vehicle boundary or a certain time limit is exceeded. The time
until the crossing is recorded and a new simulation with a new
sample of initial conditions is started. Examples of colliding
1 Strictly speaking there is no steady state at those points since the system
is non-linear and the relative speed is not zero. Nevertheless the solution of
the Riccati equation is still representative if the filter settles within a smaller
time period than the time period in which the state changes significantly.

trajectories starting from an initial position in front of the host
vehicle are depicted in fig. 1.
We have performed simulations of Ntraj = 1 · 107 trajectories for the two starting points. The result is represented by
a histogram of the number of collisions that occur within a
histogram bin, i. e. time interval, with respect to time.
Hence simulating colliding trajectories naturally leads to a
collision probability rate.
An example is given in fig. 2 where the bins are normalized
by the total number of trajectories Ntraj and the chosen
bin width of dt = 0.05s to obtain a collision probability
rate. In addition, the collision probability rate integrated by
simple midpoint quadrature from 0 to time t is shown. In this
example the probability of collision with the target vehicle
reaches a threshold of 40%, for example, within the first 4.88s.
The asymptotic value of the collision probability as t → ∞
indicates the overall probability of collision over all times.
The main contribution of this paper will be to derive
formulae that reproduce this collision probability and collision
probability rate.
In the following two sections we will review existing
approaches to computing a collision probability.
III. C OLLISION PROBABILITY FROM 2D SPATIAL OVERLAP
This is the probability of the spatial overlap between the
host vehicle and the colliding vehicle as proposed in [3], [4].
In [3] the variables of the relevant probability distribution
are either defined by the relative two-dimensional position
and relative orientation (x, y, ψ), or by the distribution of the
difference of independent probability distributions of global
two-dimensional position and orientation as in [4]. It is not explained how higher order derivatives necessary for prediction
such as ẋ, ẏ, ... have been dealt with (e. g. by marginalization).
Then in [3] the collision probability is obtained as the
integral over the pdf of relative position and orientation over
a collision volume D
ZZZ
PC (t) =
p (x, y, ψ) dxdydψ
(1)
x,y,ψ∈D

which in turn is approximated as the convolution of independent probability distributions of global two-dimensional
position of both host and colliding vehicle - orientation is
ignored. Note that even this two-dimensional integral, i. e. the
cumulative distribution function of a bivariate Gaussian, cannot be solved in closed form; however, numerical approximation schemes exist [7]. By further ignoring the x−y-covariance
the multivariate Gaussian decouples so that integration can be
factored into one-dimensional Gaussian distributions [3]. In
[4], the collision probability is computed as the integral of the
product of the two global distributions.
A problem of deriving a collision probability from 2D
spatial overlap is that this approach directly yields a collision
probability for a specific time, see fig. 3. Hence it does not
allow to answer the question ”What is the probability of
collision within the next three seconds?” because integration
of the collision probability over time does not yield a collision
probability over a certain time period as already pointed out

in [6]. In particular, time is not a random variable that can be
marginalized
over and the integral over a time interval ∆T :
R
P (t)dt as in [8] has dimension of time and does not
∆T C
constitute a probability. A rather heuristic proposal to solve
this problem has been to pick the maximal collision probability
over a time period as the collision probability for that period
[5],[1].
Another issue is that the collision probability is determined
by the presence of the colliding object anywhere inside the
entire area of the host vehicle. It could, for example be in
the center of the host vehicle, which would be a catastrophic
event and much too late for collision avoidance. What we are
actually interested in is the probability of the colliding object
touching and/or penetrating the boundary of the host vehicle.
This requires a different approach than integration over state
space as in eq. (1). Some existing approaches that consider a
boundary instead of a state space volume for the computation
of a collision probability are reviewed in the next section.
IV. C OLLISION PROBABILITY AT BOUNDARY
A probabilistic approach to computing the probability of
penetrating a boundary - instead of the probability of a spatial
overlap - has been proposed in [6]. Their method is based
on the probability density of a so-called time-to-go which is
the time to cross a straight, axis-aligned boundary assuming
a constant velocity model. The derived collision probability
refers to a time period and not just a time instant. It is
only applicable to straight paths or combinations of piecewise
straight paths and does not take into account more complex
geometries such as a rectangle. Another limitation is that
process noise is not considered. This method is an extension
of the approach discussed [5] in the sense that the uncertainty
of the initial condition is included.
A different, semi-probabilistic approach is taken in [2]
where the time-to-collision of a 2D constant velocity model
with respect to the host vehicle’s front boundary at x = 0
is computed. This TTC is then inserted into the prediction
equation to arrive at




x + tẋ
0
x 
 y + tẏ 


 → y − ẋ ẏ 
(2)
 ẋ 
 ẋ 
ẏ
ẏ
Then the second component of this vector is singled out and
interpreted as a probabilistic expression. Its distribution as
a function of the initial condition is determined by MonteCarlo simulation and integrated over the host vehicle’s front
boundary to obtain a collision probability at the TTC. As in
the previous approaches more complex geometries as well as
process noise are not considered.
The approaches discussed above all rely on a time-togo or TTC as a prerequisite quantity - either probabilistic
or non-probabilistic. As we will show in the next section,
such a temporal collision measure is not necessary for the
computation of a collision probability. Instead, we show that
the fundamental quantity to compute the collision probability
is the collision probability rate.

10

10

shape of initial
x-y covariance
sample collision
trajectories

x [m]

5

x [m]

5

shape of initial
x-y covariance
sample collision
trajectories

0

0

-5

-5
-10

-5

0

5

10

-10

-5

0

y [m]

5

10

y [m]

(a) The target is coming from the front (µx , µy ) = (10, 0) m

(b) The target is coming from the front right (µx , µy ) = (10, 10) m

0.09

0.5
collision probability rate
collision probability

0.45

P(t) from 2D overlap
TTC x

0.08

0.4

0.07

0.35

0.06

0.3

P(t) []

collision probability rate [s -1 ], collision probability []

Fig. 1. Samples of simulated colliding trajectories for vehicles initially coming from the front (a) and from the front right (b) side. The number of drawn
trajectories colliding with the edges of the host vehicle indicate for the ratio of colliding the respective edge compared to the total number of collisions.

0.25

0.05
0.04

0.2

0.03

0.15
0.1

0.02

0.05

0.01

0
0

1

2

3

4

5

6

7

8

0
2

3

4

t [s]

Fig. 2. Collision probability rate as a function of time for (µx , µy ) =
(10, 0) m based upon Ntraj = 1·107 trajectories. Also shown is the collision
probability obtained by integrating over time.

V. C OLLISION PROBABILITY RATE AT BOUNDARY

5

6

We have seen that simulating colliding trajectories naturally
gives us a probability rate and that a collision probability
rate allows us to perform temporal integration to arrive at
a collision probability for an extended period of time. The
expression for the collision probability rate will be derived on
the basis of a theorem on boundary crossings of stochastic
vector processes. For sake of lucidity of arguments we restrict ourselves to one of the four straight boundaries of the
host vehicle, see fig. 4; extension to the other boundaries is
straightforward.
We start with the prediction of the pdf of the state vector
(see eq. (22) in app. B) of a colliding object from an initial
condition at t = 0 to a future time t where process noise

8

Fig. 3. Example of collision probability over time.

(parametrized by its covariance matrix Q) is explicitly incorporated:
t,Q

A. Derivation of collision probability rate

7

t [s]

prediction : p0 (x, y, ẋ, ẏ, ẍ, ÿ) 7−→ pt (x, y, ẋ, ẏ, ẍ, ÿ)

(3)

In order to cast the following expressions into a more readable
format we define a probability distribution with fewer variables
by marginalization (see app. A for marginalization of Gaussian
densities) over the accelerations:
Z Z
pt (x, y, ẋ, ẏ) :=
pt (x, y, ẋ, ẏ, ẍ, ÿ)dẍdÿ.
(4)
ẍ∈R ÿ∈R

What we are looking for is an expression for
dPC+
(Γf ront , t)
dt
dP +

(5)

i. e. the collision probability rate dtC with dimension [s−1 ]
at time t for the front boundary Γf ront . The superscript + is

used to denote that this probability rate is referring to boundary
crossings from outside to inside.
We start with the probability of the colliding object being
inside an infinitesimally thin strip at the boundary Γf ront (see
fig. 4)
Z Z Z
dPC+ (Γf ront , t) =
pt (x0 , y, ẋ, ẏ) dxdydẋdẏ
y∈Iy ẋ≤0 ẏ∈R

Here, since we are only interested in colliding trajectories, i.
e. trajectories that cross the boundary from outside to inside,
we do not fully marginalize over ẋ but restrict the x−velocity
to negative values at the boundary.
A collision probability rate can now be obtained by dividing
the unintegrated differential dx by dt; in that way the “flow”
of the target vehicle through the host vehicle boundary is
described at x0 with velocity ẋ ≤ 0:
Z Z Z
dPC+
(Γf ront , t) = −
pt (x0 , y, ẋ, ẏ) ẋ dydẋdẏ (6)
dt
y∈Iy ẋ≤0 ẏ∈R

Here, since the velocity is restricted to negative values a minus
sign is required to obtain a positive rate.
This intuitive derivation can be corroborated as well as
generalized in a mathematically rigorous way by invoking a
result on crossings of a surface element by a stochastic vector
process described in the following box:

x
Front
boundary:  front

yL

yR

dx
Infinitesimally
thin strip

x0

Iy

left

y
right

Host vehicle

rear
Fig. 4. Horizontal view of the host vehicle rectangle with local Cartesian
coordinate system and coordinate origin at the middle of the front boundary
characterized by x = 0 and y ∈ [yL , yR ] = Iy .

In order to apply eq. (7) to the front boundary Γf ront as in
fig. 4 we need to perform the following identifications:2
ζ(t) = (x, y)

>

Γf ront = {(x, y) : x − x0 = 0 ∧ y ∈ Iy }
g(x) = x − x0
>

nΓf ront (x) = (−1, 0)
ds(x) = dy

(9)

Probability rate and probability for boundary crossings
Hence we obtain for the intermediate expectation operator
of stochastic vector processes
Here two expressions are given for the probability rate and
n
o
the probability for crossings of a surface by a stochastic
E hnΓf ront (x), ζ̇(t)i+ ζ(t) = x =
vector process that were stated in [9] and generalized in
Z Z
[10].
−
ẋ pt (ẋ, ẏ|x, y) dẋdẏ (10)
Let ζ(t) be a continuously differentiable n−dimensional
ẋ≤0 ẏ∈R
vector stochastic process with values x ∈ Rn . The probn
ability densities pt (x) and pt (ẋ, x) exist where ẋ ∈ R
dP +
are the values of ζ̇(t). Let the region S ∈ Rn be bounded
and the collision entry rate dtC as in eq. (7) becomes
by the smooth surface ∂S defined by the smooth function


g as ∂S = {x : g(x) = 0} and let Γ ⊆ ∂S be a subset
Z Z Z
+
dPC
of that surface. Let nΓ (x) be the surface normal at x
(Γf ront , t) = − 
ẋ pt (ẋ, ẏ|x0 , y)dẋdẏpt (x0 , y)dy
dt
directed towards the interior of the region.
+
−
y∈Iy ẋ≤0 ẏ∈R
Then the entry rate dPdt and the exit rate dPdt through Γ
Z Z Z
at time t is given by
=−
ẋ pt (x0 , y, ẋ, ẏ) dydẋdẏ
(11)
Z
n
o
±
dP
y∈Iy ẋ≤0 ẏ∈R
(Γ, t) = E hnΓ (x), ζ̇(t)i± ζ(t) = x pt (x)ds(x)
dt
x∈Γ
which is identical to eq. (6). Because of the simple projection
(7)
of the velocity onto the surface normal hnΓf ront (x), ζ̇(t)i+ =
where h·, ·i is the scalar product, ds(x) is an infinitesimal
ẋ for the front boundary this expression could be further
surface element of Γ at x and (·)+ := max(·, 0) and
simplified by marginalization over ẏ.
−
(·) := − min(·, 0).
The computation above applies to the front boundary of
The probability of entries and exits through the surface
the
host vehicle. In order to cover all four boundaries of the
subset Γ within a time interval ∆T = [t1 , t2 ] is given by
host vehicle the collision probabilities of the four boundaries
Zt2
can be added since the crossing events through the different
dP ±
±
P (Γ, t1 , t2 ) =
(Γ, t) dt
(8)
dt
t1

These results hold for general non-stationary processes.

2 Unlike in the box above we now do not distinguish anymore between a
stochastic process and its values.

boundaries are mutually exclusive. Hence the total collision
probability rate is given by
dPC+
(Γhost
dt

vehicle , t)

=
dPC+
dPC+
(Γf ront , t) +
(Γright , t)+
dt
dt
dPC+
dPC+
(Γlef t , t) +
(Γrear , t) (12)
dt
dt

The collision probability over a certain time period can then
be obtained by one-dimensional numerical integration over
time as in eq. (8).
The derivation above relied on a couple of assumptions.
Here we want to comment on whether these assumptions pose
any restrictions on the application of the derived collision
probability rate on more general scenarios.
a) Rectangular boundary: The boundary of the host
vehicle is modeled as a rectangle, however by the theorem
stated in the box above the formula can be applied to any
subsets of smooth surfaces, including higher dimensional ones
for three-dimensional objects, for example.
b) Point distribution: The relative state of the colliding
object is modeled by a point distribution. In many ADAS
applications the object state is indeed modeled by a single
reference point and possibly additional attributes such as width
and length. This is partly due to the fact that the estimation
of extended objects is still an active area of research, for an
overview see [11]. On the other hand, our approach can be
executed in parallel for distributions of points representative
of the colliding vehicle’s geometry [12] or for individual point
distributions of a Gaussian mixture model, for example.
c) State vector: the state vector ξ of the colliding object
needs to contain 2D relative position (x y)> and 2D relative
velocity (ẋ ẏ)> . In many ADAS applications the target vehicle
dynamics is modeled directly in relative coordinates. For state
vectors that do not contain the 2D relative velocity but other
quantities such as the velocity over ground (see e. g. [13]),
a probabilistic transformation to relative velocities must be
performed first.

B. Implementation
For further computations - especially in the Gaussian case
- it will be convenient to marginalize over ẏ and rewrite eq.
(11) in terms of a conditional probability:
Z Z
dPC+
(Γf ront , t) = −pt (x0 )
ẋ pt (ẋ, y|x0 ) dẋdy (13)
dt
ẋ≤0 y∈Iy

For general distribution functions the integral in eq. (13)
cannot be computed in closed form and numerical integration
methods must be used. Even in the bivariate Gaussian case
there is no explicit solution known to the authors. However,
by a Taylor-expansion with respect to the off-diagonal element
of the inverse covariance matrix of p(y, ẋ|x0 ) as detailed in
app. C, the integral can be factorized into one-dimensional

Gaussians and solved in terms of the standard normal onedimensional cumulative distribution function Φ. To zeroth
order the integration yields:
dPC+
(Γf ront , t) = − N (x0 ; µx , σx )
dt



−µẋ|x0
·
µẋ|x0 Φ
σ̃ẋ|x0


2
N (0; µẋ|x0 , σ̃ẋ|x0 )
σ̃ẋ|x
0

·
−
 



yR − µy|x0
yL − µy|x0
· Φ
−Φ
σ̃y|x0
σ̃y|x0
!

+ O Σ−1
(14)
12
Here, if Σ ∈ q
R2×2 is the covariance
q matrix of p(ẋ, y|x0 ),
|Σ|
|Σ|
then σ̃ẋ|x0 =
Σyy and σ̃y|x0 =
Σẋẋ , see app. C where
the integration has also been carried out to first order in Σ−1
12 .
Expression (14) can be computed on an embedded platform
using the complementary error function available in the C math
library.3
In the next section an extensive numerical study using the
above formulae and Monte-Carlo simulations is presented.
VI. N UMERICAL S TUDY
A numerical study has been carried out to address the
following questions:
• Is the expression for calculating the collision probability
rate from eq. (11) consistent with the results from large
scale Monte-Carlo simulations?
• How does the approximation (14) perform in comparison
with the numerical integration of the derived expression
for the collision probability rate?
• Can the computational effort be reduced by increasing ∆t
and still accurately calculating the collision probability
rate?
A. Is the expression of collision probability rate corroborated
by Monte-Carlo simulation?
In order to address the first question, large scale MonteCarlo simulations as described in sec. II have been performed.
Collision probability rates were calculated based on 1 · 107
sample trajectories for each of the two initial conditions
−
−
−
Ni (ξ − ; µ−
ξ i , P∞ ), where µξ i is shown in table I, and P∞ is
calculated using eq. (25) with the matrices defined in appendix
B. The two initial conditions (i ∈ {f, f r}) describe a starting
point directly in front of the host vehicle, and in front to the
right at an angle of 45 degrees with respect to the host vehicle.
Table II shows the number of collisions divided into the
respective boundaries of the host vehicle where the impact or
boundary crossing occurred for the two different simulations.
The resulting histograms of the collision probability rates
are shown in fig. 5 together with the numerical integration of
3 Φ is related to the error function erf and complementary error function




√
√
erfc by Φ(x) = 21 erfc −x
= 12 − 12 erf −x
.
2

2

TABLE I
M EAN OF INITIAL CONDITIONS FOR M ONTE -C ARLO SIMULATIONS
i
HH f
µ−
ξ
µ−
10
x [m]
µ−
0
y [m]


m
µ−
−2
ẋ  s 
m
µ−
0.1
ẏ h s i
− m
µẍ s2
−0.2
h i
m
µ−
0.0
ÿ
s2

HH

fr
10
10
−2
−1.6
−0.001
−0.01

TABLE II
N UMBER OF COLLISIONS AT HOST VEHICLE BOUNDARIES FOR 1 · 107
SIMULATED TRAJECTORIES WITH DIFFERENT INITIAL CONDITIONS

PP
PP i
Γj
P
P
f ront
right
lef t
rear
P

f

fr
106

4.46 ·
36874
6196
0
4.50 · 106

1.40 · 106
2.88 · 106
2
0
4.28 · 106

the collision probability rate as well as the difference between
the simulation and the calculation. The difference is calculated
by evaluating the collision probability rate at the same time
as the mid points of the histogram bins.
As can be seen in fig. 5, the numerical integration of the
collision probability rate accurately reproduces the collision
probability rate from the Monte-Carlo simulations. In order to
illustrate the increase in accuracy as a function of the number
of simulated trajectories, fig. 6 shows the differences between
simulation and numerical integration with increasing amount
of simulated trajectories for collisions at the right side of the
host vehicle in the front scenario.
B. Does the approximation by Taylor-expansion accurately
reproduce the exact result?
In order to be able to compute the collision probability rate
efficiently on an embedded platform, an approximation of the
exact expression (eq. (11)) was derived in eq. (14). Fig. 7
shows the differences between this approximation as well as a
higher-order approximation where the pdf is Taylor-expanded
to linear order with respect to the off-diagonal element of
the inverse covariance matrix around 0 (see app. C) and
the numerical integration. As can be seen, the higher-order
approximation reduces the error to a large extent while it can
be still calculated efficiently on an embedded platform using
the complementary error function.
C. An adaptive method to sample the collision probability rate
over ∆T
Above, the approximations of the exact expression for
calculating the collision probability rate were evaluated at
small time increments of ∆t = 0.05s. Thus, the calculation
over the entire time period of interest (e.g 8s as used above)

and for every relevant object could induce a substantial computational burden. In order to reduce this effort, we propose
an adaptive method to sample the collision probability rate
function with variable – in general larger – time increments
∆t over the time period of interest while still capturing the
characteristics of this function, in particular its shape around
the maximum. The sampling starting point is based upon the
non-probabilistic TTCs for single, straight boundaries using
a one-dimensional constant acceleration model. Those TTCs
for penetrating the front, left, and right boundaries can then be
used as initial condition for the start of the sampling iteration
of the collision probability rate.4 To reproduce the collision
probability rate without substantial loss of information but
with lower computational effort, the following algorithm is
proposed:
• Calculate the times of penetrating the front, left and
right boundaries based upon the non-probabilistic TTCs
described above.
• Calculate the collision probability rate for each time. Pick
the time with the maximum collision probability rate as
a starting point.
• Move left and right from this starting point with equally
spaced ∆t1 > ∆t and calculate the collision probability
rate at these time points. Stop on each side if the collision
dP +
probability rate has reached a lower threshold of dtC low .
• While moving left and right, check if the slope of the
collision probability rate has changed its sign.
• On every slope sign change, calculate the collision probability rate around this time interval with decreased
∆t2 < ∆t1 .
Examples of this implementation can be found in fig. 8 for the
front and front-right scenarios. It can be seen that the collision
probability rate as well as the integrated collision probability
over a certain time period can be determined with considerably
fewer sampling points while still capturing the shape of the
functions to be approximated.
VII. W HAT IS THE TTC?
There are various approaches to computing the TTC. In
[2], the TTC is computed as the mean of the time distribution
of reaching the x0 boundary of the car as a function of the
initial conditions assuming a constant speed model; process
noise is not considered. This is also presented in [1]; in
addition the time distribution for reaching the x0 boundary
as a function of the initial conditions assuming a constant
acceleration model is calculated by Monte-Carlo-simulation
and its mean values depending upon the initial condition setup
is given - again, process noise for this motion model is not
considered. However these simple temporal quantities do not
fully capture the characteristics of horizontal plane collision
scenarios as will be shown below.
In fig. 9 the collision probability rate is plotted together
with the constant acceleration motion TTCs for the x- and ydirections for an initial position at the front, right side. Both
4 Due to the low probability of penetration the non-probabilistic TTC for
the rear boundary is not considered for the determination of the sampling
starting point.

0.5

0.5
Monte-Carlo histogram
numerical integration of exact expression

0.45

0.4

collision probability rate [s -1 ]

0.4

collision probability rate [s -1 ]

Monte-Carlo histogram
numerical integration of exact expression

0.45

0.35
0.3
0.25
0.2
0.15

0.35
0.3
0.25
0.2
0.15

0.1

0.1

0.05

0.05

0

0
2

3

4

5

6

7

8

2

3

4

5

t [s]

(a) Front scenario total collision probability rate

8

10-3

2
numerical integration - Monte-Carlo histogram

numerical integration - Monte-Carlo histogram

1.5

collision probability rate [s -1 ]

1.5

collision probability rate [s -1 ]

7

(b) Front-Right scenario total collision probability rate

10-3

2

6

t [s]

1

0.5

0

-0.5

1

0.5

0

-0.5

-1

-1

-1.5

-1.5
2

3

4

5

6

7

8

2

3

4

5

t [s]

6

7

8

t [s]

(c) Front scenario total collision probability rate difference

(d) Front-Right scenario total collision probability rate
difference

Fig. 5. The histogram resulting from Monte-Carlo simulation is shown together with the numerical integration of the expression for the collision probability rate
for front (a) and front-right (b) scenario. The differences between simulation and numerical integration are calculated by evaluating the numerical integration
at the same time as the mid points of the histogram bins and shown in (c) and (d).

10-3

5
4.5

2
1.5

4

collision probability rate [s-1 ]

collision probability rate [s-1 ]

3
2.5

3.5
3
2.5
2
1.5

3.5
3
2.5
2
1.5

1

1

1

0.5

0.5

0.5

0

0
1

2

3

4

5

6

7

8

0
1

2

3

t [s]

(a) Simulation based on 1 · 105 trajectories.

Monte-Carlo histogram
numerical integration of exact expression

4.5

4

3.5

10-3

5
Monte-Carlo histogram
numerical integration of exact expression

4.5

4

collision probability rate [s-1 ]

10-3

5
Monte-Carlo histogram
numerical integration of exact expression

4

5

6

7

8

t [s]

(b) Simulation based on 1 · 106 trajectories.

1

2

3

4

5

6

7

8

t [s]

(c) Simulation based on 1 · 107 trajectories.

Fig. 6. The collision probability rate for the right side of the host vehicle for the front scenario is shown comparing the results from Monte-Carlo simulation
with increasing amount of simulated trajectories (a)-(c) with the calculated collision probability rate of the numerical integration of the expression for the
collision probability rate eq. (11). The process noise PSD for both coordinates is q̃x = q̃y = 1.0125m2 s−5 .

TTCs in x- and y-direction are significantly different from the
time of the maximum of the collision probability rate. Since
the bulk of the colliding trajectories go through two sides front and right (see also fig. 1b) - only a collision model that
takes into account the full geometry of the host vehicle can
yield accurate results.
In fig. 10 the collision probability rate is plotted together
with the constant acceleration motion TTCs (i. e. their mean

values) for the x-direction for an initial position that is straight
in front of the vehicle hence almost all trajectories pass
through the front boundary. Nevertheless the maximum of
the probability rate occurs before the mean of the TTC. This
difference increases as the process noise increases as can be
seen in fig. 11. This is due to the fact that the time of the
maximum is strongly influenced by the factor pt (x0 ) in eq.
(13); an increased level of process noise leads to a faster

10-7
approx. - num. integration
higher order approx. - num. integration

4

approx. - num. integration
higher order approx. - num. integration

10

2

collision probability rate [s -1 ]

collision probability rate [s -1 ]

10-4

12

0

-2

-4

-6

8

6

4

2

0

-8

-2

2

3

4

5

6

7

8

2

3

4

5

t [s]

6

7

8

t [s]

(a) Front scenario

(b) Front-Right scenario

Fig. 7. Differences between numerical integration and two approximations of the exact expression of the collision probability rate (eq. (11)). The first
approximation (solid line) ignores the non-diagonal entries of the covariance matrix while the second approximation (dashed line) Taylor-expands the pdf to
linear order with respect to the off-diagonal elements of the inverse covariance matrix around 0.

0.35
starting point
with increment of 0.5s
with increment of 0.2s around max
linear-order approximation
linear-order approximation with reduced samples

0.4

starting point
with increment of 0.5s
with increment of 0.2s around max
linear-order approximation
linear-order approximation with reduced samples

0.3

collision probability rate [s -1 ]

collision probability rate [s -1 ]

0.5

0.3

0.2

0.25

0.2

0.15

0.1

0.1
0.05

0

0

2

3

4

5

6

7

8

2

3

4

t [s]

5

6

7

8

t [s]

(a) Front scenario collision probability rate

(b) Front-Right scenario collision probability

0.6

0.5
Monte-Carlo simulation
linear-order approximation
linear-order approximation with reduced samples

0.5

Monte-Carlo simulation
linear-order approximation
linear-order approximation with reduced samples

0.45

collision probability []

collision probability []

0.4

0.4

0.3

0.2

0.35
0.3
0.25
0.2
0.15
0.1

0.1

0.05

0

0

2

3

4

5

6

7

8

t [s]

(c) Front scenario collision probability rate

2

3

4

5

6

7

8

t [s]

(d) Front-Right scenario collision probability

Fig. 8. Examples for reducing the number of calculations to determine the collision probability rate and the integrated collision probability. (a) and (c) show
the results for the front scenario and (b) and (d) for the front-right scenario. The used parameters in these examples are ∆t1 = 0.5s, ∆t2 = 0.2s and
+
dPC
dt low

= 0.01. In doing so the number of calculations for the collision probability rate could be reduced from 120 (using a fixed sampling increment of
∆t = 0.05s) to 13 for the front scenario and to 16 for the front-right scenario, respectively.

spreading of pt (x0 ) and hence the maximum is reached earlier.
The above discussion shows that temporal collision characteristics are encoded by the distribution of the collision

probability rate which incorporates the full geometry of the
host vehicle as well as process noise during prediction.
A quantity called TTC could then be defined as one of the

0.18
collision probability rate
TTC x

collision probability rate [s -1 ]

0.16

TTC y

0.14
0.12
0.1

0.14
collision probability rate
TTC x

0.12

collision probability rate [s -1 ]

characteristic properties of this distribution such as the mode
or the mean or the median or as a property of the integrated
collision probability rate, e. g. the time when the collision
probability exceeds a certain threshold.

0.1

0.08

0.06

0.04

0.02

0.08
0
2

0.06

3

4

5

6

7

8

t [s]
0.04
0.02
0
2

3

4

5

6

7

8

Fig. 11. Collision probability rate and mean of constant acceleration TTC for
an initial condition almost in front of the vehicle: (x, y) = (10, 0)m. The
process noise PSD for both coordinates has been increased to q̃x = q̃y =
0.1013m2 s−5 .

t [s]

Fig. 9. Collision probability rate and mean of constant acceleration TTC for
an initial condition at the front, right side of the vehicle: (x, y) = (10, 10)m.
The process noise PSD for both coordinates is q̃x = q̃y = 0.0405m2 s−5 .

0.4
collision probability rate
TTC

collision probability rate [s -1 ]

0.35

x

0.3
0.25
0.2
0.15
0.1

geometries such as a single line segment do not properly
characterize the true collision probability rate distributions.
The ground truth collision probability rate distribution has
been obtained by Monte-Carlo simulations and reproduced by
our derived collision probability rate expression. We have also
implemented an approximation of the collision probability rate
expression that can be computed in closed form on an embedded platform. This approximate formula provided collision
probability rate distributions that are almost indistinguishable
from distributions obtained by numerical integration for the
scenarios considered in this paper. In order to efficiently
sample this probability rate distribution for determination of its
characteristic shape we have worked out an adaptive method
to obtain the sampling points.
IX. ACKNOWLEDGEMENTS
Helpful clarifications by Prof. Georg Lindgren are gratefully
acknowledged.

0.05
0
2

3

4

5

6

7

8

t [s]

Fig. 10. Collision probability rate and mean of constant acceleration TTC for
an initial condition almost in front of the vehicle: (x, y) = (10, 0)m. The
process noise PSD for both coordinates is q̃x = q̃y = 0.0101m2 s−5 .

VIII. C ONCLUSIONS
As detailed in our literature review a common approach
to compute a collision probability is via temporal collision
measures such as time-to-collision or time-to-go. In this paper,
however, we have pursued a different approach, namely the
derivation of a collision probability rate without temporal
collision measures as an intermediate or prerequisite quantity.
A collision probability rate then affords the provision of a collision probability over an extended period of time by temporal
integration. We have also shown that computations of TTCs
using assumptions based on the shape of trajectories or the
prediction dynamics (disregard of process noise), or on simple

A PPENDIX
A. Partitioned Gaussian densities
In many calculations in stochastic estimation there is a need
to marginalize over certain elements of a state vector or to
obtain lower dimensional distributions by conditioning with
respect to certain elements. For these calculations the original
state vector ξ can be rearranged or partitioned such that xr
denotes the remaining state vector and xm denotes the states
to be marginalized over or which are used for conditioning.
 
xr
ξ=
(15)
xm
Hence the mean vector µ and covariance matrix Σ can be
partitioned into
 


Σrr Σrm
µr
µ=
, Σ=
(16)
µm
Σ>
rm Σmm
The following two well-known results on multivariate Gaussians are used in this paper:

a) Marginalization: The probability density of ξ
marginalized with respect to xm is
Z
p (xr ) =
p (ξ) dxm = N (xr ; µr , Σrr )
(17)
xm

b) Conditioning: The probability density of ξ conditioned on xm is

covariance matrix R(tk ). The measurement function h is given
by typical radar measurements (r, φ, ṙ), i. e.

p
x2 + y 2
y 

h(ξ) = arctan x 
x
ẋ+y
ẏ
√ 2 2
x +y

(24)
∂h
∂ξ

p (ξ|xm ) = p (xr |xm )
= N xr ; µr|m , Σr|m



(18)

with
µr|m = µr + Σrm Σ−1
mm (xm − µm )

(19)

>
Σr|m = Σrr − Σrm Σ−1
mm Σrm

(20)

and H =
is its linearization.
−
The covariance matrix P∞
at steady state can be determined
by the the discrete algebraic Riccati equation using the matrices defined above:
−
− >
P∞
= F P∞
F
− >
− >
−F P∞
H HP∞
H +R

−1

− >
HP∞
F

+Q
B. Dynamical system
The vehicle kinematics is characterized by a sixdimensional state vector
>
ξ = x y ẋ ẏ ẍ ÿ
(21)

(25)

C. Evaluation of the 2D integral for the collision probability
rate
The integral
Z Z
ẋ pt (y, ẋ|x0 ) dydẋ
(26)

The dynamical model is a discrete-time equivalent white noise
jerk model (see e. g. [14])

ẋ≤0 y∈Iy

in eq. (13) for the collision probability rate cannot be computed in closed form if the covariance matrix of pt (y, ẋ|x0 )
is not diagonal. Instead of a full numerical 2D integration
where
scheme we Taylor-expand the 2D pdf with respect to the off

∆t2k
diagonal element of the inverse covariance matrix around 0 to
1 0 ∆tk
0
0
2

2 
a certain order and then integrate. For a general 2D Gaussian
∆t
k 
0 1
0
∆tk
0
2 

pdf p(x1 , x2 ) = N (ξ; µ, Σ) with ξ = (x1 , x2 )> and mean µ

1
0
∆tk
0 
F (∆tk ) = 0 0

and covariance matrix Σ the Taylor-expansion to linear order
0 0
0
1
0
∆tk 


with respect to Σ−1
12 reads
0 0
0
0
1
0 

 

q
q
0 0
0
0
0
1
N (ξ; µ, Σ) = N x1 ; µ1 , Σ̃11 N x2 ; µ2 , Σ̃22



q
with ∆tk = tk+1 −tk . The corresponding predicted covariance
−
−1
matrix is denoted by P (tk+1 ). The process noise ν(tk )
·
−Σ12 (x1 − µ1 )N x1 ; µ1 , Σ̃11
is modeled by a white, mean-free Gaussian process with



q
covariance matrix Q
· (x2 − µ2 )N x2 ; µ2 , Σ̃22
 5

∆t4
∆t3
∆tk
k
k
q̃
0
q̃x
0
q̃x
0

20 x
8
6
2


∆t5
∆t4
∆t3
+O (Σ−1
k
k
k
 0
12 )
q̃
0
q̃
0
q̃ 
ξ − (tk+1 ) = F (∆tk )ξ(tk ) + ν(tk )

 4
 ∆tk
q̃

Q(∆tk ) =  8 x
 0
 3
 ∆tk
 6 q̃x
0

20

y

∆t3
k
q̃x
3

0
∆t4
k
8

q̃y

0
∆t3
k
q̃y
6

0
∆t2
k
q̃x
2

0

(22)

y

8

∆t2
k
q̃x
2

0
∆t3
k
3

q̃y

0

0

∆tk q̃x

∆t2
k
q̃y
2

0

6

0

y





q̃
y

2

0 
∆tk q̃y
∆t2
k

where q̃x , q̃y are the jerk power spectral densities (PSD) in xand y-direction of the underlying continuous noise process.
Discrete-time equivalent noise – as opposed to discrete-time
counterpart noise – has been deliberately chosen because the
power spectral density as characterizing noise parameter is
independent of ∆tk . Hence ∆tk in prediction can be changed
arbitrarily without adjusting the power spectral density.
The measurement model is
z(tk ) = h(ξ − (tk )) + r(tk )

(23)

where z(tk ) is the measurement and the measurement noise
r(tk ) is modeled by a white, mean-free Gaussian process with

Σ12
with Σ−1
12 = − |Σ| and Σ̃11 =
the following integral

|Σ|
Σ22 , Σ̃22

=

|Σ|
Σ11 .

This leads to

Zx1u Zx2u
x1 p(x1 , x2 )dx1 dx2 =
x1l x2l

!

#x1u
q
x1 − µ1
p
− Σ̃11 N x1 ; µ1 , Σ̃11
·
2Σ̃11
x1l
"
!#x2u
1
x2 − µ2
·
erf p
2
2Σ̃22
x2l
"
!#x1u


q
Σ̃11
x1 − µ1
−1
−Σ12 x1 Σ̃11 N x1 ; µ1 , Σ̃11 −
erf p
·
2
2Σ̃11
x1l


x2u
q

2
· Σ̃22 N x2 ; µ2 , Σ̃22
+ O (Σ−1
12 )
"

µ1
erf
2

x2l

We expand with respect to the off-diagonal entry of the
inverse covariance since this is the element that prevents factorization into one-dimensional Gaussians. We have checked
that Taylor-expansion with respect to the off-diagonal entry
of the covariance matrix leads to less accurate results to first
order.
R EFERENCES
[1] J. Jansson and F. Gustafsson, “A framework and automotive application
of collision avoidance decision making,” Automatica, vol. 44, no. 9, pp.
2347–2351, 2008.
[2] M. M. Muntzinger, S. Zuther, and K. Dietmayer, “Probability estimation
for an automotive pre-crash application with short filter settling times,”
in Proceedings of IEEE Intelligent Vehicles Symposium, 2009, pp. 411–
416.
[3] J. Jansson, “Collision avoidance theory: With application to automotive
collision mitigation,” Ph.D. dissertation, Linköping University Electronic
Press, 2005.
[4] A. Lambert, D. Gruyer, and G. Saint Pierre, “A fast monte carlo
algorithm for collision probability estimation,” in Control, Automation,
Robotics and Vision, 2008. ICARCV 2008. 10th International Conference
on. IEEE, 2008, pp. 406–411.
[5] M. Prandini, J. Hu, J. Lygeros, and S. Sastry, “A probabilistic approach
to aircraft conflict detection,” IEEE Transactions on intelligent transportation systems, vol. 1, no. 4, pp. 199–220, 2000.
[6] P.-J. Nordlund and F. Gustafsson, Probabilistic conflict detection for
piecewise straight paths. Linköping University Electronic Press, 2008.
[7] A. Genz, “Numerical computation of rectangular bivariate and trivariate
normal and t probabilities,” Statistics and Computing, vol. 14, no. 3, pp.
251–260, 2004.
[8] A. Eidehall and L. Petersson, “Statistical threat assessment for general
road scenes using monte carlo sampling,” IEEE Transactions on intelligent transportation systems, vol. 9, no. 1, pp. 137–147, 2008.
[9] Y. K. Belyaev, “On the number of exits across the boundary of a region
by a vector stochastic process,” Theory of Probability & Its Applications,
vol. 13, no. 2, pp. 320–324, 1968.
[10] G. Lindgren, “Model processes in nonlinear prediction with application
to detection and alarm,” The Annals of Probability, pp. 775–792, 1980.
[11] L. Mihaylova, A. Y. Carmi, F. Septier, A. Gning, S. K. Pang, and
S. Godsill, “Overview of bayesian sequential monte carlo methods for
group and extended object tracking,” Digital Signal Processing, vol. 25,
pp. 1–16, 2014.
[12] P. Broßeit, M. Rapp, N. Appenrodt, and J. Dickmann, “Probabilistic
rectangular-shape estimation for extended object tracking,” in Intelligent
Vehicles Symposium (IV), 2016 IEEE. IEEE, 2016, pp. 279–285.
[13] R. Altendorfer, “Observable dynamics and coordinate systems for automotive target tracking,” in Proceedings of IEEE Intelligent Vehicles
Symposium, 2009, pp. 741–746.
[14] Y. Bar-Shalom, X. R. Li, and T. Kirubarajan, Estimation with Applications to Tracking and Navigation. Wiley, 2001.

