Stage 13 · Lesson 09/16

Robot Perception, Planning & Manipulation · Lesson 09

Sampling-Based Planning

Est. 60–75 min

Why

Why this lesson matters

In Lessons 6–8 you built every ingredient: configuration space, a pose check and a motion check. A sampling-based planner uses only those two checks. It picks random configurations, keeps the free ones, and connects nearby pairs whose straight motion is free. The result is a graph — a roadmap — through free space. Search the graph, and you have a motion. Nobody ever builds the full C-space, so the method works for 6, 7 or even dozens of joints.

In the code lab you will build a Probabilistic Roadmap (PRM) for the desk arm, answer several queries from one roadmap, and see an honest limit: when there is no way through, a PRM just keeps failing — it cannot prove that no path exists. On the bench, a tiny PRM runs on the Arduino UNO itself: 24 random poses, a keep-out box measured on your desk, breadth-first search, and a real motion.

Concept

Random samples, local planners and roadmaps

1. The idea: sample, check, connect

The probabilistic roadmap planner was published in 1996 by Lydia Kavraki, Petr Švestka, Jean-Claude Latombe and Mark Overmars, under the title “Probabilistic roadmaps for path planning in high-dimensional configuration spaces”. Its basic idea is simple: randomly sample points from the configuration space, test whether they are in free space, and use a local planner to try to connect each one to nearby configurations. Then add the start and goal and search the graph.

A square full of small random dots; red dots inside a quarter circle and blue dots outside it, with the title n = 3000, pi ≈ 3.1133
Random sampling in action: dots scattered in a square, coloured by whether they fall inside a quarter circle. The fraction inside estimates π. Sampling planners use the same trick — scatter configurations and keep the ones in free space.Photo: nicoguaro · CC BY 3.0 · Source: Wikimedia Commons · resized, converted to WebP

2. Two phases: construction and query

PhaseWhat happensIn our script
ConstructionSample random configurations; keep the free ones; connect each to its k nearest neighbours (or all within a distance) if the local planner finds the motion freebuild_prm(n, k=8): uniform samples inside the joint limits, motion check every 1° (Lesson 8)
QueryConnect start and goal to the roadmap; run a graph searchquery(): link start/goal to nearest nodes, then Dijkstra

Because the roadmap is built once and reused, a PRM is a multi-query planner: once you have it, each new start–goal question costs only a few hundred checks. That suits a fixed robot cell that does many different moves in the same, unchanging space.

A small graph with six numbered circles joined by lines, each line labelled with a number, node 1 marked a and node 5 marked b
A weighted graph like a roadmap: nodes are configurations, edges are free motions, and the numbers are their lengths. A graph search such as Dijkstra’s algorithm finds the cheapest route from a to b.Photo: Ibmua · Public domain · Source: Wikimedia Commons · resized, converted to WebP

3. Probabilistic completeness

A PRM does not promise to find a path with 50 samples. Its promise is weaker, but useful: under fairly weak conditions on the shape of free space, as the number of samples grows without limit, the probability of finding a path, if one exists, approaches one. This is called probabilistic completeness. How fast it gets there depends on the free space: open spaces are easy; long narrow passages need many samples, because few random darts land inside them.

4. Where sampling wins — and where it does not

In our 2-joint test, building a 200-node roadmap costs about 24 000 collision checks — more than the 12 221 cells of the 3° grid from Lesson 6. In 2D, the grid is cheaper! Sampling wins as the number of joints grows: a grid needs (steps)^joints cells, while a roadmap just needs enough samples to cover the free space. That is why sampling-based planners are considered state of the art for motion planning in high-dimensional spaces, including robot arms. Their paths also zig-zag between random nodes: valid, but not shortest. Lesson 10 shows RRT and RRT*, which grow trees instead of roadmaps and improve paths over time.

Visual

Visualise it: random samples exploring free space

Random samples spread through free space. Sampling planners never build the whole configuration space; they only ask “is this sample free?” and “is this motion free?”. (Educational explorer, not an industrial planner.)

Interactive · RRT planning simulator · Educational

Sampling-based planningRRT concepts

Click Grow — educational RRT samples toward free space.

