Society of Robots - Robot Forum

Software => Software => Topic started by: coolshankrocks on September 11, 2007, 12:27:00 PM

Title: Mapping
Post by: coolshankrocks on September 11, 2007, 12:27:00 PM
Hi all.
I am making a project. In which i have a sample area. I need to map the area using ir sensors mounted on a robot. The robot navigates in the area and makes a map of the area indicating locations of obstacles. the area comes out to be like a grid with the obstacles marked as 'x' on the grid. Can someone plz help me out with a algorithm which makes the robot travel in the area and create a map.
Title: Re: Mapping
Post by: h3ro on September 11, 2007, 12:33:39 PM
Check out this link:
http://www.societyofrobots.com/programming_wavefront.shtml (http://www.societyofrobots.com/programming_wavefront.shtml)

Its with source code!
Title: Re: Mapping
Post by: coolshankrocks on September 11, 2007, 10:07:00 PM
hi. thx for da link. but this link contains an algorithm for travelling once the map is made..
my aim is to create a map. and determine where the obstacles are.
Title: Re: Mapping
Post by: Admin on September 12, 2007, 06:44:09 AM
Quote
I need to map the area using ir sensors mounted on a robot. The robot navigates in the area and makes a map of the area indicating locations of obstacles. the area comes out to be like a grid with the obstacles marked as 'x' on the grid.

but this link contains an algorithm for travelling once the map is made..
my aim is to create a map. and determine where the obstacles are.
look again, my algorithm does exactly what you need :P
it creates a map with a sharp IR, adds obstacles to that map, then plans a path accordingly.

you might find this helpful too
http://www.societyofrobots.com/sensors_sharpirrange.shtml
Title: Re: Mapping
Post by: cooldog on November 12, 2007, 06:27:53 PM
so could he use the $50 robot with sharp Ir upgrade and just put in a new algorithm as easy as that or are there complications
Title: Re: Mapping
Post by: Half Shell on November 13, 2007, 12:51:42 PM
CoolShank - I am actually doing the same project right now. Contact me so we can trade what we've got codewise so far.
Title: Re: Mapping
Post by: Rebelgium on November 13, 2007, 01:39:42 PM
Quote
so could he use the $50 robot with sharp Ir upgrade and just put in a new algorithm as easy as that or are there complications
Yes.
I don't know if the standard 50$ robot has wheel encoders, (little discs mounted on your wheels, which show your muC if and how fast they are turning) but you need encoders to do mapping.
Title: Re: Mapping
Post by: Asellith on November 14, 2007, 02:01:11 PM
What kind of accuracy do encoders and IR sensors produce? One of my long term goals for my R2-D2 project is to produce a mouse droid that will enter areas ahead of R2 and map for obstacles. Then send that data back to R2 so he has a more ground level view of things and can plan his initial route accordingly.

Johnny B
Title: Re: Mapping
Post by: Admin on November 14, 2007, 02:40:51 PM
Quote
What kind of accuracy do encoders and IR sensors produce?
Depends on how you use them.

The IR sensors depends on your scan resolution, which depends on your servo accuracy.

Lets say you are sensing at 3ft with a servo accuracy of 2 degrees. To calculate error:
2*pi*4ft/(360/2deg) = 0.14 ft or 1.7 inches
This isn't so bad, unless you factor in the scan time to get this accuracy . . . several seconds . . .
Then there is also error in the depth and mcu ADC conversion, which you may or may not find in the sensor datasheets.

Now for encoders . . . depends on the surface and friction and resolution, etc.

So lets say you have a 5% error in each motion your robot makes. To calculate error for a robot that moves 50 feet:
50ft * .05 = 2.5 ft error
(a lot!)
Title: Re: Mapping
Post by: benji on November 23, 2007, 11:01:04 AM
hey guys ,im goin  for this mapping project also, finally i got a sharp IR wich has a range of 150 cm as maximum.
i checked the datasheet of it but no clue if it has a spreading angle beam,
i know it should be little but is it just a striaght line? cause if there is a little spreading then someone should consider this when rotating the servo (how many degrees) (maybe 2 degrees isnt enough)

that means the more the spreading angle the less readings of range we can make,,if there is any spreading angle

Title: Re: Ultrasonic beam narrowing
Post by: paulstreats on November 23, 2007, 11:06:19 AM
the sharp ir does have a spread angle, but i cant remember off the top of my head. its quite a small angle, but obviously the further away the object, the more it appears spread.

This is why the distance detection is so limited, because as the ir light spreads out, it becomes weaker (inverse square law if anyones interested) and the less light is reflected back off the object
Title: Re: Mapping
Post by: benji on November 23, 2007, 02:20:19 PM
Quote
the sharp ir does have a spread angle,

about how many degrees?
turning the servo only 2 degrees would give a different reading than the reading before it's turned?is the beam that small?

in the sharp ir page in this website the beam is drawn as a straight line hitting an object then turning right into the reciever,, is that totally correct?
Title: Re: Mapping
Post by: paulstreats on November 23, 2007, 05:13:48 PM
its only a few degrees, and turning the servo 2 degrees would give a different reading. The important thing to realize is that the closer the object is (within the distance parameters) the more accurate it will be. at 15cm the circle of light would be about 1 cm at 30 cm distance the light circle would be about 2cm at 45 cm distance the circle would be 4cm at 60 cm the circle would be 16 cm.....
Title: Re: Mapping
Post by: benji on November 24, 2007, 01:59:06 PM
i was thinking to send the bytes of one complete scan cycle to the pc and let the software there build the plan, this way i wont need big rams in my microcontroller and i can build big maps over the pc
,the micro should just tell the robot (after it sees the one cycle scan bytes) where to go (lets say where zeros are) and if there are non it turns to get data from another angle.
what do u guys think of  this?
Title: Re: Mapping
Post by: Admin on November 24, 2007, 03:10:16 PM
Remember that an extremely accurate scan as you describe will be very slow. For example, lets say it takes 100ms per data point (because servos are slow, and the Sharp IR takes like ~60ms to get an accurate reading if I remember correctly).

Now lets say your robot scans 120 degrees (1/3 field of view in front of your robot), with 1 degree accuracy.

120 data point resolution * 100ms per scan = 12 seconds!

I don't think you want your robot to stop for 12 seconds every few feet it moves . . .

And this doesn't even factor in transmission to your PC or processing time . . .

Its always a trade between accuracy and speed.
Title: Re: Mapping
Post by: paulstreats on November 24, 2007, 06:39:35 PM
or how long it takes for the a/d conversion...

why not have more than 1 scan function such as moving scan/quick scan/deep scan/point scan
Title: Re: Mapping
Post by: DomoArigato on November 24, 2007, 10:34:57 PM
I have code that does a 2d mapping using the 150cm sharp IR rangefinder and ATMega 128 if you would like to work off it.  Looking back I see lots of room for improvement in the code, but the servo and sensor control code is pretty decent.  Let me know if you would like me to send it to you.  I have it setup with a robostix board, one servo, and one IR rangefinder mounted on an rc car.
Title: Re: Mapping
Post by: Admin on November 24, 2007, 10:52:50 PM
good idea Domo

I have some code too, go to the very bottom of this page:
http://www.societyofrobots.com/robot_omni_wheel.shtml

It uses 3 sharp IR at the same time to do 2D mapping (because 3 is 3x faster than 1). But I was definitely a noob when I wrote that code so can't promise you how easy it would be to understand it . . .
Title: Re: Mapping
Post by: benji on November 25, 2007, 08:53:57 AM
well admin, do i need to take a reading each 1 degree???
im actually goin to use the 150 cm sharp IR,so saying i will take a reading each 2 degrees then the sensor will sweep 5cm arc each turn ,(lookslike its hard to miss a chair's foot)
but also with that the time would be 6 secs,,still too long,, using 2 sharps, we got 3 secs ,,(good for a hexapod) ,,,,yea right we still want to figure out how long the adc takes to interpret,,mmm, looking to the datasheet you can minimize the conversion time by using a high freq clock source
i think this time is pretty nigligable
Title: Re: Mapping
Post by: Admin on November 25, 2007, 10:12:46 AM
Quote
well admin, do i need to take a reading each 1 degree???
I was under the impression you wanted less than 2 degree accuracy from your previous posts :P

The way I do it is my robot takes about 10 to 20 readings in under a second without stopping the servo. The angle information has a high error (10+ degrees?) because of this, but it will never miss a chair leg for sure. Then I angle shift my readings in code to make up for that time lag caused by sensor and ADC lag to try to correct for that error (if your sensor repeatedly does the same thing, you can tweak it until it works perfectly).
Title: Re: Mapping
Post by: benji on November 25, 2007, 03:32:11 PM
Quote
I was under the impression you wanted less than 2 degree accuracy from your previous posts
well yea that was when considering a sonar instead of the sharp ir ,you know big ranges draws long arcs at little angles  ;) .

