CSCI-4290/6290: Robot Motion Planning
Fall 2003

I have copies of most of these papers or you can get them from the library (especially useful are the Ejournal listings). Please contact me with a list of papers you are interested in by October 23. In some cases, we may change the set of papers slightly to better match the course topics.

If there are other papers that you are interested in presenting that are not on the list below, send me email with the paper info so I can let you know whether those papers are appropriate.

Sampling-based planning and PRM variants:

• S. M. LaValle, M. S. Branicky, and S. R. Lindemann. On the relationship between classical grid search and probabilistic roadmaps. International Journal of Robotics Research. (to appear)
• S. M. LaValle and M. S. Branicky. On the relationship between classical grid search and probabilistic roadmaps. In Proc. Workshop on the Algorithmic Foundations of Robotics, December 2002.
• Path planning in expansive configuration spaces. D. Hsu, J.-C. Latombe and R. Motwani. International Journal of Computational Geometry and Applications, 9(4 & 5), 495-512, 1999. ps
• Motion Planning for a Rigid Body Using Random Networks on the Medial Axis of the Free Space, Steven A. Wilmarth, Nancy M. Amato, Peter F. Stiller, Proceedings of the 15th Annual ACM Symposium on Computational Geometry (SoCG'99), June 1999, pp. 173-180. pdf
• A Random Loop Generator for planning the motions of closed kinematic chains using PRM methods. J. Cortes, T Simeon, J.-P. Laumond. IEEE Int. Conf. on Robotics and Automation (2002).
• A Kinematics-Based Probabilistic Roadmap Method for Closed Chain Systems, Li Han and Nancy M. Amato, Proceedings of the Workshop on Algorithmic Foundations of Robotics (WAFR'00), March 2000. pdf
• J. Yakey, S. M. LaValle, and L. E. Kavraki. Randomized path planning for linkages with closed kinematic chains. IEEE Transactions on Robotics and Automation, 17(6):951--958, December 2001.
• 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.
• Probabilistic motion planning for parallel mechanisms. J. Cortes, T Simeon. IEEE Int. Conf. on Robotics and Automation (2003).
• Path Planning Using Lazy PRM. R. Bohlin and L.E. Kavraki. IEEE International Conference on Robotics and Automation, San Francisco, April 2000. ps
• Nielsen, C. and Kavraki, L. E.. A Two-Level Fuzzy PRM for Manipulation Planning. In Proceedings of The IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1716.1722, IEEE Press, November 2000.

Nonholonomic motion planning:

• J. Barraquand and J.C. Latombe. Nonholonomic Multibody Robots: Controllability and Motion Planning in the Presence of Obstacles. Algorithmica, 10:121-155, 1993.
• Multi-Level Path Planning for Nonholonomic Robots Using Semi-Holonomic Subsystems. In Algorithms for Robotic Motion and Manipulation, J.P. Laumond and M. Overmars (eds.), A K Peters, Wellesley (MA), pages 79-96, 1997.
• Multi-level path planning for nonholonomic robots using semi-holonomic subsystems by S. Sekhavat, P. Svestka, J.-P. Laumond, M.H. Overmars. International Journal of Robotics Research, Vol.17, No. 8, pp.840-857, August 1998.
• From Reeds and Shepp's to continuous-curvature paths, Th. Fraichard and A. Scheuer and R. Desvigne, Proceedings of the International Conference on Advanced Robotics, pages 585--590, Oct 1999, Tokyo, Japan.
• Continuous-curvature path planning for car-like vehicles, A. Scheuer and Th. Fraichard, Proc. of the IEEE-RSJ Int. Conf. on Intelligent Robots and Systems, volume 2, pages 997--1003, Sep 1997, Grenoble, France.
• D. J. Balkcom and M.T. Mason. Time optimal trajectories for differential drive vehicles. International Journal of Robotics Research , Vol. 21, No. 3, March 2002, pp. 199-217.

Kinodynamic planning:

• Motion Planning in Dynamic Environments using Velocity Obstacles, P. Fiorini and Z. Shiller, International Journal of Robotics Research, volume 17, number 7, pages 760--772, jul 1998.
• Time Optimal Trajectory Planning in Dynamic Environments, P. Fiorini and Z. Shiller, Journal of Applied Mathematics and Computer Science, volume 7, number 2, pages 101--126, jun 1997.
• Quasi-Random Algorithms for Real-Time Spacecraft Motion Planning and Coordination, E. Frazzoli, To appear in Acta Astronautica, 2003.
• Maneuver-Based Motion Planning for Nonlinear Systems with Symmetries, E. Frazzoli, Submitted to the IEEE Transactions on Robotics and Automation.
• R. Kindel, D. Hsu, J.C. Latombe, S. Rock. Kinodynamic Motion Planning Amidst Moving Obstacles. Proceedings of IEEE Int. Conf. on Robotics and Automation, San Francisco, pages 537-543, April 2000.
• Randomized Kinodynamic Motion Planning with Moving Obstacles. D. Hsu, R. Kindel, J.C. Latombe, S. Rock. Workshop on Algorithmic Foundations of Robotics (WAFR'00), Hanover, NH, March 2000.
• B. Donald, P. Xavier, J. Canny, and J. Reif. Kinodynamic Motion Planning, Journal of the ACM, 40(5):1048-1066, 1993.
• Non-uniform discretization approximations for kinodynamic motion planning and its applications, J. Reif and H. Wang, Algorithms for Robotic Motion and Manipulation, J.-P. Laumond and M. Overmars (editors), A. K. Peters, Wellesley, Massachusetts, 1997, pages 97--112.

Multiple robot coordination:

• Path Coordination for Multiple Mobile Robots: A Resolution-Complete Algorithm, Thierry Simeon and Stephane Leroy and Jean-Paul Laumond, IEEE Transactions on Robotics and Automation, volume 18, number 1, pages = "42--49", feb 2002.
• On Delaying Collision Checking in PRM Planning --- Application to Multi-Robot Coordination, G. Sanchez and J.C. Latombe, International Journal of Robotics Research, volume 21, number 1, pages 5--26, January 2002.
• Coordinated path planning for multiple robots, P. Svestka and M. Overmars, Robotics and Autonomous Systems, volume 23, pages 125-152, 1998.
• Mixed integer programming for multi-vehicle path planning", T. Schouwenaars and B. De Moor and E. Feron and J. How, European Control Conference 2001, 2001, Porto, Portugal.
• Maneuver-Based Motion Planning and Coordination for Single and Multiple Unmanned Aerial Vehicles, E. Frazzoli, AIAA Conference on UAV systems and technologies, Portsmouth, VA, 2002.

Collision detection:

• Fast Proximity Queries with Swept Sphere Volumes, Eric Larsen, Stefan Gottschalk, Ming C. Lin, and Dinesh Manocha, Department of Computer Science, University of N. Carolina, Chapel Hill, TR99-018, 1999. pdf
• E. Larsen, S. Gottschalk, M. Lin, and D. Manocha, Fast Distance Queries using Rectangular Swept Sphere Volumes, IEEE Conference on Robotics and Automation, San Francisco, CA, April 2000.
• A Fast Procedure for Computing the Distance between Complex Objects in Three-Dimensional Space", E. G. Gilbert and D. W. Johnson and S. S. Keerthi, IEEE Transactions on Robotics and Automation, volume 4, number 2, pages 193--203, April, 1988.
• Brian Mirtich, V-Clip: Fast and Robust Polyhedral Collision Detection, ACM Transactions on Graphics, vol. 17, no. 3, pages 177-208, July 1998. pdf

Manipulation planning:

• A probabilistic algorithm for manipulation planning under continuous grasps and placements. A. Sahbani, J. Cortes, T Simeon. IEEE Int. Conf. on Int. Robots and Systems (2002).
• A Manipulation planner for Pick and Place operations under continuous grasps and placements. T Simeon, J. Cortes, A. Sahbani, J.-P. Laumond. IEEE Int. Conf. on Robotics and Automation (2002).
• Y. Koga and J.C. Latombe. On Multi-Arm Manipulation Planning. Proceedings of the IEEE International Conference on Robotics and Automation, pages 945-952, 1994
• R. Alami, J.P. Laumond, and T. Simeon. Two Manipulation Planning Algorithms. In Algorithmic Foundations of Robotics, K. Goldberg et al. (eds.). A K Peters, Wellesley (MA), pages 109-125. 1995.
• T.Y. Li and J.C. Latombe. Manipulation Planning for Two Robot Arms in a Dynamic Environment. International Journal of Robotics Research, 16(2):144-167, 1997.
• D. Hsu, J.C. Latombe, and S. Sorkin. Placing a Robot Manipulator Amid Obstacles for Optimized Execution. Proceedings of IEEE International Symposium on Assembly and Task Planning, Porto, Portugal, pages 280-285, 1999

Assembly planning:

• D. Halperin, J.C. Latombe, and R.H. Wilson. A General Framework for Assembly Planning: The Motion Space Approach. Algorithmica, vol. 26, no. 3-4, pages 577-601, 2000.
  ACM SoCG 1998, pages 9-18, pdf
• Algorithms for Fixture Design, C. Wentink, A. F. van der Stappen, M. Overmars, In Algorithms for Robotic Motion and Manipulation, J.P. Laumond and M. Overmars (eds.), A K Peters, Wellesley (MA), pages 321--346, 1997.
• Disassembly Sequencing Using a Motion Planning Approach, Sujay Sundaram, Ian Remmler, and Nancy M. Amato, Proceedings of the 2001 IEEE International Conference on Robotics and Automation (ICRA'01), May 2001. pdf

Flexible objects:

• F. Lamiraux and L.E. Kavraki, "Planning Paths for Elastic Objects under Manipulation Constraints", International Journal of Robotics Research, 20(3), 2001, 188-208. pdf
• 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.

Molecular modeling:

• Modeling RNA Folding Landscapes with Probabilistic Roadmap Methods, Bonnie Kirkpatrick, Xinyu Tang, Shawna Thomas, Dr. Nancy Amato, July 1, 2003.
• Teodoro, M., Phillips, G. N. Jr., and Kavraki, L. E.. Molecular Docking: A Problem with Thousands of Degrees of Freedom. In Proc. of the 2001 IEEE International Conference on Robotics and Automation (ICRA 2001), pp. 960-966
• Zhang, M. and Kavraki, L. E.. Solving Molecular Inverse Kinematics Problems for Protein Folding and Drug Design. In Currents in Computational Molecular Biology, pp. 214 Washington, DC, 2002 Details [.pdf]
• Ligand binding
• A Randomized Kinematics-Based Approach to Pharmacophore-Constrained Conformational Search and Database Screening by Steven M. LaValle, Paul W. Finn, Lydia E. Kavraki, and Jean-Claude Latombe, Journal of Computational Chemisty, Vol. 21, No. 9., pages 731-747, 2000. ps
• P. Finn and L. Kavraki. Computational Approaches to Drug Design, Algorithmica, 25, 1999, 347-371. pdf
• Efficient generation of Feasible Pathways for Protein Conformational Transitions, M. K. Kim, R. L. Jernigan, G. S. Chirikjian, Biophysical Journal, Volume 83, Sept 2002, 1620-1630.
• Donald, Dartmouth
• Erdmann, CMU

Medical surgical planning:

• R.Z. Tombropoulos, J.R. Adler, and J.C. Latombe. CARABEAMER: A Treatment Planner for a Robotic Radiosurgical System with General Kinematics. Medical Image Analysis, 3(3):237-264, 1999
• A. Schweikard, R. Tombropoulos, L. Kavraki, J. Adler, and J.-C. Latombe, Treatment Planning for a Radiosurgical System with General Kinematics Proceedings of the IEEE International Conference on Robotics and Automation San Diego, CA, 1994, 1720-1727.

Feedback motion strategies:

• A Framework for Planning Feedback Motion Strategies Based on a Random Neighborhood Graph, L. Yang and S. M. LaValle, IEEE Conference on Robotics and Automation, pages 544-549, April 2000. ps

Graphics:

• Motion planning for Animation? -- Siggraph
• Schaal & co, ICRA 2002.
• Interactive Manipulation of Rigid Body Simulations. Jovan Popovic, Steven M. Seitz, Michael Erdmann, Zoran Popovic, and Andrew Witkin. In Computer Graphics (Proceedings of SIGGRAPH 2000), Annual Conference Series. ACM SIGGRAPH 2000
• Y. Koga, K. Kondo, J. Kuffner, and J.C. Latombe. Planning Motions with Intentions. Proceedings of SIGGRAPH'94, pages 395-408, 1995

Miscellaneous

• Distributed Planning and Control for Modular Robots with Unit-Compressible Modules, Z. Butler and D. Rus, International Journal of Robotics Research, Volume 22, Issue 9, September 2003.
• A Framework for Real-Time Path Planning in Changing Environments, Peter Leven and Seth Hutchinson, International Journal of Robotics Research, Volume 21, Issue 12, December 2002.
• Elastic Strips: A Framework for Motion Generation in Human Environments, Oliver Brock and Ossama Khatib, International Journal of Robotics Research, Volume 21, Issue 12, December 2002.