Society of Robots - Robot Forum

Software => Software => Topic started by: Admin on August 12, 2007, 08:44:17 AM

Title: Wavefront propagation source code
Post by: Admin on August 12, 2007, 08:44:17 AM
Ive looked everywhere to find some basic wavefront propagation source code but no luck . . .

I can do the propagation with paper/pencil, but I cant figure out how to code that up.

Anyone have ideas?

The best I can find is this:
http://www.mines.edu/Stu_life/projects/trulla/
But it is far from efficient for use on a microcontroller . . . and its too messy for me to make any sense of it . . .
Title: Re: Wavefront propagation source code
Post by: Admin on August 29, 2007, 07:00:02 AM
Ok so oddly there is ZERO source code for a basic wavefront on the web, despite it being a 40 year old algorithm . . . so Im writing my own.

Ive had decent success. But ran into a strange problem. This is an example of it working:
Quote
Starting Wavefront

Old Map:
0 W 0 0 0 W
0 W 0 0 0 0
0 W 0 0 W 0
0 W 0 0 0 0
0 5 4 3 2 0
0 0 0 0 0 0

Starting Unpropagate
Unpropagation Complete:
0 W 0 0 0 W
0 W 0 0 0 0
0 W 0 0 W 0
0 W 0 0 0 0
0 0 R 0 0 0
0 0 0 0 0 0

Adding Goal:
0 W 0 0 0 W
0 W 0 0 0 0
0 W 0 G W 0
0 W 0 0 0 0
0 0 R 0 0 0
0 0 0 0 0 0

Finished Wavefront:
0 W 0 0 0 W
0 W 0 0 0 0
0 W 2 G W 0
0 W 3 0 0 0
0 0 R 0 0 0
0 0 0 0 0 0

Now with different robot/goal locations, this is an example of it not working. Notice the mysterious numbers appear on the very left row in sweep #0.

Quote
Starting Wavefront

Old Map:
0 W 0 0 0 W
0 W 0 0 0 0
0 W 0 0 W 0
0 W 0 0 0 0
0 5 4 3 2 0
0 0 0 0 0 0

Starting Unpropagate
Unpropagation Complete:
0 W 0 0 0 W
0 W R 0 0 0
0 W 0 0 W 0
0 W 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Adding Goal:
0 W 0 0 0 W
0 W R 0 0 0
0 W 0 G W 0
0 W 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Sweep #: 0
0 W 0 0 0 W
0 W R 2 3 4
5 W 2 G W 5
6 W 3 2 3 4
5 0 4 3 4 5
6 0 5 4 5 6

Finished Wavefront:
0 W 0 0 0 W
6 W R 2 3 4
7 W 2 G W 5
6 W 3 2 3 4
7 5 4 3 4 5
8 6 5 4 5 6

And different locations again, with the same mysterious numbers:

Quote
Starting Wavefront

Old Map:
0 W 0 0 0 W
0 W 0 0 0 0
0 W 0 0 W 0
0 W 0 0 0 0
0 5 4 3 2 0
0 0 0 0 0 0

Starting Unpropagate
Unpropagation Complete:
0 W 0 0 0 W
0 W R 0 0 0
0 W 0 0 W 0
0 W 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Adding Goal:
0 W 0 0 0 W
0 W R 0 0 0
0 W 0 0 W 0
0 W 0 G 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Sweep #: 0
0 W 0 0 0 W
0 W R 0 0 0
0 W 0 2 W 0
0 W 2 G 2 3
4 0 3 2 3 4
5 0 4 3 4 5

Sweep #: 1
0 W 0 0 0 W
0 W R 3 4 5
6 W 3 2 W 4
5 W 2 G 2 3
4 4 3 2 3 4
5 5 4 3 4 5

Finished Wavefront:
0 W 0 0 0 W
7 W R 3 4 5
6 W 3 2 W 4
5 W 2 G 2 3
5 4 3 2 3 4
6 5 4 3 4 5

Go DOWN

This is the relevent code:
Code: [Select]
int map[6][6]= {{0,255,0,0,0,255},
{0,255,0,0,0,0},
{0,255,0,0,255,0},
{0,255,0,0,0,0},
{0,5,4,3,2,0},
{0,0,0,0,0,0}};

int main(void)
{
//declare robot location and start propagation
min_node_location=propagate_wavefront(1,2);
}

