Minimizing Task-Space Fréchet Error via Efficient Incremental Graph Search

Rachel M. Holladay; Oren Salzman; Siddhartha S. Srinivasa

RA-L 201927 citations

Minimizing Task-Space Fréchet Error via Efficient Incremental Graph Search

Rachel M. Holladay, Oren Salzman, Siddhartha S. Srinivasa

Abstract

We present an anytime algorithm that generates a collision-free configuration-space path that closely follows a desired path in task space, according to the discrete Fréchet distance. By leveraging tools from computational geometry, we approximate the search space using a cross-product graph. We use a variant of Dijkstra's graph-search algorithm to efficiently search for and iteratively improve the solution. We compare multiple proposed densification strategies and empirically show that our algorithm outperforms a set of state-of-the-art planners on a range of manipulation problems. Finally, we offer a proof sketch of the asymptotic optimality of our algorithm.

BibTeX

@inproceedings{ral2019_minimizingtasksp,
  title = {Minimizing Task-Space Fréchet Error via Efficient Incremental Graph Search},
  author = {Rachel M. Holladay and Oren Salzman and Siddhartha S. Srinivasa},
  booktitle = {RA-L 2019},
  year = {2019}
}