anyways about your code, would you shift the whole angles of your readings?
the error should be only starting at specific angles, of what i understood you should only shift the angles of where the error started until the last reading,, this is a lil compicated to do isnt?
Title: Re: Mapping
Post by: Admin on November 25, 2007, 04:48:19 PM
Quote
anyways about your code, would you shift the whole angles of your readings?
the error should be only starting at specific angles, of what i understood you should only shift the angles of where the error started until the last reading,, this is a lil compicated to do isnt?
there will always be fudging and guesswork involved . . .

So if my sensor scans clockwise, I would expect say a -10 degree error (caused by lag) on average (determined from testing). So, obviously I would just do +10 in my code to each degree reading.

And when my sensor scans counterclockwise, I would get say +9 degree error, meaning I subtract 9 from my result.

etc.

Of course, the first step would be to determine your error, and if its 'acceptable enough'.
Title: Re: Mapping
Post by: benji on November 26, 2007, 10:57:09 AM
come on Domo,, we eould be glad to take a look at your code
Title: Re: Mapping
Post by: DomoArigato on November 26, 2007, 07:34:42 PM
I haven't had time to look at this for a while, and I look back and see lots of room for improvement, but here is the code.  Let me know if you have questions. Download the zip file from this link: http://domoarigatoq.googlepages.com/home
Title: Re: Mapping
Post by: benji on November 27, 2007, 11:26:48 AM
thanks Domo for the code, i took a look at it ,it looks pretty neat,but i noticed that you gave 9 msecs
to wait for the servo to settle,, right?
was that enough??

 great if it is
Title: Re: Mapping
Post by: DomoArigato on November 27, 2007, 11:54:51 AM
Looking back.  No I don't think it's enough.  Here is the post we had up when I was working on this:  http://www.societyofrobots.com/robotforum/index.php?topic=1692.0 .  Most of the conclusions I reached were totally wrong.  I just looked back at the time it takes the rangefinder to refresh, and I misread the diagram.  It takes 38.3msĀ±9.6ms for the first read and it looks like roughly 35 ms for the other  reads.  There is a 5ms delay between the read and the analog signal on the output pin.  The 9ms seemed to work at the time, but looking back it is probably bad data.  Things to keep in mind it will take up to 52.9 ms to get the first read, and after that it will settle into a stable mapping frequency.  I would use between 36 and 40 ms delay (including servo and ADC delay) if your looking for accurate mapping,  I think the 9ms would be fine if you just wanted to avoid hitting stuff, however if that were the case a sonar would be a much better choice.
Title: Re: Mapping
Post by: benji on November 28, 2007, 06:17:57 AM
adc convertion time is 13 clocks in the atmegas of the adc clock freq,, so 1 ms is sp enough.
and about the sonars,, i dont think sonars are a good choice for mapping,, their stupid beam angle can make your code a lot harder..
Title: Re: Mapping
Post by: Admin on November 28, 2007, 01:37:09 PM
Depends on which microcontroller you are using, but the first ADC run takes longer because it needs to 'warm up'

Its considered good practice to read from your ADC a few times during robot startup before you start using the ADC values.
Title: Re: Mapping
Post by: benji on November 28, 2007, 04:42:48 PM
in the atmegas datasheet it says only the first conversion takes 25 clocks,, (still nothing)
and after that it goes 13es
Title: Re: Mapping
Post by: benji on December 01, 2007, 04:01:16 PM
im sending blocks of memory (one array) after one scan to the copmputer to draw the map block after block, so when the robot turns lets say 45 degrees i need my software over the computer to recieve not only the array but also the angle of the block(array)
the problem is that i need some kind of sensor to have this information,, what can i use?

