mapping an are and figuring path...

[jamort]

so Im going to be starting a project in c++ in which the robot will "map" the area the its in and figure a path through it... Im planning on uding a few sonar sensors and maybe a couple others..... I just dont know exactly what the code will be.... please give me ideas this is my biggest task yet and im planning on making a tutorial....
thanks
CJ

[alexanderr]

I dont know what you are looking for, but have you thought about the WaveFront algoritm featured on the webpage here? I just completed a robot using the algoritm and it works like a charm. The only drawback that i could find with this method is that the maps are likely to take up alot of memory on a small microprocessor.




//Alexander

[SciTech02]

You've probably searched the forum already, but there is some very informative mapping/pathfinding threads on this forum.  I actually started one awhile back discussing the A* algorithm for mapping.  A sample C++ code was even posted in that thread.  Here's the link:

http://www.societyofrobots.com/robotforum/index.php?topic=5342.0

Unfortunately, this pathfinding program finds a path from a preexisting map, stored as a matrix (kind of like a XY grid).  It does not create its own map from sensor data.  If you could find a way to create an XY grid from sensory data, then this code could be used.  This is only 1 possible way to do this; there are many ways of approaching this task.

I would recommend you research the "Monte-Carlo/Markov localization" technique.  This, theoretically, can work using several IR or ultrasonic sensors.  Computer vision is also a possibility, but this may be difficult to implement on a microcontroller-based robot.

Hopefully, this helped give you some ideas to think about.

SciTech02

[jamort]

You've probably searched the forum already, but there is some very informative mapping/pathfinding threads on this forum.  I actually started one awhile back discussing the A* algorithm for mapping.  A sample C++ code was even posted in that thread.  Here's the link:

http://www.societyofrobots.com/robotforum/index.php?topic=5342.0

Unfortunately, this pathfinding program finds a path from a preexisting map, stored as a matrix (kind of like a XY grid).  It does not create its own map from sensor data.  If you could find a way to create an XY grid from sensory data, then this code could be used.  This is only 1 possible way to do this; there are many ways of approaching this task.

I would recommend you research the "Monte-Carlo/Markov localization" technique.  This, theoretically, can work using several IR or ultrasonic sensors.  Computer vision is also a possibility, but this may be difficult to implement on a microcontroller-based robot.

Hopefully, this helped give you some ideas to think about.

SciTech02

ok i think ive got the basic idea after relizing that an array will work.... I think that I'll use encoders and have each letter represent say a foot....
so pseudo code(a start)
robot looks around... I have sonar sensors all around or ir...
takes the measurements and taking in the most measurement im going to probably get is 15 cm if theres an object that way it will replace a variable with a x meaning it cant go that way then if it is nothing that way then it will replace the variable with a 0.... then decide if theres a 0 the front it will got forward or so on so forth im sure you get the point....
I think one problem is eventually if it keeps looping ill have to have a reall big array.... I wonder if I'd be better off having some way to save the map as it goes and update it and have the robot then shift the array over so it stays with in an 8 by 8 space...
thanks any ideas appreciated...
Ive got all summer but Im working on like three projects so....

[Ro-Bot-X]

I will be working on a similar thing for my robot this summer. The idea is to save the big map in EEPROM and pull out a 10x10 grid as the robot advances, update it if needed. I will make the cell size 10x10cm, so the grid will give me 1x1m. Now I will try to keep the robot in the center of the grid, so every time the robot advances 5 cells in one direction I will recenter it, pulling out more map data in the front and save the data in the back. If there is not enough space in the onboard EEPROM I want to use external I2C EEPROM.

[jamort]

i think being the limited range of ir range finders and sonar which is about 15cm if i remember corrrectly for anything in my price range the best thing to do is to keep the robot as small as i can... your thoughts on that?

[Ro-Bot-X]

You make the cell size so it is not much larger than the robot. Then make the grid almost 2 times bigger than the max range you get from the sensors and keep the robot centered in the grid (shift cells as the robot moves).

As far as I know, Ping sensor has max distance of 3 meters, Sharp GP2D12 has max distance of 80 cm. I have a GP2D120 which has a max distance of 30 cm mounted on the scanning servo to be able to center to robot on the objects it needs to grab, but I think I'll use only the Ping sensor to get a localisation on the map (plus encoders and compass). As I will have the map allready in the memory, I'll be fine even with a large cone the ultrasonic sensor has. I may add more sensors later if needed.

[jamort]

ok so its is a little further then i thought... i never pay attention to some of the technical aspects such as that and reallly should...