CoreSource checked

Probabilistic Roadmap

Probabilistic Roadmap samples feasible states and connects them into paths.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pathfinding
Difficulty: Intermediate
Family: Pathfinding
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 1
Code example: Ready
Visualization: Ready

Overview

Probabilistic Roadmap is a pathfinding method that searches a graph, grid, or configuration space using costs, heuristics, or incremental updates. It is useful when route quality, replanning cost, or search speed matters more than a naive traversal.

Core Concepts

state spacepath costsearch frontierfrontiercost estimatepath reconstruction

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(E)

Average

O(E log V)

Worst

O(E log V)

Space

O(V)

When to Use

Use Probabilistic Roadmap when the map, costs, and movement rules match its search assumptions.
Use it when route quality and search budget must be balanced explicitly.

When Not to Use

Avoid when the heuristic or cost model does not match the real movement constraints.
Avoid when dynamic updates make a simpler replanning strategy easier to validate.

What It Does

Searches a state space for routes
Uses costs, heuristics, or incremental updates
Returns a route or reachable region

Use Cases

Game navigation
Robotics planning
Route planning

Inputs

Graph, grid, or map
Start and goal
Costs or heuristic

Outputs

Path
Distance estimate
Search tree

Key Formulas (1)

Connection test

connect if distance(q_i, q_j) < radius and local path is collision−free

connect if distance(q_i, q_j) < radius and local path is collision-free

Builds roadmap edges between nearby sampled configurations.

Pseudocode

1.Initialize start state, goal state, and search records
2.Select the next frontier node using cost, heuristic, or sampling rule
3.Expand reachable neighbors or samples
4.Update path costs and parent links
5.Return the reconstructed path or failure result

Canonical Example

Input: grid with start S and goal G
Output: route from S to G or no path
Explanation: Probabilistic Roadmap expands candidate states and reconstructs a path when the goal is reached.

Implementation Notes

Keep cost, heuristic, and parent-link updates in separate steps.
Test blocked, unreachable, and changing-cost maps.

Common Pitfalls

Using an inadmissible heuristic while expecting optimal paths gives incorrect guarantees.
Forgetting to update parent links makes path reconstruction fail.

Interactive Mechanism Walkthrough

2D Grid Wavefront & Trajectory

Show the frontier expanding through the map and the final path being reconstructed.

Step 1 of 5: Initialize start state, goal state, and search records

pathfinding

Notes

Probabilistic Roadmap operates in O(E log V) time and O(V) space within the Pathfinding family. Key governing relation: connect if distance(q_i, q_j) < radius and local path is collision-free. Often compared with Dijkstra's Algorithm and A* Search.