Probabilistic Roadmap (PRM)

The PRM (Probabilistic Roadmap) solver implements a multi-query roadmap-based motion planner. It constructs a reusable graph representation of the free configuration space by sampling landmark configurations and attempting local path connections between each landmark and its k-nearest neighbors.

Architectural Design & Algorithm Flow

  • Base Contract: Inherits from SamplingSolver.

  • Multi-Robot C-Space: Operates in composite d-dimensional space using Point_d, mapping single- or multi-robot scenes into composite configurations.

  • Roadmap Construction Phase: 1. Add start configuration \mathbf{q}_{\text{start}} and end configuration \mathbf{q}_{\text{end}} to the roadmap graph. 2. Sample num_landmarks collision-free points using injected Sampler. 3. Query k_nn nearest neighbors for every node using NearestNeighbors. 4. Perform local edge validation with discopygal.geometry_utils.collision_detection and insert valid edges into Roadmap.

  • Graph Search Phase: Runs A^* search on the constructed roadmap to extract the shortest collision-free path.

digraph prm_algorithm_flow { rankdir=TB; node [fontname="Helvetica", fontsize=10, margin="0.15,0.1"]; edge [fontname="Helvetica", fontsize=9]; init [label="Start & Goal Configurations", shape=ellipse, style=filled, fillcolor="#E3F2FD", color="#1565C0"]; add_sg [label="Add Start & Goal Nodes to Graph", shape=box, style="filled,rounded", fillcolor="#BBDEFB", color="#1976D2"]; sample [label="Sample N Free Landmarks\n(Sampler Strategy)", shape=box, style="filled,rounded", fillcolor="#C8E6C9", color="#2E7D32"]; knn [label="Find k-Nearest Neighbors per Node\n(NearestNeighbors k-d Tree)", shape=box, style="filled,rounded", fillcolor="#FFF3E0", color="#E65100"]; validate [label="Validate Candidate Edges\n(collision_detection)", shape=box, style="filled,rounded", fillcolor="#F3E5F5", color="#7B1FA2"]; roadmap [label="Construct Adjacency Roadmap Graph", shape=box, style="filled,rounded", fillcolor="#E0F7FA", color="#00838F"]; search [label="Run A* Graph Search & Extract Paths", shape=ellipse, style=filled, fillcolor="#C8E6C9", color="#2E7D32"]; init -> add_sg; add_sg -> sample; sample -> knn; knn -> validate; validate -> roadmap; roadmap -> search; }

PRM Roadmap Construction & Search Pipeline

Parameters & Configuration

PRM Parameters

Parameter

Description

Default

Type

num_landmarks

Number of collision-free landmarks to sample

1000

int

k_nn

Number of nearest neighbors to connect per milestone

15

int

sampler

Sampling strategy distribution

UniformPointSampler

Sampler

metric

Distance metric policy

EuclideanMetric

Metric

Usage Example

from discopygal.solvers.prm.prm import PRM
from discopygal.solvers_infra import Scene

# Load scene and construct solver
solver = PRM.init_solver(num_landmarks=2000, k_nn=20)
path_collection = solver.solve(scene)

API Reference

class discopygal.solvers.prm.prm.PRM(num_landmarks, k_nn, **kwargs)

Bases: SamplingSolver

The basic implementation of a Probabilistic Road Map (PRM) solver. Supports multi-robot motion planning, though might be inefficient for more than two-three robots.

Parameters:

  • num_landmarks (int) – number of landmarks to sample

  • k_nn (int) – number of nearest neighbors to connect (k nearest neighbors)

  • nearest_neighbors (NearestNeighbors or None) – a nearest neighbors algorithm. if None then use sklearn implementation

  • metric (Metric or None) – a metric for weighing edges, can be different then the nearest_neighbors metric! If None then use euclidean metric

  • sampler (Sampler) – sampling algorithm/method. if None then use uniform sampling

build_roadmap() → Roadmap

Build a probabilistic roadmap for the robot in a given scene (sample random points and connect neighbors)

Returns:

roadmap for the given scene

Type:

Roadmap

classmethod get_arguments()

Return a list of arguments and their description, defaults and types. Can be used by a GUI to generate fields dynamically. Should be overridded by solvers.

Returns:

arguments dict

Return type:

dict