Collision Avoidance Using Partially Controlled Markov Decision Processes - Agents and Artificial Intelligence - page 87

An alternative to using dynamic programming for computing the entry time distribu-
tion offline is to use Monte Carlo to estimate the entry time distribution online. A Monte
Carlo approach does not require the uncontrolled variables to be discretized and does
not require D 0 ,...,D K ,D K to be stored in memory. However, using Monte Carlo in-
creases the amount of online computation. For problems where the conflict region is
small, the number of samples required to produce an adequate estimate of the distri-
bution may be large, though importance sampling can help improve this estimate with
fewer samples [8].

5 Airborne Collision Avoidance System

This section demonstrates the approach from the previous section on an MDP represent-
ing an airborne collision avoidance problem. In this problem, the collision avoidance
system issues resolution advisories to pilots who then adjust their vertical rate to avoid
coming within 500 ft horizontally and 100 ft vertically of an intruding aircraft. This
section considers a simplified version of the collision avoidance problem in which one
aircraft equipped with a collision avoidance system, called the own aircraft, encoun-
ters only one other unequipped aircraft, called the intruder aircraft. The remainder of
the section outlines the assumptions and decomposes the problem into controlled and
uncontrolled subproblems.

5.1 Assumptions

In this problem, s c represents the state of the vertical motion variables, and s u represents
the state of the horizontal motion variables. This problem defines coming within 500 ft
horizontally and 100 ft vertically of an intruder as a conflict.
The first assumption in Section 4.1 requires that s u ( t +1) depend only upon s u ( t ) .In
this collision avoidance problem, it is assumed that pilots randomly maneuver horizon-
tally, and that the advisories issued by the collision avoidance system do not influence
the horizontal motion.
The second assumption requires the episode to terminate when s u enters G .Inthis
problem, G is the set of states where there is a horizontal conflict, defined to be when an
intruder comes within 500 ft horizontally. The immediate cost when this occurs is given
by C ( s c ) , which is one when the intruder is within 100 ft vertically and zero otherwise.
In simulation, the episode does not terminate when s u enters G , since entering G does
not necessarily imply that there has been a conflict (e.g., the two aircraft may have
safely missed each other by 1000 ft vertically). However, it is generally sufficient to
plan up to the moment where s u enters G because adequate separation at that moment
usually indicates that the encounter is resolved.
The third assumption requires that for states where s u ∈

G the immediate cost func-
tion depends on the controlled state variables and the action. As outlined in Section 5.2,
the nonterminal cost function only depends on the advisory state and the advisory being
issued.