NSF ON NEXTGEN AIR TRAFFIC CONTROL SYSTEM

FROM:  NATIONAL SCIENCE FOUNDATION 

Designing tomorrow's air traffic control systems

MIT researcher explores algorithmic solutions to make flying more efficient
On a good day, flying can be a comfortable and efficient way to travel. But all too often, weather or overcbooking can cause delays that ripple through the system, inducing missed flights, anxiety, discomfort and lots of lost time and money.

Things had gotten so out of whack that in 2003, Congress enacted a law designed to bring online a Next Generation--or NextGen--air traffic control system by January 2020. The Department of Transportation would require the majority of aircraft operating within U.S. airspace to be equipped with new technology to track and coordinate aircraft and would institute many other programs to improve air travel.

"It's hard to argue that delays don't occur in the system," said Hamsa Balakrishnan, an associate professor of Aeronautics and Astronautics at the Massachusetts Institute of Technology (MIT). "The delays have not just economic costs--which are significant--they have environmental costs as well."

Balakrishnan began her career as an aerospace engineer. Over time, her research migrated from the nuts-and-bolts of how aircraft fly, to the details of how air traffic systems operate overall. Today, she studies air traffic control and management and works to come up with the analytic tools and algorithms required to keep flights safe and runways moving efficiently.

"We know that demand is projected to increase," she said. "How do you build algorithms that don't let your delays explode, while at the same time meeting the increased demand?"

According to Federal Aviation Administration (FAA) estimates, increasing congestion in the air transportation system of the United States, if unaddressed, will cost the American economy $22 billion annually in lost economic activity by 2022. Balakrishnan and her colleagues believe they can address major inefficiencies in the system through a combination of better models of air traffic control systems and new embedded technologies.

Even small changes in air traffic management can have a large impact on the overall air travel system. For instance: pushback, the rate at which aircraft should be leaving their gate.

"Aircraft are allowed to push back whenever they're ready to, and the problem with this is, the runway capacity is constrained," Balakrishnan explained. "Planes can only take off one at a time from a single runway, so it doesn't make sense for fifteen or twenty aircraft to be waiting there at the same time."

Aircraft taxiing on the surface contributes significantly to emissions at airports. The quantities of fuel burned, as well as different pollutants, are proportional to the taxi times of aircraft (as well as airline decisions on whether engines shut down during delays). As planes idle, unsure when they'll be called to release and unwilling to lose their departure slot due to delay, they use fuel and emit exhaust into the atmosphere.

Balakrishnan imagined a better way.

"If we can use data to predict the rate at which aircraft are going to be taking off from the airport," she continued, "then we can figure out the rate at which aircraft should be leaving their gates and starting their engines."

Over the course of years, she developed computer models that used reams of historical data to analyze and create realistic models of how airports (and the people who run them) operate under a wide range of conditions. She used these models to test ways of more efficiently releasing airplanes from airports.

When Balakrishnan had run enough virtual experiments to trust her models and the improved pushback algorithms they'd helped shape, she took her results to the FAA and to all of the major air carriers and asked for a chance to test her methods under real airport conditions. Amazingly, they said yes.

After developing algorithms that recommend the rate at which aircraft should leave their gate, Balakrishnan and her team--including Ioannis Simaiakis, Harshad Khadilkar, T.G. Reynolds and R.J. Hansman, from MIT--went in and figured out the best form of the solution that controllers could actually implement.

"The controllers told us they'd like to be told the rate that aircraft needed to be released from their gates in 15-minute increments," she recalled. "We just used color coded cards to tell them what the suggested rate was, and we found that they went along with the suggestions and implemented them and that there was a lot of benefit to be had."

But that wasn't the end of the experiment. In 2011, Balakrishnan and her team had a much better handle on the model of the system. So they ran the experiment again using even more advanced algorithms to predict the optimal pushback rates. They also developed an interface with an Android tablet computer that would communicate the pushback rate to the controllers and that the controller could use that to implement the rate for aircraft preparing to take off.

The researchers showed that, without adding any delays to the system, they were able to limit idling times and save fuel.

"In Boston, we did about 15 days of metering and anecdotally, the traffic managers believed that the surface flows during certain times were smoother when we were implementing our solution," Balakrishnan said. "We also showed that, just holding aircraft back for about 4.4 minutes, we saved between 50-60 kilograms [100 pounds] of fuel for each aircraft. Those are significant savings."

The results of the work were reported in several journal papers, most recently Transportation Research Part A: Policy and Practice in August 2014. The work also won the inaugural CNA (formerly the Center for Naval Analysis) Award for Operational Analysis in 2012, which "recognizes work that is judged as having provided the most creative, empirically based support for a real-world decision or solution to a real-world problem."

Balakrishnan and her collaborators are now planning to "pilot" a new study at LaGuardia Airport in New York City, testing their algorithms and implementation strategy at another airport, under different conditions.

Balakrishnan research is unique in the degree to which it takes into account conditions in the field. For instance: How do air traffic controllers react in the face of crowded conditions or inclement weather? How often do pilots diverge from the instructions given by controllers? And to what degree are air carriers willing to change their practices for the good of the system?

"There's this chance to actually use algorithms--the kind of control algorithms that I like developing--in a practical setting," she said. "How do you design algorithms that are practical and that can account for the fact that different people have different agendas? Just in terms of understanding the system, it's important, because it's a system that influences a couple billion people a year."

