Path Planning Systems

The "Path Planning Systems" groups is responsible for find an optimal path through the environment, given a model of the environment from the data (provided by Data Filtering Systems group). This group will be developing the high-level code to control Candii during the autonomous and GPS waypoint navigation challenges--essentially, Candii's AI. Path planning algorithms, maps, and learning are the main focus points of this group.

Path Planning Systems Architecture

People

• JP
• Jin Joo
• Husayn

Meetings

• IGVC Planning Day
  • Tuesday, 6-7pm, Tin Building
• Path Planning Meeting (with Dr. Vela)
  • Friday, 1pm, Van Leer (VL) E368
• IGVC Work Day
  • Saturday, 2-6pm, Tin Building

TODO List

• [ ] Week of January 28, 2008
  • [ ] MATLAB
    • [ ] Vectorization
  • [ ] C
    • [ ] Matrices/Vectors
    • [ ] Queues
    • [ ] Occupancy Grid

Task List

• [ ] Path Planning
  • [x] Dijkstra's algorithm
  • [ ] Gradient traversal
    • [x] manhatten distance
    • [x] vector addition
    • [ ] splines
  • [ ] A* algorithm
  • [ ] D* algorithm
• [ ] Cost Map
  • [x] Sweeping Algorithm
    • [x] implement manhattan distance
    • [x] implement geometric approximation
    • [x] add obstacles
    • [x] add variable start/goal locations
  • [ ] Obstacle Avoidance
    • [ ] using sweeping algorithm
    • [ ] using depth-limited sweep
• [ ] Implementation
  • [ ] Matlab Prototype
  • [ ] C/C++ Product

Resources

Books

• "Planning Algorithms" by Steven M. LaValle
  • http://planning.cs.uiuc.edu
  • Jin Joo has a hard copy.
• "Probabilistic Robotics" by Sebastian Thurn, Wolfram Burgard, Dieter Fox
  • JP has a hard copy.

Articles

• IEEE Xplore
  • http://www.library.gatech.edu:2048/login?url=http://ieeexplore.ieee.org
• Lengyel, Reichert, Donald, and Greenberg. "Real-Time Robot Motion Planning Using Rasterizing Computer Graphics Hardware." Comp. Graph., Vol. 243, No. 4, pp. 327-335, 1990.
  • http://www.cs.dartmouth.edu/~brd/papers/siggraph/animation.pdf
• Kimmel and Sethian. "Optimal Algorithm for Shape from Shading and Path Planning." J. of Math. Imaging and Vis., Vol 14, pp. 237-244, 2001.
  • http://www.cs.technion.ac.il/~ron/PAPERS/optimal_shading2001.ps.gz
• Wiener and Mallot. 'Fine-to-Coarse' Route Planning and Navigation in Regionalized Environments. Max-Planck-Institute Biological Cybernetics. Technical Report TR-115, 2003.
  • http://wiki.robojackets.org/wiki/images/f/f2/WienerMallot.pdf
• Kuffner. Efficient Optimal Search of Uniform-Cost Grids and Lattices. Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2004. 1946-1950.
  • http://wiki.robojackets.com/wiki/images/e/eb/KuffnerOptimalSearch.pdf
• Hassouna, Abdel-Hakim, Farag. "Robust Robotic Path Planning Using Level Sets." Proc. IEEE ICIP, pp 473-476, 2005.
  • http://www.cs.dartmouth.edu/~brd/papers/siggraph/animation.pdf