Motion Planning the Presence of Drift, Underactuation, and Discrete System Changes. Ladd, Kavarki. RSS 2005


  1. Originally in motion planning, the goal was just to find a collision-free path in C-space.  If there were dynamic constraints, it was of a secondary concern to use the original path found under those dynamic constraints.  Doing this though, is difficult (path may not actually be executable) and generally produces low quality, jerky trajectories.
  2. “This paper addresses the implementation of a planning method and its application to a motion planning benchmark with severe underactuation, significant drift, high dimensionality, discrete system changes that occur at boundary conditions, and finally a system which is not reducable to a system with lower order dynamics.
  3. Two goals of this paper:
    1. Development of online planners that provide stability and completeness guarantees
    2. Development of offline planners that can be used interactively in prototyping
  4. There are a number of criteria that make motion planning hard:
    1. Drift: When a system cannot instantaneously stop.  “From a planning perspective, systems with drift are challenging since the shortest path cost between two states frequently disagrees with this metric”
    2. Underactuation: When the dimension of the control space is less than the dimension of the state space.  Can be the result of non-holonomic or other dynamic constraints.  “Analyzing the shape and dimensionality of the reachable space in the presence of underactuation and kinematic constraints can be quite challenging”
    3. Discrete system changes:  discontinuities in the the dynamic constraints or state variables as system evolves
    4. High-dimensional systems:  In particular, this is problematic in dynamic systems where state parameters interact in a complicated way
  5. The simulation domain is the computer game of Koules, which objects pushing and bouncing on each other.  Second-order dynamic system
  6. The planning algorithm used is called PDST-Explore, it was previously introduced but is expanded here
  7. Planner is black-box, uses trajectories of libraries, search is guided by space partition data structure
  8. “A single execution of PDST-Explore is used to find a feasible path that kills on Koule [part of the solution to the full problem].  Multiple executions of the planner can be used to construct a sequence of paths that combine to be a solution for a given initial state.  However, it is possible that no solution is reachable form the final state of a partial solution generated by on execution of PDST-Explore.”   They have special machinery to take care of that situation
  9. The algorithm performs random walks to optimize coverage of the state space.  Constructs a tree with the root corresponding to the query state
  10. Way state space decomposition and knownness estimations are performed is similar to INFORMED AND PROBALISTICALLY COMPLETE SEARCH FOR MOTION PLANNING UNDER DIFFERENTIAL CONSTRAINTS. BEKRIS, KAVRAKI. AAAI 2008 (WORKSHOP?).  Basically put samples in the tree, as each sample is put in a leaf that leaf is bisected immediately
  11. Every trajectory must be contained only within one cell.
  12. There is a controller that is used, so the trajectories generated are in terms of state space and then a controller tries to find actions to satisfy that sequence of states.  I thought that this is specifically not what they are doing?  I must be misunderstanding something.  The way the trajectories are sampled has a fair amount of domain knowledge cooked in
  13. There is a backtracking mechanism to deal with partial solutions which can’t be solved
  14. Although the cost of the algorithm is N log N in terms of # of trajectories, costs look linear because the simulator dominates the cost of actually planning

Fast Tree-Based Exploration of State Space for Robots with Dynamics.  Ladd, Kavraki.  Algorithmic Foundations of Robotics.  2005.

  1. Paper for the same algorithm as above, in a longer version of the above
  2. Planner represents samples as path segments as opposed to individual states, and uses non-uniform subdivisions of the state space to do proper exploration
    1. Gets rid of problems related to sample placement, metrics, and coverage estimation
  3. Test on kinodynamic point, differential drive, and blimp-like robots
  4. There are a few families of dynamics planning problems in the literature:
    1.  Exact: Produce optimal paths but are PSPACE
    2. Path Conversion: Transform the problem into some other space and solve that easier problem, these methods tend to produce paths of low quality
    3. Sampling Based
      1. Roadmap (PRM): Global sampling and local planners to build a graph in the space.  The local planner can be problematic, as it may not be possible to compute for all domains, and is computationall expensive in most that it does exist for.  PRMs are complete
      2. Tree-based (RRT, EST): These are cheaper than PRMs, but may also leverage local planners to connect trees grown from different locations
  5. There are many exploration planners, that work to ensure state space has a good coverage.  They are used in bi-directional planning and Probabalistic Roadmap of Trees algorithm, but most instances of exploration planners are expensive
    1. Generally work by measuring which states need to be explored and then growing the tree in that direction
  6. PDST-Explore works differently, and is designed for domains with second-order dynamics
  7. Tree based planners are sensitive to the method that determines proximity
    1. In particular, the drift present in second-order systems invalidates inherent assumptions in the way the metric is used”
  8. Goal of alg is to maintain good qualities of tree based planners (such as speed), while addressing the shortcomings.  In order to do so, the algorithm:
    1. Uses path segment samples instead of state space samples
    2. Does not leverage metrics
    3. Has a greedy deterministic path segment selection method
  9. Samples put into the tree have to be collision free
  10. I’m not understanding something fully because the tree decomposes the state space, but samples in the tree are paths?
  11. I think the tree decomposition only really serves to select which point is expanded next.  All the expansions and next states are
  12. In a successful (collision-free) move, the tree further decomposes the space, changing priorities.  On failed expansions, the priority is adjusted manually (penalized)
  13. Density/knownness of a cell is determined by #of samples in the cell and the volume of the cell
  14. They run some experiments on some extremely complex 2d-navigation domains (real mazes) with differential drive
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: