Building a Mapping Robot

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
niko7865
Posts: 536
Joined: Sun Jan 21, 2007 11:47 am UTC
Location: All over washington state, USA
Contact:

Building a Mapping Robot

Postby niko7865 » Wed May 28, 2008 6:35 am UTC

I'm living by myself for the summer and decided I needed to come up with something to keep myself busy, so I've decided to build a mapping robot. I have a bit of experience with programming simple circuits and programs so I'm hoping this won't be too complicated.

I plan on using a Digilent Nexys with a Xilinx Sparten 3 FPGA to control everything (has 16MB of on board flash I think). 3 wheels, two controllable, one swivel, and a simple bump sensor on the front.

As for the mapping, I was thinking just a large array (maybe 500x500 which will easily get my apartment down to 6inch resolution), each 'point' in the array will correspond to 6 inches (determined by wheel spin time) of travel in either the up or down direction. A simple bump sensor on the front will add a dot to the empty array in the corresponding point of half-second steps away from origin.

Anyway sound like a good idea so far, anything I should probably change?
21/m/athletic/white&nerdy/washington/straight/???
Image

User avatar
und3rdark
Posts: 27
Joined: Mon Jan 14, 2008 7:25 pm UTC
Location: Canton, Michigan

Re: Building a Mapping Robot

Postby und3rdark » Thu May 29, 2008 1:40 pm UTC

I would say you should add an encoder to the non-powered wheel and also add a gyroscope:

The encoder will allow you measure the actual distance traveled, so you don't count "steps" that were taken with the powered wheel spinning faster than the robots actual movement (slipping).

The gyroscope will allow you accurately measure (with some calibration) your turn speed, allowing you to keep track of the robot's heading.

These are just my recommendations, it is possible to get fairly accurate results without these, but these sensors (if used correctly) will improve the chance of getting meaningful data from the robot.
"The impulse to discriminate is a feature of our brains. We look for patterns and make decisions based on them. Sometimes the patterns are illusions, and we come to irrational conclusions."
-Scott Adams

poohat
Posts: 230
Joined: Mon Apr 07, 2008 6:21 am UTC

Re: Building a Mapping Robot

Postby poohat » Tue Jun 17, 2008 1:54 am UTC

Sounds cool. You may want to look at SLAM (Simultaneous Localization and Mapping) to see the approach taken by various state-of-the-art approaches to the problem. The previous poster mentioned some hardware methods of improving the quality of your measurements, whereas most SLAM research is about mathematical approaches for reasoning accurately despite having errors in all your measurements. You may not want to bother with anything so technical, but the maths behind it is pretty cool so it could be interesting.

http://en.wikipedia.org/wiki/Simultaneo ... nd_mapping
http://ocw.mit.edu/NR/rdonlyres/Aeronau ... s_repo.pdf

kyt
Posts: 3
Joined: Sat Apr 12, 2008 5:49 am UTC

Re: Building a Mapping Robot

Postby kyt » Fri Jun 20, 2008 7:27 pm UTC

Before you can map, you need a method of localization (knowing where you, the robot, are).

Simply using dead reckoning (wheel rotations) to calculate where you are is very inaccurate and you will soon be very far off from where you think you are. There are dozens of ways of doing localization but many of them involve expensive hardware that a normal person can't afford.

Last, SLAM usually involves expensive laser range finders. However, it would be really cool if you adapted it to use for a simple touch sensor.

User avatar
niko7865
Posts: 536
Joined: Sun Jan 21, 2007 11:47 am UTC
Location: All over washington state, USA
Contact:

Re: Building a Mapping Robot

Postby niko7865 » Wed Jun 25, 2008 7:04 am UTC

I was thinking of some sort of compass to get heading, and maybe an infrared or sonic range finder, but those are getting a little too technical on the hardware side of things I think. I might just have to go with only having it make 90 or 180 degree turns and hoping nothing slips/goes wrong.
21/m/athletic/white&nerdy/washington/straight/???
Image

User avatar
und3rdark
Posts: 27
Joined: Mon Jan 14, 2008 7:25 pm UTC
Location: Canton, Michigan

Re: Building a Mapping Robot

Postby und3rdark » Wed Jun 25, 2008 8:02 pm UTC

SparkFun makes some nice breakout boards for various sensors:

Ultrasonic range finder
Compass Sensor
"The impulse to discriminate is a feature of our brains. We look for patterns and make decisions based on them. Sometimes the patterns are illusions, and we come to irrational conclusions."
-Scott Adams

Micron
Posts: 319
Joined: Sat Feb 16, 2008 1:03 am UTC

Re: Building a Mapping Robot

Postby Micron » Thu Jun 26, 2008 2:44 am UTC

niko7865 wrote:I might just have to go with only having it make 90 or 180 degree turns and hoping nothing slips/goes wrong.

Unfortunately this is certain to fail. Your drive motors will turn at slightly different speeds even when given the same input signal and at least one of your wheels will slip slightly on whatever surface you are driving on. You will not be able to make exactly accurate turns or accurately measure distance traveled giving you a set of small errors which will become more and more pronounced the longer the robot runs. Feel free to build it and try it but you'll be better off if you recognize the limits of your hardware now and try to account for some of them.

I don't mean to be discouraging though, you're not doing anything wrong but you should be aware that you cannot ever get perfect control and precision out of the mechanical parts you are using. There are plenty of ways you can detect and correct for these errors and variations but if you don't use any of them then it is only a matter of time before the compounded errors make your attempts at positioning wildly inaccurate. If you need to see this for yourself then try a simple test; have your robot drive straight on the longest path you can find and see how much it varies from a straight line, then have your robot spin in a circle and try to get it to stop after turning a multiple of 360 degrees. Now try those tests again when the batter has been drained by driving around for a couple of minutes and see how much the results have changed.

As mentioned before an un-powered wheel with an encoder is one option to track actual movement. You could also use the sensors from an optical mouse if it works on the surfaces you are driving on. Depending on what sort of obstacles you are concerned with you might even be able to use a range finder of one form or another but those also have a fair amount of error in their readings which you would need to correct for.

schwalord
Posts: 43
Joined: Tue Apr 29, 2008 7:27 pm UTC

Re: Building a Mapping Robot

Postby schwalord » Mon Jul 14, 2008 7:28 pm UTC

This is actually something that I have been designing a project around for the majority of the past 4 months.

Pretty much everyone has gotten it right, dead reckoning sucks big time. You can pull it off over very short distances (short being relative depending on the quality of your components) but for most hobbyist level stuff you're looking at maybe a meter at the best to not have any error.

To give you an idea for one of my robotics classes we had to dead reckon to the center of a rectangle, even after 2 weeks of work we only had about a 75% chance of actually making it withing 10-15cm of the middle, which was good enough for an A. There are so many variables that have to be taken into account when you are trying to get something to go straight. Everything from signal to battery power to line resistance can make enough difference to throw you off.

There are some pretty simple and cheap ways around it, or at least to marginalize your error. Everyone has been talking about using an encoder on a non powered wheel to see the distance that you have traveled. An encoder in case you don't know is at it's heart a ruler of sorts. most of them revolve around using some kind of photo sensor to measure the passing of alternating white and black bands on a wheel or the presence and absences of a light source. You can tell how far you have gone by how many "clicks" you have gotten from your encoder. I would warrant against using a single encoder on one wheel though. The reason for this is you cant really tell if you are going in a straight line, even though this is damn hard anyways.

But all in all this is a good project just be ready for a lot of twerking and a lot of learning the annoyances of working with low end sensors. I would suggest if you really want to get a feel for how your entire system is going to behave to build everything from scratch. It makes life much more interesting sometimes but when you get your first microcontroller actually running a bot it is hotness.

I would suggest http://www.pololu.com for some nice electornics and sensors and if you need any help determining how a sensor works feel free to ask me, the are all mostly simple though.

--Schwa

PS I am a huge robotics nerd in case you can't tell. This is what I want to do with my life after getting my masters. (Micro-Unmanned Flying Robots!)

User avatar
und3rdark
Posts: 27
Joined: Mon Jan 14, 2008 7:25 pm UTC
Location: Canton, Michigan

Re: Building a Mapping Robot

