Google Research

Learned Critical Probabilistic Roadmaps for Robotic Motion Planning

Topological Methods in Robot Planning Workshop at ICRA (2019)


Sampling-based motion planning techniques have emerged as an efficient algorithmic paradigm for solving complex motion planning problems. These approaches use a set of probing samples to construct an implicit topological graph of the robot's state space, allowing arbitrarily accurate representations as the number of samples increases to infinity. In practice, however, solution trajectories only rely on few critical states, often defined by structure in the state space (e.g., doorways). In this work we propose a general method to learn to identify these critical states via graph-theoretic techniques and to use them within a hierarchical graph, termed Critical Probabilistic Roadmaps. Critical PRMs are demonstrated to achieve two orders of magnitude improvement over uniform sampling, while perserving the theoretical guarantees of sampling-based motion planning.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work