Air Traffic Routing With Memgraph

It’s no secret that air traffic control (ATC) is one of the most stressful jobs in the world. Controllers must be quick-witted, alert, and have good decision-making skills. There are many things to consider when monitoring flights, such as avoiding collisions and storms. Sometimes pilots need to perform emergency landings. Flights get delayed or cancelled. Many things can go wrong and holding it all together is difficult work that requires teams of specialists. Even though aviation has much progressed throughout the last two centuries, there is still room for improvement in many areas of the field. Here we’ll look at how Memgraph Lab can help calculate and visualise some common ATC tasks.

Airplanes and Graphs

When travelling from one airport to another, airplanes use specific locations to navigate in the sky. These locations are called waypoints and are defined by their coordinates. Modern airplanes track these waypoints using radionavigation systems such as GPS or VOR. Both airports and waypoints, like many other aviation elements, have unique ICAO code names, and as such can be represented by nodes of a graph. If you’re not familiar with graphs and graph concepts, you can learn more about them here. In short, graphs are structures built from nodes that represent entities and relationships that represent the connections between them. With that in mind, it’s obvious that airports and waypoints can be different nodes, and the airways between them can be the relationships. The standard abbreviations for airports and waypoints are ARP and WPT, respectively, and in the following examples we will use them to define the types of our nodes.

Why Memgraph Lab?

The answer is simple: it has an integrated map of the world! Once nodes that have properties named “lat” and “lng” are loaded into the database, they are pinned to their rightful positions on the map as it appears. This gives us a clear view of the problem, as we can see the nodes as fixed points on Earth rather than moveable abstract objects. Let’s try it out!

You can find Memgraph Lab on our download page and get started by following this guide.
Once it’s ready, we’ll go to the Query tab and run the following:

CREATE (n:ARP { id: "EGLL", lat:51.477501, lng:-0.461389});

Now that we’ve created an airport node, we can see what it looks like on the map:

MATCH (n:ARP) RETURN n;

Our map is generated and it shows an ARP node with the id “EGLL” which is the London Heathrow Airport.

Loading Data

We’re gonna need more than one node to demonstrate how an airplane trip works. Instead of running the same query hundreds of times, we can import a premade set of nodes and relationships into our database. I’ve created CSV files that contain information about certain airports, waypoints and the relationships between them.

• airports.csv
• waypoints.csv
• airways.csv
• sid_stars.csv

Using this tutorial, we can load the above files and create our graph database. As previously mentioned, airports are nodes labeled ARP and waypoints are nodes labeled WPT. A relationship between two waypoints is called an airway and is labeled as such. A relationship between an airport and a waypoint includes specific route procedures called SIDs and STARs, so the relationship’s type is SID/STAR. Relationships also show the distance between two navigation points. The distance is measured in nautical miles, as it’s the favoured unit of measure in aviation. If the data was imported correctly, running the following query should produce a similar result.

MATCH (n)-[r]-(m) RETURN n,r,m;

In this case, the orange nodes are airports (ARP) and the purple nodes are waypoints (WPT).

Faster Travel

Let’s say we need to make a trip from London to Paris. More specifically, from the London Heathrow airport to the Charles de Gaulle airport in Paris. The graph we’ve previously loaded was designed for this example, as there are no navigation points outside the general routing direction, because pilots and air traffic controllers know in which direction the airplane should leave the airport. This gives us a limited but still complex network of navigation points (as seen in the previous paragraph) that are supposed to lead the airplane to its destination. Normally, a pilot doesn’t have to follow every waypoint on the route and he could fly the airplane as he pleases until finding the next waypoint, but following them is encouraged, as it’s much safer in the long run. We would like to make the trip as short as possible, as to not waste time nor fuel. We can find the shortest path between Heathrow and Charles de Gaulle using the following query:

MATCH p = (:ARP { id: "EGLL"})-[* wShortest (e, n | e.dist_nm)]-(:ARP { id: "CDG"})
RETURN p;

We would like more information about the trip. Which waypoints is the pilot supposed to follow to make the quickest safe trip?

MATCH p = (:ARP { id: "EGLL"})-[* wShortest (e, n | e.dist_nm)]-(:ARP{id:"CDG"})
UNWIND (nodes(p)) AS rows
RETURN rows.id;

If we click on Data, we will be able to see the result. We now have a list of 17 nodes (2 airports and 15 waypoints).

To find out how long the entire trip is we just have to make some minor changes:

MATCH p = (:ARP { id: "EGLL"})-[* wShortest (e, n | e.dist_nm) total_dist]-(:ARP{id:"CDG"})
RETURN total_dist;

