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)
- Lower nibble from xxxx0000 to xxxx1111 Logic 0 = cell direction not tested ...Logic 1 = cell direction tested
- 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
- The robot tests the North direction..its Clear ..... so CellValue=CellValue OR %00000001 (ie brand 1 to CellValue)
- Rotate 90° and tests East direction ....Clear ...... so CellValue=CellValue OR %00000010 ( brand 2 to CellValue)
- Rotate 180° & tests South direction ....Clear .....So CellValue=CellValue OR %00000100 ( brand 4 to CellValue)
- Rotate 270 & tests West direction ......Clear ..... So CellValue=CellValue OR %00001000 ( brand 8 to CellValue)
- Robots rotates to 360° and moves forward to next cell ...... and repeats back to step 1
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...