LaValle Planning Algorithms, ch 6

  • (206) Combinatorial methods are complete (will return a path or say one doesn’t exist, correctly)
  • The exact structure of the problem is important in combinatorial methods.  In particular cases, efficient algorithms are applicable.
  • (207) Roadmaps provide a discrete representation of the continuous planing problem
  • (208) A number of planning algorithms that work in 2D don’t generalize to higher dimensions
  • (213) Many path planning algos are based on computational geometry methods, which is generally interested in sorting in multiple dimensions
  • (215) Costs for many 2d algos are O(nlgn)
  • (224) Algorithms that work in higher-d spaces take dimensional slices at vertices until they are back to the 2d case
  • (226) In many real problems, obstacles aren’t polys but rather have smooth surfaces.
    • This can be broken down into a discrete set of configurations for a position by encoding good poses in a stack
    • “important aspect” of this is detecting critical changes when a area in the pose goes from being blocked to unblocked, or opposite
    • Since the critical changes happen at an exact point, the problem becomes discrete again when using them
  • (232) Skipping computational algebraic geometry because it is said implementation is very difficult & computationally expensive; the algorithms are powerful though
  • (249) Planning fro robots in 3D environments with noise is NEXPTIME hard (doubly-exponential)
  • (250) Davenport-Schinzel sequences are used for finding computational bounds for many problems, often uses the Ackerman function
Tagged ,

Leave a Reply

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

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

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: