The Characteristics of the Map Merging Methods: A Survey <s> C. Map Merging when the Relative Positions of the Robots Are Unknown <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> C. Map Merging when the Relative Positions of the Robots Are Unknown <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> BIB002 </s> The Characteristics of the Map Merging Methods: A Survey <s> C. Map Merging when the Relative Positions of the Robots Are Unknown <s> We address the problem of merging multiple noisy maps in the rescue environment. The problem is tackled by performing a stochastic search in the space of possible map transformations, i.e. rotations and translations. The proposed technique, which performs a time variant Gaussian random walk, turns out to be a generalization of other search techniques like hill-climbing or simulated annealing. Numerical examples of its performance while merging partial maps built by our rescue robots are provided. <s> BIB003 </s> The Characteristics of the Map Merging Methods: A Survey <s> C. Map Merging when the Relative Positions of the Robots Are Unknown <s> Most map building methods employed by mobile robots are based on the assumption that an estimate of the position of the robots can be obtained from odometry readings. In this paper we propose methods to build a global geometrical map by integrating partial maps without using any odometry information. This approach increases the flexibility in data collection. Robots do not need to see each other during mapping, and data can be collected by a single robot or multiple robots in one or multiple sessions. Experimental results show the effectiveness of our approach in different types of indoor environments. <s> BIB004 </s> The Characteristics of the Map Merging Methods: A Survey <s> C. Map Merging when the Relative Positions of the Robots Are Unknown <s> The purpose of this paper is to present a technique to create a global map of robots' surroundings by converting the raw data acquired from a scanning sensor to a compact map composed of just a few generalized polylines (polygonal curves). We propose a new approach to merging robots' maps that is composed of a local geometric process of merging similar line segments (termed discrete segment evolution) with a global statistical control process. In the case of single robot, we are able to incrementally build a map showing the environment the robot has traveled through by merging its polygonal map with actual scans. In the case of a robot team, we are able to identify common parts of their partial maps and if common parts are present construct a joint map of the explored environment. <s> BIB005 </s> The Characteristics of the Map Merging Methods: A Survey <s> C. Map Merging when the Relative Positions of the Robots Are Unknown <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> BIB006 </s> The Characteristics of the Map Merging Methods: A Survey <s> C. Map Merging when the Relative Positions of the Robots Are Unknown <s> Merging local maps, acquired by multiple robots, into a global map, (also known as map merging) is one of the important issues faced by virtually all cooperative exploration techniques. We present a novel and simple solution to the problem of map merging by reducing it to the problem of SLAM of a single ?virtual? robot. The individual local maps and their shape information constitute the sensor information for the virtual robot. This approach allows us to adapt the framework of Rao-Blackwellized particle filtering used in SLAM of a single robot for the problem of map merging. <s> BIB007
All the multi-robot mapping approaches described above require that the relative positions of the robots are known at the start or the positions are acquired during the mapping. Without the positional information these approaches cannot merge the maps. The task of fusing maps without any positional information is a harder case of the map merging that requires different solutions. Most of the map merging methods of this type use the transformations' approach. They rotate and translate one of the maps against the other to find the best possible match. The complexity of the map merging when the relative positions of the robots are unknown can differ greatly depending on the type of the maps. The maps that are most often used for mapping are metric maps and topological maps. The metric maps describe the geometric properties of the environment and are usually represented as occupancy grids, i.e., metric arrays where the value in each cell represents the probability of the responding location being free space or a part of the obstacle BIB006 . The alternative is topological maps that represent the environment as a graph where vertices represent the features (i.e. junctions) of the environment and edges represent paths between these features  . In practice, the merging of topological maps has proved to be easier than the merging of metric maps. Several researchers have addressed this problem and offered reasonable solutions  , BIB001 . Dedeogle and Sukhatme BIB001 are one of the first researchers to address the problem of topological map merging. They developed the algorithm that matches the pairs of vertices to find the best possible transformation of the maps. The best transformation is one with the highest number of overlapping vertices. Only the vertices of similar type are compared, thus the transformation space is significantly reduced. The topological map merging approach presented by Huang and Beevers  combines subgraph matching and image registration to find the potential transformations of the maps. There is one more notable difference from the approach described before, i.e., the transformations are computed by using clusters of multiple vertices. Thus, fewer transformations are verified and consequently the best transformation is acquired faster. This approach can be effectively used for rendezvous mapping, for the authors also provide a mechanism for the later verification of the map merging results  . It must be noted that both of the mentioned topological map merging methods use topological maps augmented with metric information. Without such information the topological map merging problem would become a mere search for identical subgraphs. The subgraphs can be found quite easily; however, the acquired result is much less reliable. Therefore, all considerable multi-robot topological mapping approaches use the metric information. The metric map merging is a harder problem than the topological map merging as one has to rely on the metric information alone and no graph matching techniques can be used. To make the problem easier many researchers use metric maps that are augmented with some additional information. One such example is Konolige et al.  who supplements an occupancy grid map with features to achieve a better map merging result. The use of features allows to significantly reduce the transformation space, thus the result is acquired faster. One serious problem of this map merging method, however, is the identification of the features in the occupancy grid map. Adluru et al. BIB007 use similar feature maps for map merging. However, the map merging method itself is quite different. It addresses the problem as if the partial maps were sensor readings of a 'virtual robot'. The algorithm then uses a particle filter to merge all the maps into one global map. The features are used for the search of correspondences between local maps. A different approach is offered by Amigoni and Gasparini BIB004 . They use a specific type of maps, i.e., segment maps acquired with 2D laser range sensors. The segment map consists of multiple segments and it is possible to calculate angles between consecutive segments. This property is then used as a heuristic for the search of the best transformation. It is presumed that the best transformation is the one with the largest sum of the common segment lengths. Lakaemper et al. BIB005 concentrates on the problem of merging a different type of segment maps. In this case the maps are acquired by simplifying the raw sensor data into few polylines. The map merging algorithm then extracts parts of the map and searches corresponding polylines in the other map. When similar structures with significant shape information are found, the two maps are aligned. The hypothesis is then confirmed or rejected by checking the alignment of other polylines in the maps. A map merging solution for a very specific type of the maps is presented by Williams et al. BIB002 The environment objects are represented as point features. The points are treated as graphs and the correspondence between the maps are found by searching the common subgraphs. Though in some ways similar, the point feature maps, however, are not topological maps as no navigational information is incorporated between the separate points. This kind of approach is quite original for metric maps; however, its areas of application are quite limited. Another interesting approach is devised by Ho and Newman  . In addition to the geometric information the robots also collect information about the visual appearance of the environment. The images are collected and related to the according parts of the metric maps. When it is necessary to merge the local maps of two robots, the images are compared. To avoid false matches, the metric information is taken into account. However, it is not practical to use this map merging approach if the visual information of the environment is not distinctive. All the map merging methods described above use some kind of structural or feature information to merge the maps if the relative positions of the robots are unknown. Not many researchers have addressed this problem when only geometric information is available. In fact, the only researchers to propose reasonable map merging solutions without simplifying or supplementing the occupancy grid maps are Carpin and Birk BIB006 , BIB003 . Their map merging method presented in BIB003 rotates and translates the partial occupancy grid maps to find the best transformation. The best transformation is determined by using image similarity metric. To reduce the time required to merge the maps a stochastic random walk algorithm is used for the search of the transformation space. In BIB006 this map merging approach is complemented by the acceptance metric which determines the reliability of the map merging result. However, there is one serious drawback to this method as the used stochastic algorithm is guaranteed to find the optimal solution only if the number of iterations tend to infinite. Thus, it does not guarantee the best transformation when a limited number of iterations are executed. Aware of this problem, Carpin  proposes another solution to the occupancy grid merging. The new approach uses Hough transform, a methodology used to detect geometric curves, to find the best transformations. This approach yields good results as it is fast, deterministic and capable of returning multiple hypothetic transformations. The main drawback of the algorithm is that it relies heavily on the existence of geometric curves in both maps. If such curves do not exist, it is problematic for the algorithm to rotate the maps correctly.