On robotic optimal path planning in polygonal regions with pseudo-Euclidean metrics.

Conference Paper

This paper presents several results on some cost-minimizing path problems in polygonal regions. For these types of problems, an approach often used to compute approximate optimal paths is to apply a discrete search algorithm to a graph G(epsilon) constructed from a discretization of the problem; this graph is guaranteed to contain an epsilon-good approximate optimal path, i.e., a path with a cost within (1 + epsilon) factor of that of an optimal path, between given source and destination points. Here, epsilon > 0 is the user-defined error tolerance ratio. We introduce a class of piecewise pseudo-Euclidean optimal path problems that includes several non-Euclidean optimal path problems previously studied and show that the BUSHWHACK algorithm, which was formerly designed for the weighted region optimal path problem, can be generalized to solve any optimal path problem of this class. We also introduce an empirical method called the adaptive discretization method that improves the performance of the approximation algorithms by placing discretization points densely only in areas that may contain optimal paths. It proceeds in multiple iterations, and in each iteration, it varies the approximation parameters and fine tunes the discretization.

Full Text

Duke Authors

Cited Authors

  • Sun, Z; Reif, JH

Published Date

  • August 2007

Published In

Volume / Issue

  • 37 / 4

Start / End Page

  • 925 - 936

PubMed ID

  • 17702290

Electronic International Standard Serial Number (EISSN)

  • 1941-0492

International Standard Serial Number (ISSN)

  • 1083-4419

Digital Object Identifier (DOI)

  • 10.1109/tsmcb.2007.896021