High Quality Motion Planning for Robots (and Other Creatures)
Software Workshop (sadna), Spring 2011 (0368-3500-43)
Teaching Assistants: Barak Raveh, Kiril Solovey
Wed 14-16, Schreiber 08
One of the proposed projects is in robot-boat racing, with the goal of competing in an international boat race in Germany.
The team for the robot-boat project has been selected , we thank all students who have showed their enthusiasm to take part in this project.
General information: Motion-planing algorithms compute collision-free motion paths for objects that move among obstacles. They arise in robotics, graphical animation, computer-aided surgery, 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 the physical energy of the moving system. The students will apply motion-planning techniques to virtual robots or to physical (Lego NXT) robots.
In the beginning of the workshop, we will present you with relevant backgroun material in a series of four lectures:
- 23/2/11 - Introduction to Planning High-Quality Motion Paths + List of suggested projects
- 2/3/11 - Multi-robot motion planning - two variants
Two discs hybrid planner [pdf]
Sequential plans [pdf]
- 10/3/10 -
A brief introduction to control of dynamic systems by Dr. Gabor Kosa [A quick intro to control from Wikipedia]
Planning High-Quality Motion Paths by Path Hybridization [pdf]
- 17/3/10 - Sampling-based motion planning and issues in path quality [ppt - password motion]
List of projects
Relevant information on projects (2),(3) can be found in the "Syllabus" section above.
1) Planning the motion of a (physical) Lego-NXT robot, using sensors feedback to control the robot motion.
2) Planning the motion of a large number of discs in the plane.
3) Planning the motion of a small number (2-4) of discs in the plane, but using numerically exact computations.
4) Project of your choice, as long as you consult with us, and conditioned on our approval.
* robot-boat project - the registration for this project is closed.
Course Requirements and Milestones
- The final project will be submitted on the 1st of September, 2011 (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:
- 23/3 - Choosing a project:
You will submit a short description of the selected project (title + one or two paragraphs with the basic details)
- 6/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.
- 27/4 at 14:10 – presentation
You will present the final project plan in front of the class. Please prepare to present your project and talk about it for 10-15 minutes. The talk is aimed for both the students and the teachers, so include appropriate background. Prepare in advance and practice to ensure good flow.
- 4/5 - submission of final plan
Submit a detailed final project plan, based on the initial plan, but this time we will expect more detailed solutions (and hopefully, there will be less open questions this time).
- 1/6 - Project "Proof of Concept"
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.
- 27/7 - 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.
31/8 - 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 - 15 minutes EXACTLY for each group + 5 minutes time for questions (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 desirable and expected). 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/