LQR-Trees: Feedback Motion Planning via Sums-of-squares Verification. Tedrake, Manchester, Tobenkin, Roberts. RSS 2009


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

  1. It is possible to estimate regions of attraction for smooth nonlinear systems
  2. This method is used to build a sparse tree of LQR stabilized trajectories
  3. The method probabalistically covers the controllable subset of the state space
  4. Seems to be for domains that have  a goal state
  5. Planning proceeds backwards from the goal
  6. 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
  7. It is complete
  8. Read up on nested Lyapunov functions
  9. There was similar work to this previously, but focused on optimality so could not produce sparse solutions
  10. Does not assume actual domain is linear; linearizes regions and plans nearby
  11. This looks like a nightmare
  12. Skipped at least half the paper
  13. Say their trees are grown in the same manner as rrts
  14. The trajectory optimization methods used are local optimizers
  15. They are able to completely cover swing up in a tree with 13 branches
    1. RRT uses 5600 nodes, although rrt is much cheaper per node (I suspect the algorithm as a whole is cheaper as well)
  16. Effectively time is discretized as actions are piecewise constant
  17. 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
  18. What is shooting?
  19. It is made of a few different components
    1. Local motion planner (compared to multiple shooting)
    2. Global motion planner that connects local plans (RRT)
    3. Local control design (time-varying LQR)
    4. Local verification (SOS)
  20. I am really not following this paper
  21. Say that the bottleneck is with local verification/SOS
  22. They have applied the method up to 5 dimensions
  23. “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”
  24. Discuss possible variations
  25. 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'”
  26. 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
  27. Can also try to terminate more quickly by using some other method aside from trying to blanket the entire space in funnels
  28. Bidirectional trees
  29. Other local stabilizers (instead of LQR)
  30. Other regional stability verifiers (instead of SOS) relies on semidefinite programming which is polynomial but very expensive
  31. If goal states change then parts of the tree can be reused
  32. Algorithm relies on integration
  33. They say the implementation is difficult, provide  a matlab toolbox
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: