1 of 26

Aerial Robotics

Planning: Sampling-based, RRG, RRT*

C. Papachristos

Robotic Workers (RoboWork) Lab

University of Nevada, Reno

CS-491/691

2 of 26

Sampling-based Planning

Non-Holonomic Planning – Detail:

Sampling based planning considers constraints such as environment obstacles

There may also exist kinodynamic constraints imposed on the system side

In practice, most robots will be non-holonomic

Kinodynamic constraints cannot be integrated into positional constraints

Non-holonomic planning is typically used for problems with kinematics constraints only

CS491/691 C. Papachristos

3 of 26

Sampling-based Planning

Non-Holonomic Planning – Some Approaches:

PRM

Classic approach in robotics is to decouple the problem by first solving the basic path planning component, then finding a trajectory and controller that satisfies the kinodynamic constraints

PRM may require the connection of thousands of configurations to find a solution
Resolving a non-linear control problem for each connection seems impractical

Randomized Potential Fields

Depend heavily on the choice of a good heuristic potential function

Very difficult when considering: obstacles, kinematic differential, and dynamic constraints

RRT

Can be directly applied to non-holonomic planning !

RRT does not require a connection-computing step between predetermined pairs of configurations
It lacks however the commonly desired property of Asymptotic Optimality

CS491/691 C. Papachristos

4 of 26

Sampling-based Planning

Non-Holonomic Planning – Steer to Goal:

RRTs are exceptionally tailored to efficiently handle Kinodynamic Planning

Solution 1: Use a solver to find control inputs that connect the two-points (2-point boundary value problem)

It can be expensive, and provide solutions that are quite long in comparison with the shortest path

Solution 2: Require to only approximately reach intermediate goal states

Instead of trying to join to specific samples, we can sample our controls to generate feasible local paths and choose the configuration that gets closest to the target configuration?

CS491/691 C. Papachristos

5 of 26

Sampling-based Planning

Non-Holonomic Planning – Steer to Goal Sampling in RRT:

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

CS491/691 C. Papachristos

6 of 26

Sampling-based Planning

Remember 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

7 of 26

Sampling-based Planning

Remember RRT Properties

RRT is probabilistically complete

The same bound for PRM

RRT is not asymptotically optimal

CS491/691 C. Papachristos

8 of 26

Sampling-based Planning

CS491/691 C. Papachristos

9 of 26

Sampling-based Planning

S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” CoRR, vol. abs/1105.1186, 2011

Asymptotic Optimality term:

CS491/691 C. Papachristos

10 of 26

Sampling-based Planning

CS491/691 C. Papachristos

11 of 26

Sampling-based Planning

CS491/691 C. Papachristos

Sampling-based Planning

PRM and RRT versions

The popularity of sampling-based planners has led to a huge variety of probabilistic sampling-based planning methods

Many focus of finding more optimal solutions faster, sometimes at the cost of formal guarantees

Examples:

“RRT-Connect”: Biased searching from start�and goal and meshing the two trees

Varying sampling density based on domain-knowledge
Computational improvements (collision checks, bootstrapping search, efficient data structures)

“Informed-RRT”: Biasing the search space with an ellipsoidal heuristic around an initial plan

CS491/691 C. Papachristos

25 of 26

Sampling-based Planning

PRM and RRT versions

The popularity of sampling-based planners has led to a huge variety of probabilistic sampling-based planning methods

CS491/691 C. Papachristos

26 of 26

Time for Questions !

CS-491/691

CS491/691 C. Papachristos