Hexagonifying aviation
Eugenio Neira
Grid-based geographic indexing systems are necessary for structuring two-dimensional space information (also higher dimension extension) and streamlining operations such as geographic querying, distance comparisons, proximity searches, spatial visualizations or flexible aggregations. Some of the most popular open-source spatial indexing systems are Google’s S2, Niemeyer’s Geohash and Uber’s H3.
One of DataBeacon’s key technical decisions last year was to move toward hexagonifying air space based on H3. This hierarchical hexagonal grid system, developed by Uber Engineering, has several advantages over other indexing systems:
- H3 has a hierarchical structure with a range of resolutions with an average length varying approximately from 600 NM (lowest) to 2 ft. (highest).
- The number of neighbours for hexagon grids (6) is minimum compared to square grids (9) or triangular grids (12).
- The distance to neighbour centroids is approximately constant at a given resolution.
- H3 reduces area distortion at varying latitudes compared to other grid index systems. Thus, hexagons look better on projection visualizations (i.e. Mercator).
- H3 cell indexes are designed to be integers (64 bit); when needed, they can be cast to strings. Integer representation usually allows higher performance than string operations.
- H3 has a well-documented and straightforward API with multiple programming languages support: Python, Java (portable to Scala), JavaScript and C.
- H3 has a historical track record of Data Science and Machine Learning research use cases and applications, starting from Uber’s rides matching, route optimization or flow modelling.
You can find the complete user guide and API reference here.
Would you like to know more details about use cases that can benefit from H3’s strengths?
The following summarises some of the problems H3 has helped us solve, from structuring airspace to developing real-time spatial applications. Moreover, we anticipate it will be very beneficial for upcoming machine learning applications or ATM network analyses.
Reduce the complexity of conflict detection
Real-time computation of potential conflicts over European air space requires an efficient strategy to reduce the complexity of the number of flight pairs combinations. For instance, given that the order of magnitude of en-route traffic over Europe is greater than 1,000 flights on-peak hours, the number of potential combinations tops 1 million.
An intelligent approach to this problem without computing all flight pairs’ distances is to apply H3 geospace indexing. We can simplify the number of suitable conflict computations by filtering flight pairs located in hexagon cells that, at a given resolution (size), are separated by less than a certain distance radius. For instance, if we aim to determine flight loss of separation at least 10 minutes beforehand, considering the worst case scenario of two aircraft flying in opposite directions, we would set a radius of approximately 160 NM to filter the flight pairs. Therefore, we simplify the number of combinations significantly compared to brute forcing computations all over Europe.
In case the time horizon is longer, we could reduce the number of flight combinations with a hybrid approach focused on time and space. It is said, we apply geo indexing to filter unique flights pairs within a distance radius threshold using location projections at discrete time steps (i.e. position now, in 10 minutes, in 20 minutes). Following this approach, we take into account not only the current distance but also the flight’s direction; thus, we can decrease the radius of comparison according to the length of the time step and ultimately reduce the complexity of the problem.
FIRs, sectors and airspace configuration geocoding
Airspaces are composed of a hierarchical, often irregular, structure of air volumes. Area Control Centers (ACC) manage en-route traffic for the upper airspace of the Flight Information Regions (FIR), and generally, they are organised into multiple sectors of smaller size. Moreover, the configuration and combination of active sectors may evolve over time depending on traffic demand versus capacity, adverse weather conditions or particular events, such as ATS equipment tests.
Therefore, flight positions lend themselves to being translated by latitude, longitude and altitude to an airspace sector or FIR. H3 can simplify the approach; for example, we create maps between H3 cells and altitude ranges to sectors. In other words, sectors are defined as combinations of prismatic hexagons. Therefore, we can simply hash the flight coordinates (latitude, longitude) into an H3 cell which, together with altitude, would be mapped to the corresponding sector. From there, we could efficiently retrieve airspace higher-level features, just like multi-sector, configuration or FIR.
Flexible space-time aggregations
In the context of Sierra5, our digital assistant for the ATCO supervisor, we aim to make flexible aggregations of different key indicators for complexity over time and space. To achieve so, we found H3 very handy; flight 4D trajectories can be propagated through the grid cells over time, labelling characteristic times (entry and exit), altitude and relevant events. Then, based on the geocode strategy explained in the previous section, we can map the H3 cell propagation to air space volumes as sectors or FIRs or sectors. As a result, ATCO supervisors can observe the current and expected state of different airspace configurations; for instance, they can analyse occupancy (flights demand), the number of conflicts, the number of non-conflicting or the number of traffics under evolution. Eventually, all these KPIs could be the foundation for assessing complexity or workload, a topic of frequent discussion that may arise in another post.
Wind grids
Another interesting application of hexagons in aviation is weather grids. For instance, we are have developed a model that allow us to augment wind information from traditional weather providers, where the granularity across altitude levels is low. Aircrafts provide data from wind and temperature sensors along flight routes. Local wind per flight is easily retrievable from ADSB and Mode S data, calculated as the difference between true air speed and ground speed vectors. Thereafter, local wind measurements can be cleaned and merged smartly to build an accurate 3D wind grid in areas and altitudes of flights coverage. The definition of the grid cells based on H3, due to its efficient and versatile API, facilitates the aggregation of local measurements and the use of grids in multiple applications: for example, labeling wind along a given flight trajectory and adjusting ground speed by segment.
We highly recommend h3 for managing geo-space data. The previous high level descriptions are just some examples from the first use cases within Databeacon projects and we are still looking forward to unlocking h3’s full potential in upcoming machine learning applications that may enhance air traffic management solutions.
Author: Eugenio Neira