int propagate_wavefront(int robot_x, int robot_y)
{
//clear old wavefront
unpropagate(robot_x, robot_y);

//start location to begin scan at goal location
map[3][3]=goal;

while(counter<20)//allows for recycling until robot is found
        {
        x=0;
        y=0;
    while(x<6 || y<6)//while the map hasnt been fully scanned
    {
    //if this location is a wall or the goal, just ignore it
    if (map[x][y] != wall && map[x][y] != goal)
    {
    //a full trail to the robot has been located, finished!
    if (min_surrounding_node_value(x, y) < reset_min && map[x][y]==robot)
    {
                printf("Finished Wavefront:\n");
                print_map();
    //tell robot to start moving down path
    return min_node_location;
    }
    //record a value in to this node
    else if (minimum_node!=reset_min)//if this isnt here, 'nothing' will go in the location
    map[x][y]=minimum_node+1;
    }
   
    //go to next node and/or row
    x++;
    if (x==6 && y!=6)
    {
    y++;
    x=0;
    }
    }
   printf("Sweep #: %d\n",counter);
      print_map();
   counter++;
        }
 return 0;
}

//this function looks at a node and returns the lowest value around that node
int min_surrounding_node_value(int x, int y)
{
minimum_node=reset_min;//reset minimum

//right
if(x < 5)//not out of boundary
if  (map[x+1][y] < minimum_node && map[x+1][y] != nothing)
    {
minimum_node = map[x+1][y];
min_node_location=1;
             }

//left
if(x > 0)
if  (map[x-1][y] < minimum_node && map[x-1][y] != nothing)
    {
minimum_node = map[x-1][y];
min_node_location=2;
            }

//top
if(y < 5)
if  (map[x][y+1] < minimum_node && map[x][y+1] != nothing)
    {
minimum_node = map[x][y+1];
min_node_location=3;
            }
           
//bottom
if(y > 0)
if  (map[x][y-1] < minimum_node && map[x][y-1] != nothing)
    {
minimum_node = map[x][y-1];
min_node_location=4;
            }
   
return minimum_node;
}


apologies for the messed up code formatting . . . it didnt transfer over so well . . .

Can anyone find my mistake?
Title: Re: Wavefront propagation source code
Post by: Admin on August 29, 2007, 07:54:53 AM
So I changed this:
Code: [Select]
//go to next node and/or row
x++;
if (x==6 && y!=6)
{
y++;
x=0;
}

to this:
Code: [Select]
//go to next node and/or row
y++;
if (y==6 && x!=6)
{
x++;
y=0;
}

and I have since been unable to reproduce that strange error again. I have no idea why, and I suspect that the error is still hiding in there somewhere . . .
Title: Re: Wavefront propagation source code
Post by: dunk on August 29, 2007, 08:52:23 AM
hey Admin,
so i'm too tired to dig into your code too much right now but there does seem to be a definite pattern in the output.
it appears that as the program gets to the end of each line, it is overlapping into the first value of the next line.

strange that you are not getting the same symptoms now you have changed the scan order.
what about if the goal is above the robot on the map?

dunk.
Title: Re: Wavefront propagation source code
Post by: Admin on August 29, 2007, 09:07:06 AM
Quote
strange that you are not getting the same symptoms now you have changed the scan order.
what about if the goal is above the robot on the map?
I also tried moving the walls around but still couldnt get the same error. I tried with the goal and robot all over the place . . .

I can give you all the code to play around with the map if you want . . .
Title: Re: Wavefront propagation source code
Post by: dunk on August 29, 2007, 09:40:06 AM
heh. i feel your pain.
i was faced with a similar problem a few months ago with my inter ic network protocol.
it turned out to be a buffer overflowing in a certain set of conditions.
perfectly obvious one i had worked out what was going on but brain melting trying to spot where it was happening in the first place.

Quote
I can give you all the code to play around with the map if you want . . .
heh, i'll be too busy with my own mapping algorithm soon.
i finally have my latest bot's hardware and firmware as i want it.
it all becomes a programming challenge from here on which is nice considering how little time i'm at home to work on it.

dunk.
Title: Re: Wavefront propagation source code
Post by: cybcode on August 29, 2007, 10:06:03 AM
I think I figured out exactly what the problem is.

There are 2 mistakes in your code which are both required for the problem to appear:

1. An array defined like this: int map[6][6] should be accessed like this: map[y]
In other words, the "most significant" coordinate should be first. I can tell that in your case, the most significant coordinate is y, by the way you print your array - when printed it looks the same way it does when it's defined. This means the horizontal (x) coordinate is less significant, and the vertical (y) coordinate is more significant (for every single y, there are 6 x's). So you should access your array like this: map[y]

2. You wrote "while (x != 6 || y != 6)". || stands for logical OR. You probably need to replace it with && which is AND.
In your loop, when y becomes 5, x goes from 0 to 5, and then x returns to 0, and y becomes 6. But then the condition is still met, because one of the two coordinates is not 6. So the loop continues when it shouldn't, with y=6. Because we agreed in 1 that you handle your coordinates in reverse, it is actually the horizontal coordinate (which you call "y" by mistake) that becomes 6. In memory, the 6th coordinate in a line is next to the 5th in that line, but it is also the 1st coordinate in the NEXT line. So in the function that looks for a local minimum you look at the 6th coord in a certain line, and place some value in it (because of what's in the 5th coord), but actually you placed that value in the 1st coord of the next line.
When you changed the order of the loop and advanced x instead of y, you no longer see the problem because the 6th position of x (the vertical coord) is completely outside the array (which is still bad).

