Roads, Rivers, and Obstacles: Optimal Two-Dimensional Path Planning around Linear Features for a Mobile Agent

摘要

We present an efficient algorithm for finding least-cost paths for an agent of negligible size across an important special case of two-dimensional terrain, terrain consisting of (1) a single isotropic homogeneous-cost-per-distance background region, (2) "roads" or narrow transportation corridors of low cost per distance, (3) "rivers" or narrow features of high crossing cost, and (4) untraversable "obstacles. " This work extends that of Mitchell (1987) by including rivers and new pruning heuristics for roads; our algorithm remains O(n 2 log n) in time complexity. We also show results of a first com puter implementation for this class of algorithms and analyze average-case performance and error sensitivity. This work applies primarily to high-level path planning for robots but also can help plan military maneuvers and guide construction of roads and pipelines.