The Characteristics of the Map Merging Methods: A Survey <s> A. The Reference Frames <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> BIB001 </s> The Characteristics of the Map Merging Methods: A Survey <s> A. The Reference Frames <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> BIB002 </s> The Characteristics of the Map Merging Methods: A Survey <s> A. The Reference Frames <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> BIB003 </s> The Characteristics of the Map Merging Methods: A Survey <s> A. The Reference Frames <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> BIB004 </s> The Characteristics of the Map Merging Methods: A Survey <s> A. The Reference Frames <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> BIB005
Essentially the map merging is the fusion of several local robot-made maps into one global map BIB003 . All the map merging methods can be classified in three separate groups depending on the moment when the relative reference frames of the local maps are acquired and the maps are merged: • The relative starting positions of the robots are known and all the robots start the mapping in the common reference frame BIB001 ,  ,  . • The initial relative starting positions of the robots are unknown. However, it is assumed that robots meet some time during the exploration to acquire the relative positions and determine the relative reference frames of their local maps BIB003 , BIB002 , BIB004 . The strategy when robots need to meet to merge the local maps is called rendezvous. • The initial relative reference frames of the local maps are unknown and the robots do not determine their relative positions during the exploration  ,  , BIB005 . Consequently the relative reference frames cannot be determined by using relative positions of the robots and other approaches have to be used.