So, in short, wherever you access the array (except in the print_map function which seems to be fine) you should access it with y first (map[y]
I wrote all the details above because I spent a few minutes figuring out the problem, and it would be a shame if I just told you how to correct it and you'd have to spend more time trying to understand why it works, when I've already done it.
Title: Re: Wavefront propagation source code
Post by: Admin on August 29, 2007, 10:21:12 AM
Quote
You wrote "while (x != 6 || y != 6)". || stands for logical OR. You probably need to replace it with && which is AND.
Thanks! That fixed it! Man, Im a moron . . . That error was also causing my robot software to completely fail outside of simulation, so this also fixed the robot too! :)

Quote
heh. i feel your pain.
i was faced with a similar problem a few months ago with my inter ic network protocol.
it turned out to be a buffer overflowing in a certain set of conditions.
perfectly obvious one i had worked out what was going on but brain melting trying to spot where it was happening in the first place.
I knew something like this would happen, which is why Im simulating it on my computer before transferring the code to the robot . . .

Quote
heh, i'll be too busy with my own mapping algorithm soon.
What kind of mapping algorithm?
(do tell!)

This current wave front algorithm Im working on requires encoders on my robot, but in the future I want to design it so no encoders are required . . . some form of simplified SLAM.

I should have a tutorial with source code on the wavefront algorithm in like a week or so. The very first one to be written for the entire internet (Im trying to feel special right now).
Title: Re: Wavefront propagation source code
Post by: cybcode on August 29, 2007, 10:33:10 AM
My post got a little screwed up. In (1) I meant to say you should access your array like this:

Code: [Select]
map[y][x] = 5;
and not like this:

Code: [Select]
map[x][y] = 5;
Title: Re: Wavefront propagation source code
Post by: snow on August 29, 2007, 01:16:56 PM
Simple floodfill aka wavefront algorithm for micromouse (16x16 size): http://www.micromouseonline.com/forum/viewtopic.php?t=92 (http://www.micromouseonline.com/forum/viewtopic.php?t=92).

Or i got it wrong?
Title: Re: Wavefront propagation source code
Post by: Admin on September 09, 2007, 02:06:41 PM
Ok I finally finished the darn wavefront thing this morning. I really suck at programming sometimes, took me till this morning to figure out the last bug . . . :-\

Anyway, here is the wavefront tutorial I wrote up with source code:
http://www.societyofrobots.com/programming_wavefront.shtml

And a video! With me in it! Its bound to be entertaining . . .
[youtube=425,350]N7zDiSPa3_E[/youtube]
Title: Re: Wavefront propagation source code
Post by: h3ro on September 09, 2007, 02:34:02 PM
That was very cool!

Thank you for even more great tutorials! Cant wait to get my parts so I finally can start some basic stuff to get me started.

I have a few very simple questions about the path finding:
    How do you create the grid? I can see how it could be easily created from a camera above, but how is it done with a IR sensor mounted so low?   
    How do you give it a destination to go to? Is it instructed to simply go 5 units straight ahead or is there something more behind it?

Edit:
   Does it stop to scan or to calculate?
Title: Re: Wavefront propagation source code
Post by: Admin on September 09, 2007, 03:05:17 PM
Quote
How do you create the grid? I can see how it could be easily created from a camera above, but how is it done with a IR sensor mounted so low?
I put an empty matrix (in this case, a 6 x 6 map) in its memory. When it detects an object with a scan, it adds it to the map in memory. Then it recalculates a new path.

Quote
How do you give it a destination to go to? Is it instructed to simply go 5 units straight ahead or is there something more behind it?
I preprogrammed the goal into the map in memory. In reality, the proprogrammed location could be a can of beer in your fridge :P
You could also preprogram multiple goals, and have it chose a particular goal for whatever reason. The source code easily allows this (check the tutorial).

Quote
Does it stop to scan or to calculate?
Both. The scan takes up to a second (depending on what it sees). The calculation takes like .1 seconds. For larger maps it would take longer. I didnt make the wavefront efficient . . . was too lazy . . . whats .1 seconds anyway? :P
Title: Re: Wavefront propagation source code
Post by: h3ro on September 09, 2007, 03:08:55 PM
Thanks for explaining it. One last thing, can the robot move outside the 6x6 matrix? If so, how does it do it? I assume you dont use C, so you dont have direct access to the fast vector structure for example
Title: Re: Wavefront propagation source code
Post by: Admin on September 09, 2007, 03:14:48 PM
Quote
can the robot move outside the 6x6 matrix?
Nope, cause then the software would blow up :P
But I could easily make the matrix much larger (there is more than enough memory) to where the borders are larger than the environment.

