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

Finding a shortest path between two given locations is of importance for mobile robots, but also, for example, when identifying unique paths in a given surrounding region when evaluating vision software in test vehicles, or for calculating the free-space boundary in vision-based driver assistance. We assume that the surrounding region is given as a triangulated surface which is not necessary simply connected. Our algorithm is suitable for approximately solving the 2D Euclidean shortest path (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 the surrounding region is just simply connected.


  • English

Media Info

  • Pagination: 6p
  • Serial:
    • Issue Number: 284

Subject/Index Terms

Filing Info

  • Accession Number: 01384564
  • Record Type: Publication
  • Source Agency: ARRB
  • ISBN: 9781424435029
  • Files: ATRI
  • Created Date: Aug 22 2012 4:39PM