Abstraction-Guided Sampling for Motion Planning

Proceedings of the International Symposium on Combinatorial Search, 5

Volume

Vol. 5 No. 1 (2012): Fifth Annual Symposium on Combinatorial Search

Short Papers

Motion planning in continuous space is a fundamentalrobotics problem that has been approached from many per-spectives. Rapidly-exploring Random Trees (RRTs) usesampling to efficiently traverse the continuous and high-dimensional state space. Heuristic graph search methods uselower bounds on solution cost to focus effort on portions ofthe space that are likely to be traversed by low-cost solutions.In this work, we bring these two ideas together in a tech-nique called f -biasing: we use estimates of solution cost,computed as in heuristic search, to guide sparse sampling,as in RRTs. We see this new technique as strengthening theconnections between motion planning in robotics and combi-natorial search in artificial intelligence.

10.1609/socs.v3i1.18265