-
I. Intro (Text: pdf/ps,
(last updated 9/5/2001, Copyright Howie Choset, 2001)
- Where am I?--Sensors and Methods for Mobile Robot Positioning by J. Borenstein , H. R. Everett , and L. Feng
- Robot Motion Planning by J.C. Latombe (out of print)
- Introduction to AI Robotics by Robin Murphy
- Sensors for Mobile Robots by H. Bart R. Everett
- Computational Principles of Mobile Robotics by Gregory Dudek and Michael Jenkin
- Computational Geometry: Algorithms and Applications by Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf
- Computational Geometry in C (Second Edition) by Joseph O'Rourke
- A. Bug2
- Lumelsky
- 1. Completeness
- 2. Wall Following: Numeric Continuation Methods
- 3. Centerline Sonar Model: distance to closest obstacle
- 4. Does the robot really reach the goal?
- D. Fox, W. Burgard, and S. Thrun
- Lumelsky
- B. TanBug (Rimon)
- C. WedgeBug (Laubach & Burdick)
- D. 3D Bug (Rimon)
- Configuration Space (Lozano-Perez)
- A. Attractive/Repulsive Functions
- 1. Positive Charge Analogy and Hill Climbing
- 2. Distance Function
- Definition and gradient
- Centerline Sonar Model: Distance to all obstacles
- Local Minima in sensor array
- Brushfire algorithm
- 3. Potential Function Definition
- Functional Definition
- Gradient Descent (Minima, maxima, saddle)
- Direct Sensor Measurements
- Vectorfield Histogram (Borenstein)
- Brushfire
- Fast March Algorithm (Sethian (Potential based))
- 4. Combination of Functions (related to behavioral-based)
- Piece-wise potential functions (Arkin/Balch "Aura: Principles and Practices" - adding discrete potential fields)
- B. Local Minimum Problem -- trapped
- C. Adding more forces (Balch/Arkin "Avoiding the past" - method to overcome local minima)
- D. Navigation Functions (Rimon & Kodicheck)
- E. Randomized Potentials??? (Here or probabilistic techniques chap) (Barraquand, Langlois & Latombe)
- A. Polygonal Obstacles (De Berg etc. Chapter 13)
- B. Some higher dims
- A. Search a grid (Advertise Numerical Recipes)
- B. Frontier Exploration
- C. Maybe Borenstein here....? (Borenstein)
- D. Framed Quad-Trees (Stentz)
- A. Visibility Graph
- B. Canny's Roadmap (Canny)
- C. OPP
- 1. Canny & Lin
- 2. Rimon
- D. GVG
- E. Place Maps
- A. Probability Primer (Howie wrote this)
- B. Probabilistic potential functions (??? here or above) (Latombe)
- C. Roadmaps
- D. RRT's
- A. Probability Primer
- B. Occupancy
- C. Hybrid Approaches
- Thrun
- Kortenkamp
- Arras - (finding line segments from collections of points like Hough)
- A. Kalman
- text that howie wrote
- Davison (slam using vision)
- Leonard and Durrante-Whyte
- Guivant (slam - ekf)
- B. Bayesian
- C. Topological Localization
- D. Particle Filter Techniques (Isard Condenstation algorithm for vision)
- Where? (Deans (Invariant Filter))
- A. Cellular Decompompositions
- O'Rourke - CG Ch2
- B. Boustrophedon and Related Approaches
- Choset
- Acar
- Prasad
- Lumelsky
- Hert
- Rimon
- A. Trapezoid (Chazzelle or basic thing)
- B. Boustrophedon and Related Approaches
- Acar
- 1. include Bug 2.5 here
- C. Cellular Decompomposition (Collins - (no papers))
- D. Approximate Cell Decomps and Coverage Algos (Butler (where?))
- Arras - (laser and visual homing)
- path + time-scaling = trajectory
- robot dynamics
- fully actuated vs. underactuated (more on underactuated next chapter)
- kinodynamic (Canny, Donald, Reif, Xavier...)
- RRT (LaValle and Kuffner)
- decoupled approach: path planning followed by time-scaling (Bobrow et al., Shin and McKay, Shiller, Hollerbach, ...)
- optimization approaches (Tan and Potts, Vukobratovic, many using SQP like Bobrow)
- (restrict to R^n, leave out Lie groups, coordinate-free formalisms, appendix?)
- tangent vector, tangent space, tangent bundle
- vector fields, integral curves, Lie bracket
- distributions, involutivity, integral manifold, Frobenius
- dynamical polysystem, control affine systems, drift and drift-free
- controllability definitions
- Lie algebra of vector fields, LARC
- STLC
- nonholonomic constraints: (Pfaffian) rolling, conservation of momentum
- positive formulation: vector fields; negative: constraints
- underactuated robots (2nd order constraints)
- - motion planning for cars, cars and trailers (Latombe, Laumond, Lumelsky IROS 2000, lots...)
- - holonomic planning followed by transform for STLC systems
- - optimization approaches, nonsingular loops (Wen, Sontag, Sussmann, Fernandes, others)
- - geometric phase, iterative closed loops
- - RRT
- - differentially flat systems (Murray, Fliess, Martin, others)
- - chained form systems (many)
- - kinematically controllable systems (Bullo and Lynch)
- - averaging/oscillatory approaches
- (- mixed kinematic and dynamic)
- - fictitious inputs, Lafferiere's method
- some other references: Latombe book, Canny and Li book, Murray book, Mason book, Wen article, my ME 495 lectures
- (Lots possible here: need to define scope; below is very rough)
- adding manipulation mechanics to planning
- manipulation taxonomy (Mason and Lynch)
- movable objects (Wilfong)
- transit paths and transfer paths (Alami, Dacre-Wright, Koga, Kuffner, Ferbach ...)
- assembly/disassembly planning, NDBG's, etc. (Wilson, many)
- friction, wrenches, moment labels, form and force closure
- grasp planning (including 2nd order mobility, Rimon and Burdick)
- (possibly finger gaiting, Rus-Zefran-Goodwine etc., rolling, but don't digress into control)
- push planning and controllability of manipulation (Lynch)
- other push planning (Sudsang and Ponce, Agarwal)
- grasp sequences (Brost, Goldberg), conveyor feeding
- LMT
- AND/OR graphs
II. Bug Algorithms (Text: pdf/ps, last updated 9/5/2001, Copyright Howie Choset, 2001)
III. Configuration Space, Part I
IV. Potential Functions
V. Configuration Space, Part II
VI. Pixel-Based Maps, Part I
VII. Roadmaps
VIII. Probabilistic Motion Planning Techniques
IX. Pixel-Based Maps, Part II
X. Simultaneous Localization and Mapping
XI. Visibility Based
XII. Coverage (Cell Decompositions)
XII. Coverage (Cell Decompositions)
XIII. Non-holonomic Path Planning
XIV. Visual Servoing
XV. Trajectory planning
XVI. Nonholonomic motion planning
XVII. Manipulation planning
XVIII. Miscellaneous