Postby und3rdark » Mon Jul 21, 2008 6:09 pm UTC

schwalord wrote:I would warrant against using a single encoder on one wheel though. The reason for this is you cant really tell if you are going in a straight line, even though this is damn hard anyways.


I would like to reiterate that a gyro + one encoder would work as well to tell distance and heading.

The other thing to plan for is storage: most microntrollers don't have a very large memory space to hold a large map. It might be worth it to look into something like an SD card storage system. I don't have any sources for a way to do this though.
"The impulse to discriminate is a feature of our brains. We look for patterns and make decisions based on them. Sometimes the patterns are illusions, and we come to irrational conclusions."
-Scott Adams

User avatar
HiroP
Posts: 45
Joined: Sat Jun 02, 2007 10:49 am UTC
Location: The Metaverse.
Contact:

Re: Building a Mapping Robot

Postby HiroP » Wed Jul 23, 2008 12:20 pm UTC

It might very well be a good idea to invest in sore IR reflectivity and/or triangulation sensors -- they are pretty cheap and can give you the effect of a "virtual bumper" if you use some of the digital ones. For example, Sharp has a line of IR triangulation sensors that measure the angle of reflected light to give a distance reading, and they are roughly $12 each: http://www.acroname.com/robotics/info/a ... sharp.html

As you can see, they come in all sorts of ranges and styles. With a little bit of extra logic you could probably put one on each side and improve your dead reckoning accuracy while also increasing the rate at which you make a map. These sensors are also mostly immune from ambient light, as opposed to traditional LED/phototransistor pairs.

Another idea - for dead reckoning the most important thing you need to take account of is the orientation (angle) the robot is traveling (too lazy to cite the research paper I got that from). Some sort of absolute encoder on the front wheel could do wonders in improving your accuracy.
Cow_Hat wrote:I think we're all missing one key flaw in this whole scheme: Cuttlefish have three hearts.
How could a creature with such an obviously high capacity for love be used as a trained killing machine?

schwalord
Posts: 43
Joined: Tue Apr 29, 2008 7:27 pm UTC

Re: Building a Mapping Robot

Postby schwalord » Fri Jul 25, 2008 2:54 am UTC

und3rdark wrote:
schwalord wrote:I would warrant against using a single encoder on one wheel though. The reason for this is you cant really tell if you are going in a straight line, even though this is damn hard anyways.


I would like to reiterate that a gyro + one encoder would work as well to tell distance and heading.

The other thing to plan for is storage: most microntrollers don't have a very large memory space to hold a large map. It might be worth it to look into something like an SD card storage system. I don't have any sources for a way to do this though.


Both good points.

If you're worried about storage space an array isn't that much space. (I assume were also not talking about resolution down to anything less than 3"' and nothing larger than a 200 sq ft room).

I would suggest looking at the Orangutan controllers on http://www.pololu.com you ca get one with about 16K of RAM which is a lot, for a small robotics application. If you want/need more than that I would suggest stepping away from the standard microcontroller and look at a small "computer".

HiroP wrote:It might very well be a good idea to invest in sore IR reflectivity and/or triangulation sensors -- they are pretty cheap and can give you the effect of a "virtual bumper" if you use some of the digital ones. For example, Sharp has a line of IR triangulation sensors that measure the angle of reflected light to give a distance reading, and they are roughly $12 each: http://www.acroname.com/robotics/info/a ... sharp.html

As you can see, they come in all sorts of ranges and styles. With a little bit of extra logic you could probably put one on each side and improve your dead reckoning accuracy while also increasing the rate at which you make a map. These sensors are also mostly immune from ambient light, as opposed to traditional LED/phototransistor pairs.

Another idea - for dead reckoning the most important thing you need to take account of is the orientation (angle) the robot is traveling (too lazy to cite the research paper I got that from). Some sort of absolute encoder on the front wheel could do wonders in improving your accuracy.


yay Sharp IR range finders! and boo as well.

These things are a blessing and a curse. They are very good for mildly precise distance finding, but have enough play and calibration fun that they can be a pain to use. If you do use one note that there is a dead zone (they don't read properly) under about 5" and their voltage is exponential to the distance. Think of 1/x.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 4 guests