HIERARCHICAL PATH PLANNING FOR WALKING (ALMOST) ANYWHERE

International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences

Landmark, K.^1¹ 

[1] Norwegian Defence Research Establishment (FFI), P.O. Box 25, 2027 Kjeller, Norway^1

关键词: Path planning;    Clustering algorithms;    LiDAR;    Terrain mapping;    Graph theory;    Cost function;    Walking;    Open data;   

DOI  :  10.5194/isprs-archives-XLII-4-W8-109-2018

学科分类：地球科学(综合)

来源: Copernicus Publications

【 摘 要 】

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.

【 授权许可】

CC BY