Information Technology Reference
In-Depth Information
During execution, the results from offline computation are combined to determine the
approximately optimal action.
The approach is demonstrated on an airborne collision avoidance system that rec-
ommends vertical maneuvers to a pilot. Although the pilot may maneuver horizontally,
it is assumed that the system does not influence the horizontal motion. The problem
is naturally represented using seven state variables, which is impractical to solve with
a reasonable level of discretization. By carefully decomposing the problem into two
lower-dimensional problems, a solution can be obtained quickly and stored in primary
memory. The optimized system is compared with the Traffic Alert and Collision Avoid-
ance System (TCAS), currently mandated worldwide on all large transport aircraft [22].
The next section summarizes related work on collision avoidance. Section 3 reviews
Markov decision processes. Section 4 describes the solution method and outlines the
required assumptions. Section 5 applies the method to airborne collision avoidance.
Section 6 evaluates the method in simulation with TCAS as a baseline. Section 7 con-
cludes and outlines further work.
2
Related Work
A common technique for collision avoidance in autonomous and semi-autonomous ve-
hicles is to define conflict zones for each obstacle and then use a deterministic model,
such as linear extrapolation, to predict whether a conflict will occur [4,10,6]. If conflict
is anticipated, the system selects the maneuver that provides minimal path deviation
while preventing conflict. Such an approach requires little computation and can prevent
collision much of the time, but it lacks robustness because the deterministic model ig-
nores the stochastic nature of the environment. Although one may mitigate collision risk
to some extent by artificially enlarging the conflict zones to accommodate uncertainty
in the future behavior of the vehicles, this approach frequently results in unnecessary
path deviation. The TCAS collision avoidance logic adopts an approach along these
lines but incorporates many hand-crafted, heuristic rules to enhance robustness.
Several other approaches to collision avoidance can be found in the literature that
do not use a probabilistic model of vehicle behavior, including potential field methods
[13,11,12] and rapidly expanding random trees [19,18,23]. However, avoiding collision
with a high degree of reliability while keeping the rate of path deviation low requires the
use of a probabilistic model that accounts for future state uncertainty. Several methods
have been suggested that involve using a probabilistic model to estimate the probability
of conflict and to choose the maneuver that keeps the probability of conflict below some
set threshold [26,5,15]. One limitation of these threshold-based approaches is that they
do not model the effects of delaying the avoidance maneuver. In many cases, it can
be beneficial to observe how the encounter develops before committing to a particular
maneuver. The dynamic programming approach pursued in this work, in contrast, takes
into account every possible future sequence of actions taken by the collision avoidance
system and their outcomes when making a decision.
