# Occupancy Navigation "The Great Walls of LMR"

Picture the scene :-

• Red cone is direction your Robot is pointing in.
• Coloured boxes are for the moment "Virtual could-be or could-not be walls"
• Whole square cell is say 10x10 cms
• We are working with binary values so a clear brain is needed.

Now keep the next concept in mind :-

We are using 1 Byte of data split into High&Low nibbles (4 bits=1 nibble)

1. Lower nibble  from  xxxx0000  to   xxxx1111      Logic 0 = cell direction not tested ...Logic 1 = cell direction tested
2. Higher nibble from  0000xxxx   to  1111xxxx      Logic 1 = object/Wall in this direction detected.

Each wall has a binary weighting :-

• North virtual Wall - when direction is Clear  = 1      ie  00000001      when object detected Object  =  00010000
• East virtual  Wall                            Clear  = 2      ie  00000010                                      Object  = 00100000
• South virtual                                    Clear = 4      ie  00000100                                      Object =  01000000
• West virtual                                    Clear  = 8      ie  00001000                                      Object =  10000000

The lower nibble xxxx0000 is used as a flag to tell that the direction in that cell has been tested, this will come in handy when we want to check later to see if we have missed any mapping data, ie if bit is set to 1 then its been already tested, if bit is set to 0 then this means it has not been tested.

The Higher nibble 0000xxxx is used as a flag indicating an object or wall has been found in that direction.

Here is a walkthrough of a possible scan.

Caution :- The coloured NSWE walls are "Phantom walls" until tested....

This is called the base position (Virgin cell) and is assigned an initial value = %00000000

.

For the moment we will assume that the robot is in a wide open space (no objects near).

Current robot position CellValue = %00000000

1. The robot tests the North direction..its Clear ..... so CellValue=CellValue OR %00000001  (ie  brand 1 to CellValue)
2. Rotate 90° and tests East direction ....Clear ...... so CellValue=CellValue OR %00000010 (     brand  2 to CellValue)
3. Rotate 180° & tests South direction ....Clear .....So CellValue=CellValue OR %00000100 (     brand  4 to CellValue)
4. Rotate 270 & tests West direction ......Clear ..... So CellValue=CellValue OR %00001000 (     brand  8 to CellValue)
5. Robots rotates to 360° and moves forward to next cell ...... and repeats back to step 1

Step 1.

Step 2.

Step 3.

Step 4.

Summary :- CellValue=%00001111    what does this mean ? .

It means no object was found in direction North (bit 1) , no object found East (bit 2),South (bit 3), or West (bit4)

Now lets run that again but put some objects in the way...

Example 1 , object/Wall in the South direction :-

As before we start testing in  the North direction, this is clear so CellValue=CellValue OR %00000001 (to tag it as already tested)

Same is true to East direction, all clear so tag as tested CellValue=CellValue OR %00000010       (so CellValue=%00000011)