Toy 2D RRT/RRT* — not OMPL / not MoveIt / not industrial sampling planners.

Code lab

Code lab: a probabilistic roadmap for the desk arm

prm_lab.py uses the same desk arm and bottle as Lesson 6 (bottle at (19, 10) cm). Three parts: (1) roadmaps of 25–200 samples answering the Lesson 6 query; (2) one roadmap, three queries; (3) a second bottle that closes the gap, PRMs of 50–400 samples on 10 random seeds, and a 1° grid flood fill as a cross-check. Plain Python 3. Run python3 prm_lab.py (a few seconds).

prm_lab.py · Python
"""prm_lab.py — Stage 13 L09 (AIHUB STATION lab)

A Probabilistic Roadmap (PRM) for the 2-link desk arm.
Same scene as L06 (example values, metres): links 0.15 m and 0.12 m,
link radius 1.5 cm, bottle r 3.5 cm at (0.19, 0.10).
Joint limits q1 -180..180, q2 -150..150 deg.
Run:  python3 prm_lab.py
"""
import math, random, heapq

L1, L2, LINK_R = 0.15, 0.12, 0.015
OBSTACLES = [((0.19, 0.10), 0.035)]
Q1, Q2 = (-180.0, 180.0), (-150.0, 150.0)
checks = 0

def fk(q1, q2):
    a, b = math.radians(q1), math.radians(q1 + q2)
    e = (L1*math.cos(a), L1*math.sin(a))
    return e, (e[0] + L2*math.cos(b), e[1] + L2*math.sin(b))

def seg_dist(a, b, p):
    ax, ay = a; bx, by = b; px, py = p
    L = (bx-ax)**2 + (by-ay)**2
    s = max(0, min(1, ((px-ax)*(bx-ax) + (py-ay)*(by-ay)) / L))
    return math.hypot(ax + s*(bx-ax) - px, ay + s*(by-ay) - py)

def free(q, pad=0.003):
    global checks
    checks += 1
    e, t = fk(*q)
    return all(min(seg_dist((0, 0), e, c), seg_dist(e, t, c)) >= r + LINK_R + pad for c, r in OBSTACLES)

def dist(a, b): return math.hypot(a[0]-b[0], a[1]-b[1])

def edge_free(a, b, step=1.0):            # the motion check from L08
    n = max(1, math.ceil(max(abs(a[0]-b[0]), abs(a[1]-b[1])) / step))
    return all(free((a[0] + (b[0]-a[0])*i/n, a[1] + (b[1]-a[1])*i/n)) for i in range(1, n))

def build_prm(n, k=8, seed=1):
    rng = random.Random(seed)
    nodes = []
    while len(nodes) < n:                              # 1. sample free configurations
        q = (rng.uniform(*Q1), rng.uniform(*Q2))
        if free(q): nodes.append(q)
    edges = {i: [] for i in range(n)}
    for i, q in enumerate(nodes):                      # 2. connect k nearest neighbours
        near = sorted(range(n), key=lambda j: dist(q, nodes[j]))[1:k+1]
        for j in near:
            if j in [e[0] for e in edges[i]]: continue
            if edge_free(q, nodes[j]):
                d = dist(q, nodes[j]); edges[i].append((j, d)); edges[j].append((i, d))
    return nodes, edges

def query(nodes, edges, start, goal, k=8):
    nodes = nodes + [start, goal]; s, g = len(nodes)-2, len(nodes)-1
    edges = {i: list(v) for i, v in edges.items()}; edges[s] = []; edges[g] = []
    for idx in (s, g):
        for j in sorted(range(len(nodes)-2), key=lambda j: dist(nodes[idx], nodes[j]))[:k]:
            if edge_free(nodes[idx], nodes[j]):
                d = dist(nodes[idx], nodes[j]); edges[idx].append((j, d)); edges[j].append((idx, d))
    best = {s: 0.0}; came = {s: None}; pq = [(0.0, s)]   # 3. Dijkstra on the graph
    while pq:
        c, u = heapq.heappop(pq)
        if u == g:
            path = []
            while u is not None: path.append(nodes[u]); u = came[u]
            return path[::-1], c
        if c > best[u]: continue
        for v, d in edges[u]:
            if c + d < best.get(v, 1e18): best[v] = c + d; came[v] = u; heapq.heappush(pq, (c + d, v))
    return None, None

