1 of 57

Aerial Robotics

Planning: Sampling-based, PRM, PRM*, RRT

C. Papachristos

Robotic Workers (RoboWork) Lab

University of Nevada, Reno

CS-491/691

2 of 57

Motion Planning Fundamentals

Representations and Objectives

Collision Free-Navigation – Problem Statement:

Compute a continuous sequence of collision-free robot configurations�connecting the initial and goal configurations

Path Planner

Geometry of the environment
Geometry and kinematics of the robot
Initial and goal configurations

Collision-free path�to goal

CS491/691 C. Papachristos

3 of 57

Motion Planning Fundamentals

Representations and Objectives

Coverage – Problem Statement:

Given a 3D structure to be inspected with a dynamical system equipped with a sensor, calculate a feasible path that provides viewpoints which ensure full (/maximal) coverage subject to the constraints of the robot and the environment

Path Planner

Geometry of the environment
Geometry and kinematics of the robot
Initial and goal configurations

Maximal coverage path

Structure to be inspected

CS491/691 C. Papachristos

4 of 57

Motion Planning Fundamentals

Path Planner

Unknown environment
Geometry and kinematics of the robot
Initial configuration

Next exploration step

Online 3D reconstruction

CS491/691 C. Papachristos

5 of 57

Motion Planning Fundamentals

Representations and Objectives

The workspace is often the representation of the world, possibly independent of the robot itself

Often describes some notion of reachability, what space is free or occupied

Obstacle representation can be derived from geometric considerations

Note: A convex shape can be defined by a set of half-planes

A non-convex shape sometimes makes sense to be considered as a union of convex shapes

CS491/691 C. Papachristos

6 of 57

Grid-based Planning

Grid-based Graphs for Planning

Reduce continuous State-Space to a finite set of discrete states, consider:

States as vertices
Transitions as (directed) edges

Result is a Graph, can apply Graph-search techniques for lowest-cost-path problems

Can be difficult to select a grid resolution:

Sufficiently fine to retain valid solutions
Sufficiently coarse to find a solution in a reasonable time

Connectivity determined by the grid shape can be limiting

Consider a non-holonomic system …

Challenging in higher-dimensional spaces

Suffer “Curse of dimensionality”�(exponential growth as the number of cells grows)

CS491/691 C. Papachristos

7 of 57

Grid-based Planning

Note: We can use the different paradigm of Lattice-based Graph approaches in a broader sense…

CS491/691 C. Papachristos

8 of 57

Sampling-based Planning

The Piano-Mover’s Problem

CS491/691 C. Papachristos

9 of 57

Sampling-based Planning

CS491/691 C. Papachristos

10 of 57

Sampling-based Planning

Random Sampling & Incremental Planning

Motion planning algorithms that are very successful in practice

Leverage batch / incremental sampling: draw samples from some distribution
Retain some form of completeness: “Probabilistic” or “Resolution” completeness

Incremental Sampling:

Real-time (& on-line) implementation
Applicable to very generic dynamical systems
Do not require the explicit enumeration of constraints
Adaptive (e.g. multi-resolution)

CS491/691 C. Papachristos

11 of 57

Sampling-based Planning

Random Sampling

Example Planning Graphs derived from:

A) Grid-based Graph construction
B) Random Sampling-based Graph construction

CS491/691 C. Papachristos

12 of 57

Sampling-based Planning

Random Sampling

The two most influential sampling-based motion planning algorithms to date:

Probabilistic Roadmaps (PRM, 1996)

1) Roadmap Construction
2) Search

Rapidly-exploring Random Trees (RRT, 1998)

Roadmap construction & Search�(incremental / online)

CS491/691 C. Papachristos

13 of 57

Sampling-based Planning

Probabilistic Roadmaps

Introduced by Kavraki and Latombe in 1996�Kavraki, Lydia E., et al. "Probabilistic roadmaps for path planning in high-dimensional configuration spaces." IEEE Transactions on Robotics and Automation 12.4 (1996): 566-580�Geared towards “multi-query” motion planning problems

Assumes that it is worth performing substantial precomputation on a given environment to enable subsequent planning queries
First planner ever to demonstrate the ability to solve generic planning problems in > 4-5 dimensions!

Method:

1) Build a Roadmap (graph construction – offline), represent the environment connectivity
2) Connect Start & Goal configurations to Roadmap (closest collision-free vertex)
3) Query Roadmap (graph search online e.g. A* ), find paths during runtime

