Personal tools
You are here: Home Courses Workshop Spring 2009 High-Quality Motion Paths for Robots (and Other Creatures)
« November 2022 »
Log in

Forgot your password?

High-Quality Motion Paths for Robots (and Other Creatures)

Software Workshop (sadna), Spring 2009 (0368.3500.19)

Instructur: Dan Halperin

Teaching Assistants: Barak Raveh & Naama Mayer

Wed 16-18, Schreiber 309

General Information: Motion-planing algorithms compute collision-free motion paths for objects that move among obstacles.  They arise in robotics, graphical animation, surgical planning, navigation systems, computational biology and computer games, among other domains. In this workshop we will explore and apply algorithms for planning high-quality motion paths. The quality of a motion path may be measured by the path length, smoothness, clearance from obstacles or even its physical energy. The students will apply motion-planning techniques to virtual or physical robots.

Project Examples

1. Non holonomic motion planner 

2. Robot motion planning

Useful Resources

Reading Material 
  • Chapter 7: Sampling-Based Algorithms in Principles of Robot Motion: Theory, Algorithms, and Implementations
    H. Choset, K.M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L.E. Kavraki, and S. Thrun, The MIT Press, 2005.
  • Chapter 5: Sampling-Based Motion Planning in Planning Algorithms,
    S.M. LaValle, Cambridge University Press, 2006
    Web version:


4/3 - Introduction to Planning High-Quality Motion Paths

11/3 - Sampling-Based Motion Planning (following Chapter 7, Sampling-Based Algorithms in Principles of Robot Motion: Theory, Algorithms, and Implementations)

18/3 - Details of Projects [link to ppt presentation part I and part II]

25/3 - Improving the Quality of Motion Paths [link]

List of Possible Projects

  • Planning high-quality motion path in virtual environments using Google Sketchup
  • Planning high-quality motion paths with a Lego Mindstorms NXT robot
  • Coordinating high-precision motion for multiple polygon robots in 2D.

 Course Requirements & Grading

  • In the beginning of the workshop, we will present you with the basics of algorithmic motion planning in a series of three lectures.
  • The recommended team size is three. Each group will choose a project among the list of projects, and submit the final project later in the summer - see dates below.
  • Except for doing the project for you, we are here to help you with any question. Please do not hesitate to contact the course's team.
  • In order to make sure you succesfully complete the project, you will be required to the following milestones:
      • By April 1st, 2009 - Submitting an initial plan by e-mail:
        An initial description of the project and the workplan (2-3 pages Word document):
        1. Title
        2. Description (~100-200 words) of the project's main idea.
        3. Brief description of project from a user point of view (input / output, etc.)
        4. Algorithmic details.
        5. The major programming tasks (engine, user interface, etc.) 
        6. Milestones towards the final goal. 
        7. Tools that are going to help you program / run the project (libraries, programming languages, etc.).
        8. Open questions, conflicts and so on.
        If you are considering a few ideas , you can write more than one option and we can help you decide between those options.
      • By May 6th, 2009 - Presenting the project plan:
        On May 6th we will hold a class meeting at the usual time (16:10 -- 18:00). In that meeting you are expected to give a detailed presentation of your project plan in front of the class. Please prepare to present your project and talk about it for 10-15 minutes. In addition, by this time you will need to prepare a written document describing the final plan (3-4 pages). It should include the same subjects as the initial plan (more or less, we hope that there will be less open questions), but we expect more detailed solutions.
      • By June 3rd, 2009 -  Testing the project basic infrastructure:
        The students will be required to show that the basic technical infrastructure of the project works (e.g. tools or programming libraries that need to be installed, etc.).
      • By July 24th, 2009 - Basic prototype:
        At this point in time, we will want to see your initial development, in order to make sure you are working in the right direction. You will show us a basic prototype of the project. The prototpe is not expected to be fully functional, but it should give a very good feeling of where you're heading.
      • August 28th, 2009 - Submission of a final project:
        Submitting a fully functional project, including documented code, a detailed user guide and a developer guide. You will present the project to all students of the workshop. Your project will be tested against a set of problems we will design in advance. We will provide more details in the description of each project, to appear soon. 


Document Actions