Evolving distributed agents for managing air traffic

Abstract

traffic management offers an intriguing real world challenge to designing large scale distributed systems using evolutionary computation. The ability to evolve effective air traffic flow strategies depends not only on evolving good local strategies, but also on ensuring that those local strategies result in good global solutions. While traditional, direct evolutionary strategies can be highly effective in certain combinatorial domains, they are not well-suited to complex air traffic flow problems because of the large interdependencies among the local subsystems. In this paper, we propose an evolutionary agent-based solution to the air traffic flow problem. In this approach, we evolve agents both to learn the right local flow strategies to alleviate congestion in their immediate surroundings, and to prevent the creation of congestion "downstream" from their local areas. The agent-based approach leads to better and more fault-tolerant solutions. To validate this approach, we use FACET, an air traffic simulator developed at NASA and used extensively by the FAA and industry. On a scenario composed of three hundred aircraft and two points of congestion, our results show that an agent based evolutionary computation method, where each agent uses the system evaluation function, achieves 40% improvement over a direct evolutionary algorithm. In addition by creating agent-specific "difference evaluation functions" we achieve an additional 30% improvement over agents using the system evaluation.