Software Workshop (sadna)

0368-3500-19

Lecture: Wed 16-18, Schreiber 309

Instructor: Dan Halperin

Teaching Assistants: Barak Raveh & Naama Mayer

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

• Link to OOPSMP Installation Instructions (note the patch for Windows users)
• Attachment with the Google SketchUp sample maze from class (including exported XML files that can be used as direct inputs to OOPSMP) 
• Link to Microsoft Robotics web page. The express version can be downloaded from there. The full academic version can be obtained from the system, or from https://www.dreamspark.com/default.aspx for students who are ISIC card holders (international student card). Also:
  • Attachment with the Visual Studio projects for controlling Lego Mindstorms NXT, including a .NET managed wrapper for OOPSMP. These files should only give a feel of how it works, some technical work is needed to make it fully functional
  • Do not miss the tutorials in the documentation of Microsoft Robotics. Also look up the totorial, you make skip the Xbox stuff
• Link to CGAL, boost & QT installation instructions
• The CGAL project demo program—”Polygon path example”
• CGAL website

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

Syllabus

04/03—Introduction to Planning High-Quality Motion Paths
11/03—Sampling-Based Motion Planning (following Chapter 7, Sampling-Based Algorithms in Principles of Robot Motion: Theory, Algorithms, and Implementations)
18/03—Details of Projects [link to ppt presentation part I and part II]
25/03—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 successfully 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 prototype 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.