Overview
Increasing volume of air traffic brings up the task of estimating capacity of airspace. The major impact on the capacity comes from the uncertainties associated with weather. These projects aim at designing and implementing efficient algorithms for planning safe weather-avoiding jet routes. The design vs. implementation balance is up to a student and ranges from independent problem formulation and solution to coding of existing algorithms.
See slides from HIIT seminars: Traffic Flows Clustering Flight Trajectories Capacity Estimation Weather Impact Modeling
Collaborators: Joseph Mitchell, Irina Kostitsyna, Shang Yang   @   Stony Brook University
Collaborators: Jimmy Krozel, Joe Prete, Girish Sabhnani   @   Metron Aviation
Collaborators: Joondong Kim, Jason Zou   @   Google
Students: Anne Pääkkö, Niko Kiirala, Arto Vihavainen, Mikko Sysikaski
Contact: Valentin Polishchuk, valentin.polishchuk@cs.helsinki.fi
Project I: Maximum Flows amidst Moving Obstacles
Assume that the motion of obstacles is known in advance. How to plan a maximum number of safe trajectories for aircraft through an airspace? We developed an approximation algorithm for the problem, based on computing maximum flow in the ``motion graph'' built from an adaptive grid laid out in the time-space. The goal of this project is to implement the algorithm.
The algorithm is described in the paper Maximum Thick Paths in Static and Dynamic Environments. We also made a video Routing a Maximum Number of Disks through a Scene of Moving Obstacles about the algorithm.

Our solution: Sample outputs of the algorithm's implementation

More clips on our YouTube page.

Project II: Necklace in a Box
Every so often, aircraft may have to be put into a holding pattern (say, due to a congestion in an adjacent air sector, or just to let a storm pass by). Feasible air lanes must account for this. We model this requirement as the problem of finding "necklaces". Formally, a necklace is a path that contains a sequence of points such that the distance between consecutive points in the sequence is at most L, and obstacle-free pairwise-disjoint unit disks can be placed at the points. The hardness of the problem, as well as finding shortest necklace, a maximum number of necklaces, etc. are open.

Our solution: We implemented a heuristic that finds the necklaces one-by-one in a "bottomost" fashion;
see the paper, the applet, the slides and other slides.

necklace
Project III: Merging Traffic
Most congested and weather-impacted regions of airspace are found in vicinity of airports. To ensure smooth landing, an "arrival tree" has to be laid out in airport approach space. Merge trees are only practical if they merge two lanes into one per a merge point (that is, the tree should be binary); merging three or more lanes is difficult for air traffic controllers to monitor. Furthermore, we do not want merge points to be too close to one another; we require that the distance between any two merge points is greater than 1. This would give controllers enough time to solve merging problems independently of one another (in fact, we would never assign a single controller more than one merge point to monitor). The challenge is that if one merge point moves, it may force other merge points to move in order to maintain the separation of 1. So how do you move the merge points with the dynamics of the weather constraints in a way to always have merge points clear of weather hazards?

Our solution: Sample output of our implementation

See this page for the software, developed during a Software Engineering project at the CS Dept, the University of Helsinki.

Project IV: Path Planning in Face of Uncertainty
Weather is stochastic in nature. Hence exact location of obstacles for air traffic is not known precisely in advance. Rather, a set of one or more forecasts is available, each having an associated probability of being correct. The exact positions of the obstacles are revealed only when aircraft is already in the air. Our goal is to plan short routes for safely separated aircraft avoiding hazardous weather.
Possible project stages:
Stage 1: Read in real weather data and display it either as pixels, whose color corresponds to the projected intensity, or as a set of polygons, defined by the weather cells with intensity above a certain hazard threshold.
Stage 2: Plan path for one flight. Find a path so that the expected time to traverse it is small.
Stage 3: Moving obstacles. The shape of the obstacles and the directions, in which they move, are known (it may be assumed that they all move in the same direction, say, due to the wind). The speed of motion is a random variable.
Stage 4: Paths for multiple aircraft.
Project V: Changing Altitudes
We know how to compute capacity and route paths in an airspace on one flight level. What happens when two airspaces cross, e.g., when a descent cone crosses a constant flight level? One way to create room for descending planes is to reserve portions of the airspace for the crossing traffic. How to do it optimally, and what does "optimally" mean?
Project VI: Flying over Obstacles
During the en route portion of the flight, an aircraft commonly stays at a fixed altitude, and, if faced with an obstacle, has to fly around it staying at the altitude. An alternative way is to fly above the obstacle (assuming that the obstacle is not too "high"), possibly crossing into an adjacent fly level. In other words, lower flight levels may have more obstacles than higher ones, and an aircraft that cannot make it through at a lower flight level may choose to move up to a higher level. Then, more levels may be considered, with aircraft allowed to climb up one or two or K levels for getting over storm tops. Thus, higher flight levels must consider aircraft flying into them from the boundary, as well as from internal "pop ups" from the levels below. So how do you compute the maximum capacity when such "pop ups" between flight levels are allowed?
Project VII: Hub Placement
Air planes, after takeoff, follow a network of air lanes. Given the volume of air traffic, even a slightest improvement in the locations of the network nodes, even on a local scale, will lead to enormous savings. The goal of the project is to develop a tool to optimize placement of ``hubs'' --- intersections of the ``highways in the sky''. The locations for the hubs are not completely arbitrary --- at the current stage they need to be supervised by human air traffic controllers (e.g., the hubs may have to be placed far from hazardous weather cells or from no-fly zones). The developed tool must allow controllers to specify allowable regions for the hubs. Hub placement can be formulated as a continuous optimization problem and solved via Second-Order Conic Programming; technical details are given in this pdf file.


The projects may be treated independently from each other, but, of course, they all are pieces of a big picture, and can be mixed and matched. E.g., we may want to design arrival trees with wiggle rooms in presence of uncertainty etc. etc.