2.6. Determining the current position on the map

    Lets think, that our robot can scout the location and already built all the maps. Or its owner can make these maps and load they into the robot RAM. It's important for us at this stage, that robot already has all information it need for the navigation. Our task is to identify the current robot location on the map. We need to do this by the minimum time and number of moving, if the robot will need it.
    Our scan sensor is Ultrasound Sonar. The order of stages will be:
1. Robot must scan the location around itself and remember the distances to the obstacles for the every scan.
2. Calculate the possibility of coincidence the distances for the current point on the map with data from the sonar. Do it for the every point on the map (or for the limited number of the points. We will consider - how to limit the number of possible variants, on this page late). We need also to mean the mistake of sonar measuring and robot physical allocation in the grid of the map.
3. We need to remember the coordinates of the current place on the map and the current destination of the robots chassis.
4. Look and find the other possible positions of the robot on the current map.
5. If we have some other maps, retry this procedure for the each of they.
    If we have only the one result – Great! This is our current position. If no, which is more possible, we need additional info, additional scans of location. We can make some additional scans at the same point without chassis moving, only by sonar. But also we can move to the new place and make scans there (and remember the destination and distance robot made). The second way (my point of view) is better because we can use two or more points on the map for the current robot position recognizing.
    Lets try to decide the number of sonar scans from the one point on the map. One scan is not enough because the number of possible points on the map will be many. Lets consider the situation with 2 and 3 scans we make clockwise with the step of the angle of 90 degree.

    

    As we can see in the first picture, the number of possible robot locations on the map with two scan results is a lot. This picture shows (gray color) only some possible positions of our robot. Green color is the real robot position.
    With 3 scans in one point the number of possible positions is less. We can see this in the second picture. And if we use 4 scans in the point the result will be better. But I don’t develop this idea because the real servo with sonar (even modified) can have possible physical limits with working in 360 degree. I mean problems with electric and data cables, etc. If your construction has no such problems, you can use 4 scans. But we try to use 3 with the same result. How? It’s simple.
    The fourth scan we make equal zero. It means, we just move forward to the obstacle and turn around. This will be useful, from my point of view, by some reasons. First of all, we set the limit for the number of analyzing points on the map. We can calculate only points near the obstacles. Next, I think, it will be better if the robot will begin to determine its position on the map (begin to “think”) not in the center of the room. Better - near the wall or bookcase. Robot can stay there as long time as it need without hinders people.
In the map shown above, we can identify our position near the wall by 3 scans. Course, it’s possible the situation when the room can have some similar places with the same distances to the nearest obstacles.

    
    We’ll need additional scans in this situation. Where is the better place for the next point of scans? Where to move? The simple algorithm (without turning the chassis) is to move forward and make the measuring left and right via the constant interval of time or distance. This will take us some new information. Another way – move forward to obstacles and make two scans (left/right) near the wall. I think, it’s possible to determine current position on the map by the scan results in two points in the most cases. But if we can’t identify position even after scans in two points, we have to move to the next one.
    We can use one of the simple moving algorithms. For example, random choose the turn destination (on 90 degree left/right), move to next point near the obstacle (and store in memory all our movements) scan by sonar distance to obstacles left and right. Try to delete in the list of starting possible positions some incorrect starting points.
    Of course, we can use more complex algorithm of moving. You can decide this by yourself. This picture can help you to think about improving this algorithm:

Algorithm of calculating the current robot position on the map
    According to algorithm considered above our robot will take place near the obstacle while calculating its position on the map. Therefore, we can analyze only points near the obstacles. The others we can ignore. This can save our time. I don’t consider here the algorithm identifying these points, but this is not a complex task.
    Look at the cell of the greed of the map near the obstacle. Our task is to calculate if there is one or more obstacles here, which located in the distance equal the result of the first sonar, scan? To do this, lets make the circle with the center in the analyzing cell of grid. Are there points of intersection this circle with the obstacles on the map? If no, lets analyze another cell of greed. If yes, we need to check every intersection points (1a and 1b in the picture) with the result of second scan and if we’ll need – the third scan.
    To do this, let's make the first segment from the center of the analyzing cell to the first intersection point with the length of the first sonar scan. Then, make the second segment with the length of the second scan (clockwise on 90 degree from the first segment). If the end of this second segment intersects with the obstacle edge, then check the third scan. If no, then check the next cell on the map greed. To check the third scan do the same as for the second. We will make the third segment with the length of the third scan (clockwise on 90 degree from the second segment) and check the intersection point. If all the segments satisfy the conditions of all scans, then the analyzing cell can be the point of the robot position. We can save the coordinates of this cell on the map, number of the map and destination of chassis (destination of the second segment) for the next use.

    So, we analyze all the cells near the obstacles and the similar cells on the other maps. The cells that satisfy the results of all scans we save in the list for the next analyze after the results of additional scans.


Scan mistakes and inaccuracy of the chassis positioning.
So what? (short translation)
    We can use ideal algorithms of the path finding, positioning, and building the map and navigation. But different types of mistakes can take the dramatic effect to the accuracy of the final result of calculating. But we can compensate for they.
    I think about three ways:
    1. If we have the alternative hardware, it’s better to use more precise (turn the sonar by servo vs. using DC motors on chassis). We have to construct the algorithms for the minimum use inexact equipment.
    2. It’s important to don’t accumulate the mistakes. It means to make the position more exact as often as it’s possible. If robot does this rarely, the sum of mistakes can stay big and robot can lose one's bearings. If the robot knows how to dynamically modify the map, it can corrupt it.
    3. We can compensate the hardware mistakes by the software/algorithms. The human do this very often in his brain. If we know that our hardware equipment is not the precise, our algorithms can’t say: “We are don’t know about that”.
    Practice. We have two types of mistakes Scan mistakes and inaccuracy of the chassis positioning in the real. It means that we have mistake of distance scan to the obstacle. Lets decide, that it’s not interesting for us – what is the percentage of each type in the total mistake of distance. Lets consider that this is one (total) mistake. We can try to compensate this by increasing the zone of intersection the scan segments and obstacles. This zone will be between two circles with more and less radius of each scan result. In the picture below you can see this zone as a red thick circle. And you can see one additional variant, shown by the blue color, which we have to analyze.

Additional ideas
1. Robot can determine the current position on the map in the geometrical center of the room. This point is one in each room. We have to analyze only one point in the map. Cool. But this is impossible in some situations (in some maps).
2. The ideal place for the scans – ceiling of the room. It’s much more static than the floor and we can also know the dimensions and the size of the room. This way required additional servo for the additional range of discretion for the sonar. But this is not in our target setting for the hardware list (use only one servo for the sonar).



[ Table of contents ]