Self indexed motion plannin
- Day - Time: 27 October 2017, h.11:00
- Place: Area della Ricerca CNR di Pisa - Room: C-29
Speakers
- Edgar Chavez (CICESE, Mexico)
Referent
Abstract
Motion planning is a central problem for robotics. The PRM algorithm is, together with the asymptotically optimal variant PRM*, the standard method to maintain a (collision-free) roadmap in the con- figuration space. The PRM algorithm is randomized, and requires a large number of high-dimensional point samples generated online, hence a sub- problem to discovering and maintaining a collision-free path is insert- ing new sample points connecting them with the k-nearest neighbors in the previous set. A standard way to speedup the PRM is by using an external index for making the search. On the other hand, a recent trend in object indexing for proximity search consists in maintaining a so-called Approximate Proximity Graph (APG) connecting each object with its approximate k-nearest neighbors. This hints the idea of using the PRM as a self-index for motion planning. Although similar in prin- ciple, the graphs have two incompatible characteristics: (1) The APG needs long-length links for speeding up the searches, while the PRM avoids long links because they increase the probability of collision in the configuration space. (2) The APG requires to connect a large number of neighbors at each node to achieve high precision results which turns out in an expensive construction while the PRM’s goal is to produce a roadmap as fast as possible. In this paper, we solve the above problems with a counter-intuitive, simple and effective procedure. We reinsert the sample points in the configuration space, and compute a collision-free graph after that. This simple step eliminates long links, improves the path total length, and reduce the total space needed for the algorithm. We present simulations, showing an improvement in performance for high- dimensional configuration spaces, compare to standard techniques used by the robotics community, and test how good is the obtained approximate $k$-nn graph wrt the exact version.