by Li, F, Klette, R and Morales, S
Abstract:
Finding a shortest path between two given locations is of importance for mobile robots, but also (e.g.) for identifying unique paths in a given surrounding region Π when (e.g.) evaluating vision software in test vehicles, or for calculating the free-space boundary in vision-based driver assistance. We assume that Π is given as a triangulated surface which is not necessary simply connected. Based on a known k-shortest paths algorithm and a decomposition of the surrounding region Π, this article presents an approximate algorithm for computing a general Euclidean shortest path (ESP) between two points p and q on Π, with time complexity κ(epsi;) ·O(k·|V(Pi;)|) and additional preprocessing in time O(k·|V(Π)|·log|V(Π)|) Our algorithm is suitable for approximately solving the 2D ESP problem, the 2.5 ESP problem (i.e., the surface ESP problem, as occurring, for example, in the free-space border application), and even the 3D ESP problem which is thought to be difficult even in the most basic case if all the obstacles are just convex, or if Π is just simply connected. ©; 2009 IEEE.
Reference:
An approximate algorithm for solving shortest path problems for mobile robots or driver assistance (Li, F, Klette, R and Morales, S), In IEEE Intelligent Vehicles Symposium, Proceedings, 2009.
Bibtex Entry:
@inproceedings{li2009anassistance,
author = "Li, F and Klette, R and Morales, S",
booktitle = "IEEE Intelligent Vehicles Symposium, Proceedings",
pages = "42--47",
title = "An approximate algorithm for solving shortest path problems for mobile robots or driver assistance",
year = "2009",
abstract = "Finding a shortest path between two given locations is of importance for mobile robots, but also (e.g.) for identifying unique paths in a given surrounding region Π when (e.g.) evaluating vision software in test vehicles, or for calculating the free-space boundary in vision-based driver assistance. We assume that Π is given as a triangulated surface which is not necessary simply connected. Based on a known k-shortest paths algorithm and a decomposition of the surrounding region Π, this article presents an approximate algorithm for computing a general Euclidean shortest path (ESP) between two points p and q on Π, with time complexity κ(epsi;) ·O(k·|V(Pi;)|) and additional preprocessing in time O(k·|V(Π)|·log|V(Π)|) Our algorithm is suitable for approximately solving the 2D ESP problem, the 2.5 ESP problem (i.e., the surface ESP problem, as occurring, for example, in the free-space border application), and even the 3D ESP problem which is thought to be difficult even in the most basic case if all the obstacles are just convex, or if Π is just simply connected. ©; 2009 IEEE.",
doi = "10.1109/IVS.2009.5164250",
isbn = "9781424435043",
language = "eng",
}