CS491/691 C. Papachristos

14 of 57

Sampling-based Planning

Variant: Probabilistic Roadmaps (PRM)

1) Roadmap Construction:

CS491/691 C. Papachristos

15 of 57

Sampling-based Planning

Variant: simplified Probabilistic Roadmaps (sPRM)

1) Roadmap Construction:

CS491/691 C. Papachristos

16 of 57

Sampling-based Planning

Probabilistic Roadmaps

1) Roadmap Construction:

CS491/691 C. Papachristos

17 of 57

Sampling-based Planning

Probabilistic Roadmaps

2),3) Multiple Queries:

CS491/691 C. Papachristos

18 of 57

Sampling-based Planning

CS491/691 C. Papachristos

19 of 57

Planning Algorithm Definitions

Per-Sample Complexity

Algorithm that does not necessarily terminate – how to measure complexity?

Main ideas:

Treat the number of samples as the “size of the input”
Complexity Per-Sample: how much effort (time/memory) is required per sample

Useful for comparison of sampling-based algorithms

Not for comparison against deterministic, complete algorithms

CS491/691 C. Papachristos

20 of 57

Planning Algorithm Definitions

CS491/691 C. Papachristos

21 of 57

Planning Algorithm Definitions

Probability of not finding a solution to a robustly feasible problem decreases exponentially with the number of vertices

CS491/691 C. Papachristos

22 of 57

Planning Algorithm Definitions

CS491/691 C. Papachristos

Sampling-based Planning

PRM* adds a constant number of edges at each iteration, but remains asymptotically optimal

CS491/691 C. Papachristos

30 of 57

Sampling-based Planning

Random Sampling

Narrow-Passage Problem

Uniform sampling is not a very effective tool to find paths through narrow passageways

Gaussian Sampling:

1) Sample points uniformly
2) For each sampled point, sample a second point from a Gaussian distribution centered at the first point
3) Discard both if they are either:

Both free, or
Both in collision

4) Keep the free sample if they are NOT both free or both in collision

CS491/691 C. Papachristos

31 of 57

Sampling-based Planning

Gaussian Sampling:

1) Sample points uniformly
2) For each sampled point, sample a second point from a Gaussian distribution centered at the first point
3) Discard both if they are either:

Both free, or
Both in collision

4) Keep the free sample if they are NOT both free or both in collision

Samples drawn by leveraging�Gaussian Sampling

CS491/691 C. Papachristos

32 of 57

Sampling-based Planning

Probabilistic Roadmaps

Conceptually very simple, rapidly popular due to their ability to solve previously challenging problems (high-dimension planning, snake robots, piano-mover)

Limitations:

Hard to apply to problems where edges are directed, i.e. kinodynamic problems

Planning with differential constraints, not easy to encode control information (undirected edges)

Two steps: Graph construction, then Graph search

Not suitable for dynamic environments
Underlying assumption: Worth performing substantial precomputation to enable multiple queries

Often we are only interested in efficient single-query without precomputations

Combine exploration and search into a single method
Tree-based Planning !

CS491/691 C. Papachristos

33 of 57

Sampling-based Planning

45 iterations

2345 iterations

CS491/691 C. Papachristos

34 of 57

Sampling-based Planning

RRT :

RRT is probabilistically complete

The probability of success goes to 1 exponentially fast, if the environment satisfies certain “good visibility” conditions

RRT is not asymptotically optimal

Sampling-based Planning

CS491/691 C. Papachristos

51 of 57

Planning Algorithm Definitions

Sample Voronoi Diagram

CS491/691 C. Papachristos

52 of 57

Sampling-based Planning

RRT Voronoi Bias:

RRT expansion becomes biased towards the earlier generated Voronoi regions

A product of the nearest-node connection strategy during incremental construction

http://msl.cs.uiuc.edu/rrt/gallery.html

CS491/691 C. Papachristos

53 of 57

Sampling-based Planning

RRT Properties

RRT is probabilistically complete

The same bound for PRM

RRT is not asymptotically optimal

CS491/691 C. Papachristos

54 of 57

Sampling-based Planning

RRT’s Power

RRT and its variants are widely applicable in diverse planning problems

CS491/691 C. Papachristos

55 of 57

Sampling-based Planning

CS491/691 C. Papachristos

56 of 57

Sampling-based Planning

CS491/691 C. Papachristos

57 of 57

Time for Questions !

CS-491/691

CS491/691 C. Papachristos