Grid-based mapping

This approach was originally proposed by Elfes [23] and Moravec [51]. Cells in an occupancy grid contain information about the presence or not of an obstacle. Each of these cells is updated using sensor readings, and its value represents the degree of belief in the presence of an obstacle. The vast number of grid-based algorithms differ on the way in which sensor readings are translated into occupancy levels. Among other techniques, probability theory [51,66,67] and fuzzy set theory [41,40] have been used. This mapping approach can be used in conjunction with the two localization approaches, as has been just described above.

In this approach, navigation is performed using path planning algorithms, which compute precise routes through the environment in order to reach a goal avoiding the obstacles.

Although this approach is widely used and achieves very good results, it is mainly focused for indoor structured environments. The size of such environments permits the robot to maintain a grid with a high enough resolution (i.e. small cells). In large outdoor environments, however, this technique cannot be applied, as the computational cost of the grid would be too high.

Moreover, in most of the algorithms following this approach, the robot has a training period in which it navigates through the environment with the only purpose of building a map. After this training period, the robot is able to perform its task and localize itself using the already built map. In our scenario, however, there is no such training period, as the robot does not have the opportunity to inspect the environment before attempting to reach the target, but has to reach it while exploring the environment for the first time.