Robot control
Probabilistic roadmap
Definition
A probabilistic roadmap is a motion-planning graph built by sampling collision-free configurations and connecting nearby samples with feasible local paths. The graph can then answer start-to-goal queries within the modeled environment.
Also known as: PRM, Probabilistic roadmaps
Updated
Build a reusable map of possible motion
A roadmap represents robot configurations as vertices and checked motions as edges. LaValle's Planning Algorithms explains the multiple-query setting: invest computation in a graph that can serve many future queries while the robot and obstacle models remain fixed.
For example, a robot repeatedly moving its arm among work areas may reuse a roadmap through the same surrounding geometry.
Connect the query to the graph
The basic method separates preprocessing from query answering. At query time, the start and goal are connected to the roadmap with a local planner. Graph search then identifies a sequence of edges between them.
This differs from growing a fresh rapidly-exploring random tree primarily around one query, although both belong to sampling-based planning.
Reuse depends on the model staying valid
A stored edge only records a motion checked against a particular model. If objects move, earlier collision checks may no longer apply. Roadmap coverage and the local connection method also affect whether a route can be found. A missing connection in a finite graph is not by itself proof that no physical route exists.
Sources
Related terms
Motion planning
Motion planning finds a robot movement from an initial state to a goal while satisfying constraints such as collision avoidance. A planner may produce a geometric path, a timed trajectory, or a sequence of controls.
Configuration space
Configuration space is the set of all possible configurations of a robot or mechanical system. Each point specifies the entire modeled arrangement, and the space has as many local dimensions as the system has degrees of freedom.
Rapidly-exploring random tree
A rapidly-exploring random tree is a sampling-based structure that grows through a configuration or state space toward sampled targets. Motion planners use it to search for feasible routes through spaces with obstacles and movement constraints.