START, GOAL = (-29.4, 54.1), (51.8, 59.4)     # elbow + IK of the L06 tip targets
print("1. Build a roadmap, then answer the L06 query")
print(f"   start q={START}, goal q={GOAL}")
for n in (25, 50, 100, 200):
    checks = 0
    nodes, edges = build_prm(n)
    nedges = sum(len(v) for v in edges.values()) // 2
    c_build = checks; checks = 0
    path, cost = query(nodes, edges, START, GOAL)
    res = f"path {len(path)} configs, joint-space length {cost:.0f} deg" if path else "NO PATH (roadmap not connected here)"
    print(f"   {n:3d} samples: {nedges:4d} edges, {c_build:6d} collision checks to build; query: {res}")
print("   For comparison, the L06 3-degree grid has 12221 cells. In 2D the grid is still cheaper!")
print("   Sampling wins when joints are many: the roadmap size does not grow like (steps)^joints.")
print("   PRM paths zig-zag between random nodes; they are valid, not shortest (smoothing, RRT* in L10).")

print("\n2. One roadmap, many queries (multi-query)")
checks = 0
nodes, edges = build_prm(200)
build_checks = checks
for s, g in ((START, GOAL), ((-90.0, 30.0), (120.0, -40.0)), ((150.0, 20.0), (-60.0, -100.0))):
    checks = 0
    path, cost = query(nodes, edges, s, g)
    print(f"   {s} -> {g}: {'path, length %.0f deg' % cost if path else 'NO PATH'}, only {checks} new checks")
print(f"   (building the roadmap cost {build_checks} checks once)")

print("\n3. When there is NO way through: a second bottle closes the gap")
OBSTACLES = [((0.19, 0.10), 0.035), ((0.137, 0.147), 0.035)]
A, B = (-29.4, 54.1), (100.0, 20.0)
print(f"   start q={A} free: {free(A)}, goal q={B} free: {free(B)}")
for n in (50, 100, 400):
    ok = 0
    for seed in range(10):
        nodes, edges = build_prm(n, seed=seed)
        path, _ = query(nodes, edges, A, B)
        ok += path is not None
    print(f"   {n:3d} samples: path found in {ok}/10 random roadmaps")
# Cross-check with a full 1-degree grid flood fill (possible only because we have 2 joints)
STEP = 1.0
def cell_free(i, j): return free((Q1[0] + i*STEP, Q2[0] + j*STEP), pad=0.003)
NI, NJ = int((Q1[1]-Q1[0])/STEP) + 1, int((Q2[1]-Q2[0])/STEP) + 1
grid = [[cell_free(i, j) for j in range(NJ)] for i in range(NI)]
si, sj = round((A[0]-Q1[0])/STEP), round((A[1]-Q2[0])/STEP)
gi, gj = round((B[0]-Q1[0])/STEP), round((B[1]-Q2[0])/STEP)
seen = {(si, sj)}; stack = [(si, sj)]
while stack:
    i, j = stack.pop()
    for di in (-1, 0, 1):
        for dj in (-1, 0, 1):
            u, v = i+di, j+dj
            if 0 <= u < NI and 0 <= v < NJ and (u, v) not in seen and grid[u][v]:
                seen.add((u, v)); stack.append((u, v))
print(f"   1-degree grid flood fill ({NI*NJ} cells): goal {'reachable' if (gi, gj) in seen else 'NOT reachable'} from start (at this resolution)")
print("   PRM alone can never PROVE there is no path - it only fails to find one.")
print("   With 2 joints a fine grid can show it (at its resolution); with 6 joints it cannot,\n   so an honest planner reports 'no plan found in the time allowed', not 'impossible'.")

Output (run with python3 prm_lab.py)