Quote
I assume you dont use C
I use C, its my fav language :P

Quote
so you dont have direct access to the fast vector structure for example
a what what? its all done on a microcontroller, so Im limited on fanciness . . .
Title: Re: Wavefront propagation source code
Post by: h3ro on September 09, 2007, 03:26:18 PM
Quote
a what what? its all done on a microcontroller, so I'm limited on fanciness . . .
Its a very powerful dynamic array. 
std::vector <int> variableName

Have you tried to make it work in larger environment?

Maybe have it search its near environment using the 6x6 matrix and have a separate matrix store direction to target? Not sure if it works good or not...

Is matrix manipulation very costly to do?
Title: Re: Wavefront propagation source code
Post by: Admin on September 09, 2007, 05:57:40 PM
Quote
Have you tried to make it work in larger environment?

Not yet . . . mostly been too lazy. I probably should though . . . Ill get on it in the next few days I think. If I dont, it will just sit in the corner until I forget how the code works like all my other old robots . . .

Quote
Is matrix manipulation very costly to do?
So in a typical 6x6 map it sorts through the matrix about 20-30 times per calculation. It depends a lot of obstacle locations, goal location, and start location. I would assume a map with 4x the node number would on average take 4x as long. Perhaps half a second at most?

I didnt implement another method that would halve computational time, but I could.
Title: Re: Wavefront propagation source code
Post by: JesseWelling on September 09, 2007, 06:19:18 PM
About the 90 vs 45 degree angle thing... Look up Field D* by Fergusun and Stentz (http://www.google.com/url?sa=t&ct=res&cd=7&url=http%3A%2F%2Fgs2045.sp.cs.cmu.edu%2Fdownloads%2Ffdstar.pdf&ei=s4rkRsu6NoiUigHJ0oCDDA&usg=AFQjCNEt-t7zbO8_Wj5mhEiUrbTqumUV2g&sig2=whzpjvCDqOKJ2Akq8NhpEA). There is also a multi-resolution Field D* (http://www.google.com/url?sa=t&ct=res&cd=6&url=http%3A%2F%2Fgs2045.sp.cs.cmu.edu%2Fdownloads%2Fmr-fdstar.pdf&ei=s4rkRsu6NoiUigHJ0oCDDA&usg=AFQjCNEDbKO72-OOl-O7892EDfvwK9X2ag&sig2=PZLZK7RdfuogRGE3c-D5vw) that helps with memory and speed requirements in sparse environments. Also, from what I understand D* will be faster at re-planning in large environments but is trickier to implement.
Title: Re: Wavefront propagation source code
Post by: Admin on September 09, 2007, 06:49:01 PM
Im not good enough yet to do D* on a microcontroller :P

The thing with D* is that it requires a nice map, which by definition requires tons of trig . . . which just doesnt work on a microcontroller.
Title: Re: Wavefront propagation source code
Post by: JesseWelling on September 09, 2007, 08:39:52 PM
Not that I want to be contrary or any thing but....
Trig on a Micro isn't that bad as long as you use piece wise linear interpolation.

But yes daunting on a micro none the less...  :-\

Title: Re: Wavefront propagation source code
Post by: Admin on September 09, 2007, 08:52:55 PM
Quote
Trig on a Micro isn't that bad as long as you use piece wise linear interpolation.
hmmmm ok good point . . .

still a heck of a lot of calculations tho . . . there are a few simpler precursers to D* that I could perhaps attempt in the future . . . build up my skills first I think . . .

I definitely learned a lot when doing the wavefront project . . .
Title: Re: Wavefront propagation source code
Post by: MadMax on September 11, 2007, 02:15:53 PM
Hmm, just thinking here... Just an idea...

Use a dynamic array (a vector).. build a compass into your robot and let it run around the house, dynamicly resizing the array (using the sensor and a simple algorithm)  when it:


Build in a small information storeage to remember the information and it last known position. Heck, build in an algorithm to find it's location based on its readings (for example (0 = open, 1 = not-open) : If this is the array, and the robot is at R, make it drive left, check position... 4 steps right, check position, one up check position, two left check positions. If they're all 1, the robot knows where it is...

1   1   1   1   1   1   1   1   1
1   0   0   0   1   0   0   0   1
1   0   R   0   0   0   1   0   1
1   0   0   0   1   0   1   0   1
1   1   1   1   1   0   1   0   1
1   0   0   0   0   0   1   0   1
1   0   0   0   0   0   1   0   1
1   1   1   1   1   1   1   1   1

My $0.02 of brain-food
Title: Re: Wavefront propagation source code
Post by: JesseWelling on September 11, 2007, 03:16:52 PM
Use a dynamic array (a vector).. build a compass into your robot and let it run around the house, dynamicly resizing the array

Dynamic memory is a problem on a micro controller. Thats why I opt for the Linux robot route though :P
Title: Re: Wavefront propagation source code
Post by: MadMax on September 11, 2007, 11:37:25 PM
Ah, sorry, I didn't know that. I still have a lot to learn!
Title: Re: Wavefront propagation source code
Post by: Admin on September 12, 2007, 06:41:07 AM
I think it'd be easier if I just create one giant matrix and just fill in the map as the robot goes. Knowing the size of my bot and the size of my house, I can calculate how big I need the matrix to be. Nothing wrong with using all the memory on a microcontroller if I dont need it all.

Any area on the matrix that is marked as an obstacle requires is basically ignored by my algorithm so as obstacles get added, it will take less and less processing power . . .

Ill try this out the next chance I get . . . Ill try to improve dead-reckoning and operate the bot only on hardwood floors to improve the encoder accuracy.

Here is a question . . . so when the robot cannot find a clear path I have it delete its entire map to start over. This works really well for small maps. But for large maps this is bad because travel/scan time is expensive . . . anyone can think of an intelligent way to rescan previously blocked areas efficiently? A scan takes between .3 and 2 seconds . . . I can think of a few ideas but they all have flaws . . .
Title: Re: Wavefront propagation source code
Post by: HDL_CinC_Dragon on September 12, 2007, 08:08:32 AM
Question 1:
Can you use some external flash or EEPROM memmory on these MCUs? Maybe buy the now cheap 1Gb thumb drives, rig it to work with the MCU, and bingo! Near limitless (relatively :P) memmory for your bot... would something like that work?

Question 2:
Can MCUs handle 3D arrays? Add a height plain to the equation? That would be sweet.
Title: Re: Wavefront propagation source code
Post by: MadMax on September 12, 2007, 10:27:54 AM
Well intelligent? I don't know. Maybe use sinus and cosinus functions together with the angle of your rangefinder? (don't know the range, so if it has a small range, it isn't that effective)
Title: Re: Wavefront propagation source code
Post by: JesseWelling on September 12, 2007, 10:47:58 AM
This is the whole problem I'm having in my design (it's a problem in any map building algorithm)
Adding is easy but to take away intelligently.... that is an issue. I'm on my lunch break so I don't have
time to explain what I'm planning but it will definitely not work on a normal micro on the scale I'm working
but... after work I'll do some explaining...
Title: Re: Wavefront propagation source code
Post by: dunk on September 12, 2007, 11:30:18 AM
Quote
Here is a question . . . so when the robot cannot find a clear path I have it delete its entire map to start over. This works really well for small maps. But for large maps this is bad because travel/scan time is expensive . . . anyone can think of an intelligent way to rescan previously blocked areas efficiently? A scan takes between .3 and 2 seconds . . . I can think of a few ideas but they all have flaws . . .
i haven't implemented this yet but i intend to mark each positive sensor hit with a value dependant on the reliability of the sensor "seeing" it.
i will then degrade all the values over time so eventually the bot will forget about objects it has not seen for a long time.

