Abstraction-Guided Sampling for Motion Planning

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.

Authors

• Scott Kiesel
• Ethan Burns
• Wheeler Ruml

Keywords

• Abstraction
• Sample-Based
• Shortest Path