In 2007, Balakrishnan was awarded a Faculty Early Career Development (CAREER) award from the National Science Foundation (NSF) to begin studying these questions. Her research continued as part of the NSF-funded ActionWeb project (2009-2015), whose goal is to develop networked, embedded, sensor-rich systems that can coordinate among multiple decision-makers. Her work is part of a growing effort to design better Cyber-Physical Systems--systems where humans and computers work together to accomplish a task: in this case the efficient landing and take-off of aircraft.

"Air traffic management marries the physical world, including the airplanes and the environment in which they reside, with the control algorithms and the pilots and traffic control managers," said David Corman, a program director in the Computer and Information Science and Engineering directorate at NSF. "The algorithms that Dr. Balakrishnan and her team are developing can have huge societal impact through intelligent reduction of traffic delays and fuel consumption. We look forward to working with Dr. Balakrishnan and team to rapidly mature and transition these exciting capabilities into practice."

Not only are Balakrishnan's algorithms useful, the fundamental research that underlies them extends beyond air traffic control to many areas of research.

One of Balakrishnan's colleagues, Claire Tomlin of the University of California, Berkeley, is using related algorithms to study energy usage in a home, while another collaborator is working with Uber, the popular ridesharing service, to improve their queuing system.

Because of its fundamental nature, the work will have far reaching benefits.

"There are many cases where we can improve the performance of systems that billions of people interact with," Balakrishnan said. "And it all begins with fundamental research to develop better algorithms that incorporate data from the real world."

-- Aaron Dubrow, NSF
Investigators
Edward Lee
David Culler
Saurabh Amin
Claire Tomlin
Asuman Ozdaglar
S. Shankar Sastry
Hamsa Balakrishnan
Related Institutions/Organizations
University of California-Berkeley
Massachusetts Institute of Technology

PRODUCING ALOGORITHMS THAT ANALYSE HUMAN LANGUAGE

FROM:  NATIONAL SCIENCE FOUNDATION 

Growing field of natural language processing works at the interface of computers and language

Researcher's algorithm design produces valuable tools for translation, text mining, question answering and more

Most of us never actually bother to read text labeled "terms and conditions," "privacy policy," or "financial prospectus." We usually just check the "accept" box, assume all is well, and move on. Still, wouldn't it be nice to have a computer program that could read them for us, and alert us to any problems?

This ultimately could be among the potential benefits of natural language processing, a field that works at the interface of computers and language. The goal of this growing field, which dates back to the 1950s, is to enable computers to glean meaning from language through the use of automated algorithms that process linguistic data from text.

"Imagine a computer program that reads text and interprets it to do something useful, but not the way you and I would do," says Noah Smith, an associate professor at Carnegie Mellon University's School of Computer Science. "This program could read text that people don't like to read, or don't have time to read."

Smith designs algorithms that analyze human language, research that produces valuable software tools for translation, text mining, question answering, information extraction as well as "scientific discovery wherever text serves as data," he says, for example in sociolinguistics, political science or economics.

The National Science Foundation (NSF)-funded scientist specifically is studying computational models for natural language parsing and semantic analysis, that is, to "take a sentence and try to figure out what it means," Smith says. "Doing this could help with certain tasks that people cannot do easily, such as extracting information out of very large collections, and would rather delegate it to a computer that will perform consistently and without getting tired."

It's kind of like the automated equivalent of the sentence diagramming that many of today's adults engaged in during elementary school. "Our programs analyze sentences into deeper linguistic structures," Smith says.

To be sure, these programs have a long way to go before attaining human-like reading and comprehension skills, he says. However, "humans are not always perfect at these things," he says. "People do have cognitive limitations, or limitations on memory, or they get distracted. Computer programs have complementary strengths.

"The public perception of this artificial intelligence branch of computer science is often colored by fears that robots might replace us," he adds. "We are, in fact, trying to make tools that will make life easier and less tedious for people."

Smith is conducting his research under an NSF Faculty Early Career Development (CAREER) award, which he received in 2011. The award supports junior faculty who exemplify the role of teacher-scholars through outstanding research, excellent education and the integration of education and research within the context of the mission of their organization.

Smith also has applied his methods to problems like measuring public opinion as expressed in social media messages, and in understanding the underlying ecosystems of companies by scrutinizing their press releases. The latter could benefit economists who study companies, specifically how companies interact with government or with each other.

As for social media, "text exists in a larger social context," he says. "People don't create language purely because they feel like it. Social media, like Twitter and Facebook, are intended to be read by people we know, but often there is a much larger conversation that goes on. The advent of these platforms allows us to observe more of these interactions, and hopefully to develop statistical methods to better understand what people mean when they write or talk."

Educational activities as part of the grant include the development of new exercises and a competitive project within the undergraduate course on natural language processing. In past years, Smith has written problems for the Computational Linguistics Olympiad, a high school competition. Smith also is committed to tutoring and mentoring the graduate students he advises. His group calls itself "Noah's ARK."

"A lot of them interact with each other, including the junior doctoral students who can learn from the more senior ones," he says. "I try to promote opportunities for them to see all parts of my job, and work with me on not just research, but on service and teaching at the university and beyond."

Finally, his research group makes its software publicly available, not just for students in the classroom, but "so it can be used by other researchers and startup companies, as well as by regular people who want to try their hand at natural language processing," he says.

-- Marlene Cimons, National Science Foundation
Investigators
Noah Smith
Related Institutions/Organizations
Carnegie-Mellon University