High Quality Motion Planning for Robots (and Other Creatures)
Software Workshop (sadna), Spring 2013 (0368-3500-43)
Teaching Assistants: Oren Salzman
Wed 14-16, Schreiber 08
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:
- Introduction to Motion Planning
- Motion Planning via Manifold Samples and project presentation
[MMS slide] [project description]
- 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!)
20.3 Forming teams - You will submit (by email) the group members, a group name and a general description (100-200 words) of the project's main idea.
24.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.
29.5 Project "Proof of Concept'' By this time, you will be required to show (presentation in the lab) 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.
24.7 Prototype and Integration (league interface freeze) At this point in time, we wish to see (presentation in the lab) 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.
28.8 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.
8.9 League + Presentation Participation required.
This year projects will be based on Pololu 3pi robots, groups will be given up to 5 robots in 1-2 robots increments.
in order to control the robots all you have to do is use a serial communication protocol through the usb dongle we will provide. for the first step you can use the Arduino serial monitor.
- Arduino program download: http://arduino.cc/en/Main/Software
- note that the arduino software comes with the drivers to operate the modem, but if you are using windows 8 or a unix/mac system you might need to download FTDI drivers on your own -http://www.ftdichip.com/FTDrivers.htm.
- Once you have the software ready (just unzipping it) select the proper COM port under tools and than start the "Serial Monitor" this little terminal allows you to transmit chars to your robots for controls.
- make sure to change the serial communication speed to 57600.
- for starting phase you only get 4 char commands, more than that and robot will not behave as expected the list of commands is:
- r - turn right
- l - turn left.
- f<#> f plus number 1 to nine makes it move a # patches.
- b<#> same but reverse (towards the blue lights)
- a <char> <char> <char> - sets speed to left right and delay. allows for specific control.
- meaning you can have the robot do 4 consecutive right turns by sending "rrrr" or going forward and backwards by sending "f8b3" but a command of "rrllf9" will not carry the forward part.
- the a for arch allows you to control each motor individually (left, right). the last char is for duration of movement. you can read exact numbers at:http://www.asciitable.com/ the delay is in miliseconds - and in that time the robot will not perform other actions.
an example of how to communicate with the robot using python with the pyserial module:
ser = serial.Serial('COM9',57600)
ser.write("a00z") #this zero is not a zero speed but the ASCII zero meaning 48, z is 122.
ser.write(100) # these 4 commands will also initiate a proper sequence.
at the first stage each group will get one robot fully equipped an XBEE modem with a USB and these commands settings. later during the workshop you will get further commands to allow for grouping the robots or receiving other information from them.
- those who want to program the robots themselves for personal fittings are welcomed to do so - the robots can be programed using C/C++ Tom and I will be able to help - programming guides:
Lab guide: Ziv Ramati - firstname.lastname@example.org
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
s.init('com11') # this is the com the xbee dongle identified itself on my computer.
s.move('1', 255, -117)
s.stop('G') # ok so robot #2 never started moving but this will control all the group.
readme file is attached to the installation pack and has a list of commands.
- 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