|
||||
|
 In this picture you can see the situation where the robot is in the unknown room at the first time. Robot - is the green spot on the map near the door. The furniture is painted by the brown color. The rays from the green spot are the borders of the sectors of ultrasound sonar scans. Green segments is the places where is sonar signal are reflected from the obstacles. They shown as the robot can “see” they. The total picture of the robot vision will be like this:  You can see the white zones being in the “shadow” of the obstacles. They are out of the robots view from this point. To build the total map, robot need to make some additional scans of this zones. To collect the missing information, our robot needs to change its current location. But robot doesn’t know that yet. It has only the data from the sonar. What we have to do next? Our current task is to formulate the criteria – how to make a decision: continue scouting the room in the new points or not (the map is ready?). If yes, it might be well to minimize the number of scans by the minimizing the number of scan points and the number of scans in every point (narrow the scan sector). So, how to make the decision with the available information? Lets pay our attention to some features of the current map represented by the histogram of distances:  We can see the regularity. The scans of the room places without the “shadows” are changing quite smoothly. But the scans of the places near the “shadow” zones have a big difference between next distances. Big value of the difference can be the reason of decision to make an additional scout in the “suspect” place. We can control the sensitivity of the robot by the difference of the adjoining scans. These differences are shown as blue lines in the picture of histogram placed above. Using this data the robot also can know the directions and distances to the points of additional scans. And calculate the degree of the chassis turn for the optimal scanning. 
The approximate algorithm of calculating the next point for scouting at the next step (step+1) can be the following. Using the data of the distances of sonar on the previous step we: 1. Determine the direction of robot moving, using the number of scan and knowing the servo degree for the one scan. Lets consider that 0 degree – is the west direction from chassis. The single angle of servo rotation U = 10 degrees. Then, the direction of robot moving for the sensing of scan N is (N-1)*U. For 8 scan: (8-1)*10=70 degrees. For 14: (14-1)*10=130 degrees 2. Determine the distance of robot moving. There are some variants. It depends of the future scan sector. The picture is show algorithm: - Determine adjoining scans on histogram (or table) with big difference between. - Move to the distance equal to sum of smaller scan and the half of the difference between the bigger and smaller scans, i.e. to the middle of segment of unknown zone. For 8 scan: 38 + (66-38)/2 = 52. For 14: 51 + (85-51)/2 = 68. 3. Determine the direction of sonar in the target point of scout. It’s simple. Look at two scans with big difference. If the smaller scan is previous (left from big), then turn servo left, else – right. 4. Determine the start and finish degree of sonar. In our case this range is always equal 180 degree. But you can use another algorithm. For example, move in item 2. to the distance of smaller scan and then scan the sector of 90 degree. So, situation for the 14 scan will be: 
For 8 scan: 
Total picture after the room scan: 
We can improve the precision of scans by minimizing the turning angle of sonar or by decreasing the range of scan to obstacles. In the case of precision chassis we can also scout the room like this.  Filling the table of map by the data of sonar is geometrical task. May be with some nuances… I think it will be better to fill the map by data in real time. But this is a good idea only if the CPU is quite fast. Otherwise when the robot “thinking” for a long times in the middle of the room or narrow way this is not good idea. Another problem – how to avoid scouting already inspected zones. We can use non real time algorithm filling while robot scouting. When we make scans in some points and then building the map by filling the table. This is the real problem because, as you can see in the previous pictures, it can be possible the situation when our robot may decide to scout the “shadow” zone which already scanned. This is not a problem for the real time building the map. We just fill the entire map by zero (for example). And check the “unknown” zone using the building map if the robot will decide to try to scout it (when it has two scans with big differences in one of additional scout points). And final. We consider the discovery of the simple room. If we connect the points of scans by the lines, we’ll get the graph of scans with two levels. But in real room this graph can be more complex:  |
||||
