Personal tools

Course Schedule

Document Actions
  • Send this
  • Print this
  • Content View
  • Bookmarks

Course Schedule Information

Lecture Topic Remarks  Video
0 Overview

Required reading:

  1. Motion planning: A journey of robots, molecules, digital actors, and other artifacts. J.C. Latombe. Int. J. Robotics Research, 18(11):1119-1128, 1999.


1 Path planning for point robots

Required reading:

  1. Robot Motion Planning (Chapter 1). J.C. Latombe. Kluwer Academic Publishers, 1991.

Supplementary reading:

  1. Principles of Robot Motion (Chapter 4, 5, 6). H. Choset et al., The MIT Press, 2005.


2 Configuration space; Minkowski sum

Supplementary reading:

  1. Robot Motion Planning (Sections 2.1-2.3.1, 2.4, 2.5, 2.7-2.9). J.C. Latombe, Kluwer Academic Publishers, 1991.
  2. Principles of Robot Motion (Section 3.1-3.3, 3.5-3.7). H. Choset et al., The MIT Press, 2005.

out:

  • Homework 1

3 Collision checking

Required reading:

  1. OBB-Tree: A hierarchical structure for rapid interference detection. S. Gottschalk, M. Lin, and D. Manocha. In SIGGRAPH 96 Conference Proceedings, pp. 171-180, 1996.
  2. V-Clip: Fast and robust polyhedral collision detection. B. Mirtich. ACM Transactions on Graphics, 17(3):177-208, 1998.

Supplementary reading:

  1. Efficient distance computation between non-convex objects. S. Quinlan. In Proc. IEEE Int. Conf. Robotics & Automation, pp. 3324-3329, 1994.
  2. Computational Geometry: Algorithms & Applications (Section 7.1). M. de Berg et al., Springer, 2000.

out:

  • Presentation information
4 Introduction to randomized motion planning; Multi-query PRM; Analysis

Required reading:

  1. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. L.E. Kavraki, P. Svestka, J.C. Latombe, and M. Overmars. IEEE Trans. Robotics & Automation, 12(4):566-580, 1996.
  2. Path planning in expansive configuration spaces. D. Hsu, J.-C. Latombe and R. Motwani. Int. J. Computational Geometry & Applications, 9(4 & 5):495-512, 1999. (read Sections 1 and 2)

Probability review

out:

  • Homework 2

5 Single-query PRM; Ssampling strategies

Required reading:

  1. Path planning in expansive configuration spaces. D. Hsu, J.-C. Latombe and R. Motwani.  Int. J. Computational Geometry & Applications, 9(4 & 5):495-512, 1999.
  2. Path planning using lazy PRM. R. Bohlin and L.E. Kavraki. In Proc. IEEE Int. Conf. Robotics & Automation,  pp. 521–528, 2000.

Supplementary reading:

  1. Randomized kinodynamic planning. S. M. LaValle and J. J. Kuffner. Int. J.  Robotics Research, 20(5):378-400, 2001.

out:

  • Project information
6 Sampling strategies for narrow passages

Required reading:

  1. The Gaussian sampling strategy for probabilistic roadmap planners. V. Boor, M.H. Overmars, and A.F. van der Stappen. Proc. IEEE Int. Conf. Robotics & Automation,  pp. 1018-1023, 1999.
  2. Towards Optimal Configuration Space Sampling. B. Burns and O. Brock.  In Proc. Robotics: Science and Systems, 2005.

Supplementary reading:

  1. On the Probabilistic Foundations of Probabilistic Roadmap Planning. D. Hsu, J.C. Latombe, and H. Kurniawati. 2005.
  2. OBPRM: An obstacle-based PRM for 3D workspaces. Nancy M. Amato, O.B. Bayazit, L.K. Dale, C. Jones, D. Vallejo. In P. K. Agarwal, et al., editors, Robotics: the Algorithmic Perspective, pp. 155-168, A. K. Peters, 1998.
  3. The bridge test for sampling narrow passages with probabilistic roadmap planners. D. Hsu, T. Jiang, J. Reif, and Z. Sun. Proc. IEEE Int. Conf. on Robotics & Automation, pp.4420-4426, 2003.
 Student presentations
7 Digital actors; Virtual environment navigation

Required reading:

  1. Planning motions with intentions. Y. Koga, K. Kondo, J. Kuffner, and J.C. Latombe. In SIGGRAPH 94 Conference Proceedings, pp. 395-408, 1994.
  2. Motion planning for camera movements in virtual environments. D. Nieuwenhuisen and M.H. Overmars. 2003.

