go away spammer

Author Topic: Wavefront propagation source code  (Read 18637 times)

0 Members and 1 Guest are viewing this topic.

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,703
  • Helpful? 173
    • Society of Robots
Wavefront propagation source code
« 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 . . .

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,703
  • Helpful? 173
    • Society of Robots
Re: Wavefront propagation source code
« Reply #1 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?

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,703
  • Helpful? 173
    • Society of Robots
Re: Wavefront propagation source code
« Reply #2 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 . . .

Offline dunk

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 1,086
  • Helpful? 21
    • dunk's robot
Re: Wavefront propagation source code
« Reply #3 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.

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,703
  • Helpful? 173
    • Society of Robots
Re: Wavefront propagation source code
« Reply #4 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 . . .

Offline dunk

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 1,086
  • Helpful? 21
    • dunk's robot
Re: Wavefront propagation source code
« Reply #5 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.

Offline cybcode

  • Jr. Member
  • **
  • Posts: 18
  • Helpful? 0
Re: Wavefront propagation source code
« Reply #6 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]
  • = 5;

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]
  • = 5. Not the other way around.


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]
  • ). And change the || condition into a && condition. It doesn't matter in what order you advance the coords.

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.

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,703
  • Helpful? 173
    • Society of Robots
Re: Wavefront propagation source code
« Reply #7 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).

Offline cybcode

  • Jr. Member
  • **
  • Posts: 18
  • Helpful? 0
Re: Wavefront propagation source code
« Reply #8 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;

Offline snow

  • Full Member
  • ***
  • Posts: 73
  • Helpful? 0
Re: Wavefront propagation source code
« Reply #9 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.

Or i got it wrong?
« Last Edit: August 29, 2007, 01:21:08 PM by snow »

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,703
  • Helpful? 173
    • Society of Robots
Re: Wavefront propagation source code
« Reply #10 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]

Offline h3ro

  • Full Member
  • ***
  • Posts: 110
  • Helpful? 0
Re: Wavefront propagation source code
« Reply #11 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?
« Last Edit: September 09, 2007, 02:35:41 PM by h3ro »

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,703
  • Helpful? 173
    • Society of Robots
Re: Wavefront propagation source code
« Reply #12 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

Offline h3ro

  • Full Member
  • ***
  • Posts: 110
  • Helpful? 0
Re: Wavefront propagation source code
« Reply #13 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

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,703
  • Helpful? 173
    • Society of Robots
Re: Wavefront propagation source code
« Reply #14 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 . . .

Offline h3ro

  • Full Member
  • ***
  • Posts: 110
  • Helpful? 0
Re: Wavefront propagation source code
« Reply #15 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?

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,703
  • Helpful? 173
    • Society of Robots
Re: Wavefront propagation source code
« Reply #16 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.

Offline JesseWelling

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 707
  • Helpful? 0
  • Only You Can Build A Robot!
Re: Wavefront propagation source code
« Reply #17 on: September 09, 2007, 06:19:18 PM »
About the 90 vs 45 degree angle thing... Look up Field D* by Fergusun and Stentz. There is also a multi-resolution Field D* 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.

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,703
  • Helpful? 173
    • Society of Robots
Re: Wavefront propagation source code
« Reply #18 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.

Offline JesseWelling

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 707
  • Helpful? 0
  • Only You Can Build A Robot!
Re: Wavefront propagation source code
« Reply #19 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...  :-\

« Last Edit: September 09, 2007, 08:42:07 PM by JesseWelling »

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,703
  • Helpful? 173
    • Society of Robots
Re: Wavefront propagation source code
« Reply #20 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 . . .

Offline MadMax

  • Full Member
  • ***
  • Posts: 58
  • Helpful? 0
Re: Wavefront propagation source code
« Reply #21 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:

  • sees an open spot
  • is at the border of the pre-programmed array

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

Offline JesseWelling

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 707
  • Helpful? 0
  • Only You Can Build A Robot!
Re: Wavefront propagation source code
« Reply #22 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

Offline MadMax

  • Full Member
  • ***
  • Posts: 58
  • Helpful? 0
Re: Wavefront propagation source code
« Reply #23 on: September 11, 2007, 11:37:25 PM »
Ah, sorry, I didn't know that. I still have a lot to learn!

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,703
  • Helpful? 173
    • Society of Robots
Re: Wavefront propagation source code
« Reply #24 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 . . .

Offline HDL_CinC_Dragon

  • Supreme Robot
  • *****
  • Posts: 1,261
  • Helpful? 5
Re: Wavefront propagation source code
« Reply #25 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.
United States Marine Corps
Infantry
Returns to society: 2014JAN11

Offline MadMax

  • Full Member
  • ***
  • Posts: 58
  • Helpful? 0
Re: Wavefront propagation source code
« Reply #26 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)

Offline JesseWelling

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 707
  • Helpful? 0
  • Only You Can Build A Robot!
Re: Wavefront propagation source code
« Reply #27 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...

Offline dunk

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 1,086
  • Helpful? 21
    • dunk's robot
Re: Wavefront propagation source code
« Reply #28 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.

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,703
  • Helpful? 173
    • Society of Robots
Re: Wavefront propagation source code
« Reply #29 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 . . .

 


Get Your Ad Here

data_list