Author Topic: grid infront (Read 5456 times)

benji · « **on:** February 03, 2008, 07:29:27 AM »

hey guys , i have my bot making a scan,then walk based on this scan,then take another scan ,......etc
problem is after i make this one scan(which is 180 readings from a sharp ir each 1 degree) im searching for a good algorithm to make it navigate depending on this scan, my scan lookslike the one i attached (this is after transforming it into cartesian coordinates x and y)
anyone every worked somthin similar?
after taking multiple scans i have my code in matlab to build a global map
my problem is just when i take my first scan where should i command my bot to move?

dunk · « **Reply #1 on:** February 03, 2008, 08:29:20 AM »

Quote

my problem is just when i take my first scan where should i command my bot to move?

what's your robots goal?
do you want it to move as far away as possible, move to a specific location or maybe move to the nearest unmapped location?

i have mine explore unmapped areas until it is commanded to move to move to a specific location, then the behaviour changes and it uses the map it has built to get there.

dunk.

benji · « **Reply #2 on:** February 04, 2008, 11:00:42 AM »

Quote

do you want it to move as far away as possible

sure no

Quote

move to a specific location

yea but after i map the room

Quote

move to the nearest unmapped location?

YUPPP

Quote

i have mine explore unmapped areas until it is commanded to move to move to a specific location, then the behaviour changes and it uses the map it has built to get there.

exactly what i want to do, i would be glad that you tell me about it,your algorithm, the way you implemented that,, thanks for any help in advance

dunk · « **Reply #3 on:** February 04, 2008, 02:55:33 PM »

Quote

exactly what i want to do, i would be glad that you tell me about it,your algorithm, the way you implemented that,, thanks for any help in advance

so it's pretty easy to find your nearest unmapped location. just iterate through all your map points, starting at your bot's location and working outwards.

this is not always the best way to do things though as it is not always the case that the nearest unmapped point is the easiest to get to. for example if the bot has to drive round an obstacle to get there there may be an easier target closer.

the way i do it at the moment is to use the same algorithm the guys solving mazes use but implemented a little differently.
http://micromouse.cannock.ac.uk/maze/solving.htm

to initially find the closest unmapped area i start at the bot's location and expand out the way only if the bot can reach the area i'm expanding into. (similar to the algorithm described in the micromouse link except they start at the destination. we don't know the destination yet. you don't need to record the number of iterations on this run either.)
the first unmapped section you reach will be the closest. record it's position on your map as the destination.
once you have found your target destination you want to run the algorithm again, this time exactly as it is described in the micromouse link.
have your bot drive to successively lower numbers on the map.

i still have a lot of fine tuning to do. i intend to give areas near obstacles higher less weight than clear areas to help keep my bot in the open.
i also need to work on decision making when the bot has more than one possible choice of paths. (ie, when there is more than one pixel on the map with the same value next to each other.)

to be honest i'm a while away from having a working solution but that's part of the fun right?

the guys working on computer games put a lot of thought into path planning for AI bots. you might try looking for links that way as well.

dunk.

benji · « **Reply #4 on:** February 04, 2008, 04:58:23 PM »

well thanks for that its kinda helpfull but i have some questions

1/ at the beginning after you take your first scan you are going to decide which closest unmapped area youll go to,is that going to depend on your first scan position only?or considering whats in that scan too(obsticales)?

2/do you determine your global map size before you start mapping?

thanks

dunk · « **Reply #5 on:** February 04, 2008, 05:17:56 PM »

Quote

1/ at the beginning after you take your first scan you are going to decide which closest unmapped area youll go to,is that going to depend on your first scan position only?or considering whats in that scan too(obsticales)?

umm. i don't understand the question.

Quote

2/do you determine your global map size before you start mapping?

at the moment yes. fixed size.
in the future it will be scalable.

dunk.

benji · « **Reply #6 on:** February 04, 2008, 05:33:05 PM »

i meant when your robot starts mapping its gonna be in a specific location with respect to the global map,well then its gonna take a scan to produce the grid just like in that attached picture,after recording that grid into the global map we have to move the robot to get a different grid and puzzle it to the global map again, that was my question, after taking the first grid you have to move the bot to another point, you decided nearest unmapped area,well
moving into that point would be based on the obsticales the first grid had?

