## Probabilistic Roadmap(PRM)

This article mainly refers to

[1] lecture notes of Fall 2019: CS 287 Advanced Robotics by Prof. Pieter Abbeel from UC Berkeley, Dept of Electrical Engineering & Computer Sciences;

[2] MIT Course Number 16.410/16.413: Principles of Autonomy and Decision Making, Prof. Brian Charles Williams, Prof. Emilio Frazzoli

[3] Lecture notes of COMS W4733, Computational Aspects of Robotics, Fall 2015 by Prof. Peter K. Allen from Columbia University, Department of Computer Science.

[4]Leven, Peter, and Seth Hutchinson. “A framework for real-time path planning in changing environments.”

The International Journal of Robotics Research21, no. 12 (2002): 999-1030.

### Basic idea

### How PRM works^{[1]}: 7 steps

- Configurations are sampled by picking coordinates at random.

- Sampled configurations are tested for collision (the purple points are in the free space, the black ones are in the infeasible space).

- The collision-free configurations are retained as milestones (the red ones in the picture).

- Each milestone is linked by straight paths to its nearest neighbors (i.e. the criteria to decide which pairs of milestones to connect: nearest neighbors).

- The collision-free links are retained as local paths to form the PRM. If there is a collision connecting two milestone, then discard the link.(i.e. verification that a pair of milestones can be connected。 Traditionally, this is the most expensive part of the PRM method.[4])

- The start and goal configurations are included as milestones.

- Search for a path from
**s**to**g**.

### Unanswered questions for PRM^{[1]}

- How are random configurations chosen?
**How to sample uniformly**(or biased according to prior information) over configuration space?

- Collision checking: Often takes majority of time in applications (In sampling-based algorithms, collision checking is usually the most expensive operation and reportedly consumes up to 90–95% of the planning time, Check this paper)

- How are closest neighbors found?
- Naïve search? K-D trees?

- How to connect neighboring points (How is local path generated?):

### Why PRM^{[2]}

The reason PRM is called multi-query planning methods is that once the roadmap is built, and if you have a new target position, you can just use the roadmap that is already built. So it can be reused as many times as you want. For RRT, if you have a new target position, you probably need to span the tree more. So the same tree can’t be reused for a second time. That’s why it’s called single-query planning method.

Path planning in low dimension space(joint space or operating space) is doable just using brute-force search. But for scenarios with high dimension space:

- Explicit Geometry based planners are impractical in high dimensional spaces.
- Exact solutions with complex geometries are provably exponential.

Sampling based planners can often create plans in high-dimensional spaces efficiently. Rather than compute the c-space(configuration space) explicitly, we sample it.

### Pros and Cons about PRM

Sampling based planning algorithms are used to reduces computational complexity by sacrifice optimality and completeness, and perhaps escape from local minimum:

- Deterministic sampling (e.g sampling on a fixed grid)
- Stochastic sampling (e.g. Monte Carlo sampling)

PRM is a sampling based planning algorithm. PRM is **Probabilistic Complete Planner** (Essentially not complete): if a solution exists, planner will eventually find it using random sampling as opposed to Resolution Complete Planner(same as above but based on a deterministic sampling)

## 2 Comments