The result is the total distance in nautical miles.

Emergency Landing

A pilot can decide to make an emergency landing if a situation that requires it occurs. While there are different kinds of emergency landings, we will only demonstrate precautionary landing here because other landing types don’t include landing on airports. Precautionary landings can be caused by fuel shortage, bad weather or minor malfunctions, and in these situations, the goal is to leave the planned route and find the nearest available airport.

Let’s say the airplane has just passed waypoint BELDI and it needs to make a precautionary landing. From this waypoint, we must find the shortest path to an available airport. The query we need is similar to the previous one, except this time we are not looking for a specific destination airport.

MATCH p = (:WPT { id: "BELDI"})-[* wShortest (e, n | e.dist_nm) total_dist]-(:ARP)
RETURN p;

The result is a graph with the waypoint BELDI in the middle and paths branching out to different airports from it.

While this gives us a general view of all the possible landings we can make, we must find the path to the closest airport. We can do that by adding a limit to our previous query:

MATCH p = (:WPT { id: "BELDI"})-[* wShortest (e, n | e.dist_nm) total_dist]-(:ARP)
RETURN p, total_dist
ORDER BY total_dist ASC LIMIT 1;

We’ve found the nearest available airport quickly and the emergency landing was successful.

In some extreme cases, military airports may deny any emergency landings, so the airplane must look for airports that are open to the public. We can alter the previous query with this constraint:

MATCH p = (:WPT { id: "BELDI"})-[* wShortest (e, n | e.dist_nm) total_dist]-(:ARP {use: "Open to the Public"})
RETURN p, total_dist
ORDER BY total_dist ASC LIMIT 1;

Now we get a slightly longer journey.

MATCH p =(:WPT { id: "BELDI"})-[* wShortest (e, n | e.dist_nm) total_dist]-(:ARP {use: "Open to the Public"})
RETURN nodes(p)
ORDER BY total_dist ASC LIMIT 1;

Storm Evasion

Although most modern aircraft is designed to withstand stormy conditions, some difficult weather is best avoided. During a flight, pilots can either request for weather updates from ATC or they can pick up on upcoming storms via weather radar technology. In most cases, a dangerous area can be evaded without straying from the designated route too much, but sometimes the area needs to be steered clear of completely. In that case, a pilot may ask ATC to deviate from the route. Instead of controllers having to check for another route, we can let Memgraph Lab do it for us.

What if the pilot, while flying over waypoint TOMMO, received information from ATC that dangerous storms are located near waypoints ACORN, BEXIL and TMA18? He needs to avoid these locations while making the trip as short as possible. Let’s change the weather property of these waypoints.

MATCH (n:WPT { id: "ACORN"})
SET n.weather = "dangerous”

We do the same for the other two waypoints. Now we have to run the shortest path query again, but this time we need to add a filter lambda to only consider paths with no dangerous weather.

MATCH p = (:WPT { id: "TOMMO"})-[* wShortest (e, n | e.dist_nm) total_dist(e, n | n.weather="normal")]-(:ARP {id: "CDG"})
RETURN p, total_dist;

We’ve found the new route the pilot needs to take.

Visualisation with Style Editor

Using style script, we can customize visuals of our graphs and make the data more understandable at first glance. Once we click on the Style Editor, we notice it already has some styles applied:

How can we use Style Editor to illuminate our graph in a clever manner? Let’s look at our previous example with storms. We could colour all waypoints with dangerous weather red and enlarge them to invoke caution.

@NodeStyle Equals(Property(node, "weather"), "dangerous") {
    color: red
    color-hover: Darker(red)
    size: 30
}

After clicking Apply, our graph should look like this:

What about edges? We could colour all edges that use SID and STAR procedures in orange to make them stand out.

@EdgeStyle Equals(Type(edge), "SID/STAR") {
    color: orange
    width: 200
}

What if we wanted to see which airways are longer than 50 nautical miles? Let’s colour them magenta.

@EdgeStyle And(Equals(Type(edge),"AIRWAY"),Greater(Property(edge,"dist_nm"),50)) {
    color: magenta
    width: 200
}

The possibilities are endless. You can play around with Style Editor as much as you like and make your graph look unique.

Conclusion

There are many things that can be optimized in aviation, just like in any other modern industry. A large network of navigation points is a classic graph structure and as such would benefit greatly from using a graph database. We’ve gone through some basic functionalities of Memgraph Lab to show how its features can be used to manipulate data with an emphasis on speed, visual display and ease of understanding. If you’re feeling creative, you can come up with your own flight scenarios and try them out. The sky's the limit!