Research accomplishments

Path enumeration in obstacle-rich airspace

Summary

Background

In an obstacle-rich environment like urban airspace, there needs a fast and robust method that can generate route candidates for aerial vehicles. The airspace to be used for both cargo and passenger carrying operations is limited in availability due to spatial constraints. The presence of buildings and terrains at low altitudes creates a challenging environment for drone navigation. In UAM airspace, airspace constructs, such as airport procedures, UAS facility maps and temporary flight restrictions, add difficulty in finding the altitude at which routes exist for a given OD.

Objective

This study proposes to use a two-layered graph structure that can be used for path enumeration in an obstacle-rich 3D environment.

Contribution

The propose method encodes the vertical and lateral connectivity in a compact graph structure. The first-layer graph encodes the vertical connectivity of airspace based on the topological concept of Reeb graph, whereas the second-layer graph encodes the lateral connectivity of airspace using the medial axis transformation. The two-layer graph structure enables a fast computation for path existence and can be used to find multiple route candidates in a fast and robust way using computational geometric algorithms (in time linear with the number of obstacles).

Related publication

Cho, J. (2020). Urban airspace availability assessment framework and its applications using geometric and topological algorithms (doctoral dissertation). Korea Advanced Institute of Science and Technology. [pdf]
Cho, J., & Yoon, Y. (2019). Extraction and Interpretation of Geometrical and Topological Properties of Urban Airspace for UAS Operations, ATM Seminar 2019. [pdf]

Proposed method

Two-layer graph structure of airspace

The entire airspace is sliced at parallel planes at altitude h. At each slice, there exist several disjoint pieces of airspace, each of which is called segment.

Note that every segment is a single connected component. Each segment is mapped to a single node in the Reeb graph, as it can be topologically retracted to a single point.

All of the segments are regarded equally in terms of topology, despite of their different geometrical features. In the proposed method, the geometric features are encoded based on the medial axis graph, in order to derive a data structure that contains both the vertical and horizontal connectivity within the entire airspace.

Obstructed airspace(left) and available airspace segments(right)

We modeled the vertical and horizontal connectivity of airspace using the two graph structures - Reeb graph and medial axis graph. In short, the vertical adjacency between airspace segments at different altitudes is modeled using Reeb graph, and the horizontal adjacency within each airspace segment is modeled using medial axis graph.

Reeb graph

Reeb graph is a shape descriptor widely used in computational geometry and computer graphics applications such as 3D shape encoding, segmentation, and comparison [1-6]. The method to compute an approximated Reeb graph [7-9] is detailed in the doctoral dissertation [10].

Medial axis graph

The inherent limitation of Reeb graph as a shape descriptor is that the geometry inside each segment is not embedded in the graph. Since every segment is a single connected component, it is mapped to a single node in Reeb graph as it can be topologically retracted to a single point. All of the segments are topologically equivalent, despite of their distinct geometrical features such as size and shape. This requires an additional graph layer to obtain a representation that retains also a geometric correspondence with the actual airspace.

The medial axis of a polygon is a subset of the Voronoi diagram generalized to an infinite set of points on the boundary [11-12]. One common way to compute the Voronoi diagram is to use the Delaunay triangulation of densely-sampled points on the polygon boundary, and detailed method is included in the doctoral dissertation [10].

Two-layer graph structure of urban airspace

Path enumeration process

Path enumeration has three steps.

Backbone search in the two-layer graph:
Identify airspace segments at various altitudes that aircraft can navigate to reach its destination, by searching through the Reeb graph. Find the sequence of medial axis nodes connecting starting and ending points.
Corridor construction:
Once the Reeb graph nodes and the medial axis nodes connecting O and D are found, construct a corridor that contains a set of feasible paths from O to D corresponding to nodes.
Path refinement in the corridor:
Find the shortest path inside the corridor, using triangulation-based pathfinding algorithm.

Illustratation of the proposed path enumeration process

1. Backbone search in the two-layer graph:

Given the origin and destination pair, we first locate Reeb graph nodes containing the OD pair. We then extract a backbone path in the Reeb graph by extracting the sequence of Reeb graph nodes that connect the origin and the destination.

Backbone search in the medial axis graph, corridor construction, and path refinement

2. Corridor construction

By utilizing connectivity information encoded in Reeb graph and geometric information embedded in medial axis graph, we generate corridors that contain a set of feasible path candidates.

Corridor construction step is largely based on the works of Explicit Corridor Map, ECM [13-15]. We compute a high-level path over a simplified medial axis graph and create the air corridor corresponding to the path.

The following figures show the corridor construction process of ECM. A slight modification is made so that a path can be computed while keeping non-uniform clearances from obstacles.

Medial axis transform based on constrained Delaunay triangulation (left) and corridor definition (right)

Corridor corresponding to the sequence of medial axis cells (left) and triangulated corridor (right)

Corridor retraction with respect to the safety margin of an agent

3. Path refinement in the corridor

The final path is found by performing the shortest path search inside a corridor. We use the Funnel algorithm [16] to find the unique shortest path from origin to destination inside the corridor, whose runtime is linear in the number of triangles.

Shortest pathfinding in a triangulated corridor using Funnel algorithm

Results