(i need to specify the orientation of the robot )
i need this sensor (or trick) because considering the robot will not be aligned as it should after let5s say 20 turns ........

any help?
Title: Re: Mapping
Post by: HDL_CinC_Dragon on December 01, 2007, 04:10:17 PM
You could probably use encoders and have the robot track its own movements using the encoders on the wheels... dunno how accurate that would be after a while though.
Title: Re: Mapping
Post by: Admin on December 01, 2007, 04:36:02 PM
so encoders will work for awhile until error builds up . . . you can also try a gryo or digital compass, but they aren't perfect either . . . you can also trying combining them to minimize error

what you need is a 'global sensor', meaning something that the robot can use to correct for large global errors.

what about a beacon(s) of some type? you can use the beacon positions to detect error . . .
Title: Re: Mapping
Post by: Ro-Bot-X on December 02, 2007, 02:45:56 AM
Admin is right, error is building up. Depending on your level of accuracy required, you may use just wheel encoders, or add a compass, then a beacon triangulation.

A few tips to minimise error adding up when using wheel encoders:
- slowly accelerate and decelerate your robot, so there is no wheel slipage
- try to use it on hard surfaces only, avoid carpet
- calculate a wheel circumference of integer number of inches or cm
- divide that into integer numbers of clicks for the wheel encodes
- use pid control for your motors
- avoid crashes into objects!

When using a compass:
- install it high above the motors and other electronics that can cause electromagnetical fields
- give it a little time to update the angle after turning (check the data sheet)

Beacon triangulation:
- the best system it is supposed to be a mixture of IR light and Ultrasound
- fire each beacon at a regular interval, large enough to eliminate the sound bouncing off walls
- fire both IR and sound at the same time, light will reach the robot almost instantly, then calculate the time the sound needs to get to the robot, bigger distance, more time it needs to get there
- use cones to center the signal to the US and IR sensors on the robot, one sensor for each carrier is enough
- install the beacons in the corners of the room
- if one beacon is blocked by an object, make sure the robot keeps track of distance traveled out of range, then recalculate position after it gets back in range

Title: Re: Mapping
Post by: paulstreats on December 02, 2007, 08:39:43 AM
why not try a different approach at mapping. This is something that i am going to be working on soon:-

take 1 scan and store it in memory. (98 120 0 0 0 67 54 73 89)

Move and take another scan. (54 73 89 43 98 0 0 0 56)

compare the scan and see if scan 1 and 2 overlap(with a slight error threshhold)(98 120 0 0 0 67 54 73 89 43 98 0 0 0 56)

if so join them up together to make 1 piece and scan again.

Your robot can find its position by scanning the area and comparing it to whats in memory.

Remember, your robot doesnt actually have to use a grid reference system like a1=empty, c3 = object. This is a system created by humans, our own intelligence doesnt it.
Title: Re: Mapping
Post by: benji on December 02, 2007, 02:06:41 PM
well im sorry i forgot to mention that my robot is a hexapod ... so noway i can use encoders.
about becaons i dont prefer to use em,,,maybe the compass is my choice
..i have no info about em,, do they provide 1 degree resolution?? what are good ones to use? their numbers? thanks
Title: Re: Mapping
Post by: DomoArigato on December 03, 2007, 11:30:22 AM
maybe GPS? I've thought about rigging up an encoder using a computer mouse.  The only tricky part would be touching it to the ground, but I don't think that would be too hard to do.  Maybe a camera aimed at the ground if you money to do it.
Title: Re: Mapping
Post by: Admin on December 03, 2007, 12:00:23 PM
One method I've seen is randomly spreading beacons on the floor every few meters.

Then the robot counts beacons as it passes them, given the know direction it passes between beacons, and beacon signal strengths to triangulate.
Title: Re: Mapping
Post by: Ro-Bot-X on December 03, 2007, 12:01:11 PM
I am building a biped and I am facing the same problems regarding the encoders. I am still planning the thing, not started the construction yet.