Supplementary reading:

  1. Robot Motion Planning (Sections 11.1-11.4). J.C. Latombe. Kluwer Academic Publishers, 1991.
  2. An intelligent user interface with motion planning for 3-D navigation. T.-Y. Li and H.-K. Ting. In Proc. IEEE Virtual Reality, 2000.
  3. Interactive navigation in complex environments using path planning. B. ACM  Symp.  Interactive 3D Graphics, 2003
 Student presentations

due: project proposal
8 Target finding & Tracking

Required reading:

  1. A visibility-based pursuit-evasion problem. L.J. Guibas, J.C. Latombe, S.M. LaValle, D. Lin, and R. Motwani. Int. J. Computational Geometry & Applications, 9(5):471-194, 1999.
  2. Real-time combinatorial tracking of a target moving unpredictably among obstacles. H.H. Gonzalez-Banos, C.Y. Lee, and J.C. Latombe. Proc. IEEE Int. Conf. on Robotics & Automation, 2002.
Student presentations
9 Multiple robot coordination

Required reading:

  1. Deadlock-free and collision-free coordination of two robot manipulators. P.A. O'Donnell and T. Lozano-Perez.  Proc. IEEE Int. Conf. Robotics & Automation, pp. 484-489, 1989.
  2. Using a PRM planner to compare centralized and decoupled planning for multi-robot systems. G. Sánchez-Ante, J.C. Latombe.  Proc. IEEE Int. Conf. Robotics & Automation, 2002.

Supplementary reading:

  1. Guest editorial: Advances in multirobot systems. T. Arai, E. Pagello, L.E. Parker. IEEE Trans. Robotics & Automation, 18(5):655-661, 2002.
  2. Simulating virtual human crowds with a leader-follower model. T.Y. Li, Y.J. Jeng, and S. Chang. Proc. Computer Animation Conf., 2001.
 Student presentations
10 Kinodynamic motion planning

Required reading:

  1. Motion planning for car-like robots, a probabilistic learning approach, P. Svestka, M.H. Overmars. Int. J. Robotics Research 16:119-143, 1997.
  2. Randomized kinodynamic motion planning with moving obstacles. D. Hsu, R. Kindel, J.C. Latombe, and S. Rock. Int. J. Robotics Research, 21(3):233-255, 2002.

Supplementary reading:

  1. Kinodynamic motion planning. B. Donald, P. Xavier, J. Canny, and J. Reif. J. ACM, 40(5):1048-1066, 1993.
  2. Randomized kinodynamic planning. S. M. LaValle and J. J. Kuffner. Int. J.  Robotics Research, 20(5):378-400, 2001.
Student presentations
11 Special topics
Required reading:
  1. Motion planning for humanoid robots. J.J. Kuffner, K. Nishiwaki,
  2. Towards autonomous free-climbing robots. T. Bretl, S.M. Rock, and J.C. Latombe,  Int. Symp. on Robotics Research, 2003.
Supplementary reading:
  1. Motion planning for knot untangling. A.M. Ladd and L.E. Kavraki. Proc. Int. Workshop on Algortihmic Foundations of Robotics, 2002.
 Student presentations
12 Molecular motion

Required reading:

  1. A dimensionality reduction approach to modeling protein flexibility. Teodoro, M., Phillips, G. N. Jr., and Kavraki, L. E.. In Proc.  ACM Int. Conf. on Research in Computational Biology (RECOMB), pp. 299–308, 2002.
  2. Elastic models of conformational transitions in macromolecules. M.K. Kim, G.S. Chirikjian, and R.L. Jernigan. J. Molecular Graphics & Modelling, 21:151-160, 2002.

Supplementary reading:

  1. A randomized kinematics-based approach to pharmacophore-constrained conformational search and database screening. S. M. LaValle, P. Finn, L. Kavraki, and J.C. Latombe.  J. Computational Chemistry, 21(9):731--747, 2000.
Student presentations
13 Project presentations

Copyright 2007, by the Contributing Authors. Cite/attribute Resource. Hsu, D. (2007, November 19). Course Schedule. Retrieved March 12, 2010, from RoboticsCourseWare.org Web site: http://roboticscourseware.org/fullcourses/motion-planning-and-applications-robots-digital/schedule. This work is licensed under a Creative Commons License. Creative Commons License