An approximate algorithm for solving shortest path problems for mobile robots or driver assistance

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 Pi when (e.g.) evaluating vision software in test vehicles, or for calculating the free-space boundary in vision-based driver assistance. We assume that Pi 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 Pi , this article presents an approximate algorithm for computing a general Euclidean shortest path (ESP) between two points p and q on Pi , with time complexity k(epsiv)-O(k - |V(Pi)|) and additional preprocessing in time O(k - |V(Pi)| - log |V(Pi)|). 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 Pi is just simply connected.