1. Build a roadmap, then answer the L06 query
   start q=(-29.4, 54.1), goal q=(51.8, 59.4)
    25 samples:  103 edges,  10250 collision checks to build; query: path 4 configs, joint-space length 291 deg
    50 samples:  228 edges,  14352 collision checks to build; query: path 6 configs, joint-space length 318 deg
   100 samples:  472 edges,  19290 collision checks to build; query: path 5 configs, joint-space length 229 deg
   200 samples:  927 edges,  24033 collision checks to build; query: path 7 configs, joint-space length 226 deg
   For comparison, the L06 3-degree grid has 12221 cells. In 2D the grid is still cheaper!
   Sampling wins when joints are many: the roadmap size does not grow like (steps)^joints.
   PRM paths zig-zag between random nodes; they are valid, not shortest (smoothing, RRT* in L10).

2. One roadmap, many queries (multi-query)
   (-29.4, 54.1) -> (51.8, 59.4): path, length 226 deg, only 387 new checks
   (-90.0, 30.0) -> (120.0, -40.0): path, length 362 deg, only 259 new checks
   (150.0, 20.0) -> (-60.0, -100.0): path, length 348 deg, only 396 new checks
   (building the roadmap cost 24033 checks once)

3. When there is NO way through: a second bottle closes the gap
   start q=(-29.4, 54.1) free: True, goal q=(100.0, 20.0) free: True
    50 samples: path found in 0/10 random roadmaps
   100 samples: path found in 0/10 random roadmaps
   400 samples: path found in 0/10 random roadmaps
   1-degree grid flood fill (108661 cells): goal NOT reachable from start (at this resolution)
   PRM alone can never PROVE there is no path - it only fails to find one.
   With 2 joints a fine grid can show it (at its resolution); with 6 joints it cannot,
   so an honest planner reports 'no plan found in the time allowed', not 'impossible'.

Try it: press “Grow ×8” again and again and watch random samples spread through the free space. (This explorer grows a tree — the RRT you will meet in Lesson 10 — but the sampling idea is the same. Educational explorer, not an industrial planner.)

Interactive · RRT planning simulator · Educational

Sampling-based planningRRT concepts

Click Grow — educational RRT samples toward free space.

Toy 2D RRT/RRT* — not OMPL / not MoveIt / not industrial sampling planners.

Bench build: a tiny PRM on the Arduino UNO

tiny_prm.ino builds a 24-node roadmap on the UNO itself. Node 0 is HOME (30°, 90°), node 1 is GOAL (150°, 90°); the rest are random free samples. The obstacle is a keep-out box in joint space with 5° padding, which you measure on your bench by slowly jogging the arm towards a foam cup. Edges join nodes less than 45° apart if the straight motion is free, checked every 1°. Press GO and it runs breadth-first search, prints the path and plays it, then returns the same way. If the random roadmap is not connected, it says so and does not move — press reset for a new roadmap.

Safety: servos get their own supply — never a GPIO pin or the UNO 5 V pin. Use a soft obstacle (a foam cup) until your keep-out box is measured and padded. Moves are slowed to 1° every 15 ms; keep fingers out of the arm’s reach.
PartConnectionNote
Shoulder servo (SG90-class)signal → D9servo degrees used directly (0…180)
Elbow servo (SG90-class)signal → D10same
Servo supplyred → +5–6 V, brown → supply GNDseparate supply (about 2 A); supply GND joined to UNO GND
GO buttonD3 → button → GNDINPUT_PULLUP
A0leave unconnectedfloating input seeds the random generator
tiny_prm.ino · Arduino C++
// tiny_prm.ino — Stage 13 L09 (AIHUB STATION lab)
// A very small Probabilistic Roadmap (PRM) running ON the Arduino UNO.
// 1. sample random joint configurations, keep the free ones
// 2. connect near pairs whose straight joint-space motion is free (checked every 1 deg)
// 3. on GO, search the roadmap (breadth-first) from HOME to a goal and play the path
//
// The obstacle is a "keep-out box" in JOINT space that you measure on your bench:
// jog the arm towards a soft obstacle (foam cup) and note the joint angles that touch it.
//
// Wiring (Arduino UNO):
//   Shoulder servo signal -> D9, elbow servo signal -> D10
//   Servo red/brown -> SEPARATE 5-6 V supply (about 2 A), GND joined to UNO GND
//   GO button: D3 -> button -> GND (INPUT_PULLUP)
//   Serial Monitor 115200 shows the roadmap and the path
#include <Servo.h>

