The Characteristics of the Map Merging Methods: A Survey <s> A. Map Merging when the Initial Relative Positions of the Robots Are Known <s> We present an incremental method for concurrent mapping and localization for mobile robots equipped with 2D laser range finders. The approach uses a fast implementation of scan-matching for mapping, paired with a sample-based probabilistic method for localization. Compact 3D maps are generated using a multi-resolution approach adopted from the computer graphics literature, fed by data from a dual laser system. Our approach builds 3D maps of large, cyclic environments in real-time, and it is robust. Experimental results illustrate that accurate maps of large, cyclic environments can be generated even in the absence of any odometric data. <s> BIB001 </s> The Characteristics of the Map Merging Methods: A Survey <s> A. Map Merging when the Initial Relative Positions of the Robots Are Known <s> An efficient probabilistic algorithm for the concurrent mapping and localization problem that arises in mobile robotics is presented. The algorithm addresses the problem in which a team of robots builds a map on-line while simultaneously accommodating errors in the robots’ odometry. At the core of the algorithm is a technique that combines fast maximum likelihood map growing with a Monte Carlo localizer that uses particle representations. The combination of both yields an on-line algorithm that can cope with large odometric errors typically found when mapping environments with cycles. The algorithm can be implemented in a distributed manner on multiple robot platforms, enabling a team of robots to cooperatively generate a single map of their environment. Finally, an extension is described for acquiring three-dimensional maps, which capture the structure and visual appearance of indoor environments in three dimensions. <s> BIB002 </s> The Characteristics of the Map Merging Methods: A Survey <s> A. Map Merging when the Initial Relative Positions of the Robots Are Known <s> An extended Kalman filter (EKF)-based algorithm for the localization of a team of robots is described in this paper. The distributed EKF localization scheme is straightforward in that the individual robots maintain a pose estimate using EKFs that are local to every robot. We then show how these results can be extended to perform heterogeneous cooperative localization in the absence or degradation of absolute sensors aboard the team members. The proposed algorithms are implemented using field data obtained from a team of ATRV-mini robots traversing on uneven outdoor terrain. <s> BIB003 </s> The Characteristics of the Map Merging Methods: A Survey <s> A. Map Merging when the Initial Relative Positions of the Robots Are Known <s> Autonomous vehicles require the ability to build maps of an unknown environment while concurrently using these maps for navigation. Current algorithms for this concurrent mapping and localization (CML) problem have been implemented for single vehicles, but do not account for extra positional information available when multiple vehicles operate simultaneously. Multiple vehicles have the potential to map an environment more quickly and robustly than a single vehicle. This paper presents a cooperative CML algorithm that merges sensor and navigation information from multiple autonomous vehicles. The algorithm presented is based on stochastic estimation and uses a feature-based approach to extract landmarks from the environment. The theoretical framework for the collaborative CML algorithm is presented, and a convergence theorem central to the cooperative CML problem. is proved for the first time. This theorem quantifies the performance gains of collaboration, allowing for determination of the number of cooperating vehicles required to accomplish a task. A simulated implementation of the collaborative CML algorithm demonstrates substantial performance improvement over non-cooperative CML. <s> BIB004 </s> The Characteristics of the Map Merging Methods: A Survey <s> A. Map Merging when the Initial Relative Positions of the Robots Are Known <s> This paper introduces a new method for representing two-dimensional maps, and shows how this representation may be applied to concurrent localization and mapping problems involving multiple robots. We introduce the notion of a manifold map; this representation takes maps out of the plane and onto a two-dimensional surface embedded in a higher-dimensional space. Compared with standard planar maps, the key advantage of the manifold representation is self-consistency: manifold maps do not suffer from the 'cross over' problem that planar maps commonly exhibit in environments containing loops. This self-consistency facilitates a number of important autonomous capabilities, including robust retro-traverse, lazy loop closure, active loop closure using robot rendezvous, and, ultimately, autonomous exploration. By way of validation, this paper also includes experimental results obtained using teams of two to four robots in environments ranging in size from 400 m/sup 2/ to 900 m/sup 2/. <s> BIB005 </s> The Characteristics of the Map Merging Methods: A Survey <s> A. Map Merging when the Initial Relative Positions of the Robots Are Known <s> This paper presents an implementation of the local maps fusion concept for the simultaneous localization and mapping (SLAM) problem within the extended Kalman filter (EKF) framework. Several problems never addressed before, arise while implementing the solution for indoor environments, and are successfully solved to obtain maps of quite large real indoor environments with more than one robot in real time. <s> BIB006
Initially multi-robot mapping methods were simply extended single robot mapping methods  . Consequently the map merging problem was also simplified by assuming that the robots create their maps in common reference frame. For this approach to work usually the robots must know their relative starting positions. Several authors have developed multi-robot mapping methods based on this assumption. One of the first researches in multi-robot mapping dates back to the 1993, when Ishioka et al.  implemented and described an algorithm that was able to merge the local maps of two robots once the overlap of the maps was identified. The merging of the local maps was accomplished by rotating and sliding the maps until the best match was found. The task was alleviated by the fact that the initial starting positions and wheel slippage ratios of the robots were assumed to be known. These assumptions significantly reduce the search space of the transformations. Thrun et al. BIB001 , BIB002 combines the idea of posterior estimation with incremental map construction using maximum likelihood estimation to create the mapping algorithm that enables data integration from multiple robots. Though the starting locations of the robots aren't assumed to be known, there is a restricting assumption that each robot starts in the map of one specific robot, the team leader. Robots localize themselves in this map and only then the mapping process begins. In reality this means that the relative positions are known when the mapping starts. The mapping algorithm devised by Simmons et al.  also uses the maximum likelihood estimation. The relative positions of the robots are assumed to be approximately known and their algorithm is able to deal with small starting position errors. One more application of the maximum likelihood estimation is found in the work by Howard et al. BIB005 . The main difference from the other works is the use of the manifold maps. The manifold maps represent the environment in a higher-dimensional space as multiple overlapping layers. Besides the different environment representation the authors use the robot meetings to make a data correspondence problem easier. Mapping methods described above use the maximum likelihood estimation for mapping. Another possible option is to use the Kalman Filter. There are several researchers that have based their mapping algorithm on this technique BIB003 , BIB004 , BIB006 . Although the main idea is similar, some differences exist between these approaches. Fenwick et al. in BIB004 assume that distinctive environment features can be extracted from raw sensor data. These features are then used to localize the robot and improve feature estimates, which are updated using an Extended Kalman Filter. Madhavan et al. BIB003 turn their main attention to the distributed localization problem. The approach by Rodriguez-Losada et al. described in BIB006 deals with robots who independently construct their local maps and only fuses the local map with global map from time to time. Both the local map and the global map constructions are implemented with the Kalman Filter. The restriction on the known relative positions of the robots, however, is still there. Another approach to the mapping is attempted by Ceccarelli et al.  . They use a set membership localization and map building to construct the map of the environment. Like most approaches described above, the local maps of the robots are merged at the beginning of the mapping with the knowledge of relative starting positions. Each robot then updates the global map as the mapping proceeds.