Smarter Collision avoidance
By Keith Button|June 2017
Examining the aerospace industry’s next-generation software
On the morning of June 30, 1956, two airliners embarked on flights that would shape the next 60 years of air traffic safety measures. The planes departed from Los Angeles International Airport within three minutes of each other, one headed for Chicago and the other for Kansas City, Missouri. Their paths converged 90 minutes later, at 21,000 feet over the Grand Canyon in Arizona. The left wing of the Chicago-bound United Airlines Douglas DC-7 smashed into the tail of the Trans World Airlines Lockheed L-1049 Constellation, shearing off the tail of the Constellation and badly damaging the DC-7. Perhaps most terrifyingly, crash investigators reported that it was possible that the DC-7’s pilots saw the pending collision and attempted a last-second maneuver.
The angle of impact of the DC-7 on the Constellation, as deduced from the wreckage, suggested that the DC-7 was rolled to the right and pitched down relative to the Constellation. The collision killed all 128 aboard the two planes. At the time, it was the worst commercial air disaster in history.
The public outcry from the Grand Canyon air disaster spurred Congress to create the FAA in 1958. Among the agency’s first actions was to study potential collision avoidance systems that planes might carry to alert pilots. By 1981, researchers had developed the Traffic Collision Avoidance System, or TCAS, a box of electronics and software that transmits a radar signal that interrogates transponders on nearby planes. The responding radio signals contain the altitudes of the surrounding planes, and distance is calculated from the fractions of a second it takes for them to arrive. If the TCAS software on one plane judges another as too close, an automated voice sounds “traffic, traffic!” After a midair collision in 1986 that killed 79, Congress required all large aircraft in the U.S. to carry TCAS. Since 1993, Congress has required all planes with 30 or more passengers to carry TCAS 2, which issues coordinated collision resolution advisories to each pilot such as “climb, climb!” or “descend, descend!” or “level off, level off!”
Now, computer scientists and aerospace engineers are finishing development and testing of a new onboard alert software developed under the guidance of the industry’s RTCA association, founded in 1935 as the Radio Technical Commission for Aeronautics. The new software is called the Airborne Collision Avoidance System Xa, or ACAS Xa for short (The “a” stands for active surveillance.).
It’s supposed to outperform TCAS 2 on safety and reduce unneeded alerts by adopting a more modern computing approach and by taking advantage of GPS position reports in the messages sent from the Automatic Dependent Surveillance-Broadcast transponders that planes are starting to carry. The work is funded by the FAA, the European Organisation for Civil Aviation Equipment and RTCA.
The stakes will be high as ACAS Xa begins to replace TCAS 2. If market projections are accurate, air traffic will continue to grow. In the year of the Grand Canyon disaster, 45.9 million passengers flew on commercial airlines. That number climbed to 3.8 billion as of 2016 and is predicted to explode to 7.2 billion by 2035, according to the International Air Transport Association.
Fresh thinking
ACAS Xa and TCAS 2 take two very different computational approaches to the problem of calculating when to sound an automated voice alert to the pilot. The TCAS 2 software runs through a long series of “if-then” statements to determine whether to issue an alert. In contrast to this conventional computing method, developers of ACAS Xa at the Johns Hopkins University Applied Physics Laboratory in Maryland and MIT Lincoln Laboratory outside Boston capitalized on concepts within the field of artificial intelligence. The software directs the computer to make decisions based on probability distributions for possible outcomes at each step in a time sequence, because the exact circumstances for those decisions can be only partially known ahead of time.
The FAA began flight tests of ACAS Xa in March with a goal of validating the results of years of modeling and simulation. Developers don’t expect problems. Dating back to 2011, ACAS Xa software has run through millions of simulated encounters and 180,000 real-life potential collision situations as recorded by radar stations near busy airports. The testing and simulation results are analyzed by industry groups representing pilots, air traffic controllers, avionics manufacturers and others. Developers then tweak the ACAS Xa code based on this feedback. When the ACAS Xa code is finalized, an RTCA committee will recommend it as a standard for the FAA and regulators in Europe and elsewhere to possibly adopt by 2020.
For the FAA, shifting to ACAS Xa is about preparing for the future more than fixing any serious flaws in TCAS 2. There has never been a collision in U.S. airspace involving an airplane equipped with TCAS 2, and internationally, accidents and near misses have been rare.
Job number one for the developers was to make sure that ACAS Xa and TCAS 2 software would be interchangeable, so that transitioning to ACAS Xa would amount to a software upgrade by an avionics vendor. TCAS 2 and ACAS Xa run on the same components: a computer, typically weighing 5 to 9 kilograms; plus antennas; transponders; a control panel; and a visual display. For the crew, the experience will be the same in terms of the alerts. The initial “traffic, traffic!” alert prompts the pilot to look out the window to try to visually spot and avoid the other airplane. With both software options, an imminent collision, say within 15 to 35 seconds, prompts a computer voice to sound maneuver alerts, and the cockpit display tells the pilot at what rate to climb or descend. The altitude-encoded transponders on both aircraft communicate to coordinate the maneuver, so that if one climbs, the other descends.
When the planes are no longer in danger of hitting each other, the pilots hear “clear of conflict.” The collision avoidance maneuvers are always vertical; the systems do not tell pilots to turn left or right. Separately, FAA-funded developers of a version of ACAS for unmanned aircraft, dubbed ACAS Xu, are trying to build a computer program that can order horizontal collision avoidance maneuvers.
Seeing the future
Developers of ACAS Xa faced two main challenges: As precise as ADS-B is, the future trajectories of airplanes remain notoriously hard to predict mainly because of the range of navigation decisions that pilots of two planes might make. Secondly, ACAS Xa relies on transponders — both the altitude-encoded transponders of the TCAS 2 systems and the new ADS-B transponders — that provide data that isn’t always accurate. To solve those challenges, ACAS Xa attacks uncertainties with probability distributions.
“One of the things that ACAS leverages is that nothing that is unknown in the world is a point anymore,” says Josh Silbermann, project manager for ACAS and TCAS at the Applied Physics Lab. Unknowns are treated by the computer code as a “distribution” of possibilities. “We think [a plane is] going to be here, but it might be over there; there’s less of a chance it might be over there.”
TCAS 2 and ACAS Xa each receive updated transponder data every second, but aside from that, they take two different pathways of logic to predict the future. TCAS 2 starts out by predicting that two planes will continue flying straight on their current trajectories. Then it follows a series of if-then statements to expand its alerting criteria to account for the possibility that the straight-line predictions might be wrong. By contrast, ACAS Xa assumes that the current courses of the planes could change in a few seconds. It calculates every possible future pathway for the planes for the time period between the present and the time of possible collision. Then, for each of those pathways, it calculates the probability of the plane taking that pathway. It predicts the future pathways for every one-second increment moving forward in time. For example, starting from an airplane’s current trajectory, ACAS Xa might predict that one second into the future the airplane’s most likely state would be to continue flying straight with no acceleration. The second-most-likely state one second into the future might be flying in a straight line with a small acceleration and flying in a straight line with a small deceleration. And the third-most-likely state one second in the future might be a straight line with slightly larger accelerations or decelerations. From each possible state one second in the future, ACAS Xa calculates every possible state two seconds in the future, and the probability for each of those states. It calculates this for every one second increment into the future, figuring every possible future pathway and its probability within the given time.
ACAS Xa calculates its future pathways inside a bubble measuring 40 seconds from a possible collision. All of the calculations are completed ahead of time and loaded into the ACAS Xa software on the onboard computers. In flight, once two planes are 40 seconds away, ACAS Xa consults this giant look-up table containing 4.5 million possible future states between the present and the possible collision, calculated horizontally. Each state is defined in five dimensions: the vertical separation of the aircraft, the vertical rate of climbing or descent for the host aircraft, the vertical rate of climbing or descent for the other aircraft, the time until loss of horizontal separation and the current alert for the host aircraft — whether it’s being told to climb, for example. Each dimension is described in 10 to 60 ways.
The ACAS Xa giant look-up table also defines the correct alert action for every possible state in the 40-second bubble around a potential collision. The software has determined the optimal alert actions ahead of time, before the software is loaded into the onboard computer. It calculates this by starting at the end state, which is when the distance measured horizontally between the airplanes would be zero, also known as the closest point of approach. The closest point of approach isn’t necessarily a collision; it’s a stack of points along a vertical line where the horizontal distance to the other aircraft is zero. The software calculates the optimal action the pilot should take at the end state. Even if that end state is zero horizontal distance and zero vertical distance between the planes — essentially a collision — the software’s logic never sees giving up as an option; it always sees a mathematically optimal action to take. Then, backing up one second, it calculates every possible state that would lead to that end state. And for each of those backed-up-one-second states, it calculates the optimal action the pilot should take to avoid the end state.
The software repeats the process, backing up one second at a time, until it has covered every possible state — tens of millions of them — in that 40-second bubble, as measured in the five dimensions. An algorithm compresses the number of states to 4.5 million by removing duplicates.
In flight, once ACAS Xa locates the current state in the giant table, it executes the predetermined action: alerting or not alerting, and telling the pilot the avoidance maneuver if warranted. The alert or no-alert decision for each state is based on probability distributions that account for uncertainties, accounting for all possible outcomes and selecting the optimal decision, says Mykel Kochenderfer, a computer scientist and aerospace engineer at Stanford University who in 2008 created the concept that other researchers developed into ACAS Xa.
“The computer reasons about all of these low-probability events in a way that humans are not quite as skilled at doing,” he says. “We as humans like to think about the world evolving largely deterministically. So, we predict the aircraft flying straight. The computers, however, can take into account the probability that they’re flying straight — or they’re turning, or climbing — as the next step.”
The ACAS Xa approach of projecting the future as a range of probability-weighted possibilities is supposed to do a better job of accommodating the possibility that transponder data could be inaccurate.
“It’s fairly difficult for a human engineer to write down rules that will accommodate the spectrum of sensor error,” Kochenderfer says. “Even if you had perfect sensor information, you wouldn’t be able to perfectly predict where all the aircraft will be in the future.”
An example of the sensor error problem: Mode C transponders, typically flown on smaller aircraft, report altitude to the nearest 100 feet, while Mode S transponders typical for larger airplanes report altitude to the nearest 25 feet. So two airplanes equipped with Mode C transponders shown as flying within 200 vertical feet of each other might actually be flying with 150 to 250 feet of vertical separation. Even with altitude readings rounded off to the nearest 25 feet, a calculated climb or descent rate based on those readings could differ considerably from the actual rate.
Changing the rules
ACAS Xa also avoids what developers say is another major drawback of TCAS 2, which is that changing its rules for making alerts can be incredibly complicated. Altering any of the vast number of if-then rules in the TCAS 2 programming logic risks unintended consequences. Changing one rule can cause a ripple effect that forces programmers to make other changes in the system’s logic.
Regulators then require extensive modeling and testing to make sure no unintended consequences are missed. This means that even relatively simple changes to TCAS 2 can takes years to implement. A case in point was the fallout from the 2002 midair collision over Germany between a Tupolev Tu-154 passenger plane flown by Bashkirian Airlines and a Boeing 757 cargo plane flown by DHL. The incident exposed a dangerous flaw in the TCAS 2 logic and is the subject of “Aftermath,” an Arnold Schwarzenegger movie released in April.
With the two planes on a collision course, their TCAS 2 software coordinated a “resolution advisory” that instructed the Tupolev pilot to climb and the DHL pilot to descend. The trouble was, an air traffic controller had already told the Tupolev flight crew to descend, and the crew followed that advice rather than what they were hearing from their TCAS 2. Both planes continued to descend, and the resulting collision killed all 69 aboard the Tupolev and the two aboard the DHL plane.
Programmers set out to fix the TCAS 2 glitch that maintained a resolution advisory even when two planes continued on a collision course, because one of the planes did not comply with that advisory. It took nearly 15 years to prove that these relatively minor changes to its logic would be safe and win approval of regulators. The updated software is just now being rolled out. Adjusting the logic for ACAS Xa will be far easier than for TCAS 2, says Neal Suchy, the FAA’s program manager for ACAS Xa. Regulators can tweak the new collision avoidance system to accommodate changes much more quickly.
While ACAS Xa developers took several years to create the code that built the giant look-up table, it now takes only 10 to 15 minutes on a desktop PC to generate a new version of the table with modified parameters or conditions for advisories.
Programmers could make TCAS 2 account for anything that ACAS Xa does, if they wrote enough lines of code, Suchy says. “But that’s a dangerous game in terms of software development, in terms of all the different metrics we have to do; the time it takes to actually get that system out. We’re able to do these things much more efficiently and much faster and much better, with the ACAS X architecture.”
“Even if you had perfect sensor information, you wouldn’t be able to perfectly predict where all the aircraft will be in the future.”
Mykel Kochenderfer, Stanford University
SAFETY IMPROVEMENT
The FAA typically sets safety standards for airplane components as measured in acceptable failure rates, such as 1 catastrophic failure in 1 billion hours of flight time, or 1 in 10 million hours. But for collision avoidance systems, the FAA measures relative risk. For the best version of TCAS 2, if both airplanes are equipped with the system, their risk of colliding is 97 percent less than if they didn’t have the system.
For ACAS Xa, the relative risk is about 98.5 percent less than not having the system, or 40 percent better than TCAS 2.