The case study area is the inner Seoul with its dimension 10 km X 15 km. This region consists of major business and residential districts of Seoul. Both terrain elevation and building heights are taken into account in constructing the airspace availability map as well as the two-layer graph structure.

Backbone pathfinding over a simplified medial axis graph is computed based on Dijkstra algorithm and has a linear time complexity with the number of intersections (nodes with degree>2) in the graph.

Path refinement takes a linear time with the number of obstacle vertices associated with the sequence of medial axis edges and thus the number of triangles. For 10 km X 15 km environment with various obstacles, the mean computation time for each computation step is below 0.2 seconds, as shown in the right figure.

Path refinement results, in Seoul airspace at an altitude of 80 m (available airspace is shown in green, corridors in different colors, and final path in magenta)

Average runtime for the two-layer graph construction

Average runtime for path emueration steps

Conclusion

Conventional grid-based approach to pathfinding in a large-scale map suffers from the trade-off between map accuracy loss and computation time; the higher the grid resolution of a map is, the greater the size of its adjacency graph, increasing the computation time for graph-search algorithms exponentially.

We can directly apply this framework to compute k-shortest loopless paths [17,18] on the simplified medial axis of a segment (in the backbone pathfinding step). A set of path options with additional information including the width of air corridor and the density of traffic in medial cells can be obtained within a few milliseconds.

By performing the path search at all navigable altitudes, one can provide operators with a rich information of path options so that the operators can choose their preferred path.

One limitation is that the refined path is not necessarily the globally shortest path. Generating k-shortest loopless paths may overcome this limitation. Offline and online construction time can be improved by at least three times ifrectangular geofence is used rather than circular one.

References

Reeb, G. (1946). Sur les points singuliers d' une forme de pfaff completement integrable ou d' une fonction numerique [on the singular points of a completely integrable pfaff form or of a numerical function ]. Comptes Rendus Acad. Sciences Paris , 222 , 847-849.
Pascucci, V., Scorzelli, G., Bremer, P. T., & Mascarenhas, A. (2007, August). Robust on-line computation of Reeb graphs: simplicity and speed. In Acm transactions on graphics (tog) (Vol. 26, No. 3, p. 58). ACM.
Tierny, J., Vandeborre, J. P., & Daoudi, M. (2006, October). 3D mesh skeleton extraction using topological and geometrical analyses. In 14th Pacific Conference on Computer Graphics and Applications (Pacific Graphics 2006) (p. s1poster).
Biasotti, S., De Floriani, L., Falcidieno, B., Frosini, P., Giorgi, D., Landi, C., … Spagnuolo, M. (2008). Describing shapes by geometrical-topological properties of real functions. ACM Computing Surveys, 40(4), 1–102. https://doi.org/10.1145/1391729.1391731
Ge, X., Safa, I. I., Belkin, M., & Wang, Y. (2011). Data skeletonization via Reeb graphs. In Advances in Neural Information Processing Systems (pp. 837-845).
Doraiswamy, H., & Natarajan, V. (2013). Computing reeb graphs as a union of contour trees. IEEE transactions on visualization and computer graphics, 19(2), 249-262.
Munch, E., & Wang, B. (2016). Convergence between categorical representations of Reeb space and Mapper. In 32nd International Symposium on Computational Geometry (SoCG 2016).
Singh, G., Mémoli, F., & Carlsson, G. E. (2007, September). Topological methods for the analysis of high dimensional data sets and 3d object recognition. In SPBG (pp. 91-100).
Shinagawa, Y., & Kunii, T. L. (1991). Constructing a Reeb graph automatically from cross sections. IEEE Computer Graphics and Applications, (6), 44-51.
Cho, J. (2020). Urban airspace availability assessment framework and its applications using geometric and topological algorithms (doctoral dissertation, chapter 3&4). Korea Advanced Institute of Science and Technology. [pdf]
Tam, T. K. H., & Armstrong, C. G. (1991). 2D finite element mesh generation by medial axis subdivision. Advances in engineering software and workstations, 13(5-6), 313-324.
DeFloriani, L., & Spagnuolo, M. (2008). Shape analysis and structuring. Springer.
Geraerts, R. (2010). Planning short paths with clearance using explicit corridors. Proceedings - IEEE International Conference on Robotics and Automation, 1997–2004. https://doi.org/10.1109/ROBOT.2010.5509263
Geraerts, R., & Overmars, M. H. (2007). The corridor map method: Real-time high-quality path planning. Proceedings - IEEE International Conference on Robotics and Automation, 1023–1028. https://doi.org/10.1109/ROBOT.2007.363119
Geraerts, R., & Overmars, M. H. (2008). Enhancing Corridor Maps for Real-Time Path Planning in Virtual Environments. Computer Animation and Social Agents, 64–71.
Chazelle, B. (1982, November). A theorem on polygon cutting with applications. In 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982) (pp. 339-349). IEEE.
Yen, Jin Y. (1970). An algorithm for finding shortest routes from all source nodes to a given destination in general networks. Quarterly of Applied Mathematics. 27 (4): 526–530. MR 0253822.
Eppstein, D. (1998). Finding the k shortest paths. SIAM Journal on Computing, 28(2), 652–673. https://doi.org/10.1137/S0097539795290477

Page updated

Google Sites

Report abuse