Volume XLII-4/W8
Int. Arch. Photogramm. Remote Sens. Spatial Inf. Sci., XLII-4/W8, 109–116, 2018
https://doi.org/10.5194/isprs-archives-XLII-4-W8-109-2018
© Author(s) 2018. This work is distributed under
the Creative Commons Attribution 4.0 License.
Int. Arch. Photogramm. Remote Sens. Spatial Inf. Sci., XLII-4/W8, 109–116, 2018
https://doi.org/10.5194/isprs-archives-XLII-4-W8-109-2018
© Author(s) 2018. This work is distributed under
the Creative Commons Attribution 4.0 License.

  11 Jul 2018

11 Jul 2018

HIERARCHICAL PATH PLANNING FOR WALKING (ALMOST) ANYWHERE

K. Landmark and E. Messel K. Landmark and E. Messel
  • Norwegian Defence Research Establishment (FFI), P.O. Box 25, 2027 Kjeller, Norway

Keywords: Path planning, Clustering algorithms, LiDAR, Terrain mapping, Graph theory, Cost function, Walking, Open data

Abstract. Computerized path planning, not constrained to transportation networks, may be useful in a range of settings, from search and rescue to archaeology. This paper develops a method for general path planning intended to work across arbitrary distances and at the level of terrain detail afforded by aerial LiDAR scanning. Relevant information about terrain, trails, roads, and other infrastructure is encoded in a large directed graph. This basal graph is partitioned into strongly connected subgraphs such that the generalized diameter of each subgraphs is constrained by a set value, and with nominally as few subgraphs as possible. This is accomplished using the k-center algorithm adapted with heuristics suitable for large spatial graphs. A simplified graph results, with reduced (but known) position accuracy and complexity. Using a hierarchy of simplified graphs adapted to different length scales, and with careful selection of levels in the hierarchy based on geodesic distance, a shortest path search can be restricted to a small subset of the basal graph. The method is formulated using matrix-graph duality, suitable for linear algebra-oriented software. Extensive use is also made of public data, including LiDAR, as well as free and open software for geospatial data processing.