Collision Avoidance for Unmanned Aircraft using Markov Decision Processes*

Selim Temizer, Mykel J. Kochenderfer, Leslie Pack Kaelbling, Tomás Lozano‐Pérez, James K. KucharAIAA 2010 · DOI

TL;DR

This paper proposes using Markov Decision Processes (MDPs) and Partially Observable Markov Decision Processes (POMDPs) to automatically generate robust collision avoidance strategies for unmanned aircraft. By modeling aircraft dynamics, sensor limitations, and intruder behavior, their approach can optimize for both safety and flight plan adherence, demonstrating effectiveness across various sensor types.

What Problem Does This Paper Address?

Integrating unmanned aircraft (UAs) into civil airspace is a significant challenge, primarily due to the need for robust and reliable sense-and-avoid capabilities. Unlike manned aircraft that rely on pilots, UAs require automated systems. Developing a universal collision avoidance system is difficult because of the vast diversity in UA platforms, sensor configurations, and their inherent limitations (e.g., field-of-view, noise, false positives/negatives). Existing systems like TCAS are designed for human pilots and are not autonomous. The FAA's stringent safety requirements necessitate a rigorous development and certification process, which is further complicated by the need to accommodate this wide range of UA characteristics. This paper aims to address this by proposing a flexible, model-based approach to automatically generate collision avoidance policies.

Methods

The core of this work lies in formulating the collision avoidance problem as a Markov Decision Process (MDP) or a Partially Observable Markov Decision Process (POMDP).

  • MDP Formulation: For sensors that provide precise localization of intruder aircraft, the problem is modeled as an MDP. This involves defining a state space (representing relative positions, velocities, etc.), an action space (vertical accelerations), and a reward function that penalizes collisions and protected airspace violations while also considering flight plan deviation.
  • POMDP Formulation: When sensors have positional uncertainty or limited field-of-view, the problem is framed as a POMDP. This adds an observation model to account for sensor noise, false positives/negatives, and limited sensing capabilities. The system then operates on a "belief state" – a probability distribution over possible true states.
  • Solution Approach: The authors leverage existing MDP and POMDP solvers (specifically mentioning Heuristic Search Value Iteration (HSVI) and Successive Approximations of the Reachable Space under Optimal Policies (SARSOP)) to compute optimal or near-optimal policies offline. These policies are then executed efficiently in real-time.
  • Sensor Modeling: Four sensor models are developed and used:
  • Perfect Sensor: Idealized, no noise, omnidirectional.
  • TCAS Sensor: Modeled after the Traffic Alert and Collision Avoidance System, with specific bearing, altitude, and range errors.
  • Radar Sensor: Limited field-of-view (FoV) with bearing, elevation, range, and range rate measurements, subject to noise and false detections.
  • EO/IR Sensor: Similar to radar but without range, relying on bearing and elevation with noise.
  • Aircraft Modeling: A parametric aircraft model is used, based on the Global Hawk UAV, with parameters for velocity and climb/descent rates.

Datasets

The paper uses a simulation framework that incorporates an "encounter model" derived from 9 months of national radar data to generate 15,000 scripted encounters between pairs of aircraft. This dataset is used to evaluate the performance of the developed collision avoidance systems against baseline approaches. No new datasets are introduced.

Key Insights and Ideas

  • Generality of MDP/POMDP: The paper demonstrates that MDPs and POMDPs provide a flexible and powerful framework for generating collision avoidance strategies that can adapt to diverse sensor capabilities and aircraft dynamics. This moves away from hand-crafting solutions for every scenario.
  • Balancing Objectives: The reward function is crucial for balancing competing objectives: minimizing collision risk (high penalty for NMAC - Near Mid-Air Collision) versus minimizing flight plan deviation (penalties for excessive maneuvering).
  • Impact of Sensor Limitations: The results clearly show how sensor limitations (especially limited FoV in radar and EO/IR) significantly increase collision risk compared to perfect or TCAS-like sensors. This highlights the importance of accurate state estimation and robust policy generation under uncertainty.
  • POMDPs for Uncertainty: POMDPs are shown to be effective in handling sensor uncertainty, allowing for strategies that can still achieve low risk ratios by making more conservative maneuvers to compensate for lack of precise information.
  • Offline Computation, Online Execution: The ability to compute complex policies offline and execute them efficiently in real-time is a key enabler for practical deployment.

Key Results

  • MDP with Perfect Sensor: Achieved significantly lower risk ratios and velocities compared to baseline systems (e.g., Basic CAS, Analytic CAS) when using a perfect sensor. For instance, with a vertical velocity penalty of -2.00, the MDP CAS achieved a risk ratio of 0.036734, far superior to the nominal flight risk ratio of 1.000000.
  • MDP with TCAS Sensor: Even with noisy TCAS sensor data and using a simple alpha-beta tracker for state estimation, the MDP CAS performed well, outperforming baseline TCAS-based systems in terms of risk ratio.
  • POMDP with TCAS Sensor: The POMDP approach for TCAS sensor data showed a significant reduction in risk ratio (0.002770) compared to TCAS Version 7, though it involved more maneuvering.
  • POMDP with Radar/EO/IR Sensors: These sensors, with their limited FoV, inherently lead to higher risk ratios than TCAS. However, the POMDP approach still managed to generate strategies that were superior to basic collision avoidance logic for these sensors. The EO/IR sensor results showed that accurate vertical localization is more critical than horizontal for evasive maneuvers.
  • Policy Verification: The paper notes that while POMDP-generated policies might be complex to verify, they can inspire hand-crafted techniques or serve as valuable baselines.

Limitations and Future Work

  • Discretization: The state space is discretized, leading to a loss of information from the full 13-dimensional aircraft state vectors. Finer discretization improves performance but drastically increases computation time.
  • Parameter Tuning: Many parameters were chosen through experimentation, and better matching of internal models to the encounter model could further improve performance.
  • Missing State Information: The current state representation does not include ownship's roll angle, which can be crucial for limited FoV sensors. This affects intruder detectability.
  • Observation Models: Coarse discretization of Gaussian distributions for sensor errors is used. More sophisticated discretization or analytical solutions could improve intruder localization.
  • Vertical Velocity and Closure Rate Estimation: Finer discretization of the projection plane is needed for more accurate estimation of intruder vertical velocity and closure rate, which currently can be affected by observation patterns.
  • 3D Motion: The current formulation is primarily 2D (relative motion in RCS). Extending to full 3D motion would significantly increase the state space size beyond current solver capabilities, necessitating investigation into new representations and solvers.

Summary updated

Abstract

we investigate the automatic generation of collision avoidance algorithms given models of aircraft dynamics, sensor performance, and intruder behavior. By formulating the problem of collision avoidance as a Markov Decision Process (MDP) for sensors that provide precise localization of the intruder aircraft, or a Partially Observable Markov Decision Process (POMDP) for sensors that have positional uncertainty or limited eld-of-view constraints, generic MDP/POMDP solvers can be used to generate avoidance strategies that optimize a cost function that balances ight-plan deviation with collision. Experimental results demonstrate the suitability of such an approach using four dierent sensor modalities and a parametric aircraft performance model.
BibTeX
@inproceedings{temizer2010collision,
  author = {Selim Temizer and Mykel J. Kochenderfer and Leslie Pack Kaelbling and Tomás Lozano‐Pérez and James K. Kuchar},
  title = {{Collision Avoidance for Unmanned Aircraft using Markov Decision Processes*}},
  booktitle = {AIAA},
  year = {2010},
  doi = {10.2514/6.2010-8040},
}
Figure