High Quality Motion Planning for Robots (and Other Creatures)
Software Workshop (sadna), Spring 2012 (0368-3500-43)
Teaching Assistants: Oren Salzman, Kiril Solovey
Wed 14-16, Schreiber 08
Code and related files / links:
- CGAL installation guidelines [link]
- Workshop code framework ALPHA (simple GUI, no server) [code] [documentation]
- Programming assignment - CGAL bootcamp [code]
General information: Motion-planning 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. Specifically, the students will utilize a framework, called Motion Planning via Manifold Samples (MMS), where exact geometric tools are combined with a sampling-based approach, to implement a new planner. The workshop will end in a competition between the different teams' planners.
In the beginning of the workshop, we will present you with relevant background material in a series of lectures:
- 7.3 Introduction to Motion Planning
- 14.3 Motion Planning via Manifold Samples and project presentation
[MMS slide] [project description]
- 21.3 Path Quality; CGAL and auxiliary code overview
[path quality slides] [auxiliary material] [more on CGAL]
- Programming abilities: The students are expected to program in C++. Familiarity with the language is preferred but not required.
- Teamwork: The project is intended to involve a significant amount of teamwork. The recommended team size is three.
- 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.
Project examples from the 2011 workshop
Tentative Schedule (stay tuned!)
28.3 Forming teams - You will submit (by email) the group members and a general description (100-200 words) of the project's main idea.
18.4 Planned project presentation (!) - You will have a 15 minutes slot to present the project to us, followed by a discussion. Other students will not see your presentation so do not hesitate to reveal your plans. [more details]
29.4 Submission of final plan. Submit a detailed final project plan (by email), based on the initial plan, but this time we will expect more detailed solutions:
(i) Algorithmic details.
(ii) Milestones towards the final goal.
(iii) Tools that are going to help you program / run the project (libraries, programming languages, etc.).
(iv) Open questions, conflicts and so on.
30.5 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. By this date you will need to decide (and commit to this decision) what prototype you will be presented at the next milestone.
25.7 Prototype and Integration (league interface freeze) (!) At this point in time, we wish 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 (as you committed to). 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. In addition, by this stage we will check that your code can integrate with ours for the league to run smoothly.
2.9 Submission. Submitting a fully functional project, including documented code, a detailed user guide and a developer guide + presenting it to class.
(i) 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 the algorithm and the implementation. You will need to discuss the advantages and disadvantages of your implementation.
(ii) Developer guide - will include details about the algorithm, the implementation and the code design, to allow a new developer to approach your code.
(iii) User guide - should outline the purpose of your project and its usage in a clear manner.
5.9 League (!) Participation required.
- Oren Salzman, Michael Hemmer, Barak Raveh, and Dan Halperin.
Motion Planning via Manifold Samples
In Proceedings of the 19th Annual European Symposium on Algorithms (ESA), pages 493-505, 2011 [link]; arXiv, 2011 [pdf]
- Oren Salzman, Michael Hemmer, and Dan Halperin.
On the Power of Manifold Samples in Exploring Configuration Spaces and the Dimensionality of Narrow Passages
arXiv, 2012 [pdf]
- Barak Raveh, Angela Enosh, and Dan Halperin
A Little More, a Lot Better: Improving Path Quality by a Path Merging Algorithm (H-Graphs)
IEEE Transactions on Robotics, 27(2): 365-371, 2011 [link] ; arXiv [link]
- 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/
- Motion Planning via Manifold Samples http://acg.cs.tau.ac.il/projects/mms/project-page