Now when South is tested it detects an object , South Cell as an object detected weighting of 64 ,so CellValue=CellValue OR %01000000   (now CellValue=%01000011

South Cell also needs to be tagged as tested so CellValue=CellValue OR %00000100   (now CellValue=%01000111)

Finally the West direction is tested ,all clear so the last tested flag is set CellValue=CellValue OR %00001000

End result is CellValue=%01001111

Summary :- what does this mean ?

It means an object was found in South direction (bit 7 ) , no object found East (bit 2),South (bit 3),West (bit4), all tagged in lower nibble as being tested.

One more for luck ..... if you understand and follow this then a well deserved Pat on the back is called for.......

Testing direction North gives a clear view of site so CellValue=CellValue OR %00000001

The East Direction is blocked by a wall so CellValue=CellValue OR %00100000, also tag it as being tested CellValue=CellValue OR %00000010   (so CellValue=%00100011)

The South Direction  is also blocked CellValue=CellValue OR %0100000, also needs to be tagged as tested CellValue=CellValue OR %00000100   (so CellValue=%01100111)

The West is also Blocked so CellValue=CellValue OR %10000000  , also need to be tagged as tested CellValue=CellValue OR %00001000

End result is CellValue=%11101111

Summary :-   what does this mean ?

It means an object was found in East (bit 6),South (bit 7),West (bit 8) direction - no object found North (bit 5),all directions tagged as tested (low nibble).

This is a basic system for Occupancy navigation, in reality this is a single cell of an XY array CellValue(x,y) or directly poked to memory (saves more).

Here is a quick example of a 3x3 grid - the robot has already tested the North direction (fire_ing its lassiter to the wall to measure distance) and then it rotated 90° anticlockwise and fired its lassiter again.

You can start to see how the cells are showing the pictorial Maze like surroundings.........

Conclusion :- For the cost of 1 byte/cell four object walls and 4 direction tested flags can be indicated - Pretty compact.

Dare you try to decode this on %11101110 ? ........ if you know then post below...

## Comment viewing options

My brain has hit a wall...

Why aren't the squares equal to the outside dimentions of the robot's chassis?

One square=one body-length unit of movement.

There is no limit to the size you use - just memory limitations ......(which is why i devised this method)....(well actually the lower nibbles are more important)

I understood what your system is doing the first time around, I just didn't agree with the solution.

When you store information about 'walls' you are actually storing information about cell conectivity (as in 'can i cross from this cell into the cell to the north?', and you can answer with yes, no, unknown) and since you have only 4 bits you basically force your robot to think that a cell can have only 4 neighbors.

This system is also far from optimal in terms of memory usage because information about a wall is actually stored twice (unless you want to represent the situation where a robot may drive from north to south but not from south to north.

So, instead of going through all this trouble you can just have two 'bit' arrays, with one bit per cell. One array tells you if a cell has been scanned and one tells you if the robot can drive on it.

In your system a grid of 64 by 64 cells takes up 4kb of memory while in my system it takes up only 1kb. This means you could have a grid with smaller cells (2 times smaller, double resolution) in the same amount of ram.

Thanks for your observations........ can you "Blog/Tip" your idea (diagrams would be cool) ....you could be onto something that i have overlooked and is of use to others.......as it seems many LMRs are working into this direction anyways.....

The strategy i show here is from my very early maze solving/creating programs based on  6502&Z80 chip sets. The assembler  code_ing worked very well and fast.

It is not a complete solution, however maybe for Maze solving robots it provides a good start (as they are Cell/Wall based)

The advantage of tagging none tested cells, means that you can retrace back to them (for maze solving - super cool)...

G.

I suppose you could do that.   its a designers choice thing.   in conjunction with all the other factors and capabilities of the equipment.

for instance if your laser measurement device can resolve to a cm, then the cells in your array could represent something as small as 1cm.   or divide by cm by 100 for each cell to represent 1 meter.    if your bot can move 1 foot with accuracy then each cell could be 1 foot.    it forces you to return to the big picture and ask what do you need to do?

dealing with big arrays is just as easy as small arrays, if you have the memory or the ability to address large numbers.   whats the largest array propellor will allow you to work with?   is that a typical declared variable? or something else like addressing ram, or eeprom?

It’s a compact system, but what I don’t understand is what you need the lower nibbles for? If your robot is running around mapping a grid, why would you not always check all directions?
If your positioning system is spot on I can understand that you calculate directions that don’t need to be checked but what would that data be used for, just debugging?
Great illustrations by the way!

Illustrations where made with the freeware 3D "Blender" package..... (-: need to start practicing in case a laser printer comes my way :-)

I wanted a system that would tell me which cells had not been tested yet, ie a Roomba would like to pick up the very last piece of fluff.

The end result would be a picture of the surrounding room.

4 bits can only show 16 possible wall configurations (no room for tested flag-so this is why lower nibble is needed)

I might be missing the point, but this looks overly complicated.

Are you trying to represent walls instead of cells?

I don't think it is very useful to keep track of the "walls" because this restricts you to moving in 4 directions only.

If you really want to store both "occupied" and "tested" information in as little memory as possible I suggest you actually make 2 separate arrays. You can make them as small as possible by storing information for 8 cells in one byte.

So for a map of let's say 64 by 64 cells you create 2 arrays of 64x8 bytes, which is exactly 1kilobyte.