Navigating Through the Environment

The beta-coefficient system described above provides the means for computing the location of a target even if it is not visible. This is very useful if the robot is navigating in an environment with a high density of landmarks and obstacles that occlude the target. In this case, the robot is able to go towards the target by seeing other landmarks. However, in some cases the obstacles might be blocking the direct path to the target. In this case, knowing the location of the target is not enough and an alternative route to reach it must be computed using the topological map.

Although a route consists of a sequence of regions the robot should navigate through in order to reach the target, only the first region is taken into account. The reason for doing so is that since the environment is never fully known, the robot cannot commit to a given route because it might encounter new landmarks and obstacles that would change the shape of the map, and possibly, the route to the target. Therefore, hereafter, instead of talking about routes, we will talk about diverting targets. A diverting target can be: (1) an edge between two landmarks, which the robot has to cross in order to go from one region to another, or (2) a single landmark to which the robot has to approach.

When the system is asked for a diverting target in order to reach another target, it first finds out in which region the robot is currently located, using the information about the landmarks whose location is known. This region will be the starting node on the topological map. The shortest path from this node to any of the nodes containing the target landmark (a landmark can be component of several topological regions) is computed. The edge connecting the current region with the next one on the shortest path will be the diverting target. The edge is given as a pair of landmarks, one that has to be kept on the left hand side of the robot and another to be kept on the right hand side, so the robot knows which way the edge has to be crossed. An example is shown in Figure 3.11. In this case, the robot is in region ABC, the target is G, and the shortest path to the target would be {ABC,ABD,BDE,BEF,EFG}. Thus, the diverting target would be the edge AB.

**Figure 3.11:** Diverting target computation

However, it could happen that there is no such shortest path. The cases in which such path does not exist are the following:

The robot is not in any topological region.
The cost of the shortest path is infinite. This means that the path is blocked by an obstacle, so it is not a valid path.
The target is not found in any topological region.

To solve the first two cases, the map has to be enlarged with virtual regions through which the robot can navigate. The idea is to let the robot move in an unknown area outside the map. The virtual regions are built by placing some virtual landmarks around the existing map, and creating the appropriate regions using the same algorithm as described in the previous section. An example of these virtual regions is depicted in Figure 3.12. To force the robot to use regions of the original map, the arcs connecting virtual regions are labelled with a high cost (though not infinite), so that they are used only if it is absolutely necessary. With this enlarged map, the shortest path is computed again. However, it can be that the edge to be crossed contains one virtual landmark. In this case, the edge cannot be given as the diverting target, since the virtual landmarks do not exist on the real environment and cannot be tracked. In this situation, the direction to the middle point of the edge is computed and given as the diverting target. We assume that there is always some free space around the explored area, so that the regions created with the virtual landmarks can be traversed.

**Figure 3.12:** Enlarging the map with virtual regions (dotted lines)
$\includegraphics[height=4cm]{figures/outside-map}$

In the case the target is not in any topological region, there is no way to compute which should be the next region to visit, since there is no destination node. When this happens, the diverting target is set to any of the visible landmarks, hoping that on the way to this diverting target, the map is updated and the target for which a diverting target has been computed is incorporated into it.