CPSC 689: Special Topics in Randomized Motion Planning
Course Homepage
Spring 2000

Instructor: Nancy Amato
office: 414B Harvey R. Bright Bldg
office hours: TBD, or by appointment
email: amato@cs.tamu.edu
url: http://www.cs.tamu.edu/faculty/amato
office phone: 862-2275
home phone: 693-1855 (please don't call after midnight or before 9am)

Course homepage: http://www.cs.tamu.edu/faculty/amato/Courses/689

Special Announcements

Handouts

• Syllabus html
• Some Useful Links

Back to beginning

Reading Assignments

• Thur Jan 27: Paper to be distributed (either in email or hardcopy)

• Thur Feb 3: Re-read paper from last week, and also MAPRM papers (available here)
  • "Motion Planning for a Rigid Body Using Random Networks on the Medial Axis of the Free Space", Wilmarth, Amato, Stiller.
  • "MAPRM: A Probabilistic Roadmap Planner with Sampling on the Medial Axis of the Free Space", Wilmarth, Amato, Stiller.

• Tue Feb 8: At least one of Howie Choset's GVG Papers. You can look through his publications page and find one of interest.
  I'd recommend the WAFR 96, or ICRA 95 papers. Or, if you are ambitious, his thesis. Since some of you have had troubles getting them, I've copied them here:
  • Sensor Based Planning, Part I: The Generalized Voronoi Graph , ICRA 95.
  • Sensor Based Planning, Part II: Incremental Construction of the Generalized Voronoi Graph , ICRA 95.
  • Sensor Based Motion Planning: The Hierarchical Generalized Voronoi Graph , WAFR 96.

• Tue Feb 15: The Ariadne's Clew algorithm. This paper is I think the first one. If you are interested, you can look into some of the more recent ones. (FYI, copies of the paper are available in the conference room in 407.)
  • "The Ariadne's Clew Algorithm: Global Planning With Local Methods", P. Bessiere, J. M.Ahuactzin, E.-G. Talbi, E. Mazer, Proc. Intern. Conf. on Intelligent Robotics and Systems (IROS), pp. 1373-1380, 1993.

• Thu Feb 24: Rapidly-Exploring Random Trees (RRT).
  Everyone should read (most have already):
  • Rapidly-Exploring Random Trees: A New Tool for Path Planning by Steven M. LaValle, Technical Report No. 98-11, Dept. of Computer Science, Iowa State University, Oct. 1998.
  And you should also pick one other RRT paper - all can be found on Steve's homepage or on his RRT page . Here are some links to particular papers.
  • RRT-Connect: An Efficient Approach to Single-Query Path Planning by James J. Kuffner, Jr. and Steven M. LaValle, to appear, 2000 IEEE International Conference on Robotics and Automation.
  • Randomized Kinodynamic Planning by Steven M. LaValle and James J. Kuffner, Jr., 1999 IEEE International Conference on Robotics and Automation.

• Tue Feb 29: Randomized Kinodynamic Motion Planning with Moving Obstacles.
  This is some new work by Latombe's group which builds a tree from the the start, and deals with moving obstacles with known trajectories. There are two papers - one to be presented at WAFR in March and the other at ICRA in April. Everyone should read the WAFR one, and you should also look to see if there is anything different in the ICRA one.
  • Randomized Kinodynamic Motion Planning with Moving Obstacles. D. Hsu, R. Kindel, J.C. Latombe, S. Rock. To be presented at Workshop on Algorithmic Foundations of Robotics (WAFR'00), Hanover, NH, March 2000.
  • Kinodynamic Motion Planning Amidst Moving Obstacles. R. Kindel, D. Hsu, J.C. Latombe, S. Rock. To be presented at IEEE Int. Conf. on Robotics and Automation, San Francisco, CA, April 2000.

• Tue Mar 7: SANDROS planner.
  Everyone should read the Transactions paper. You can also look through the original ICRA paper to see if there is something extra there.
  • SANDROS: A Dynamic Graph Search Algorithm for Motion Planning. Pang C. Chen and Yong K. Hwang, IEEE Transactions on Robotics and Automation, vol. 14, no. 3, June 1998.
  • SANDROS: A Motion Planner with Performance Proportional to Task Difficulty. Pang C. Chen and Yong K. Hwang, IEEE International Conference on Robotics and Automation, 1992, p. 2346-2353.

• Tue Mar 28: Visibility Roadmaps.
  Everyone should read (copies will be placed in 407):
  • Notes on Visibility Roadmaps and Path Planning, by JP Laumond and T. Simeon, Workshop on Algorithmic Foundations of Robotics (WAFR), March 2000.

• Thu Apr 6: A PRM for Closed Chain Systems.
  Everyone should read:
  • A Probabilistic Roadmap Approach for Systems with Closed Kinematic Chains by Steven M. LaValle, Jeffrey Yakey, and Lydia Kavraki, IEEE International Conference on Robotics and Automation, 1999.

• Tue Apr 11: PRMs for Deformable Parts
  Everyone should read:
  • Deformable Volumes in Path Planning Applications, E. Anshelevich, S. Owens, F. Lamiraux, L. Kavraki, IEEE International Conference on Robotics and Automation, San Francisco April 2000.
  Other related papers can be found on Lydia Kavraki's publications page. The following two papers represent previous/background work:
  • Towards Planning for Elastic Objects, L. Kavraki, F. Lamiraux, C. Holleman, 3rd Workshop on the Algorithmic Foundations of Robotics, Houston, April 1998.
  • Path Planning for Elastic Plates Under Manipulation Constraints, F. Lamiraux, L. Kavraki, IEEE International Conference on Robotics and Automation, Detroit May 1999.

• Tue April 18: Motion Planning and Drug Design
  Latombe's group has done some work on the applications of motion planning, and PRMs in particular, to problems in computational Biology and Chemistry. You can find them on his webpage.
  Everyone should read:
  • A Motion Planning Approach to Flexible Ligand Binding A.P. Singh, J.C. Latombe, and D.L. Brutlag. In Proc. 7th Int. Conf. on Intelligent Systems for Molecular Biology (ISMB), AAAI Press, Menlo Park, CA, pp. 252-261, 1999.