Informed and Probalistically Complete Search for Motion Planning under Differential Constraints. Bekris, Kavraki. AAAI 2008 (workshop?)


  1. A motion planner that incorporates heuristics, doing both greedy and methodical search
  2. Has completeness guarantees
  3. Domains of interest are non-holonomic systems w/2nd order constraints, such as a car with bounded acceleration and steering velocity
  4. Constructs paths that have a stable end state
  5. RRT requires a distance metric, but it may be difficult to define a good one for many domains, which severely impacts the quality of solutions
  6. There is another algorithm PDST that doesn’t require a distance metric and performs adaptive subdivision and is probabistically complete
  7. Both methods “can be viewed as continuous-space analogs of traditional uniformed search.”
  8. This paper proposes a method that performs informed search in state space
  9. Algorithm proposed is called Informed Subdivision Tree (IST)
  10. Algorithm operates in C-Space
  11. Say that operating in C-space can lead to getting stuck in local minima (I don’t know enough about the field to know why this is)
    1. In order to resolve the problem it uses the adaptive subdivision methods of PDST
  12. Builds a tree, everytime a random point is selected the tree subdivides the leaf that point corresponds to is subdivided
  13. Similar in concept to MRE, using the size of the leaf to determine how well known a region is
  14. Cells that have no connected points have an “exploration value” of ∞
  15. For some domains it is possible to do a projection to work in a smaller dimension problem.  The car domain that was mentioned is one example
  16. They use a precomputed PRM to create a good heuristic for the planning space
  17. The heuristic function used is a product of a number of terms (such as distance to nearest obstacle), so its a little more expensive to query but empirically leads to more efficient planning
  18. There is also a penalty for repeatedly trying to plan from the same edge
  19. Trajectory libraries are used for planning to connect points
  20. There are many components to the paper and I’m only half paying attention because I am a displaced person at the moment
  21. Skipping completeness proof
  22. The planner is up to an order of magnitude faster than RRT-goal bias, RRT*, and PDST
    1. Paths formed are also of higher quality, which is attributed to the good heuristic function
  23. “Sampling-based kinodynamic planners are unable to solve some hard kinodynamic problems but they often face the problem of regression as they propagate trajectories in already explored space.  Heuristic search can be very beneficial in guiding the operation of sampling-based planners in such challenging problems so as to avoid regression and focus the search in the part of the state space that is beneficial to the solution of a problem.”
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: