Does “probabilistic” refer to uncertain obstacle locations?

In classic PRM, it primarily refers to randomized sampling. Extensions may model additional uncertainty, but that is not implied by the name.

Can one roadmap answer several queries?

Yes. Reuse across start-goal pairs in the same environment is a central motivation of the traditional approach.

Does no graph path mean no physical path exists?

No. The sampled graph may miss connections present in the underlying free configuration space.

AI Glossary / Graphs and symbolic AI / Intermediate

Probabilistic roadmap

Definition

A probabilistic roadmap is a graph built from sampled robot configurations and feasible local paths between them. The probabilistic roadmap method, or PRM, uses that graph to answer motion-planning queries between start and goal configurations. Randomness helps construct a useful representation of free space; it does not mean that a returned path is deliberately allowed to collide with obstacles.

What it means

A robot's configuration specifies its relevant position and joint settings. Configuration space can have many dimensions even when the physical workspace is three-dimensional. Explicitly describing every obstacle-free configuration can be difficult, so PRM samples configurations and tests whether nearby samples can be connected.
The resulting graph is a partial representation of the free space. Vertices represent feasible configurations, and edges represent local motions accepted by the planner's validity tests. A traditional PRM separates roadmap construction from query answering, making it useful for multiple queries in the same modeled environment. Variants can build or refine the roadmap incrementally.

How it works

Sample candidate configurations and reject those that violate modeled constraints, such as collisions. Select neighboring samples and use a local planner to propose connections. Keep connections whose paths pass the required validity checks.
For a query, connect the start and goal to the roadmap when possible, then search the graph for a path. Concatenate the local motions represented by its edges. The graph's path cost depends on the chosen edge weights. A shortest path in the sampled graph is not automatically the shortest feasible motion in the full configuration space. If the environment changes, previously accepted edges may require revalidation.

Three practical examples

A robot-arm planning experiment can build a roadmap of collision-free joint configurations around fixed fixtures and reuse it for several target poses.
A simulation tool can test whether a modeled part can move between assembly positions through a cluttered environment.
An educational planner can illustrate how increasing samples changes graph connectivity and the ability to find a route through a narrow region.

Think of it this way

Think of surveying a large terrain by recording safe stopping points and verified trails between them. A route planner then joins those trails into a journey. The analogy is limited because robot configurations include orientations and joint angles, and a trail that looks clear for one point in space may collide when the robot's full shape moves along it.

Worked example

Consider an invented roadmap with start S, goal G, and sampled configurations A, B, and C. Suppose valid undirected edges have costs S - A = 2, A - B = 3, B - G = 2, S - C = 4, and C - G = 5. Assume the local path for each listed edge has passed the model's validity test.
The route S - A - B - G costs 2 + 3 + 2 = 7. The route S - C - G costs 4 + 5 = 9. In this graph, the first is the cheaper complete route. An attempted direct S - G connection was rejected, so it is not available merely because it would be convenient.
Now suppose a changed obstacle invalidates A - B. If that edge is removed and all remaining edges are still valid, the cost-9 route remains available. If C - G is invalidated as well, the current graph has no S-to-G route. That failure does not prove there is no feasible path in the continuous configuration space: additional samples and valid connections might discover another route. The example distinguishes graph search, edge validation, and completeness of the roadmap.

Illustrative case study

In a fictional robot-training lab, a planner repeatedly fails to connect start and goal around a fixture. Students initially conclude that the task is impossible. Visual inspection of the configuration-space model reveals a narrow feasible region that the small sampled roadmap rarely covers.
The team increases and refines sampling near the difficult region and checks all proposed local paths. It records success frequency across independent runs rather than reporting only a favorable attempt. The case illustrates a sampling limitation; it does not guarantee that extra samples solve every problem or establish real-robot execution safety.

Common misconceptions and mistakes

Checking only the endpoints of an edge is insufficient. Both endpoints can be collision-free while the connecting motion passes through an obstacle. The local path needs validation at a resolution or with a method appropriate to the model.
Probabilistic completeness is also not a finite-time guarantee. Under the conditions of a relevant completeness result, the probability of finding an existing suitable path approaches one as sampling effort grows. It does not mean a fixed small roadmap always succeeds or that failure proves infeasibility. Standard PRM should also not be assumed to provide asymptotic optimality merely because related variants study that property.

Business use

PRM can help when repeated motion queries share a mostly stable environment and roadmap construction can be reused. Its value depends on configuration dimension, obstacle geometry, connection strategy, and the cost of collision checks. A reusable graph can reduce repeated work, but stale geometry can invalidate that advantage.
For practical evaluation, record roadmap construction time, query time, success rate, and path quality separately. Include difficult cases and changes in the modeled environment. Keep geometric planning distinct from time parameterization, dynamic limits, sensing, and feedback control. A valid path in a simplified model is one component of an executable robotic task.

Check your understanding

If the valid A - G edge with cost 3 is added to the worked graph, what is the cheapest listed route from S to G?

Answer: S - A - G costs 2 + 3 = 5, which is lower than the original costs 7 and 9. This is optimal among the routes available in the stated graph, not a proof of continuous-space optimality.

Related terms

Configuration space
Motion planning
Graph search
sampling-based planning
local planner
collision checking
probabilistic completeness
PRM*
roadmap

Learn next

Next, study configuration-space collision checking. Explain why moving a robot's center along a clear line may still cause a collision due to its shape or orientation. Then compare roadmap construction cost with query cost when answering one query versus many queries in an unchanged scene.

Configuration space

Sources

Kavraki and Latombe, Probabilistic Roadmaps for Robot Path Planning, overview and PRM planner sections: https://www.kavrakilab.org/publications/kavraki-latombe1998probabilistic-roadmaps-for.pdf . Relevant original-author sections were read. The graph costs and laboratory scenario are original illustrations; historical experimental timings are not presented as current performance guarantees.

Previous: Probabilistic relevance model Next: Probabilistic Sampling