its just consider my first grid shown in the pic attached, where would the bot move considering your algorithm?

dunk · « **Reply #7 on:** February 04, 2008, 05:51:14 PM »

Quote

well
moving into that point would be based on the obsticales the first grid had?

i'm afraid i'm struggling with your grammar.
if you are asking "would moving to that point would be based on the obstacles in the first grid?" then yes, of course. that is the whole point.

Quote

its just consider my first grid shown in the pic attached, where would the bot move considering your algorithm?

if that map segment was the first one to be included in the main map then the area directly behind the robot would be un scanned so it would just spin round and scan there.

it is worth noting i will be recording 3 different states for each map cell: empty, occupied and unknown.

dunk.

benji · « **Reply #8 on:** February 04, 2008, 06:22:36 PM »

Quote

i'm afraid i'm struggling with your grammar.

sorry

anyways i kind of made an algorithm that makes a robot moves untill it sees an occupied line and then still walk beside this line untill this line makes a closed line(a wall) in the global map and then it leaves it
so if the line was not a wall(lets say a table or any obstcale) then the robot will walk around the table then leaves it.
this algorithm is very efficient in finding occupied elements first in the global matrix(map) but it still doesnt provide to not map pre-mapped areas
,,maybe i can develop the states to make em 3 instead of 2 (adding the state of known and unknown)
ill see if thats possible.....

dunk · « **Reply #9 on:** February 04, 2008, 06:45:20 PM »

Quote

,,maybe i can develop the states to make em 3 instead of 2 (adding the state of known and unknown)

yea, i should have said that before.
when i was describing how to find the bot's nearest unmapped area you need to have recorded not only where obstacles are but also where empty spaces are so it knows which bits it has mapped already.

if your sensors can see a wall 1meter away it's a reasonable assumption that all the map cells between the bot and the wall are empty so you can record them as empty.
if you know you sensors are fairly accurate to a distance of 2m and your sensor is not seeing any obstacle in a particular direction then it is safe to presume all cells in that direction are empty out to a distance of 2m.

dunk.

benji · « **Reply #10 on:** February 05, 2008, 07:21:53 AM »

Quote

if your sensors can see a wall 1meter away it's a reasonable assumption that all the map cells between the bot and the wall are empty so you can record them as empty.

sure thats the way im buiiding my grid

but you have a problem when the still un-mapped area is not a rectangular (or the size of your matrix) then you have to modify the algorithm to make the robot orient itself so the unmapped area would be all mapped its somthin like this (WHITE: unmapped , BLACK: mapped)

benji · « **Reply #11 on:** February 05, 2008, 07:26:53 AM »

The thing i just mentioned is just to map the unmapped area in shorter time, u sure still can map it gradually

dunk · « **Reply #12 on:** February 05, 2008, 11:11:36 AM »

Quote

The thing i just mentioned is just to map the unmapped area in shorter time, u sure still can map it gradually

hehe. one step at a time man.
trust me, you will find far more problems along the way before you need to start worrying about that one...

dunk.

benji · « **Reply #13 on:** February 05, 2008, 04:23:02 PM »

yea right,
actually one of the biggest problems im facing is when i want to move my robot to the nearest unmapped location
there would be many ways,
by the way ,do you treat unmapped areas as one global matrix element? or a smaller matrix?
treating it as an element would lead to when
trying to approach this unmapped element there would be multiple ways (i mean the robot can be oriented in many angles looking at this
unmapped element(blue))
considering you choose the shortest path(yellow)(or an obstacle(gray) in the stright path) then the bot would be oriented lets say 35 degrees looking at this element
so moving this robot back into its 0 degree orientation when you reach the destination(rose) would be kind of a stupid step....
but if i wanna avoid this step then my second scan would be oriented also and thus the same algorithm would fail so you need a new decent algorith to treat matrix with respect to their angles, things owuld get shittier.... $:-\$

with what angles do you approach your destination? only 0 90 180 270 ?

benji · « **Reply #14 on:** February 06, 2008, 10:48:46 AM »

by the way , considering this reach for your closest unmapped area will get your algorith just sickier and sickier cuz the robot is able to turn more than just 90 degrees........

