View Full Version : Region coverage algorithm [URGENT]

12-24-2005, 02:18 AM
Hi I'm new to robotics and currently working on a project relating to region coverage mobile robot.

The robot is supposed to cover all points in a specific terrain (unexplored, i.e. the robot must explore the region itself). This kind of robot can be applied for vacuum cleaning robot, and things like that.

Anyone has gone thru this kind of project can give me a hand? I need info. about the algorithm and relevant sensors needed.

Thank you very much.

12-24-2005, 02:29 AM
be a little more specific about the terrain on which u wanna ur robo to naviate ...... because alot of things will depend on that.
if the terrain is big and unknown... and u don want to collide with obstacles.... u ll have to go for sonars and do grid mapping of the entire enviroment and then proceed in the desired path as per ur algo...
so be more specific about the enviroment,....

12-24-2005, 08:36 AM
Hi as you said the terrain is quite large compared to the robot and also an unknown region. The robot must cover all area by ifself.

I think I can use IR sensors instead, cant I? and could you tell my more about grid mappings and more specific algo. or where I can get that.

Thank you for your help :)

12-24-2005, 09:43 AM
hi there,

see ir's never gives satisfactory performance on many instances.....
it largely depends n reflectivity,smoothness, color of the surface of the object infront....
if the object is carbon black,,, u r dead.
but sonars r faithful...
by grid mapping i meant tat u can keep on scanning the entire surrounding around u, and then map the entire enviroment{in which area there r obstacles and where there's a free area to move} and then decide ur course of action.
but simple navigation is not gr8 idea....
think of some idea or some job which ur robo must perform in this course...
it can be anything, for a start up say, u can fix the coordinates of the ending point and the robo must reach there navigating thro obstacles.tat ll be a gud one ...

so first decide firmly on sonars or ir's????

12-24-2005, 10:36 AM
oh yeah in fact my project is to build a robot capable of scanning through every area within an unknown region. It is like to build a vacuum cleaner or lawn mower, things need to pass through every area in the enviroment to finish its job. This is a region covering robot.

I think I'll use a IR sensor anyway, partially bcoz of my limited funding. So I would appreciate if you can explain more about this, things like mapping (how the robot does it) and how to design a proper sensor system for this specific job.

Thank you my friend.

12-24-2005, 10:45 AM
its pretty interesting problem{ to explore every point}
isnt tat simple....
u will also need feedback of the position to know where u r.
if u can use steppers, and contruct a gud drive system, then ur this tension might be reduced....
or else u ll have to go for optocouplers or wheel encoders for speed feedback.
anywayz begin with making a simple ir module for obstacle detection using tsop.....
get it done first, then proceed into other things....
do the project in a modular way.
gud luck.

12-24-2005, 10:55 AM
hmm what do you mean by a feedback of the position? What is this and how to construct one?

12-24-2005, 11:53 AM
You need a 360degree Rotational Scanning Array.
Consider your horizon as 360 degrees. Divide area into 16 0r 32 quadrants. Scan each quadrant sequentially and memory map the results.
This is Positional Feedback.
Sorry, this is as simple as i can make it right now! :wink:

12-24-2005, 12:22 PM
ya, as docel sugested.... divide the 360' into small sectors....
mount ur sensors on a stepper motor and give a gud sweep...
u will get to know about all stuffs that r there in ur robo's surrounding....
now process it in ur algo for suitable decision making..

12-24-2005, 01:29 PM
Mount four IR sensors( the TSOP combination) on four stepper motors on the corners of the robot. Now grid mapping exactly means dividing the total area into a grid like a graph paper. You can have the points as the corners in the grid, now just move on grid lines and keep marking the points as visited.

I have suggested four motors so as you can map the area quickly, because doing it with one will take more time.

12-24-2005, 02:09 PM
Hi thank you for your valuable info.

By mounting the sensors on motors, do you mean that the sensors are made rotating around?

Also, I'm not quite sure about landmarking, or marking the visted points as devpriya said. Could you explain more about this to me. Is this based on the change of the outputs? and if I'm not wrong the landmark info. can be store in RAM of the microcontrollers right?

Hope someone can clear my wonder. Thanks a million :)

12-24-2005, 06:47 PM
wat dev meant was tat u scan a particular area and have something like a matrix in which u put a value '0' if there is no obstacle and a value '1' if there is an obstacle...
the idea is to mount ur sensors on a stepper and give a gud sweep so tat u can map the entire enviroment at one go at a faster rate.
and u gotto store all these datas in the mic's ram...
once u have mapped the enviroment, then u can decide the future course of action.

12-25-2005, 01:08 AM
Hi I have a question:

How can the robot mark a point (such as wall or obstacle)?

