probabilistic roadmap

A sampling-based motion planningmotion planning, n.: Working out how a robot should move from where it is to where it needs to be, without hitting anything and within the limits of what its body can do. method that first builds a reusable graph of the robot's free configuration spaceconfiguration space, n.: An imaginary space in which a robot's whole body position is a single point, which turns 'move this many-jointed robot without hitting things' into 'find a path for a dot'. and then answers route requests on it. To build the roadmap, it draws random configurations, throws out any that collide, and tries to join each survivor to its neighbors — the closest few, or all within some distance — keeping an edge wherever a simple local planner finds a collision-free motion. To answer a request, it links the start and goal into the roadmap and runs an ordinary graph search, such as A*A* search, n.: A method for finding the shortest route on a map or network that weighs both how far you have already come and a smart guess of how far is left, so it tries the most promising paths first. or Dijkstra's algorithm. Because the roadmap is built once and reused, the method suits multi-query settings, such as a robot working repeatedly in a fixed cell. It is probabilistically complete under mild conditions — the chance of finding an existing path tends to one as samples grow — but struggles with narrow passages that uniform sampling rarely hits; biased sampling strategies and the asymptotically optimal PRM* address these weaknesses.

We precompute a probabilistic roadmap of the work cell overnight and query it in milliseconds.