Department of Computer Science
Korea Advanced Institute of Science and Technology (KAIST)

CS780: Topics in Computer Graphics (Fall 2009) <br> Motion Planning and Applications(Fall 2009)

CS780: Topics in Computer Graphics (Fall 2009)
Motion Planning and Applications

Instructor: Sung-eui Yoon

When and where: 10:30-11:45pm on Tues. and Thur. at Room 4448 in the CS building
First class: Sep-3 (Thur.) (please come to first class for more information)
Please refer to the first lecture slide for other course information
Textbook: Planning Algorithms, Steven M. LaValle, 2006 (online version is available)



  • Course overview
  • Lectures and tentative schedule
  • Student presentations
  • Additional reference materials
  • Line

    Course overview

    A robot in a complex 3D CAD model (a power plant model)

    It is expected that robots with some sort of intelligence will be a part of our lives in future. Many challenges are ahead of us to realize robots to be a part of our lives. In this course, we will consider issues of motion planning of real and virtual robots for various applications. We will focus more on virtual robots and their applications in games, movies, virtual prototyping, crowd simulations. We will go over basic materials related to motion planning and their applications.

    What you will get at the end of the course:

  • Broad understanding on various motion planning methods
  • In-depth knowledge on recent methods related to motion planning
  • What you will do:

  • Choose and present a few papers from a paper list
  • Final project: come up with your own idea related to the topic, (optionally) implement it to improve the state-of-the-art techniques, and write a final report
  • Mid-term exam: reviewing basic motion planning methods
  • Line

    Lecture schedule (subject to change)

    # of lecture, date Topics and slides Related material(s)
    1, Sep - 3 (Th) Overview on the course and course policy
    2, Sep - 8 (T)
    3, Sep - 10 (Th)
    Motion planning for point robots
    4, Sep - 15 (T)
    5, Sep -17 (Th)
    6, Sep - 22 (T)
    C-Space: Part I
    7, Sep - 24 (Th) C-Space: Part II
    8, Sep - 29 (T)
    9, Oct - 1 (Th)
    Proximity queries
    Oct - 6 (T)
    Oct - 8 (Th)
    Oct - 13 (T)
    Oct - 15 (Th)
    No class due to conf. attendance
    10, Oct - 20 (T)
    Probabilistic Roadmaps
    Oct - 22 (Th) Mid-term period (No mid-term exam
    Oct - 27 (T) TJKim 1
    Oct - 29 (Th) Invited talk:
    Coping with non-penetration constraints in Graphics, Robotics, and CAD, by Prof. Young J. Kim
    Nov - 3 (T) Student presentation 2 (TJKim), 3 (Bochang)
    Nov - 5 (Th) Mid project presentations (Lunch will be provided)
    Nov - 10 (T) Invited talk
    Robotics and motion planning at Samsung
    Nov - 12 (Th) Student presentation 4 (Bochang), 5 (JiEun)
    Nov - 17 (T) Student presentation 6 (KunHo) , 9 (DongHun)
    Nov - 19 (Th) Student presentation 8 (JDChoi), 10 (JiEun)
    Nov - 24 (T) Student presentation 11 (DongHun), 12 (Duksu), 7 (KunHo)
    Nov - 26 (Th) Student presentation 13 (JongYun) , 15 (beibei)
    Dec - 1 (T) Student presentation 14 (JongYun), 16 (JaePil)
    Dec - 3 (Th) Student presentation 17 (JDChoi), 18 (JaePil)
    Dec - 8 (T) Student presentation 19 (Beibei), 20 (Duksu)
    Dec - 10 (Th) Final project presentations (Lunch will be provided)

    Student presentations and reports

    For your presentations, please use the this powerpoint template.

    For your final report, please use the this latex template


    Additional reference materials and links

    Public software:

    The OOPSMP Motion Planning Library from the Kavraki Lab at Rice University

    Possible project topics from Prof. Latombe's class

    Links to websites of some well-known researchers in motion planning

    Paper search:

  • Google scholar
  • Tim Rowley's graphics paper collections
  • Ke-Sen Huang's graphics paper collections
  • Line

    Acknowledgements: The course materials are based on those of Prof. Dinesh Manocha (UNC-Chapel Hill) and Prof. David Hsu (NUS). Thank you so much! Line

    Copyright 2009. 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.