const int N = 24;                  // roadmap nodes (node 0 = HOME, node 1 = GOAL)
const float LINK_DEG = 45.0;       // try to connect nodes closer than this (joint space)
// Keep-out box in joint space (servo degrees), measured on YOUR bench.
const int BOX_Q1_MIN = 70, BOX_Q1_MAX = 110, BOX_Q2_MIN = 60, BOX_Q2_MAX = 180;
const int PAD = 5;                 // safety padding in degrees

Servo s1, s2;
int q1[N], q2[N];
uint32_t adj[N];                   // adjacency as bit masks (N <= 32)
int curA = 30, curB = 90;

bool poseFree(float a, float b) {
  return !(a > BOX_Q1_MIN - PAD && a < BOX_Q1_MAX + PAD && b > BOX_Q2_MIN - PAD && b < BOX_Q2_MAX + PAD);
}

bool edgeFree(int i, int j) {      // motion check every 1 degree
  float da = q1[j] - q1[i], db = q2[j] - q2[i];
  int n = max(1, (int)ceil(max(fabs(da), fabs(db))));
  for (int k = 1; k < n; k++)
    if (!poseFree(q1[i] + da * k / n, q2[i] + db * k / n)) return false;
  return true;
}

void moveTo(int a, int b) {        // synchronised slow move, 1 deg per 15 ms
  int steps = max(abs(a - curA), abs(b - curB));
  int a0 = curA, b0 = curB;
  for (int k = 1; k <= steps; k++) {
    s1.write(a0 + (long)(a - a0) * k / steps);
    s2.write(b0 + (long)(b - b0) * k / steps);
    delay(15);
  }
  curA = a; curB = b;
}

void buildRoadmap() {
  q1[0] = 30;  q2[0] = 90;         // HOME (left of the box)
  q1[1] = 150; q2[1] = 90;         // GOAL (right of the box)
  int n = 2, tries = 0;
  while (n < N && tries < 2000) {  // 1. sample free configurations
    tries++;
    int a = random(10, 171), b = random(0, 181);
    if (poseFree(a, b)) { q1[n] = a; q2[n] = b; n++; }
  }
  int edges = 0;
  for (int i = 0; i < N; i++) adj[i] = 0;
  for (int i = 0; i < N; i++)       // 2. connect near pairs with free motions
    for (int j = i + 1; j < N; j++) {
      float d = sqrt(sq((float)(q1[i] - q1[j])) + sq((float)(q2[i] - q2[j])));
      if (d < LINK_DEG && edgeFree(i, j)) { adj[i] |= (1UL << j); adj[j] |= (1UL << i); edges++; }
    }
  Serial.print(F("roadmap: ")); Serial.print(N); Serial.print(F(" nodes, "));
  Serial.print(edges); Serial.print(F(" free edges after ")); Serial.print(tries); Serial.println(F(" samples"));
}

int findPath(int from, int to, int *path) {   // 3. breadth-first search
  int prev[N]; bool seen[N] = {false};
  int queue[N], head = 0, tail = 0;
  queue[tail++] = from; seen[from] = true; prev[from] = -1;
  while (head < tail) {
    int u = queue[head++];
    if (u == to) break;
    for (int v = 0; v < N; v++)
      if ((adj[u] >> v & 1UL) && !seen[v]) { seen[v] = true; prev[v] = u; queue[tail++] = v; }
  }
  if (!seen[to]) return 0;
  int len = 0;
  for (int v = to; v != -1; v = prev[v]) path[len++] = v;
  for (int i = 0; i < len / 2; i++) { int t = path[i]; path[i] = path[len-1-i]; path[len-1-i] = t; }
  return len;
}

void setup() {
  Serial.begin(115200);
  pinMode(3, INPUT_PULLUP);
  randomSeed(analogRead(A0));      // floating A0 gives a different roadmap each reset
  s1.attach(9); s2.attach(10);
  s1.write(curA); s2.write(curB);
  buildRoadmap();
  Serial.println(F("Press GO (D3) to plan HOME -> GOAL on the roadmap."));
}

