Department of Computer Science
College of Arts and Sciences
The University of North Carolina at Chapel Hill
COMP 790-058: Motion Planning in Real and Virtual Worlds
- Time and Place: MW 11:00-12:15pm, Room: 115
- Prerequisites: Undergraduate Algorithms Course, Some Background in Geometry OR Instructor's approval
- Textbook: Course Notes and In-Class Handouts
- Reference Book LaValle's Book on Planning Algorithms
COURSE OVERVIEW: Motion is ubiquitous in both the real world and synthetic environments. Representations of motion are central to all computational disciplines that deal with modeling dynamical or kinematic systems in the biological, physical or virtual world. For example, interaction with objects in the virtual environment, design and assembly of electronic appliances, animation of articulated figures, manipulation of nano-structures, modeling of tissues and muscles, etc. Recently, motion planning techniques are also used in computer games and virtual worlds like Second Life to control the motion of the avatar. With the recent advent of consumer robots like the Roomba and development of autonomous ground vehicles (e.g. DARPA Grand Challenge), there is more interest in development in motion and path planning algorithms. In this seminar course, we will study recent advances in motion planning including but not limited to:
The course will consist of lectures by the instructors on the fundamental concepts in the areas, student lectures on selected topics of interests, and special guest lectures on recent research or work in progress. The goal of this class is to get students an appreciation of computational methods for motion planning and synthesis. We will discuss various considerations and tradeoffs used in designing various methodologies (e.g. time, space, robustness, and generality). This will include data structures, algorithms, computational methods, their complexity and implementation. Depending on the interests of the students, we may cover topics of interests in related areas. We also plan to use Second Life as a driving application to implement motion planning algorithms.
- Path Planning for Autonomous Agents
- Sensor-based Planning, Localization, and Mapping
- Navigation in Complex Virtual Environments
- Motion Planning with Dynamic Constraints
- Motion Planning of Deformable Bodies
- Collision Detection
- Motion Planning of Characters in Virtual Worlds
Here is a list of lecture topics (subject to change). Schedule and information on each topic (e.g. readings, web pointers) will be added during the semester before each class.
- Introduction Slides (August 22, 2007) , Second Life Slides (August 22, 2007) ,
- Path Planning for Point Robots (August 27, 2007) Slides; Chapter 2 in Lavalle's Book
- Configuration Space (August 29, 2007)
- Configuration space (Sep. 05, 2007)
- Probabilistic Roadmap Methods (Sep. 10, 12 & 17)
- Student Project Presentations (Sep. 19)
- Introduction to Second Life (Sep. 24, Russ Gayle): (Slides)
- Penetration Depth Computation & Applications (Sep. 26, 2007, Liangjun Zhang)
- Bots and Motion Planning in Second Life (Russ Gayle, October 01, 2007)
- Motion Capture (Tao Yu, October 03, 2007) Slides;
- Human Motion (Sachin Patil, October 08, 2007) Slides;
- Visibility based Motion Planning (Georgi Tsankov , October 10, 2007) Slides;
- Coverage Planning (Jamie Snape, October 15, 2007) Slides;
- Machine Learning and Motion Planning (David Millman October 17, 2007) Slides;
- Crowd Behavior and Traffic Patterns (Nick Dragan, October 22, 2007) Slides;
- Sound-based Techniques for Navigation (Josh Markwordt, October 24, 2007) Slides;
- Motion Planning in Surgical Simulation (Mert Sedef , October 29, 2007) Slides;
- Collision Detection between Deformable Models (Sean Curtis , October 31, 2007)
- Motion Planning in Dynamic Environments (Jur van den Berg, lectures on Nov. 05 and 07) Slides ;
- Kineodynamic Planning (Jur van den Berg, lecture on Nov. 12) Slides ;
- Local Dynamics Models for Crowd Simulation (Yero Yeh, Nov. 14) Slides;
- Swarm Intelligence and Amorphous Computing (Sang Woo Lee, Nov. 19) Slides;
- Motion Planning between deformable models (William Moss, Nov. 26)
- Assembly Maintainability with Motion Planning (Xin Huang, Nov. 28)
- Multi-Robot: Search and Rescue (Joohwi Lee, Dec. 03
ASSIGNMENTS AND PROJECTS The class grade of each student is determined by
STUDENT COURSE PROJECTS
STUDENT PROJECTS (FALL 2007)
PAST STUDENT PROJECTS (FALL 2005)
COURSE READING MATERIALS
Reference Papers Used in Lectures:
DARPA Grand Challenge
Motion Planning Research at UNCThe GAMMA group at UNC has implemented several distinct motion planning systems:
GEOMETRIC ALGORITHMS AND SOFTWARES AVAILABLE ON THE WEB: Here are just some possible locations to find geometric software/libraries and algorithmic toolkits you may need:
ADDITIONAL REFERENCE MATERIALS
Reference Books in Robotics:
- Robot Motion Planning, by Jean-Claude Latombe, Kluwer Academic Publishers, 1991.
- Robot Manipulators: Mathematics, Programming, and Control, by R. P. Paul, MIT Press, 1981.
- Principles of Robot Motion : Theory, Algorithms, and Implementations , by Howie Choset, Kevin M. Lynch, Seth Hutchinson, George Kantor, Wolfram Burgard, Lydia E. Kavraki, and Sebastian Thrun.
Reference Books in Computer Animation:
- Making Them Move: Mechanics, Control and Animation of Articulated Figures, by Badler, Barsky and Zelter, Morgan Kaufmann Publishers, 1991.
- Advanced Animation and Rendering Techniques: Theory and Practice, by A. Watt and M. Watt, 1992.
- Computer Animation: Algorithms and Techniques, by Rick Parent, 1999.
Reference Books in Geometry:
- Computational Geometry (Algorithms and Applications), by de Berg, van Kreveld, Overmars and Schwarzkofp, Springer-Verlag, 1997.
- Computational Geometry In C (Second Edition), by O'Rourke, Cambridge University Press, 1998.
- Handbook on Discrete and Computational Geometry, by Goodman and O'Rourke (eds), CRC Press LLC, 1997.
- Applied Computational Geometry: Toward Geometric Engineering, by Lin and Manocha (eds), Springer-Verlag, 1996.
- Algorithms in Combinatorial Geometry, by Edelsbrunner, Springer-Verlag, 1987.
- Computational Geometry (An Introduction), by Preparata and Shamos, Springer-Verlag, 1985.
Reference Books in Mechanics:
- Concepts and Applications of Finite Element Analysis, by R. D. Cook, D. S. Malkus and M. E. Plesha, John Wiley & Sons, 1989.
- Finite Element Procedures, by K.-J. Bathe, Prentice Hall, 1996.
- First Course in Continuum Mechanics, by Y.C. Fung, Prentice Hall, 1993.
Reference Books in Numerical Methods:
For more information, contact Dinesh Manocha, firstname.lastname@example.org,
Copyright 2007. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the author.
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.