The Characteristics of the Map Merging Methods: A Survey <s> B. Map Merging when Robots Identify Their Relative Positions During the Mapping <s> In this paper, we present a new approach to the problem of simultaneously localizing a group of mobile robots capable of sensing one another. Each of the robots collects sensor data regarding its own motion and shares this information with the rest of the team during the update cycles. A single estimator, in the form of a Kalman filter, processes the available positioning information from all the members of the team and produces a pose estimate for every one of them. The equations for this centralized estimator can be written in a decentralized form, therefore allowing this single Kalman filter to be decomposed into a number of smaller communicating filters. Each of these filters processes the sensor data collected by its host robot. Exchange of information between the individual filters is necessary only when two robots detect each other and measure their relative pose. The resulting decentralized estimation schema, which we call collective localization, constitutes a unique means for fusing measurements collected from a variety of sensors with minimal communication and processing requirements. The distributed localization algorithm is applied to a group of three robots and the improvement in localization accuracy is presented. Finally, a comparison to the equivalent decentralized information filter is provided. <s> BIB001 </s> The Characteristics of the Map Merging Methods: A Survey <s> B. Map Merging when Robots Identify Their Relative Positions During the Mapping <s> An important assumption underlying virtually all approaches to multi-robot exploration is prior knowledge about their relative locations. This is due to the fact that robots need to merge their maps so as to coordinate their exploration strategies. The key step in map merging is to estimate the relative locations of the individual robots. This paper presents a novel approach to multi-robot map merging under global uncertainty about the robot's relative locations. Our approach uses an adapted version of particle filters to estimate the position of one robot in the other robot's partial map. The risk of false-positive map matches is avoided by verifying match hypotheses using a rendezvous approach. We show how to seamlessly integrate this approach into a decision-theoretic multi-robot coordination strategy. The experiments show that our sample-based technique can reliably find good hypotheses for map matches. Furthermore, we present results obtained with two robots successfully merging their maps using the decision-theoretic rendezvous strategy. <s> BIB002 </s> The Characteristics of the Map Merging Methods: A Survey <s> B. Map Merging when Robots Identify Their Relative Positions During the Mapping <s> We consider the problem of how two heterogeneous robots can arrange to meet in an unknown environment from unknown starting locations: that is, the problem of arranging a robot rendezvous. We are interested, in particular, in allowing two robots to rendezvous so that they can collaboratively explore an unknown environment. Specifically, we address the problem of how a pair of exploring agents that cannot communicate with one another over long distances can meet if they start exploring at different unknown locations in an unknown environment. ::: ::: We propose several alternative algorithms that robots could use in attempting to rendezvous quickly while continuing to explore. These algorithms exemplify different classes of strategy whose relative suitability depends on characteristics of the problem definition. We consider the performance of our proposed algorithms analytically with respect to both expected- and worst-case behavior. We then examine their behavior under a wider set of conditions using both numerical analysis and also a simulation of multi-agent exploration and rendezvous. We examine the exploration speed, and show that a multi-robot system can explore an unknown environment faster than a single-agent system, even with the constraint of performing rendezvous to allow communication. ::: ::: We conclude with a demonstration of rendezvous implemented on a pair of actual robots. <s> BIB003 </s> The Characteristics of the Map Merging Methods: A Survey <s> B. Map Merging when Robots Identify Their Relative Positions During the Mapping <s> This paper presents a multi-robot mapping and localization system. Learning maps and efficient exploration of an unknown environment is a fundamental problem in mobile robotics usually called SLAM (simultaneous localization and mapping problem). Our approach involves a team of mobile robots that uses Scan-Matching and Fast-SLAM techniques based on scan-laser and odometry information for mapping large environments. The single maps generated for each robot are more accurate than the maps generated only by odometry. When a robot detects another, it sends its processed map and the master robot generates a very accurate global map. This method cuts down the global map building time. Some experimental results and conclusions are presented. <s> BIB004
An alternative to giving the robots their relative positions at the start of the mapping is to use a rendezvous strategy. In this case, the robots create their maps independently until one robot meets another. From this point the approaches to further mapping differs. While in some approaches the robots continue to create maps independently, in others all the robots contribute to one global map cooperatively. A very simplified map merging approach with rendezvous is discussed in BIB003 by Roy and Dudek. Once the two robots meet, their produced local maps are merged manually. Of course, this is not a suitable solution if robots are to be completely autonomous. A more sophisticated mapping approach is used by Roumeliotis and Bekey BIB001 , who use a Kalman Filter for mapping. Their Kalman Filter approach differs from those mentioned earlier. While approaches described previously assume either that robots create the global map simultaneously or that the initial positions of the robots are known, this approach assumes neither. Each robot constructs its own map independently and these maps can be merged when two robots meet during the mapping process. Although the authors use Kalman Filter primarily for localization, they note that the algorithm can be easily adapted to map merging. Ko et al. BIB002 use particle filters, an alternative to Kalman Filter, for the relative localization of robots. The initial starting positions of the robots are completely unknown and in order to verify that the two maps overlap an active location verification has to be performed. To verify the relative locations the robots agree on a rendezvous point. If they fail to meet, the hypothesis about relative locations is discarded and the map merging is not performed. The particle filter concept for the multi-robot mapping is also utilized by Howard  . He assumes that the robots encounter each other at some time during the exploration and are able to correctly determine their relative positions. When the meeting occurs, the robots further contribute their observations to a common global map in one reference frame and the subsequent meetings of these two robots are ignored. The interesting part of the algorithm is that the already collected environment observations are added to the global map in a backwards manner. Thus, the map merging procedure is not really performed. Instead it appears that for a while two 'virtual' robots are contributing to the mapping process. Bergasa et al. BIB004 use the particle filters together with the scan matching to achieve the generation of a highly accurate local maps of the individual robots. When two robots meet, the map merging process is performed; however, it is very simplified. The authors of this approach note that very accurate relative position detection is required for the maps from two robots to be merged correctly. Even a very small orientation error causes the construction of an inaccurate global map.