2.4. Building the map   (part 2)

    Lets examine a question of using scouting algorithm considered in the part 1 of this article. Probably we need two different integer-valued arrays (two-dimensional tables) in the robot RAM. The first table consists of only one line and stores the results of sonar distances in the polar coordinate system. Every number is correspond to its sonar turning angle. The dimension of this array (number of items) depends of the single sonar turning angle. The less turning angle the more number of scans and higher precision of the map.
    The second table we’ll use to compose the map. The size of the items of grid on the map, I think, we can choose by the size of our robot. Plus some space to guarantee the robot can pass in the item of greed. But this is my point of view. You can compose the map with the precision you need (or your sonar can provide). But we can’t know the dimensions of this array because we don’t know the dimensions of the room at the first stage of scouting. The data from sonar at the first step (first level in the scan graph) can’t help us to solve this problem. The real dimensions of the room can be unavailable because of the nearest obstacles. One of the ways of solving this problem, I think, may be reserving wittingly larger array for the current map composing. We can calculate the real room dimensions after finishing building the map of the room and move this data to the new map array with known dimensions. This is possible really if the robot programming la! nguage support the dynamical memory reservation. Otherwise we have to work with memory directly.
    So, we have the second (map) table. Lets initialize it by zero filling. Lets decide that zero (“0”) will be the symbol of non-scanned zone. It’s not important now – this is a code or a symbol.
    I don’t stop here on the algorithm of filling the array by the codes of pass ability or not for the robot. If anybody has good idea or the ready code, I’ll include this text here with the link to the author. My E-mail: vkaniv(*)fuib.com. One of the features of this algorithm can be the rule of the decision-making – how to mark the dubious items. They can be passable on 90 % or have some non-scanned place (corner). How to make a decision in this case?
    When I filled the map listed below by the codes, I used the simple rule. If the reflected signal passed through the current cell on the map and the area of the “obstacle” was less then 5-10 % of the total area of this cell and situated in the corner, I marked this cell as free. Also, if the problem place (non scanned corner) is in the cell far from the robot we can say with high probability that this obstacle is supposed, not real.
    Lets decide that we’ll mark the cell by “1” when it is passable for robot and “9” – impassable. Then our map after the first scan near the door will be:
    
    Blue color – is the border of scanned and passable zones and non-scanned. This is the places on the map which is probably can be interesting for the robot - areas where it has to continue the scouting.
    The total map of the room built by the sonar data and our algorithm will be:
    
    You can see some differences between the map built by the robot and the real map of the room. The biggest differences, as you can see, is in the zones far from the robot. This fact we can use to make our algorithm more sophisticated to increase the precision of the map. But our current map built by the minimum robot motions, I think, is quite convenient for the navigation.