void loop() {
  if (digitalRead(3) != LOW) return;
  delay(30);
  int path[N];
  int len = findPath(0, 1, path);
  if (len == 0) {
    Serial.println(F("no path in this roadmap: press reset to sample a new one (no move)"));
  } else {
    Serial.print(F("path:"));
    for (int i = 0; i < len; i++) {
      Serial.print(F(" (")); Serial.print(q1[path[i]]); Serial.print(F(",")); Serial.print(q2[path[i]]); Serial.print(F(")"));
    }
    Serial.println();
    for (int i = 1; i < len; i++) moveTo(q1[path[i]], q2[path[i]]);
    delay(800);
    for (int i = len - 2; i >= 0; i--) moveTo(q1[path[i]], q2[path[i]]);   // same path back home
    Serial.println(F("back at HOME"));
  }
  while (digitalRead(3) == LOW) delay(10);
}
Serial Monitor (115200) — the shape of a run (your numbers change after every reset) · Text
roadmap: 24 nodes, <edges> free edges after <samples> samples
Press GO (D3) to plan HOME -> GOAL on the roadmap.
path: (30,90) (q1,q2) (q1,q2) ... (150,90)
back at HOME

or, if this random roadmap is not connected:
no path in this roadmap: press reset to sample a new one (no move)

Debugging

SymptomLikely causeFix
PRM never connects start and goaltoo few samples or too short connection radiusMore samples; larger k or radius; check start and goal are free
Fails only through a narrow gapfew samples land in the passageMany more samples, or sample more densely near obstacles
Path found but robot clips an obstacleedge check too coarseUse the Lesson 8 step bound for edge checks
Path zig-zagsrandom nodesShortcut: replace parts of the path by straight free motions; or RRT* (L10)
Different result every runrandom samplingFix the seed while debugging; test over many seeds before trusting it
Bench: same roadmap after every resetA0 connected to somethingLeave A0 floating, or seed from a timer

Real world

Sampling-based planners in the real world

Blue polygon obstacles on a white background with small black dots near their corners and some thin lines joining dots
A frame from an animation of a probabilistic roadmap planner working around polygonal obstacles: sampled points (black dots) and connections (lines) are building a roadmap through the free space.Photo: Eric O. Scott · CC BY-SA 4.0 · Source: Wikimedia Commons · resized, converted to WebP
  • Robot arms: sampling-based planners are the usual choice for arms because they scale to many joints.
  • Beyond robots: the same methods have been applied to problems with dozens or hundreds of dimensions — robot manipulators, biological molecules, animated characters and legged robots.
  • Fixed cells: a cell doing many moves in an unchanging space can build a roadmap once and answer many queries quickly.
  • Your lab: always test a sampling planner over many random seeds. One lucky run proves nothing.

Think

Think about it

Think

A PRM with 400 samples fails 10 times out of 10. Your friend says “so there is no path”. What would you say, and what would you try?

Experiment

Try it in the lab

About 60 minutes. Python 3 for the script; Arduino UNO, two servos on a 2-link arm with their own supply, a push button and a foam cup for the bench.

Experiment

Throw darts at configuration space

You will need

  • `prm_lab.py` (Python 3, no libraries)
  • RRT planning simulator (in your browser)
  • Arduino UNO, 2 × SG90-class servos on a 2-link arm, separate 5–6 V supply, push button, jumper wires, foam cup

Steps

  1. Run the script. In part 1, try k = 4 and k = 16. How do edges, checks and path length change?
  2. Run part 1 with 10 different seeds at 25 samples. In how many is a path found?
  3. Move the second bottle in part 3 slightly so a narrow gap opens. How many samples does the PRM need now?
  4. Add a shortcutting step: try to replace pairs of path segments with one straight free motion. How much shorter does the path get?
  5. Bench: measure your keep-out box with a foam cup, add 5° padding, and run the tiny PRM 10 times (reset each time). Count successes.
  6. Bench: make the box taller to create a narrow corridor and repeat the count.

Interactive · RRT planning simulator · Educational

Sampling-based planningRRT concepts

Click Grow — educational RRT samples toward free space.

Toy 2D RRT/RRT* — not OMPL / not MoveIt / not industrial sampling planners.