if a sensor thinks an area is clear where in the past there was an object that positions value will be degraded by an amount depending on the reliability of the sensor.

in this way it may take a few sensor readings that show a position has become clear before a bot trust's it's sensors.

this way of doing things has the nice bonus of helping with the problem of accumulative error in the bot's position.
if correctly calibrated the map will fade as the error relative to those points builds up.


dunk.
Title: Re: Wavefront propagation source code
Post by: Admin on September 12, 2007, 11:50:03 AM
dunk, your idea wont work well for really large maps . . . the forget delay would need to be a function of map size, but i can see cases where:

A) the delay time is guessed/tweaked by the programmer
B) control oscillations from new paths suddenly appearing because of forgetting obstacles
C) moving objects near the robot (highest probability of error) would be the freshest in memory
D) very large maps would need a very long forget delay - or the robot would forget the first half of the map while it explores the second half

Perhaps the solution is not a software thing, but I just need a much faster/better scanning algorithm . . . or maybe i should use beacons so the bot can occasionally realign the map to the world . . .
Title: Re: Wavefront propagation source code
Post by: JesseWelling on September 12, 2007, 04:25:42 PM
My idea is based the certainty grid idea as well.

First consider each map square as the certainty that something is in that square. Every thing starts at 0.
Then as your robot takes a scan you increment all the squares where you measured an object (yes you have to use some trig, look up table/piece wise linear interpretation should be used) But also you decrement every square that is between your robot and it's measurement. And you should probably saturate at around 100.

Of course you aren't going to do an on-line raytrace of each scan line, but you pre-compute each scan line and create an array of references to each square that is passes through, so that if you know the distance to the object you know which squares up to the object you should decrement and then increment the final square.

Of course I'm working on a 400MHz ARM processor so this may not be entirely practical for most people...

This also has the advantage that it works well with noisy sensors because its the add up that counts not the stray reading... Which will get wiped out eventually.

Then you can layer a fast VFH or ND algorithm with a window ( size would depend on your sensor range) for local pathfinding, and over that Layer a D* or wave front for global pathfinding, (global path finder feeds waypoints to local pathfinder, thus the global pathfinder helps the local pathfinder avoid local minima confusion). There are also some clever tricks I plan to play on the D* algorithm because I don't want a brand new plan on every new piece of data, so I'll only force a re-planning if the lateral path error from last waypoint to next waypoint (cause by the local path planner avoiding objects) exceeds a certain threshold.

That's the rough Idea I've been working together but it does have the weakness of not being able to find new openings where there were previously none because the local planner will go straight to the new waypoint and never exceed the later path error threshold... So I think I need to keep track of a rough delta value and if a square changes from saturation (100 or whatever) to near 0 in a short amount of time, I need to force a re-plan of the global path planner.

hows all that sound to you guys? :-[
Title: Re: Wavefront propagation source code
Post by: HDL_CinC_Dragon on September 12, 2007, 05:05:40 PM
OO! Question! Admin! Pick me! PICK ME!

Can it scan more than just 1 grid spot away if it had a longer distance rangefinder? So instead of scanning 1 grid locale away, it can scan 2 grid locations?
Title: Re: Wavefront propagation source code
Post by: JesseWelling on September 12, 2007, 05:12:19 PM
HDL: Wouldn't that be a function of the dimensions of the grid vs the distance of your sensors?
Title: Re: Wavefront propagation source code
Post by: dunk on September 12, 2007, 06:03:05 PM
Quote
dunk, your idea wont work well for really large maps . . . the forget delay would need to be a function of map size, but i can see cases where:

A) the delay time is guessed/tweaked by the programmer
B) control oscillations from new paths suddenly appearing because of forgetting obstacles
C) moving objects near the robot (highest probability of error) would be the freshest in memory
D) very large maps would need a very long forget delay - or the robot would forget the first half of the map while it explores the second half

i don't see why you have an issue with large maps as long as the forget delay is indeed a function of map size.
the degrading of occupancy probability should be very gradual compared to the input from sensors (positive or negative).
map points should only really be degraded when they can no longer be trusted. this will indeed require some tweaking by the programmer, but then what doesn't?
bear in mind, like JesseWelling, i'll be running this on something with a lot more power than your average microcontroller so i'm not really exploring the time involved or memory constraints which large maps involve in this discussion. (which i probably should be as that's where the conversation started....)

for point C), that is precisely why sensor readings are cumulative.
presumably an object moving through the field of view will create more "empty" readings than "occupied" ones so the average will be "empty".

point B) is valid but there have to be some challenges left to solve....


dunk.
Title: Re: Wavefront propagation source code
Post by: paulstreats on September 12, 2007, 06:10:19 PM
Question 1:
Can you use some external flash or EEPROM memmory on these MCUs? Maybe buy the now cheap 1Gb thumb drives, rig it to work with the MCU, and bingo! Near limitless (relatively :P) memmory for your bot... would something like that work?


You can use flash etc.. with an mcu with some time and effort but you must beware of their limitations....
I had a call 6 months ago by an accountant friend of mine saying that he had a usb flash stick that was 128mb (small but still..) but he had only used 7mb of space on the device and it wouldnt let him save anymore. After about 1hr of playing about, i realised the problem was that although his files were small, the device could only hold 256files regardless of its size i.e. they have a smallish allocation table that wouldnt really be suitable for storing arrays. Most memory devices operate in this way by allowing you to program a certain amount of information within predetermined spots ie 256 data areas allowing 1mb of data = 256mb - but you cant have 512 data areas of half a mb. Some algorythms need to be created to store more than one array segment to any area in external ram.

Im currently working on this because i think it is an important part of using and storing sensor data.
Title: Re: Wavefront propagation source code
Post by: paulstreats on September 12, 2007, 08:36:12 PM
So i know that the propogation type software can only work if your robot knows how far its actually moved in a particular direction...

I did have some systems set up to evaluate and move a robot built for my virtual robot software, but after reading this thread and the tutorial and therefore thinking about the subject more, there is a difference between my virtual robot moving forwards 5 pixels and a real robot moving forwards any distance since you can see motors/servos move and unless you have encoders etc.. you dont get linear motion if any at all. To overcome this, ive just bought some accelerometers which will probably need an mcu on their own to coordinate properly....

