A Quadratic Regulator-Based Heuristic for Rapidly Exploring State Space. Glassman, Tedrake. ICRA 2010

RRTs don’t grow efficiently in domains with differential constraints

This is because the euclidian distance, which is the most common metric used doesn’t take system dynamics into account when selecting which node of the tree is closest to the randomly selected point

They use an affine quadratic regulator to build a better distance metric

They use the methods to explore in double integrator and swing up

Improvement drops off as nonlinearity and complexity increase

Just use MRE?

The Euclidean metric works well in holonomic domains but is a bad choice when there are a large number of constraints

There are additions to RRT that try to prevent good “closest” nodes, such as a method that removes weight from nodes that have not been attached successfully to a random point. Another method is to bias the placement of random samples in areas that are likely to be easy to hit, for example, scattered around the current tree

In practice, RRTs expand the tree for a fixed-length amount of time, so fixed time discretization

Ah, the affine quadratic regulator is needed instead of vanilla LQR because here we are trying to connect two points in state space, but either/both of them are almost always not stabilizable (you can’t stop moving at a a point that requires you to have some nonzero velocity)

They define a new coordinate system based around the random point

Can find which regions are least explored by doing a Voronoi tessalation and select region with highest area

There is an advantage to using this method in the double integrator (which is linear), but in acrobot and cart pole it doesn’t help very much