Introduction: Adaptive Mapping and Navigation With IRobot Create
This tutorial will demonstrate how to do mapping and navigation with the iRobot Create for under $30! And better yet, its designed to be an easy add-on to your already existing robot (butler robot, anyone?).
Why is mapping useful? Have you ever wanted your robot to navigate through your house, by starting in one room and going in to the next, despite unplanned objects in the way? Ever wanted your robot to go to the fridge, navigate around pizza boxes, and then go straight to you before the beer gets hot?
This tutorial has two parts. The first part demonstrates how the Create can track and follow objects (specifically, a can of beer) using a single Sharp IR. Video in step 5.
The second part demonstrates mapping, and how it can update its map when objects get in the way. Its not just reactive wandering, but planned navigation useful for any house based robot. Video in step 6.
Plans and source code to add to your robot will follow.
So what do you need?
Sharp IR $14.50
http://www.acroname.com/robotics/parts/R48-IR12.html
Hitec HS-311 Servo $8.99
http://www.servocity.com/html/hs-311_standard.html
Grid-Style PC Board with 356 Holes $1.79
http://www.radioshack.com/product/index.jsp?productId=2102844&cp
36 position breakaway male header $1.63
http://www.digikey.com/scripts/DkSearch/dksus.dll?Detail?name=WM6436-ND
Stuff you probably have:
wiring
solder with soldering iron
double sided sticky tape
two screws with two matching nuts
screwdriver or allen wrench
holepuncher or hand drill
(local hardware store or Radioshack)
Optional: Dremel to cut down the PC Board
Final Design (simplicity at its best):
Step 1: The Stampy Edge Detection Algorithm
To get my Create to perform some complex tasks without requiring huge amounts of memory or processing power, I decided to implement my Stampy Edge Detection algorithm using a scanning Sharp IR rangefinder.
The concept is simple. A scanning Sharp IR rangefinder does only two things:
If no object is seen, the scanner turns right.
If an object is seen, the scanner turns left.
The image of a googley-eyed robot shows the scanner converging on the edge. The robot will then drive towards the detected edge of any object.
This step is to build the scanner.
Here is video instruction on how:
Required parts are shown below.
Now that you have the scanner built, lets wire it up . . .
Step 2: Wiring Up the Scanning Sensor
Now get some wiring to attach the servo and Sharp IR to the Create robot serial port. Going through my box of scrap wire, I found this. Its just basic serial wiring with attached male and female headers. There are a dozen other ways you can do this.
Then just plug it in to the middle serial port as shown. I included an image from the Create manual showing you the pinouts of the port.
Basically just attach wires to the top four left pins of the middle serial port connector as shown:
Step 3: Make a Power Distribution Board
Now you need to send power to the servo and Sharp IR. The best way to do this is to make a power bus - something that connects all grounds together, all power together, and a pin for each signal wire. The servo and the Sharp IR each have one signal wire.
To make a power bus, I got a piece of PC breadboard and male headers as shown. Then I used a dremel to cut off a small square peice of it, and soldered on the broken down headers with the proper power distribution wiring.
What does that mean? Connect all the grounds (black) to each other, and connect all the power lines (red) to each other. Each signal line (yellow) gets its own serial cable wire.
Then I plugged in everything to the power bus as so. Refer to the pinout in the previous step to make sure where everything plugs in to.
Step 4: Attach Servo to Create
The last hardware step is to attach the servo. You need to have the Sharp IR sensor centrally located, such as that large empty space in the center (its a no-brainer).
I didn't want to drill holes or make a special mount (too much unnecessary effort), so I decided to use extra strength double sided sticky tape (see below image). My only concern about this tape was that I may have difficulties removing the servo in the future . . . (its not a ghetto mount, this stuff really holds).
Step 5: Program Your Create
There are many ways to program your Create. iRobot recommends you using WinAVR (22.8mb) as do I. Install that program. But I perfer to program using the IDE called AVR Studio, version 4.13, build 528 (73.8mb). An optional install.
I wont go into detail in programming the Create because the manual tells you how. But if you are still curious how I did it, here is my write-up on how to program an AVR.
I used AVR Dude (that came with WinAVR) to program the Create. To do this, just open up a command window and do stuff like shown in the below image.
The command is:
avrdude -p atmega168 -P com9 -c stk500 -U flash:w:iRobot.hex
Again, its all in the Create manuals.
Here is my source code for download:
iRobot Create Sharp IR Stampy Edge Finder source code (August 11th, 2007)
After uploading the program, just turn on your robot, push the black button, and off to attacking cute kittens it goes!
Enjoy the beer-seeking robot video:
Could this not be any more entertaining? Probably the first robot capable of seeking out beer . . . Remember, beer is bad for both you and your robot!
Step 6: Adaptive Mapping and Wavefront Algorithm
We are going to do something much more advanced called the Wavefront algorithm.
Upload this code to your Create:
iRobot_Create_wave_front.zip September 9th, 2007
The wavefront basically discretizes the surroundings and records locations of objects. The attached image of my kitchen is a good visualization of it.
In the source code look for a matrix called 'map'. Using the map, redefine the goal location, robot location, and object locations as you like. Dont worry too much about the objects however, the robot will scan and update the map for you.
Enjoy the unedited final video!
Yes, I realize I have a lot of cereal boxes . . . I have more actually . . . I like cereal =)
Now what if you want to add this algorithm to YOUR robot as an addition? Simple, add this line in your code:
#include "wave_front.c"//put this at the top
And then put this in your main() code:
direction_to_move = propagate_wavefront(robot_x,robot_y,goal_x,goal_y);
//input location of robot and desired goal
Just tell it where your robot is, and it will tell your robot where to move (1=north, 3=south, 2=east, or 4=west). Dont forget to define start and goal location in the wave_front.c file!
To update the map, just call the function find_walls(); and it will automatically do all the hard work for you.
With only slight modification, the highly commented code is designed to work on any robot chassis with any sensor, not just the Create! In the map, by default the robot starts at the bottom and the goal is at the top (as in the video).
Step 7: Conclusion, Extra Info
My goal of this project was not to make something amazingly cool, but instead something extremely cheap, easy, and useful to add to someone elses robot - basically a feature that enhances (or is required) for any other robot.
This meant under $30, minimal hardware construction, and source code that does not require understanding to make use of it. It doesnt even matter what sensors you use, so if you have say sonar on your delivery/butler robot, now your robot can remember where its been and figure out where its going!
Remember, this isnt pure reactive mapping:
it knows where it is
it knows where it has been
it knows where it is going
it knows the locations of moving obstacles
it optimizes for minimal travel distance
AND it cannot be tricked! Its adaptive!
Note: The algorithm had to be extremely robust to cluttered home environments (any random obstacle can be detected). My algorithm is capable of having the robot wander 5x faster, but I decided to keep it slow because the Create's encoders have high error rates. The encoders are driven by a flexible rubber belt, so useless . . . haha . . .
And remember, the most useful feature is that the map updates. No need to reprogram your robot if you rearrange furniture!
Note: Below is an example of the wavefront algorithm, with the robot R counting down to the goal G. Theory is out of scope of an instructable, but if you want to understand more, please check out my tutorial on the Wave Front.
Note: The goal location can be easily changed for your robot - for example if you say 'get me a beer' to your butler robot, all it would need to do is look up the location of the beer in its memory and it will automatically plan that path for you.
Note: The demo map is only 6 x 6 squares, with each square the size of the robot. The algorithm can be easily be modified to accomodate much larger maps (such as below), as the current map takes a fraction of a second to calculate.
Step 8: Optional: Wavefront Simulation
This step is entirely optional, just noted to help you out with planning your own maps.
So here goes on robot simulation . . .
It can be quite time consuming to test out robot navigation algorithms on the actual robot. It takes forever to tweak the program, compile, upload to robot, set up robot, turn it on, watch it run, then figure out why it failed . . . the list goes on.
Instead, it is much easier to do this debugging with simulation. You write the program, compile, then run it locally. You get an instant output of results to view.
The disadvantage to simulation is that its really hard to simulate the environment as well as get the robot physics perfect, but for most applications simulation is best to work out all the big bugs in your algorithm.
This is a simulation I did showing a robot doing a wavefront, moving to the next location, then doing another wavefront update. For a robot (R) moving through terrain with moving objects (W), the robot must recalculate the wavefront after each move towards the goal (G). I didnt implement the adaptive mapping in simulation, just the wavefront and robot movement.
If you want to see the entire simulation, check out the simulation results.txt.
You can also download a copy of my wave front simulation software and source. I compiled the software using Bloodshed Dev-C++. If you want, you may also try a different C language compiler.
This is an example of the simulated output:
