Mapping and Navigation

As already mentioned, the task the robot has to perform is to navigate through an unknown unstructured environment and reach a target landmark specified by a human operator. This task is not easy to solve, since it has to be carried out in a complex environment, and the target can be occluded by other objects. Purely reactive robotic systems would have problems trying to accomplish this task, since they do not build any model of the environment. If the target were lost, it would be difficult to recover its visibility and continue the navigation towards it. For this reason, we thought that the robot should build a map of the environment in order to navigate through it. The information stored in the map must permit the robot to compute its location, the location of the target, and how to get to this target. Although the objective of this PhD thesis is to develop a navigation system for indoor environments, we have used a map representation that also works outdoors, since this is the next milestone of the project in which we are involved. Thus, instead of using a grid-based approach, the most widely used approach for indoor environments, we have used a topological one, most appropriate also for outdoors.

Our approach is based on the model proposed by Prescott in [55]. The principles underlying this model are inspired by studies of animal and human navigation and wayfinding behavior. This model, called beta-coefficient system, does not only deal with how to represent the environment as a map, but also adds a mechanism for computing the location of landmarks when they are not visible, based on the relative positions of the landmarks. This mechanism is what we have used to provide the robot with orientation sense, since it captures the relationship among different places of the environment. The robot makes use of this orientation sense to compute the location of the target when it is occluded by other objects or obstacles.

In this chapter we firstly describe how Prescott's model works when the robot is able to have exact information about its environment, and then we explain how we have extended it to work with imprecise information. We also describe the method used for dividing the environment into appropriate topological regions, and finally how the topological map is used to navigate through the environment.