LaValle Planning Algorithms, ch 5


  • (153) Using traditional planning methods become difficult as the problems become large.  In these cases, sample-based methods are more effective
  • (155) State space for motion planning is uncountably infinite, but only a countably infinite number of samples can be used for planning
  • (168) A grid optimizes dispersion as measured by the inf-norm.  Optimizing by L2 norm is unsolved for larger than 2 dim
  • Placing grids on manifolds
  • (170) Grids can sometimes cause unexpected behavior in sample-based planning because they may align in a way that prevents a solution from being found
    • Because of this methods have been developed that form other patterns
  • (172) Methods such as Halton pts and Hammersley pts dont sample exactly according to a grid but are still more regular than uniform random sampling
    • Don’t work in large (>10) dimensional spaces
    • The above methods are cheap to use
  • (173) Once samples are allocated, need to check whether a configuration results in a collision or not, so this has to be done efficiently, since it is done constantly
  • (177) There are methods that can determine what time resolution a path should be sampled from, but the computation is expensive (it is sometimes possible to derive a Lipshitz constant to do this)
  • (180) There are methods that care just about planning from one start to one goal, and others that find a general solution (roadmaps)
  • (180) Planning methods are similar to classical graph search, except instead of following an edge by taking a single action, a whole path segment is created
  • (181) Path segments used in this search are often done greedily are are expected to fail on occasion
  • (185) Resolution can be refined iteratively, interleaving sampling and searching phases
  • (186) Potential (attract/repulse) methods
  • (188) Ariadne’s Clew tries to find a path from a vertex to a pt as far away from what has been explored
    • Requires an optimization step, which is difficult
    • A similar method, Expansive-space planner tries to explore from “isolated” vertices, requires alot of tuning
  • (189) Rapidly exploring dense trees. Works by selecing a point in space and then tries to connect the nearest vertex to that pt.  If edge is closes to that pt, the edge is bifurcated, adding a vertex in the edge
  • (194) KD-trees are efficient up to about 20 dimensions, beyond that it may just be cheaper to do naive knn
  • Various options of RDTs:
    • Can bais growth of tree towards goal
    • (195) Can use multiple trees
  • (196) Simple modifications to RDTs can be used to develop roadmaps
  • (200) Visibility roadmap methods try to get global coverage w/ a low # of vertices in path graph
    • During creation of graph, vertices are categorized as either guards or connectors, which have different properties/uses.  Only holds onto vertices if they satisfy certain criteria
  • (201) A number of tricks to try and find a path in very tight domains; one is to try and sample right around the edges of obstacles
Advertisements
Tagged ,

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: