Personal tools
You are here: Home Courses Workshop Fall 2014
« January 2023 »
Log in

Forgot your password?

High Quality Motion Planning for Robots (and Other Creatures)

Software Workshop (sadna), Autumn 2013-2014 (0368-3500-43)

Instructor:  Dan Halperin

Teaching Assistants: Kiril Solovey, Oren Salzman
Assistance with CGAL: Efi Fogel 
Assistance with robots and cameras: Zim Ramati, Tom Shachar

Wed 14-16, Kaplun 324

General information: The aim of this workshop is to design, implement, and execute a system of a self-assembling puzzle. In particular, given a disassembled puzzle that consists of several pieces which are mounted on several pololu robots your task is to assemble the puzzle by moving the robots while avoiding collision between the robots and obstacles placed in the environment. The project consists of designing an algorithm, implementing a simulator, and executing the solution on real-life robots.

More details: The input of the problem consists of a description of polygonal puzzle pieces placed in some initial positions and an image of the assembled puzzle. The goal is to construct a series of movements of the robots that brings all the pieces to the target position.   As the task of assembly can be extremely challenging in some situations we impose that following restrictions to our puzzle:

  • Puzzle can be assembled using two hands.
  • Only one piece moves at a time. 
  • Puzzle can be assembled in a monotone manner: there is a sequence of solution movements where each piece moves at most once.


In the beginning of the workshop, we will present you with relevant background material in a series of lectures:

  • Project presentation
  • Introduction to motion planning, sampling-based motion planning and the MMS algorithm [slides]
  • CGAL and auxiliary code overview

Course Requirements 

  • Programming abilities: The students are expected to program in C++. Familiarity with the language is an advantage but not required.
  • Teamwork: The project is intended to involve a significant amount of teamwork. Based on our experience over the years, the recommended team size is six students, where three students will be working on the simulation and the rest on the physical robots.
  • 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

  • Robot-boat racing: Roboat
  • Motion-planning in dynamic environments: MaBaker
Project examples from the 2012 workshop

Tentative Schedule (stay tuned!)

The project will proceed according to the following milestones:

23.10 Forming teams - You will submit (by email) a list of the group's members, a group name, and the roles of the participants (simulation/physical robots/integration).
27.11 Planned project presentation - You will have a 15 minutes slot to present the project to us in class, followed by a discussion.

4.12 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.

1.1 Project "Proof of Concept'' By this time, you will be required to show that the basic technical infrastructure of the project works.
  • The robot groups are required to be able to solve a simple puzzle that consists of two polygonal parts (which they will construct either from cardboard or by 3D printing). They should design the puzzle by specifying the start and target positions and send a query, that describes the problem, to the simulation group, which will return a solution to the problem. Then, the robot groups should be able to execute the solution. 
  • The simulation group should be able to execute a simple assembly problem that consists of two parts, and produce smooth paths. Additionally, they should be able to cope with scenarios that involve several more robots.
  • Each group should choose a coordinator that will interact with the robot/simulation group. All groups should decide on a unified standard for communication, e.g., how should a path or scenario be represented. 
  • Additionally, every group is required to present in the meeting a document that describes the tasks they are planning to complete for the prototype meeting.
27.2 Prototype 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.

30.4 Submission. Submitting a fully functional project, including documented code, a detailed user guide and a developer guide .
(i) Developer guide - will include details about the algorithm, the implementation and the code design, to allow a new developer to approach your code.
(ii) User guide - should outline the purpose of your project and its usage in a clear manner.

7.5 16:00 at Schreiber 309 Presentation Participation required.
The presentation will be public and will not be restricted to the participants of the workshop.
You should give a concise description of the methods. You will need to discuss the advantages and disadvantages of your implementation.

Simulation Section

CGAL warm-up: Download the C++ code and fill the blanks. You may need to generate a VSe solution to test your result. Don't forget to set the correct paths, according to the CGAL installation guide (QT paths are not required in this specific exercise). [code]

Robot Section

This year's physical-robot projects will be based on Pololu 3pi robots, groups will be given up to 5 robots in 1-2 robots increments.


  1. python2.7
  2. robo3pi a python library for controlling robots.
    1. a newer version which also introduces the method 'rotate' for servo movement can be found here.
  3. FTDI drivers for the USB dongle
    1. if you have problems with installing theses drivers try the Arduino IDE, which has a drivers library with full support.

3pi control

Added here is a python library to control your 3pi robots using serial wireless dongle (zigbee/bluetooth/UHF).

Unlike the first stage this gives you direct control over the robot allowing movement by selecting a speed for each wheel - now the timing factor is on you! make sure your robot is burned with the code for this kind of movement (displaying "Sadna  2.1" or greater on startup).

the speed can be any number x as long as -256<x<256 (notice the no '='). 255 is 1m/s in either direction so calculate your timing.

example of use:

import robo3pi as s

import time

s.init('com11') # this is the com the xbee dongle identified itself on my computer.

s.move('1', 255, -117)


s.addToGroup('1', 'G')

s.addToGroup('2', 'G')

s.stop('G') # ok so robot #2 never started moving but this will control all the group.

Note that you should give the robot time between one command and the next to process.


Camera Tracker

Please download the tracker here.

The program will allow you to send the location of each polygon using UDP methods. and a written CSV log for debugging purposes.

THIS is a link to the instructions video showed at the beginning of the workshop.

3D Printing

Among other tasks, you will need to produce the puzzle pieces (subassemblies) either from cardboard or from plastic.

Recently, we have purchased a dual-head 3D printer from Something3D, a local company that manufactures 3D printers.
The printer is located in the ACG lab (Schreiber basement M-18).

The printer supports three types of filaments:

  1. ABS
  2. PLA
  3. PVA is water soluble best used for support material, and probably not needed for this project.
Currently, the ABS filament is mounted on the the first nozzle. (We haven't even ordered PVA yet).

If you decide to 3D-print the puzzle pieces (which is recommended), you will need to create digital models of the puzzle pieces to start with. A comprehensive list of modeling software tools can be found here. If you don't have a preferable modeling tool, we recommend Sketchup Make.

Once you have a model, you will need to generate the "program" that consists of instructions to print it. Our 3D-printer (like most 3D printers) accepts programs written in G-Code. A G-Code program can be fed directly to the printer from a flash memory card.  The printer in the lab is also mounted on a computer. We have installed Repetier and Slic3r on this computer. These software tools are freewares, so you can install them on your private computer and use them to generate the necessary G-Code programs. You can come to the lab with the G-Code programs and a memory flash, and start a print job right away. Alternatively, you can come to the lab with the digital models, and use the computer, the printer is mounted on, to generate the G-Code programs, and then start a print job.

We don't have much experience with the this new printer (or with any 3D-printer for that matter), but we will be happy to assist you as much as possible.
The website of Something3D contains a complete user manual of the printer.
Please, coordinate with us before you start your first print job.

Visit the 3D printing page for more information.

Reading Material

  • 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]

Additional 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:


Document Actions