The Characteristics of the Map Merging Methods: A Survey <s> I. INTRODUCTION <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> I. INTRODUCTION <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> BIB002 </s> The Characteristics of the Map Merging Methods: A Survey <s> I. INTRODUCTION <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
The development of the autonomous mobile robots is a popular field of research in the artificial intelligence since 1980s BIB002 . Research is motivated by the many possible applications of autonomous mobile robots, which include planetary exploration, reconnaissance, rescue, mowing, and cleaning BIB001 . One of the fundamental problems in mobile robotics that has to be solved is the environment mapping problem. Robots need to be able to construct a map of the environment and to use it for the navigation. A lot of research has been dedicated to the single robot mapping. However, there are problems that are hard to solve, such as measurement errors, high dimensionality of mapping, or data correspondence BIB002 . The use of multiple robots for mapping can solve some of these problems  , and it also offers several other advantages over single robot mapping. Often it is possible to create a map of the environment faster with multiple robots than with only one robot BIB001  . Multirobot mapping teams are more fault tolerant than single robot platforms, as the defection of one robot does not necessarily imply the termination of mapping process. Multiple robots can also use different sensors for mapping, thus improving the quality of resulting map  . Robot teams originated in late 1980s  , however only during the last ten years has the multi-robot mapping question been intensively studied. This may be due to the fact that, although robot teams offer multiple advantages over single robot platforms, several new problems, specific to the multirobot mapping, arise  . From all the multi-robot mapping problems only map merging is considered in this paper. When a robot explores, it collects the information about the environment by using sensors. If multiple robots are used for the exploration of the environment, their collected information has to be fused into one general global map. The fusion of the map information from multiple robots into one global map is called map merging BIB003 . As Konolige et al. notes, "map merging is an interesting and difficult problem, which has not enjoyed the same attention that localization and map building have"  . Although several years since this statement have passed and the map merging problem has received more attention, most of the published papers on the matter are descriptions of specific map merging methods. There are no comprehensive surveys where the information about existing map merging methods would be collected. Consequently no real classification of map merging methods exists. Therefore the goal of this paper is to summarize the information about the existing work in the field of map merging and to identify main characteristics of the map merging methods. The identified characteristics are then further used for the classification of the map merging approaches. The structure of this paper is as follows. At first the related work is discussed in Section II. Then the existing map merging approaches are divided into three groups and described in Section III. From the described map merging approaches the most important map merging characteristics and their possible values are identified and described in Section IV. Section V shows the identified relationships between the values of the characteristics and how to use these relationships for the classification of map merging approaches. Finally, the conclusions are drawn and possible future work defined.