Mobile Robot Motion Planning Outline of Papers for Book (incomplete)

Last modified: Tue, July 25, 2006

I. Intro
• 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

II. Bug Algorithms
• A. Bug1 & 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
• B. TanBug (Rimon)
• C. Brief Mention of other bugs
  • WedgeBug (Laubach & Burdick)
  • 3D Bug (Rimon)
• D. Implementation (Implicit Function Theorem)

III. Configuration Space
• A. Two Two-dimensional Examples (De Berg etc. Chapter 13)
  
  • 1. circle chaped
  • 2. polygonal
  • 3. two link (and then put the pointer that is in fgreen)
• B. Introduction to Manifolds and Dimensions
  
• C. Topolog and Configuration Spces
  
• D. Parameterizations of Configuration Spaces
• E. Representations of Obstacles
  


• Configuration Space - Planar Robot Simulator with Obstacle Avoidance

IV. Potential Functions
• A. Additive Attractive
• B. Local Minimum Problem and Gradient Descent
• C. Wavefront Planner
• D. Bavigarion Functions (RImon and Kodicheck)
• E. Potential Functions in Non-Euclidean Configuration Spaces

V. Roadmaps (Text:
• A. Visibility Graphs
  
• B. Retracts
  
  • 1. Generalized Voronoi Diagram (Yap, Choset, Rao)
    
  • 2. Construction (Choset)
    
• C. Retract-like Structures
  
  • 1. Generalized Voronoi Graph (Choset)
    
• D. Retract-like Structures in non-Euclidean Spaces
  
• E. Silhouetees
  
  • 1. Canny's Original Roadmap (Canny)
    
  • 2. OPP (Canny and Lin, Rimon)
    
• F. Others
  
  • 1. Grids
    
  • 2. Topological Maps (Kuipers)
    
  • 3. Place Maps (Taylor and Kreigman)
    

VI. Probabilistic Motion Planning Techniques
• A. Introduction
  • A.0 Formulate as a discrete search in a continuous space
  • A.1 distance metric and node connection
  • A.2 collision checking for nodes and path segments
  • A.3 search for a path
  • A.4 improving the path
• B. Multiple-Query Methods
  • B.0 Explain Philosophy (e.g. "capture connectivity of free space")
  • B.1 Basic PRM Planner (algorithm) [Kavraki, Svestka, Overmars, Latombe]
  • B.2 selection of nodes
    • - basic random [Kavraki et al]
    • - grid based [Bohlin][Overmars]
    • - deterministic [Lavalle]
    • - visibility-based [Laumond]
    • - close to the obstacles [Amato][Overmars]
    • - close to the medial axis [Holleman][Lin][Amato]
    • - in difficult areas [Kavraki]
    • - others
  • B.3 Theoretical analysis [Motwani][Overmars][Kavraki][Bohlin]
• C. Single-Query Methods
  • C.0 Relationship to classical AI Incremental Search
  • C.1 Basic Framework [Hsu][Lavalle]
  • C.2 selection of nodes
    • - RPP (potential fields) [Barraquand & Latombe]
    • - monte-carlo [Mazer]
    • - using expansive spaces [Hsu, Latombe]
    • - RRTs [Lavalle & Kuffner]
    • - using lazy methods [Bohlin][Sanchez]
    • - incremental [Gupta]
    • - others
  • C.3 Theoretical analysis [Hsu][Lavalle]
• D. Beyond Basic Path Planning
  • D.0 non-holonomic [Laumond][Overmars]
  • D.1 kinodynamic [Hsu][Lavalle][Latombe]
  • D.3 manipulation [Simeon][Nielsen][Amato]
  • D.4 sensing [Gupta]
  • D.5 changing environments [Seth][Hsu]

VII. Kalman Approaches
• A. Kalman Primer
  • Kalman's original paper
  • Nebot, How-to Presentation on SLAM
  • Abhishek,A Tutorial on Kalman Filter based SLAM
    
  • More Kalman Filter links
• B. Localization
• C. SLAM
  • SLAM in Kalman context : Smith/Self/Cheeseman
  • Durrant Whyte/Leonard: Adapt Smith/Cheesman to larger situations
  • Breaking up the map
  • Doing things to the covariance matrix to make it more invertible
  • Examples
    • Range Only: Kantor
    • Bearing Only: Dissanayake

VIII. Bayesian Methods
• A. Occupancy Grids
  • Occupancy Grids [Elfes / Morevac ]
• B. Localization with known Maps
  • Basic Idea of Probabilistic Localization [Burgard]
  • Probabilistic Localization as Recursive Bayesian Filtering [Burgard]
  • Derivation of Probabilistic Localization [Fox & Burgard, 1996 AAAI]
  • Implementation of Probabilstic Localization
    • Kalman Filter
    • Piecewise Constant Approximation [Fox & Burgard, 1998 JAIR]
    • Particle Filters [Fox, CPR99]
    • [Kleeman 1999, Chong & Kleeman, IJRR 1999, FSR 1997]
  • Sensor Models for Probabilstic Localization
• C. SLAM
  • Improved Occ Grids [Konolidge]
  • Thrun/Wolfram/Fox
  • Gutman

IX. Cellular Decompositions
• A. Trapezoid (Chazzelle or basic thing)
  • Chazzelle - (no papers)
  • O'Rourke - CG Ch2
• B. Morse Decomposition and Sensor-Based Coverage
• C. Approximate Cell Decomposition and Coverage
  • Zelinsky and Yuta
  • Rimon
• D. Visibility-based Decomposition and Coverage
• E. Cellular Decompomposition (Collins - (no papers))

X and XI. Dynamics and Trajectory Planning
• 1. Preliminaries
  
• 2. Lagrangian Dynamics
  
  • 2.1 Standard Forms for Dynamics
    
  • 2.2 Velocity Constraints
    
  • 2.3 Dynamics of a Rotating Rigid Body
    
• 3. Decoupled Trajectory Planning
  
  • 3.1 Zero Inertia Points
    
  • 3.2 Global Time-Optimal Trajectory Planning
    
• 4. Direct Trajectory Planning
  
  • 4.1 Optimal Control
    
  • 4.2 Nonlinear Optimization
    
  • 4.3 Grid-based Search
    
  • 4.4 Rapidly Exploring Random Trees
    
  • 4.5 Potential Fields
    

XII. Nonholonomic Motion Planning
• 1. Preliminaries
  
  • 1.1 Tangent Spaces and Vector Fields
    
  • 1.2 Distributions and Constraints
    
  • 1.3 Lie Brackets
    
• 2. Control Systems
  
• 3. Controllability
  
  • 3.1 Local Accessibility and Controllability
    
  • 3.2 Global Controllability
    
• 4. Simple Mechanical Control Systems
  
  • 4.1 Simplified Controllability Tests
    
  • 4.2 Kinematic Reductions for Motion Planning
    
  • 4.3 Simple Mechanical Systems with Nonholonomic Constraints
    
• 5. Motion Planning
  
  • 5.1 Optimal Control
    
  • 5.2 Steering Chained-Form Systems Using Sinusoids
    
  • 5.3 Nonlinear Optimization
    
  • 5.4 Gradient Methods for Driftless Systems
    
  • 5.5 Differentially Flat Systems
    
  • 5.6 Cars and Cars Pulling Trailers
    
  • 5.7 Kinematically Controllable Systems
    
  • 5.8 Extended Systems
    
  • 5.9 Rapidly Exploring Random Trees
    

A.I Appendix

• Mathematical Notation
• Closure and Interior Relationships
• Basic Definitions
• Graph Representation and Basic Search
• Stentz
• Koenig & Likhachev
• Statistics Primer
• Bayesian Primer (Howie)

A.II Non-Appendix

• Sonar Sensor Processing
  • Kleeman & Kuc