Occupancy Grid - beginner

[activex]

Hi

If I want to make occupancy grid, what are the steps I have to do. Prefer C# or psuedocode algorithm

Thanks

[activex]

Hi

So I initialize a matrix of 17x17.
I am initializing my self at [8,0] -> to represent myself at 0,0.
I use a laser range finder to find the surrounding objects.
And then I map it over to the matrix cells.
The picture attached is an example of the 180 degrees front view which all blocked by walls 8 meters ahead, 8 meter to the left, and 8 meter to the right. The 1 represent wall. The 0 means empty. Note, the map should be 16x16 meter, not 8x8 meter.

My problem is,
If i make another pose, how can i update the new info onto the existing map? or, how to enable the map to expand to radially.

[Mr. Ninja]

From my understanding (which is, to say the least, very small) of two-dimensional arrays, what you could do is set a variable to each of the axis (x for the x-axis and vice versa) and add or subtract to the variable to locate your position. Every time it was moved, you would remap it to the occupancy grid. (I would think)

[activex]

does someone know where to find a source code or nice tutorial on making occupancy grid

thanks

[jwatte]

I see two problems here. One is that you seem to center the map on (0, instead of (8, . The other is that you're using a fixed-size array, but then want to expand it.

I'd recommend implementing your grid as a "sparse array." When you detect an obstacle, insert that grid cell as "blocked" in the array. The array starts out empty. A sparse array is easiest to implement as a hash table where the key is struct { public int x; public int y; }. The good news with this is that it can be as large as you want; just keep adding blocked cell coordinates to it. To check whether a cell is blocked or not when searching, just check whether the cell in question is in the hash table.

Also, it seems as if you insert "blocked" when the range finder returns the maximum value. It's better to treat this as "unknown" and only insert blocking information when you have positive confirmation that a cell is blocked (a reading shows that it's significantly closer than the max range, for more than one cycle, say.) Also, you want to keep an estimate of likelihood that something is blocked; add 1 to the "blockedness value" of a cell rather than just using a boolean, and don't mark the cell as fully blocked until you get N positive confirmations that it's blocked. Over time, slowly decay the blockedness value, so that things that can move, will eventually go away from the map. Also, you may be able to remove (or decrement) cells from the table when you get a reading that shows that that cell is now non-blocked.

Finally, an equally hard problem is to correlate the sensor reading to real world. What exact direction is the sensor pointing in? What exact direction is the bot pointing in? What exact position does the bot have in world space? How does this change as the robot moves around? Using good IMU and GPS sensors as well as movement wheel/motor sensors is pretty much required.