Roads, Rivers, and Obstacles: Optimal Two-Dimensional Path Planning around Linear Features for a Mobile Agent
- 1 December 1990
- journal article
- other
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 9 (6) , 67-74
- https://doi.org/10.1177/027836499000900606
Abstract
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(n2 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.Keywords
This publication has 4 references indexed in Scilit:
- Structure of intelligence for an autonomous vechilePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- An Efficient Snell's Law Method for Optimal-Path Planning across Multiple Two-Dimensional, Irregular, Homogeneous-Cost RegionsThe International Journal of Robotics Research, 1990
- An algorithmic approach to some problems in terrain navigationArtificial Intelligence, 1988
- An algorithm for planning collision-free paths among polyhedral obstaclesCommunications of the ACM, 1979