Let's Make Robots!

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

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Thanks for diagramming this out.  It's very similar to something I've been working on myself.

this means:

North - not tested

East - tested, object present

south - tested, object present

west - tested, object present

but I'm a little hazy on why store info on my surrounding cells, in my current cell?

At least someone understands my theory......phew. At least now i know my write-up is clear.....

Those big walls are actually contained within the current cell we are testing, the inner walls are just phantom walls. (it was the only way i could show my concept in picture form, without the big walls hide_ing the bit values)

I reality when testing North for example 5,6,7,8,9,etc cells can be tested in same direction (until an object blocks the way).

It's not difficult to understand but I'm wondering how efficient it is. This appears to use a strict block size which will add up. Great if you have the memory to give to it, but then you'll also run into the cost of reading and writing that memory which will slow you down. How about using relative block values? Block sizes can then be scaled by factor of x. I have to head to work buy maybe I can sketch it there to give an example. Yes there are considerations like when those blocks have to be broken down int o smaller ones due to a new occupier, but this should be solvable.

Cell size can be anything - its just relative to the cm/inch units you apply to it.(ie 1cell could represent a 100x100cm or 1x1mm etc)

Yes you have to choose an array/memory grid size that encompasses memory availability.

Yes would love to see a diagram,

With the single byte value that you use to hold the data, this would require a second byte to set what value the block size is based on per sector and sub sector..  

when testing North for example 5,6,7,8,9,etc cells can be tested in same direction (until an object blocks the way).


you mean if you use SRF or some other way to measure North, and it reveals no objects for 5 or 6 blocks, then you would go ahead and load the appropriate byte into those cells to the north?

so I'm loading values about my neighbors into my cell, instead of my neighbor cells.

If you fire your laser/SRF North and read its distance .... say at 55cm it hits an object  (cells are 10cm square) then the north  wall from current cell and the North & South walls up to the 55cm cell will be marked as clear/tested ie bit 1 and bit 8.

This means that if i look up any byte from the array i know what walls are contained there, the information in essence is already pre formated.

If you used the Dot in the cell method then to test if a direction is free then another calculation run has to be made....

I will be making 1 or 2 more drawings of multiple cell configurations shortly (brain is resting after this current lot)

BOOM! I almost had it... Now my grey matter is also dripping from the north wall.... :-)