Random samples plus two checks are enough to plan in high-dimensional spaces. The price: no guarantee in a fixed time, trouble in narrow passages, and zig-zag paths — all of which Lesson 10 starts to fix.

Knowledge check

Check your understanding

Knowledge check

1. A sampling-based planner avoids…

2. The two phases of a PRM are…

3. In a PRM, the local planner…

4. PRM is probabilistically complete. This means…

5. Why are narrow passages hard for PRM?

6. A PRM fails 10 times. The honest report is…

7. In our 2-joint test, which was cheaper: the 3° grid or a 200-node PRM?

8. PRM is called a multi-query planner because…

Mini assignment

Hands-on assignment

Mini assignment

A roadmap for your desk

Build and evaluate a PRM for your own desk arm and obstacles, and run one of its paths on the bench.

Deliverables

  • Your obstacles measured on the desk and added to `prm_lab.py` (or a copy), with start and goal from your real task.
  • A table over 10 seeds for 25, 50, 100 and 200 samples: success rate, collision checks and path length.
  • A shortcutting step and the path length before and after.
  • A bench log from `tiny_prm.ino` with your measured keep-out box: successes in 10 resets, plus one path played.

Do this, step by step

  1. Run prm_lab.py and note the roadmap size and the path it finds.
  2. Add your own obstacle to OBSTACLES and run again.
  3. Change the number of samples and k and record path cost and number of collision checks.
  4. Run the same query twice on one roadmap and see that the second query is cheap.
  5. Bench: upload tiny_prm.ino with your keep-out box and log the roadmap and the path to GOAL.

Stuck? Hints, one at a time

NoteTry the task first. Read one hint, try again, and only then read the next one.
  1. If no path is found, try more samples first, then a larger k.
  2. edge_free() must check the straight motion, not just the two nodes (Lesson 8).
  3. In the sketch, PAD is 5° around the box. If nodes never connect, check LINK_DEG (45°) is not too small.

Challenges (pick by level)

  • 🟢 Beginner: On graph paper, draw a (q1, q2) square with a box, drop 20 random dots with dice, and connect the ones that can “see” each other. Find a path.
  • 🟡 Intermediate: Add shortcutting to prm_lab.py and compare path lengths over 10 seeds.
  • 🟠 Advanced: Add a third joint (wrist) and self-collision from Lesson 7. Compare PRM checks with a 3° grid of 121 × 101 × 121 cells.
  • 🔴 Expert: Implement “lazy” PRM: skip edge checks while building, and check only the edges of the path the search returns, re-searching when one fails. Count the saved checks.
  • ⚫ Research: Read the 1996 PRM paper by Kavraki, Švestka, Latombe and Overmars. Write one page on what they mean by a “high-dimensional configuration space” and how they handled narrow passages.

Next step

A roadmap is great when the world stays the same and you have many queries. For one query, it is faster to grow a tree straight from the start. In **Lesson 10 — RRT and RRT* Concepts** you will grow random trees and see how RRT* makes paths shorter the longer it runs.

Look back: Lesson 8: Collision-Free Motion. Next: Lesson 10: RRT and RRT* Concepts. Related: Stage 12 — Simulation & Digital Twin.

Sources

  • Wikipedia — Probabilistic roadmap — Kavraki, Švestka, Latombe and Overmars, IEEE Transactions on Robotics and Automation, 1996; random samples, free-space test, local planner, k nearest neighbours; construction and query phases; probabilistic completeness; narrow passages.
  • Wikipedia — Motion planning — sampling-based algorithms cannot determine that no path exists; state of the art in high-dimensional spaces; applied to manipulators, molecules, animated characters and legged robots.
  • Arduino Servo library (GitHub) — controlling RC hobby servos.
  • Photos: Wikimedia Commons (credits under each image).

Self-attested for now — keep artifacts in your lab notebook.

Complete

Today's goal

0 of 1 done today

0-day streak
Daily goal:lessons, quizzes or assignments a day

Mark this lesson complete when you have worked the experiment, knowledge check, and assignment (even roughly).

Stuck somewhere?

Ask a doubt about this lesson

Saved with this lesson's id and your email so we can reply. Privacy · or email contact@aihubstation.in