Bob and Howie's Excellent Outline
Outline Pointers
I
Intro
II
Bug Algorithms
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
XIII
Non-holonomic Path Planning
XIV
Visual Servoing
Outline wo/papers
Research Links
Author web pages
references start
I.
Intro
II.
Bug Algorithms
A. Bug2
Lumelsky
-
(no papers)
1. Completeness
2. Wall Following: Numeric Continuation Methods
3. Centerline Sonar Model: distance to closest obstacle
4. Does the robot really reach the goal?
B. TanBug
Rimon
-
(no papers)
C. WedgeBug
Laubach
Burdick
-
(no papers)
D. Others??
III.
Configuration Space, Part I
IV.
Potential Functions
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
Adding more forces
Balch/Arkin
"Avoiding the past" - method to overcome local minima
C. Navigation Functions
Rimon
-
(no papers)
Kodichek
-
(no papers)
D. Randomized Potentials??? (Here or probabilistic techniques chap)
V.
Configuration Space, Part II
A. Polygonal Obstacles
B. Some higher dims
VI.
Pixel-Based Maps, Part I
A. Search a grid (Advertise Numerical Recipes)
1. Depth-first, breadth first
Nourbash
-
(no papers)
iterative depth first deepening (combo of depth first and breadth first)
2. Dijkstra's Algorithm
3. A* (some basic thing)
4. D*
Stentz
-
(no papers)
Balch
"Grid-based Navigation for Mobile Robots" - brushfire applied to occupancy grid
B. Frontier Exploration
Yamauchi
Simmons
C. Maybe Borenstein here....??
Borenstein
D. Framed Quad-Trees
VI.
Roadmaps
A. Visibility Graph
B. Canny's Roadmap
1.
Canny
-
(no papers)
C. OPP
D. GVG
1.
Rao
2.
Choset
E. Place Maps
1.
Kuipers
2.
CJ
-
(no papers)
3.
Kriegman
-
(no papers)
VII.
Probabilistic Motion Planning Techniques
A. Probability Primer (Howie wrote this)
B. Probabilistic potential functions (??? here or above)
Latombe
C. Roadmaps
Kavraki
Latombe
Amato
Gupta
-
(no papers)
D. RRT's
Kuffner
-
(no papers)
Lavalle
-
(no papers)
VIII.
Pixel-Based Maps, Part II
A. Probability Primer
B. Occupancy
Morevac
Elfes
Konolidge
(Improved Occ)
C. Hybrid Approaches
Thrun
Kortenkamp
Arras
- (finding line segments from collections of points like Hough)
IX.
Simultaneous Localization and Mapping
A. Kalman
text that howie wrote
Davison
(slam using vision)
Durrante-Whyte
-
(no papers)
Leonard
-
(no papers)
Guivant
(slam - ekf)
B. Bayesian
Burgard
(Markov Localization)
Fox
(Monte Carlo Localization)(Particle Filter)
Thrun
Konolidge
(Markov Localization using Correlation )
C. Topological Localization
Choset
Kuipers
D. Particle Filter Techniques
Isard
Condenstation algorithm for vision
Where?
Deans
(Invariant Filter)
X.
Visibility Based
A. Art Gallery
O' Rourke
-
(no papers)
B. Voronoi Diagram
Choset
C. Pursuer-Evader
Lavalle
-
(no papers)
XI.
Coverage (Cell Decompositions)
A. Trapezoid (Chazzelle or basic thing)
Chazzelle
-
(no papers)
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?)
XII.
Non-holonomic Path Planning
XIII.
Visual Servoing
Arras
- (laser and visual homing)
Return to the bug algorithm in coverage