But here are my thoughts:
- keep track of gait, number of steps, etc;
- devise step lenght so it will be easy to calculate how many steps will be necesary to go a certain distance;
- use a compass for turning corectly;
- use known fixed points of reference to recalculate the position on the map;
- if there are no such fixed points of reference, try to determine at least 3, measure the distance to them, calculate the coordinates and mark them on the map;
- if one of the 3 points of reference moves or dissapears from it's place, find another point and mark it on the map.
- use both ultrasonic and IR sensors to determine the distance to the the points of reference;

Another possibility may be to use a camera to establish the fixed points of reference, but that is too advanced for me to tackle. If I'll be able use the AVRcam to find objects, go to them and pick them up I'll be more than happy.
Theoreticaly I know what I have to do, but to code that... it's still a lot for now.

I'll build a wheeled platform to test out some code...
Title: Re: Mapping
Post by: Ro-Bot-X on December 03, 2007, 12:35:33 PM
Hey, I just remembered something, about 12 years ago I was working on digitizing street maps using AutoCad12. After a while, the company brought us street survey measurements. This is how it is done:

On the streets the are some places marked by a bolt burried in asphalt. Those places have known real world coordinates. The survey team mounts their measurement instrument on a trypod, making sure it's center points a lead string to that bolt in the asphalt. They verify the real world coordinates looking at other points of reference, like verry tall buildings, radio antenae and so on. This is the first station. They measure the height the instrument is at, so they can calculate the z coordinate. Then one team member goes to the points they need to survey, one point after the other, holding a divided stick verticaly. The other team member looks at the stick with the instrument, reads the division to get the height difference, reads the angle the instrument is turned at, and reads the distance to the stick. This is done for each point they need to include in the survey. Each point is numbered, and the data is recorded in a notebook. Then they move the instrument at a certain distance and angle from the first station and they survey more points, them move the instrument again a few times until they reach another bolt in the asphalt, where they check back some of their readings from the previous station. At the end of the day, there are several stations with several points related. All this data is entered in a data base, then the coordinates of these points are calculated and entered in a map (x, y, z, where z is height measured from sea level). Then a program connects these points with lines, following certain pattern rules.

Now lets say that the instrument is the servo. It rotates at known angles, the sensor measures the distance to the points and records them on the map. Coordinates can then be calculated, then lines can be drawn to determine boundaries of the objects. And so on... Error corection measurements can be done to a point from different stations...

What do you think about this?
Title: Re: Mapping
Post by: benji on December 05, 2007, 05:40:52 PM
hey folks, are there any already made libraries in c i can use for mapping? i think that would save some time
Title: Re: Mapping
Post by: Admin on December 05, 2007, 07:22:57 PM
you mean other than my wavefront C code (http://www.societyofrobots.com/programming_wavefront.shtml)? :P

or the D* code (http://www.societyofrobots.com/robotforum/index.php?topic=1325.msg9799) posted awhile back?

 ;D
Title: Re: Mapping
Post by: benji on December 06, 2007, 06:28:49 PM
the wavefront doesnt explain how u build the whole map,,,,,,it just explains the way the bot traces its goal
Title: Re: Mapping
Post by: Admin on December 06, 2007, 08:58:32 PM
Quote
the wavefront doesnt explain how u build the whole map,,,,,,it just explains the way the bot traces its goal
my code also creates and modifies the map ;D

making the map is the easy part (its just a matrix), the hard part is making the map useful . . .
Title: Re: Mapping
Post by: benji on December 07, 2007, 02:34:52 PM
well my approach to mapping is to send a 90 scan to the computer after each scan and the software there will build the map,the robot would only know where to go,, the computer will tell the bot to stop after the map has been built, so the robot has roamed the whole room, the computer programing part isnt that easy, you have to make a software that takes the info from the serial port and plots the room step after step...... ;) , ,it need info about (range,degree) for each scan and when the bot changes its orientation you have to send data also to the pc so we have to use a compass here,,that makes the pc software a little harder, when the pc sees a closed line (robot has scanned the room) it should make the bot stop (mission complete) . im not discussing here any goal trackin or anythin.
so the functions im talkin about are both functions that can help (computer side and robot saide)
somthin like dealin with adc with functions(easier) , or servos(its a hexapod)
........... thats whats it about