The Characteristics of the Map Merging Methods: A Survey <s> B. The Type of the Maps <s> This paper describes a landmark-based algorithm for map matching, and demonstrates its use in efficiently combining topological maps of indoor environments built by autonomous mobile robots. Results of the first implementation are presented, in which two robots with different mechanics and sensory capabilities independently explore their environments with no a priori maps. Each robot is initially unaware of the other’s relative position and orientation. Using the match algorithm, they eventually merge their maps into a topologically correct single map in real time, based only on the feature sets they have discovered independently. <s> BIB001 </s> The Characteristics of the Map Merging Methods: A Survey <s> B. The Type of the Maps <s> In this paper we consider the problem of exploring an unknown environment by a team of robots. As in single-robot exploration the goal is to minimize the overall exploration time. The key problem to be solved in the context of multiple robots is to choose appropriate target points for the individual robots so that they simultaneously explore different regions of the environment. We present an approach for the coordination of multiple robots which, in contrast to previous approaches, simultaneously takes into account the cost of reaching a target point and its utility. The utility of a target point is given by the size of the unexplored area that a robot can cover with its sensors upon reaching that location. Whenever a target point is assigned to a specific robot, the utility of the unexplored area visible from this target position is reduced for the other robots. This way, a team of multiple robots assigns different target points to the individual robots. The technique has been implemented and tested extensively in real-world experiments and simulation runs. The results given in this paper demonstrate that our coordination technique significantly reduces the exploration time compared to previous approaches. <s> BIB002 </s> The Characteristics of the Map Merging Methods: A Survey <s> B. The Type of the Maps <s> This article provides a comprehensive introduction into the field of robotic mapping, with a focus on indoor mapping. It describes and compares various probabilistic techniques, as they are presently being applied to a vast array of mobile robot mapping problems. The history of robotic mapping is also detailed, along with an extensive list of open research problems. <s> BIB003 </s> The Characteristics of the Map Merging Methods: A Survey <s> B. The Type of the Maps <s> This paper presents a novel approach to the multi-vehicle simultaneous localisation and mapping (SLAM) problem that exploits the manner in which observations are fused into the global map of the environment to manage the computational complexity of the algorithm and improve the data association process. Rather than incorporating every observation directly into the global map of the environment, the constrained local submap filter (CLSF) relies on creating an independent, local submap of the features in the immediate vicinity of the vehicle. This local submap is then periodically fused into the global map of the environment. This representation is shown to reduce the computational complexity of maintaining the global map estimates as well as improving the data association process. This paper examines the prospect of applying the CLSF algorithm to the multi-vehicle SLAM problem. <s> BIB004 </s> The Characteristics of the Map Merging Methods: A Survey <s> B. The Type of the Maps <s> Mapping can potentially be speeded up in a significant way by using multiple robots exploring different parts of the environment. But the core question of multirobot mapping is how to integrate the data of the different robots into a single global map. A significant amount of research exists in the area of multirobot mapping that deals with techniques to estimate the relative robots poses at the start or during the mapping process. With map merging, the robots in contrast individually build local maps without any knowledge about their relative positions. The goal is then to identify regions of overlap at which the local maps can be joined together. A concrete approach to this idea is presented in form of a special similarity metric and a stochastic search algorithm. Given two maps m and m', the search algorithm transforms m' by rotations and translations to find a maximum overlap between m and m'. In doing so, the heuristic similarity metric guides the search algorithm toward optimal solutions. Results from experiments with up to six robots are presented based on simulated as well as real-world map data <s> BIB005
It is evident in the map merging overview that the maps used for the mapping are very different. In the 1980s and early 1990s the dominant map types were metric and topological maps BIB003 . The metric maps describe the geometric properties of the environment and are usually represented as occupancy grids BIB005 . The topological maps represent the environment as a graph where vertices represent the features of the environment and edges represent paths between these features  . The line between the metric and topological maps, however, has become quite fuzzy as often topological maps are augmented with metric information or metric maps supplemented with features. Nowadays, primarily three map types are used for the mapping and map merging: • Metric maps BIB002 ,  ,  ; • Metric maps with features  , BIB004 ; • Topological maps  , BIB001 . This classification assumes that all the topological maps are augmented with some kind of metric information, for strictly topological maps aren't used anymore. Another assumption is that the features incorporated into metric maps can be different. For example, occupancy grid map supplemented with images is also considered to be a feature map. It must be noted that some map merging approaches merge the maps without modifying them BIB005 while other approaches modify the maps and then merges the resulting maps  . This is often the case with the metric maps when features are extracted from the metric information. In the classification, however, only the unmodified maps should be considered as they are the original data source for the map merging method.