Software Workshop (sadna), Spring 2013 (0368-3500-43)

Instructor: Dan Halperin

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.

Link to Sadna 2009

Link to Sadna 2010

Link to Sadna 2011

Link to Sadna 2012

Syllabus

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

• Introduction to Motion Planning
  [slides]
• 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]

Course Requirements

• 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 2009 workshop

1. Non holonomic motion planner

2. Motion planning for a Lego-NXT robot

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

  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
  • Motion Planning via Manifold Samples
    

    Robot Section

    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:
    1. r – turn right
    2. l – turn left.
    3. f<#> f plus number 1 to nine makes it move a # patches.
    4. b<#> same but reverse (towards the blue lights)
    5. 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:
    import serial
    ser = serial.Serial(‘COM9’,57600)

    ser.write(“f3”)

    ser.write(“a00z”) #this zero is not a zero speed but the ASCII zero meaning 48, z is 122.

    ser.write(“a”)

    ser.write(255)

    ser.write(113)

    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:

1. http://www.pololu.com/docs/0J51
2. http://www.pololu.com/docs/0J20

Good luck.

Lab guide: Ziv Ramati – [email protected]

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)
time.sleep(0.4)
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.