CSCI-4965/6963: Robot Motion Planning
Fall 2001

Here is a preliminary list of papers that students in CSCI-6963 can select for their class presentations. Depending on the topic selected, the presentation may require you to read one or more papers in the area and summarize them appropriately.

I have copies of most of these papers or you can get them from the library. Please contact me with an indication of the set 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. Here is the current list of assigned presentations .

PRMs and variants:

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
Visibility based probabilistic roadmaps for motion planning, T Simeon, J.-P. Laumond. and C. Nissoux. To appear in Advanced Robotics Journal 14(6) (2000). pdf
Notes on Visibility Roadmaps and Path Planning, by JP Laumond and T. Simeon, Workshop on Algorithmic Foundations of Robotics (WAFR), March 2000. pdf
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 Kinematics-Based Probabilistic Roadmap Method for Closed Chain Systems, Li Han and Nancy M. Amato, to appear in Proceedings of the Workshop on Algorithmic Foundations of Robotics (WAFR'00), March 2000. pdf
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.
Path Planning Using Lazy PRM. R. Bohlin and L.E. Kavraki. IEEE International Conference on Robotics and Automation, San Francisco, April 2000. ps

Sensor-based strategies:

Sensor-Based Exploration: The Hierarchical Generalized Voronoi Graph, Howie Choset and Joel Burdick, The International Journal of Robotics Research 19, no. 2 (2000): 96-125.
Sensor-Based Exploration: Incremental Construction of the Hierarchical Generalized Voronoi Graph, Howie Choset, Sean Walker, Kunnayut Eiamsa-Ard, Joel Burdick, The International Journal of Robotics Research 19, no. 2 (2000): 126-148.
Visibility-Based Pursuit-Evasion in a Polygonal Environment by Leonidas J. Guibas, Jean-Claude Latombe, Steven M. LaValle, David Lin and Rajeev Motwani, International Journal of Computational Geometry and Applications, Vol. 9, No. 5, pages 471,494, October 1999.
An Algorithm for Searching a Polygonal Region with a Flashlight, by Steven M. LaValle, Borislav Simov and Giora Slutzki, 2000 ACM Symposium on Computational Geometry (SoCG).
S.M. LaValle, H. Gonzalez-Banos, C. Becker, and J.C. Latombe. Motion Strategies for Maintaining Visibility of a Moving Target. Proceedings of the IEEE International Conference on Robotics and Automation, 1997.
S.M. LaValle, D. Lin, L.J. Guibas, J.C. Latombe, and R. Motwani. Finding an Unpredictable Target in a Workspace with Obstacles. Proceedings of the IEEE International Conference on Robotics and Automation, 1997.

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

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.

Kinodynamic planning:

Randomized Kinodynamic Planning by Steven M. LaValle and James J. Kuffner, Jr., International Journal of Robotics Research, V. 20, N. 5, pp. 379-400, May 2001.
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.

Multiple robot coordination:

Multiple path coordination for mobile robots: a geometric algorithm, 16th International Joint Conference on Artificial Intelligence (IJCAI'99), S. Leroy, J.-P. Laumond, and T. Simeon, Stockholm, Sweden, pages 1118-1123, August 1999.
B. Aronov, M. de Berg, A.F. van der Stappen, P. Svestka, J. Vleugels. Motion planning for multiple robots. Discrete & Computational Geometry, 22:505-525, 1999

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.
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:

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:

Using Motion Planning to Study Protein Folding Pathways, Guang Song and Nancy M. Amato, Proceedings the 5th International Conference on Computational Molecular Biology (RECOMB), April 2001, pp. 287-296. pdf
A.P. Singh, J.C. Latombe, and D.J. Brutlag. A Motion Planning Approach to Flexible Ligand Binding. Proceedings of the 7th International Conference on Intelligent Systems for Molecular Biology (ISMB), AAAI Press, Menlo Park (CA), pages 252-261, 1999 ps
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

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.

Graphics:

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

Mobile Robot Localization and Mapping:

H.H. Gonzalez-Banos, E. Mao, J.C. Latombe, T.M. Murali, and A. Efrat. Planning Robot Motion Strategies for Efficient Model Construction. Proceedings of International Symposium on Robotics Research, Snowbird (UT), October 1999.

CSCI-4965/6963: Robot Motion Planning Fall 2001