My idea is similar to dunks with a degrading occupancy, but im also playing with a moveable grid system. Where you break an area down into the grid, if the robot moves 2pixels left then the grid does also. So the map is not set into statically defined boundaries which means that youre robot isnt either(obviously waypoints have to be reconfigured also).... It seems to work within my predefined space with my virtual robot, but you would need an infinity system to work in the real world so im looking back to some of my theory programming projects like 'langtons ant' to see how it defines space within a processor, Ive got a few ideas but none that i want to stick with at the moment.

Its certainly a deeper subject than what i first thought :o
Title: Re: Wavefront propagation source code
Post by: h3ro on September 13, 2007, 02:29:53 AM
Quote
You can use flash etc.. with an mcu with some time and effort but you must beware of their limitations....
I had a call 6 months ago by an accountant friend of mine saying that he had a usb flash stick that was 128mb (small but still..) but he had only used 7mb of space on the device and it wouldnt let him save anymore. After about 1hr of playing about, i realised the problem was that although his files were small, the device could only hold 256files regardless of its size i.e. they have a smallish allocation table that wouldnt really be suitable for storing arrays. Most memory devices operate in this way by allowing you to program a certain amount of information within predetermined spots ie 256 data areas allowing 1mb of data = 256mb - but you cant have 512 data areas of half a mb. Some algorythms need to be created to store more than one array segment to any area in external ram.

Would it be better to use a small HD from a laptop? They are not that much bigger, but would they work with a microcontroler?
Title: Re: Wavefront propagation source code
Post by: JesseWelling on September 13, 2007, 06:06:05 AM
h3ro: They use use more power than you'd like for a mobile robot.

CF cards are way better because they use IDE interface so they are pretty much a standard HD,
But they use way less power, and there is no 'seek' time because there is no spinning disk.
And there is no limitation on how you can use the space because it is a HD, and not usb mass
storage interface. But then if you are using a micro, you have to write (or port) your own file
system if you have more than one map  :P

I think we are rambling off topic a bit though...
Title: Re: Wavefront propagation source code
Post by: Admin on September 13, 2007, 08:31:45 AM
jesse . . . yea your algorithm is crazy processor/memory intensive, but its interesting how you are solving it. the latest in SLAM technology is comparing old maps to new maps and then match fitting through probability to prevent drift. its all still complicated for me, but im learning!

Quote
Can it scan more than just 1 grid spot away if it had a longer distance rangefinder? So instead of scanning 1 grid locale away, it can scan 2 grid locations?
i didnt implement this from laziness, but yes its more than possible and it would be more optimal too. but the problem is that you cant scan behind other objects, so its not very useful in very cluttered environments.

Quote
for point C), that is precisely why sensor readings are cumulative.
presumably an object moving through the field of view will create more "empty" readings than "occupied" ones so the average will be "empty".
for a map that drifts with encoder errors, cumulative sensor readings arent very useful . . . if i can prevent the drift then this will work for stationary vs moving objects very well.

Quote
but im also playing with a moveable grid system. Where you break an area down into the grid, if the robot moves 2pixels left then the grid does also. So the map is not set into statically defined boundaries which means that youre robot isnt either(obviously waypoints have to be reconfigured also)....
very interesting idea! i think this can be added to my wavefront with very little effort, too! hope you dont mind me 'borrowing' your idea :P
hmmmm thinking a bit more . . . when you shift the grid, new empty squares come in possibly giving a false clear path. will probably still need to use a large map to negate that possibility. and the other problem, way points. perhaps just count the travel distance, and then use other sensors to find the goal visually?


as for the other ideas about using a thumbdrive and harddrive . . . interfacing them requires a PC, negating the need for a microcontroller being the primary processor . . .
Title: Re: Wavefront propagation source code
Post by: MadMax on September 13, 2007, 04:06:56 PM
use somekind of threshold variable...