As in my opinion, the robot can do this by storing specific values of the outputs corresponding to the points since each point would produce a different output. But what if two or more outputs is similar and the robot can not distinguish them.

Please answer my question and correct me if I'm wrong.

Thanks a million. :)

12-25-2005, 11:27 AM
no no its not like tat..
see u just break the entire 360' into many sectors and then make scans and search for objects in these sectors.
if u get any object then mark that sector as '1' or else '0'. so at a time there can be any one value for a particular sector. on a whole there will be many o's and many 1's.obviously 1's means a no entry zone and 0's means empty zones{u ll have to have the information whether u visited thiis sector or not before, so tat u don explore an already explored area }
now u ll have to be aware of ur present position and where u want to move to next{ use some optocoupler ka feedback or stepper motors} and then viewing these strings of 0's and 1's u gotto decide which way to move along and reach ur goal.
look buddy, u get along with the work. begin making dem, get the sensors done, these ideas u ll have to keep on trying and changing.

12-27-2005, 01:30 AM
ok guys,
Now all this is a tall order and not really that easy. Getting those steppers to move itself is a great problem; Swinging sensors on top of them, monitoring their outputs, storing the values, comparing them with newer updated data, eliminating , redundency etc is a real nightmare.
Mapping is not as simple as a 0, 1, null kind of thing. There is this 'dynamic' readings that need time division algorithms with fairly accurate values to be 'good' or 'bad'. Else the robot will never know where it is at any given time.
I'm not sure if Ichigohnvn is thinking of the "Grid' mapping contest or if he is building a vaccum cleaner. We planned for the GRID contest and dropped the idea for next year. Reason : impossible in 2 months of student programming.
If a vaccum cleaner or landmower, The robot needs to have a fixed bearing first and then compare its running values with this. A combination of proximity/distance sensors can be useful , along with odometric values from the wheel/s.
1. 4 sensors for F, B, L & R. These should be analog for distance measurement.
2. Odometry ie,. wheel rotation = dist travelled. Could be chopper wheel.
3. 4 sensors for obstacle avoidance.
4. Lots of memory ram, A/d conv.

My 360degree scanner is NOT MOBILE. Its a ring of static sensors which are scanned sequentially, once every second or so, depending on needed resolution.
Imagine: each sensor represents a particular quadrant. If 8 then N, NE,E,SE,S,SW,W,NW. The sensor 'cone' of influence will overlap enough to cover the overall horizon. The horizon meaning immediate surroundings of say 1meter. may be 10 meters but not really necessary, since the speed of the robot will not be much. Nor the actual dimensions.
This robot will decide where it is first and memorise coordinates. Then it moves in one direction for x cms. update readings and decide next move- say E...then for e cms. etc......All this needs some pretty funny software routines and expertise!!!!

So, ichigohnvn, first make something with 3 wheels and make it move by itself. Then put in 1... repeat ONE sensor and see what happens. and take it from there.
like addy says.....

12-27-2005, 02:34 AM
ya docel...
i fully agree wid u..
the project is not at all simple.
tats why i ve suggested ichigohnvn many times in these posts to get the sensor module goin first and then take the entire process in modules..
every thing will depend on the module which he prepares...
its range, effi8ciency,etc will add constraaints to be dealt with...
and grid mapping will always be a difficult task.

12-27-2005, 04:24 PM
Yes addy. Sometimes, too much theory will STOP you from Doing things practically!! Theres a lot of difference in just doing something, however simple it might seem. I've seen plenty of final years' struggling for weeks to get a car moving straight!!....and their joy after the success!

12-27-2005, 09:20 PM
I've seen plenty of final years' struggling for weeks to get a car moving straight!!....and their joy after the success!

Docel your words touched my heart, I still remember the day when I made my first wired remote controlled vehicle and it moved straight. I still have the video with me................. :D

I wrote this to tell ichigohnvn that nothing is easy here, even making a SONAR work is a big deal in itself.

I myself took help of Sumandeep and JD to make my first obstacle avoiding robot using SONAR and believe me the mapping part was not at all easy.

So ichigohnvn start off with a sonar interfaced with a computer using LPT port and see if its working........then move forward to uC ........and finally mount it on your vehicle.

Few tips I would like to give which might help you initially.....I personally prefer puttin a lot of LEDs on my robot for moniotring the input and output data....this tells me whether my algorithm is working fine or not.....this help me see what my robot is seeing.....and how it is responding.

Hope all these are useful to you. :)

12-27-2005, 10:34 PM
Thank you all my friend!

I am starting to source for parts now. I hope you all will help me with other problems in the future :)

12-27-2005, 11:27 PM
ya tats it man...
the game begins now.
go ahead and dun woryy..... RI is behind u.