Hathaway Zhu

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 Research 21, no. 12 (2002): 999-1030.

Basic idea

How PRM works^[1]: 7 steps

1. Configurations are sampled by picking coordinates at random.

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

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

4. 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).

5. 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])

6. The start and goal configurations are included as milestones.

7. Search for a path from s to g.

Unanswered questions for PRM^[1]

1. How are random configurations chosen?
2. How to sample uniformly (or biased according to prior information) over configuration space?

3. 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)

4. How are closest neighbors found?
   • Naïve search? K-D trees?
5. 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:

1. Deterministic sampling (e.g sampling on a fixed grid)
2. 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)

Distance to Obstacles and Collision Detection