for example (I've got no idea how to implent the 2pixels of thing)

Code: [Select]

bool CheckOffset() {
  if (pixelsAwayFromGrid > threshold ) {
    //lets assume the grid is 5x5
    //and because I'm lazy, I only have the algorithm to move the map to the right (compass sensor could fix it)
    for (int x = 4; x >= 0; x--) {
      for (int y = 0; y < 5; y++) {
        int otherX;
        if (x + 1 > 4) {
          otherX = 4;
        } else {
          otherX = x + 1;
        WavefrontArray[otherX][y] = WavefrontArray[x][y];
      }
    }
    return true;
    pixelsAwayFromGrid = 0;
  } else {
    return false;
  }
}

void main() {
  //something happens so you need to call the function
  if (CheckOffset() == true) {
    do some scanning
  } else {
    // or not
  }
}

maybe you could check it's position in between... For example, if you knew that on the original left border of the map their should be a wall, you could check if it's the same image.
Title: Re: Wavefront propagation source code
Post by: paulstreats on September 13, 2007, 04:23:08 PM
Quote
as for the other ideas about using a thumbdrive and harddrive . . . interfacing them requires a PC, negating the need for a microcontroller being the primary processor . . .
 
 

ive just ordered som i2c compatable eeprom to help with data storage. I couldnt find anywhere to buy any normal ram chips but i know they exist because ive used them once before
Title: Re: Wavefront propagation source code
Post by: JesseWelling on September 13, 2007, 04:59:26 PM
admin: I'm not really doing any thing that hasn't been done before, it's just how I'm putting the big blocks together that's different. So the map aging and how VFH and D* work together is new.

You should check out VFH because it has the whole slidding window over the environment too, which I might implement as having finner granularity (4cm x 4cm) for VFH and then bigger squares for the global path planner to reduce memory (1m x 1m). I've also found a paper on dynamic resolution for field D* which would be good for sparse environments, but I'm still reading through field D* and wrapping my mind around it.

About the SLAM statistical matching, I'm not so interested in in mapping as I am Object avoidance and pathfinding so I'm going with a simple (or more simple) solution for mapping. But for localization, because of where I work, I'm willing to work more on signal processing, so I plan on working out an encoder/IMU/GPS system to get better accuracy.
Title: Re: Wavefront propagation source code
Post by: paulstreats on September 13, 2007, 06:13:27 PM

hmmmm thinking a bit more . . . when you shift the grid, new empty squares come in possibly giving a false clear path. will probably still need to use a large map to negate that possibility. and the other problem, way points. perhaps just count the travel distance, and then use other sensors to find the goal visually?


 2 map are definately needed - 1 infinite scale map and 1 small scale (current area) map, which need to update each other accordingly.
Since the large scale map will likely start at 0x - 0y it is possible to travel below these coordinates so there needs to be some way of storing this data outside of a predefined array. this is not a necesarry step but something that would make the program more universal.
using int variables rather than bits will allow for more than just detecting an obstacle in the map, you can also record a different variable for a light spot etc (photovore) and the ability to set way points on the large scale map.
part of my interest in this is to build it as a character trait of my robot - to explore uncharted territory when bored.
I hope to be able to send my map data to a lcd screen so i can actually see the world that the robot sees, if not it can be retrieved with hyper terminal and fed into a custom java app.

I hope to have wavefront and mapping systems on my robot in about 4 weeks (with the bored - explore)
Title: Re: Wavefront propagation source code
Post by: Ro-Bot-X on September 14, 2007, 10:25:57 AM
There was a game called Diablo. It was an isometric view from behind the character, the place was some underground dungeon. The game had a map that revealed to the character by exploring the area. After geting far from some visited parts of the map, something like a fog would cover it. The walls remained, but other creatures would became invisible. Only the line of sight was visible completly.

I think something like this should be in our robot too. There is the line of sight (camera plus sonars and infrared), so that part of the map is actively updated. This should be the small map, with a finer grid. As the robot travels, the big map will became larger with the newly explored part. On the old visited part the clutter can fade away but the walls should stay in place.
Title: Re: Wavefront propagation source code
Post by: kshv01 on August 13, 2011, 02:40:39 AM
Hello all,

i am currently working on a project for one of my uni's course units. it involves making a robot that needs to move from its base in a 2mx2m arena, and then when let loose it has to go and find small polystyrene balls which have been scattered around in the arena.

can i use the wavefront algorithm to actually do this? i have already got my IR rangefinders etc etc. now it's the coding part. so how would i actually have to come up with that if i am to use the wavefront algo? coz instead of ignoring an obstacle detected, i have to actually go and get it and then the aim is to get the polystyrene balls and then come back to the base the robot was launched from.

i would appreciate if someone could help!

Thank you !!

please see an image of the arena attached. i must point out here, that the balls are gonna be scattered anywhere over the place and not placed in the center as shown in the picture.
Title: Re: Wavefront propagation source code
Post by: Admin on August 15, 2011, 12:06:22 PM
Nah, the wavefront is best for cluttered areas. What you'd want is called the bug algorithm (https://encrypted.google.com/search?sourceid=chrome&ie=UTF-8&q=robot+bug+algorithm), which is much simpler and easier to learn.
Title: Re: Wavefront propagation source code
Post by: kshv01 on August 17, 2011, 09:00:48 AM
thanks admin!

btw, have you got any good sources or references which i could have a look at.. google doesnt give a lot of help..

Thanks
Title: Re: Wavefront propagation source code
Post by: Admin on August 20, 2011, 12:00:51 PM
The bug algorithm is nothing more than photovore + obstacle avoidance.

Sensor(s) move your robot to a specific object, while another sensor says 'something is in the way, go around it first'.

pseudocode:
look for object to get
if object on left, turn left
if object on right, turn right
if object straight ahead, go straight ahead
if wall in the way, turn left