anyways im developing a new algrithm and till now it seems to work
it when the robot sees an obstacle it goes near it and walk around it untill this obstacle make a closed line then it leaves it
,thats because every obstacle is a closed line in the map
after it makes a closed line it leaves this obstacle and mark it as mapped and go to search for a new line to follow(or walk nearby )
in case that this line is a wall then its gonna make a closed line too and then the bot will leave it with the same algorithm
.... it still need some more work to handle some awkward situations

Admin · « **Reply #15 on:** February 17, 2008, 09:29:51 AM »

benji, I know you are aware of this tutorial, but I'm going to post it again because it answers/solves every question you just asked in this thread

http://www.societyofrobots.com/programming_wavefront.shtml

benji · « **Reply #16 on:** February 17, 2008, 12:09:11 PM »

admin, dnt get me wrong but i cannot go with the wavefront cuz its made for 90 degrees turns only,my bot is capable of making turns
as small as 5 degrees, i searched for algorithms that makes this possible but the algorithm would be very complicated
so i decided to give up this precise turns and be ok with 45 degrees turns only

i would be more glad to use the wavefront as soon as i get it to work with 45 d turns
cuz certainly it would be a lot easier to implement compared to A*

another stuff about wavefront:
it wouldnt be able to smooth its path so we need to add another algorithm for that ,while A* can with little modding.

i cannot give up the turning issue cuz actually in my project the cost G is battery power and not distance
so im trying to reach my goal with less battery consumption and that would be avoiding turns cuz its a hexapod.

Admin · « **Reply #17 on:** February 17, 2008, 12:48:13 PM »

Well if you want the most optimal path, you want to use D*

benji · « **Reply #18 on:** February 17, 2008, 01:00:03 PM »

Quote

you want to use D*

as long as i l know D* is the same as A* but made for dynamic environments
,mine is static,,,,can it add other things?

Admin · « **Reply #19 on:** February 17, 2008, 02:46:03 PM »

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

benji · « **Reply #20 on:** February 17, 2008, 05:00:45 PM »

should i learn this one? can you tell me what makes it better than A*?

Admin · « **Reply #21 on:** February 23, 2008, 02:14:34 PM »

Well, D* doesn't require the world to be grid shaped. It can account for objects of any shape, too, not just squares. Movement no longer is constrained to a grid, but can now allow for any robot angle/speed.

benji · « **Reply #22 on:** February 23, 2008, 04:41:20 PM »

well im really glad with A* with too many mods to make it work for my bot
i started to build my functions over matlab

ryan · « **Reply #23 on:** August 16, 2008, 11:30:41 AM »

This thread is very information, I'm trying to learn wavefront algorithm too to implement in my project

JesseWelling · « **Reply #24 on:** August 16, 2008, 05:34:42 PM »

Admin, you are talking about Field D* which interpolates the best path between each grid coordinate. Normal D* is still grid based. A common architecture is to use Coarse D* for the 'world path planer' with a 'local path planner' such as Vector Field Histogram (VFH or VFH+) or Nearnes Diagrams (ND). So the D* says which grids to go to but the VFH or ND keeps your robot from moving in a straight grid lines or running in to corners of objects. The trick there is to make the D* grid small enough so that the robot can squeeze through gaps, but still maintain the computational advantage of the dual layer system (VFH works runs on a smaller grid).

For example, Use a D* grid square size of 10-20cm with the global map as big as it has to be, with a VFH as a 1 meter local map with 1cm grid squares. But what you will be able to do reasonably will depend on your the MIPS your processor is capable of. Such is the world of AI....

Admin · « **Reply #25 on:** August 22, 2008, 11:44:49 AM »

The most advanced D* I've seen didn't use a grid. It looked like a snow flake growing inside a maze, where resolution was controlled by the number of new branches created per unit distance.

I assume with this method, resolution can be variable. Increase resolution until a solution is found . . .

JesseWelling · « **Reply #26 on:** August 22, 2008, 02:08:36 PM »

I think i've got the paper on that if you like.

benji · « **Reply #27 on:** August 25, 2008, 05:31:15 AM »

look for D* lite

News:

Author Topic: grid infront (Read 5456 times)

Related Topics