This seems to be a longer version of the original RSSS publication

- It is possible to estimate regions of attraction for smooth nonlinear systems
- This method is used to build a sparse tree of LQR stabilized trajectories
- The method probabalistically covers the controllable subset of the state space
- Seems to be for domains that have a goal state
- Planning proceeds backwards from the goal
- The algorithm samples randomly from a distribution over the state space and attempts to connect the sample to the tree, and then repeat. Ifa pt can’t be connected, it is discarded, and it may be possible to connect it later when the tree is more fully developed
- It is complete
- Read up on nested Lyapunov functions
- There was similar work to this previously, but focused on optimality so could not produce sparse solutions
- Does not assume actual domain is linear; linearizes regions and plans nearby
- This looks like a nightmare
- Skipped at least half the paper
- Say their trees are grown in the same manner as rrts
- The trajectory optimization methods used are local optimizers
- They are able to completely cover swing up in a tree with 13 branches
- RRT uses 5600 nodes, although rrt is much cheaper per node (I suspect the algorithm as a whole is cheaper as well)

- Effectively time is discretized as actions are piecewise constant
- In this implementation, a path to the tree is found by randomly sampling a piecewise constant action, and where the time horizon is randomly sampled
- What is shooting?
- It is made of a few different components
- Local motion planner (compared to multiple shooting)
- Global motion planner that connects local plans (RRT)
- Local control design (time-varying LQR)
- Local verification (SOS)

- I am really not following this paper
- Say that the bottleneck is with local verification/SOS
- They have applied the method up to 5 dimensions
- “The reliance on linearized controller synthesis means that LQR-Trees is not directly applicable to nonlinear systems which are controllable but have uncontrollable linearizations, such as nonholonomic systems”
- Discuss possible variations
- For discrete time, the approach is a bit simpler, but “(1) it is more difficult to do a careful time-discretization of a ploynomial system than a linear one, and (2) the tree will now consist of a collection of points instead of a smooth manifold, complicating any efforts to create a final value constraint which can ‘walk along the tree'”
- Method does not make any claim about optimality. If you want local optimality, you should start the tree with trajectories that satisfy that criteria and then fill the tree
- Can also try to terminate more quickly by using some other method aside from trying to blanket the entire space in funnels
- Bidirectional trees
- Other local stabilizers (instead of LQR)
- Other regional stability verifiers (instead of SOS) relies on semidefinite programming which is polynomial but very expensive
- If goal states change then parts of the tree can be reused
- Algorithm relies on integration
- They say the implementation is difficult, provide a matlab toolbox

Advertisements