Algorithmic Robotics 2007, Final project

Below you'll find a list of topics for possible final projects. You have a lot of freedom in choosing a project and you are encouraged to suggest your own topic. You may also propose variations on the themes below.

By February 5th 2007, you have to submit a brief (up to one page) proposal for approval by the instructor. The submission date of the final project is March 15th 2007 . (For every day of delay you will be fined 3 points out of 100.) Notice that in addition to submitting the project to Ophir Setter you need to fix a meeting for an oral exam with me (D.H.) (on the project and the course). The exams will be held before the end of March. It is your responsibility to schedule the time for the exam.

If you need your grade earlier, or just wish to finish with the course duties earlier, let me know when you hand in your project proposal.

Every project should include an implementation with (possibly very simple) graphic output, and accompanying text explaining the problem, the solution, and the implementation.

Do not undertake big projects. In particular you may propose partial solutions to the projects proposed here---the part you plan to solve however should be clearly stated in the brief proposal document. It's better that you'll opt for a smaller project and do it thoroughly including extensive experimentation, careful testing, comparison with other solutions experimentally and theoretically (where applicable).

Good luck!

Project topics

The blue bullets designate projects that can be based on MPK (Motion Planning Toolkit) by Mitul Saha from Stanford. Click here for the webpage established by Ophir for that. The planning algorithm implemented in MPK is the so-called SBL algorithm: Single query, Bi-directional, Lazy collision-checking planner.

 Implement RRT in the same environment, and compare the performance of the two planners on several input instances.

 The current planner in MPK cannot solve the "dancing spider arms" problem packed in spider.tar.gz (see the webpage by Ophir). Devise a planner that can solve this and/or related problems. (The "and" refers to the fact that the planner should not be too specifically tailored for this one special instance. The "or" is for the case you find this specific input instance too difficult.)

 Improve the performance of SBL. For example by improving the sampling or connection strategies. Demonstrate the improvement on several input instances.

 Solve the partition problem for a collection of polygons in the plane under infinitesimal translation and rotation.

 Devise an interactive robot game (see for example:, possibly (but not necessarily) for a two-link planar arm. In your program the user should be able to build her/his own polygonal obstacles, and upon request the program should present a solution when one exists.

 (difficult) Devise an interactive robot game for a three-link arm in the plane.

 Implement an exact version of the robot localization algorithm by Detweiler et al (see details in the class of 27.11.2006.)

 /  Devise a planner for the coordinated motion of two polygons moving among polygons in the plane. You can solve it using a sampling-based planner. It becomes more challenging if you do it partly exact; see the paper: S. Hirsch and D. Halperin
Hybrid motion planning: Coordinating two discs moving among polygonal obstacles in the plane
Proc. 5th Workshop on Algorithmic Foundations of Robotics (WAFR), Nice, 2002, 225-241.

 Write a program to solve the puzzle "Gordian's knot" (and similar puzzles). Click here for the webpage established by Efi Fogel ( for that.