Minimizing Task Space Frechet Error via Efficient Incremental Graph Search
This is an incremental improvement for robot motion planning, addressing the specific challenge of task-space path following in manipulation.
The paper tackles the problem of generating collision-free robot paths that closely follow a desired task-space path using the discrete Fréchet distance, and it shows that their algorithm outperforms state-of-the-art planners on manipulation tasks.
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 Frechet 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.