High Quality Motion Planning for Robots (and Other Creatures)
Software Workshop (sadna), Spring 2010 (0368.3500.19)
Teaching Assistants: Barak Raveh, Oren Zalz., Asaf Porat
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 robots, to physical (Lego NXT) robots, or to protein molecules.
Note to bioinformatics students: One of the fascinating applications of motion-planning algorithm is to simulate the motion of protein molecules. The amino-acids of the protein molecules are likened to rigid links, and the protein chain is free to rotate around its backbone torsion angles. Bioinformatics students may take this workshop as their 3rd year workshop. Along the way you will learn about both the state-of-the-art in algorithmic motion planning, and the important relation between protein motion and protein function. More information can be found in this link.
In the beginning of the workshop, we will present you with the basics of algorithmic motion planning in a series of four lectures:
- 24/2/10 - Introduction to Planning High-Quality Motion Paths
- 3/3/10 - Theory of Sampling-Based Motion Planning (i) + List of Suggested Projects
- 10/3/10 - Theory of Sampling-Based Motion Planning (ii)
(following Chapter 7, Sampling-Based Algorithms in Principles of Robot Motion: Theory, Algorithms, and Implementations)
- 17/3/10 - Designing High-Quality Motion Paths ; Review of Technical Programming Details
Course Requirements and Milestones
- The final project will be submitted on the 1st of September, 2010 (details below).
- Teamwork: The project is intended to involve a significant amount of teamwork. 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.
- Course staff: 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.
- Milestones: In order to make sure you successfully complete the project, you will be required to the following milestones:
- 17/3 - Choosing a project:
You will submit a short description of the selected project (title + one or two paragraphs with the basic details)
- 12/4 - Submitting an initial project plan (by e-mail):
An initial description of the project and the work plan (2-3 pages Word document):
b. Description (~100-200 words) of the project's main idea.
c. Brief description of project from a user point of view (input / output, etc.)
d. Algorithmic details.
e. The major programming tasks (engine, user interface, etc.)
f. Milestones towards the final goal.
g. Tools that are going to help you program / run the project (libraries, programming languages, etc.).
h. Open questions, conflicts and so on.
Note: if you are considering two options, you can write more than one option and we can help you decide between those options.
- 26/5 - Project "Proof of Concept" / presentation / submission of final plan
By this time, you 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.). We will give you a small programming task that you will need to accomplish by this time.
In addition, you will present the final project plan in front of the class, and describe the task that you have accomplished. Please prepare to present your project and talk about it for 10-15 minutes.
We will also ask you to submit the final project plan based on the initial plan, but we will expect more detailed solutions (and hopefully, there will be less open questions this time).
- 20/8 - Basic prototype: (date might change, please follow up)
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 final project. The prototype is expected to be a relatively small part of the final project (it is not expected to be fully functional). However, it should give a very good feeling of where you're heading.
- 20/9 - Submission of a final project + presentation:
Submitting a fully functional project, including documented code, a detailed user guide and a developer guide + presenting it to class.
> Presentation (9:00 - 12:00, Schreiber 210) - 15 minutes EXACTLY for each group + 5 minutes time for questions (we have six groups - we will be strict on time). You should give a concise description of the project goals, the algorithm, the project implementation, the GUI and the final outcome. You will need to design a set of problems where your projects succeeds and also show us the places where it fails. Each group should give at least one non-trivial scene where the algorithm works, and one hard scene where the algorithm fails (more scenes are welcome). Please provide explanations as to why you think the algorithm succeeds in each case, and provide ideas for further improvements.
> Developer guide - will include details about the algorithm, the implementation and the code design, to allow a new developer to approach your code.
> User guide - should outline the purpose of your project and its usage in a clear manner.
Project examples from the 2009 workshop
- 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: http://planning.cs.uiuc.edu/