Issuing the right warnings

New approach to collision avoidance could
improve safety and efficiency

A new approach to warning pilots about imminent collisions could allow planes to fly more safely, even as airspace grows more crowded. The system being developed by MIT Lincoln Laboratory researchers Mykel Kochenderfer and James Chryssanthacopoulos and their associates, Professors Leslie Kaelbling and Tomas Lozano-Perez from MIT CSAIL, under sponsorship from the Federal Aviation Administration (FAA), relies on a precalculated table of risks to pick the best possible action to avoid midair crashes. It might eventually replace the Traffic Alert and Collision Avoidance System (TCAS), which was developed in the late 1970s and 1980s, when fewer aircraft were trying to share the same space.

"In very busy areas, such as around JFK, it's really important to use whatever airspace you have as efficiently as possible," says Kochenderfer. "The problem is TCAS assumes certain flight distances that may not be true in the future."

Unfortunately, it is no simple task to update TCAS. Over the years, as they collected data from both real-world experience and computer simulations of close encounters between aircraft, programmers have updated the computer logic underlying TCAS. They did that work using pseudocode, a simplified programming language that is understandable to humans but leaves out certain details. The problem with that approach is that the logic has evolved into a complex tapestry of programming so that what seems to be a simple tweak could have unintended consequences. "It's just grown to be very, very complicated, and if you change one part of the logic to try to fix a problem, you may introduce problems elsewhere because it has so many moving parts," Kochenderfer explains.

The legacy development required a manual revision of the pseudocode based on the evaluation after each step. The new method involves an optimization of the model and performance metrics to create a logic “lookup” table.The legacy development required a manual revision of the pseudocode based on the evaluation after each step. The new method involves an optimization of the model and performance metrics to create a logic "lookup" table.

Looking at where both planes are headed and how close they're likely to come, the current version of this system has three options: it can tell the pilot to climb at least 1500 feet per minute, it can tell the pilot to descend at the same rate, or it can do nothing and issue no alert at all. If the system issues an alert, the pilot is expected to react five seconds later by maneuvering the plane. Then the system has three new options. It can cancel the advisory and let the pilot go back to the original course. It can strengthen the advisory and tell the pilot to climb or descend faster. Or it can reverse the advisory, turning the descent into a climb, or vice versa.

How does the system know which action to tell the pilot to take, or whether to issue an alert at all? Kochenderfer has assigned a theoretical cost to different outcomes. The cost is highest for a so-called near midair collision—when the planes are within 500 feet of one another horizontally and within 100 feet of each other vertically. There is a much lower cost for issuing an alert. The cost of strengthening the advisory is slightly lower than the cost of reversing it because the maneuvering required to reverse is more difficult. If, for example, a conflict costs 1, an alert or a reversal might cost 0.01, and a strengthening might cost 0.009. There's also a slight bonus for not issuing an alert, so the system has an incentive to stop alerting once the danger has passed.

On the basis of the separation between two planes, the speed at which they're traveling, and any alert already being displayed to the pilot (lumped together as the "state" of the aircraft), Kochenderfer calculates a cost table by using a computational method called dynamic programming that shows how much a given choice is expected to cost in each situation. The system then simply measures which state it is in, looks that up in the cost table, and chooses the least expensive response.

The cost table is used in conjunction with the current state estimate of the aircraft to select the optimized advisory and notify the pilots of the appropriate action.The cost table is used in conjunction with the current state estimate of the aircraft to select the optimized advisory and notify the pilots of the appropriate action.

For instance, if an intruding aircraft a certain distance away is climbing at 1100 feet per minute, the table might show that the cost of issuing a descent order is 0.14. The cost for climbing at the same point is 0.65, and the cost of not issuing an alert is 0.66. Since the descent alert is the cheapest option, that's the one the system selects.

An important advantage of this approach is that the dynamic programming algorithm automatically computes the cost table from the assigned costs and from models of the expected pilot and aircraft behavior. Those models specify the probability of going to a particular state one second in the future, given the current state and a particular alert action. The human designers of the collision-avoidance system work with those cost assignments and models rather than attempting to design complex computer logic.

The onboard system doesn't have to actually calculate the cost of each action for all the possible states of the aircraft, of which there are millions. Instead, a desktop computer does those calculations and produces the cost table, which is stored in the onboard system. The system on the plane has merely to check the table to decide what to do. By using some simplifying assumptions, Kochenderfer was able to reduce the time to produce the table from weeks to under a minute.

The notional diagram above shows the transition probabilities for the three available actions from the current state.
The notional diagram above shows the transition probabilities for the three available actions from the current state. The best action is the one that minimizes the expected cost, taking into account the transition probabilities. In this example, there are only two transition probabilities to next states, although there may be many more in reality.
 

To test the system, Kochenderfer runs computer simulations. In one such experiment involving one million simulated encounters, airplanes using the current version of TCAS had 101 near midair collisions. The cost-table system issued a third fewer alerts than TCAS, and its planes had only one near midair collision.

Since the initial work, the system has been tweaked to relax some of the assumptions and make them more realistic while still giving reasonable computation times. For example, the system can now take into account the possibility of maneuvering horizontally and not just going up or down. Kochenderfer has also worked on computationally efficient methods for handling encounters with multiple intruders and strategies for coordination between collision avoidance systems, similar to what TCAS does today.

The human element has also been factored in. TCAS assumes that a pilot will execute a maneuver "perfectly," exactly five seconds after the alert, but in reality the pilot may react sooner or later, and might climb somewhat faster or slower than expected. Also added to the system is the ability to deal with uncertainty about the current state, in the form of calculating probabilities, in case the sensors aren't exactly accurate about the positions of the aircraft.

The beauty of the approach is that it shouldn't be as difficult to update as TCAS. If the FAA decides to change the system's behavior, on the basis of operational experience or changes in technology, it is just a matter of changing the cost assignments or models and calculating a new cost table. Although current collision avoidance is based on beacon radar readings to get the positions of aircraft, this approach would also work with anything else that gave accurate readings, such as GPS. "You can plug in any kind of sensor system you want, as long as you can produce these state estimates," Kochenderfer says.

Over the course of 2012, his team will be performing rigorous safety studies, running millions of simulations and looking for possible problems. If the FAA decides the approach is safe and effective, it can propose it as a replacement for the current TCAS system to the U.S. and international organizations that set the standards for airborne collision-avoidance systems. Because the model-based dynamic programming approach is so different from that followed in the past, it is expected to take some time to reach the international consensus required for such a change. However, the discussion is expected to revolve around issues such as the cost assignments, the pilot and aircraft behavior models, and the safety analysis and certification methods that are appropriate for this approach, rather than details of program logic design as in the past.

"The goal is to begin airborne flight testing in 2013 and to have a certified system available for use in aircraft currently equipped with TCAS within ten years," Kochenderfer concludes. "Additionally, this approach is also being explored as the basis for a collision-avoidance capability on unmanned aircraft and smaller general-aviation aircraft not currently equipped with TCAS."

Posted May 2012

top of page