The Characteristics of the Map Merging Methods: A Survey <s> II. RELATED WORK <s> The connectivity of the configuration space has been a valuable concept in the motion planning for single robots in both known and unknown terrains. We show here that n-connectivity plays a similar role for mobile robot teams in providing algorithms for terrain model acquisition in unknown terrains. A bound on the connectivity degree of the free-space, reflected in that of a navigation course, provides us an estimate of the size of a robot team that is effective for the terrain. We consider an unknown planar polygonal terrain. The robots are point-sized and equipped with visual sensors which acquire all visible parts of the terrain by scan operations executed from their locations. The performance is measured by the number of sensor (scan) operations which are assumed to be the most time-consuming of all the robot operations. We show that the Voronoi diagrams and trapezoidal decomposition methods yield solutions for efficient terrain model acquisition by a 2- and 3-robot team using visual sensors. <s> BIB001 </s> The Characteristics of the Map Merging Methods: A Survey <s> II. RELATED WORK <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> BIB002 </s> The Characteristics of the Map Merging Methods: A Survey <s> II. RELATED WORK <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> BIB003 </s> The Characteristics of the Map Merging Methods: A Survey <s> II. RELATED WORK <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> BIB004 </s> The Characteristics of the Map Merging Methods: A Survey <s> II. RELATED WORK <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> BIB005 </s> The Characteristics of the Map Merging Methods: A Survey <s> II. RELATED WORK <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> BIB006 </s> The Characteristics of the Map Merging Methods: A Survey <s> II. RELATED WORK <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> BIB007 </s> The Characteristics of the Map Merging Methods: A Survey <s> II. RELATED WORK <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> BIB008
The map merging is still a new research field, so there are no comprehensive surveys available on the matter. However, there are some trends in existing publications that are used in this paper for the identification of characteristics of map merging methods. The robot mapping has been researched intensively for a long time and a lot of progress has been made. Naturally there have been attempts to summarize and to classify the existing methods. One of such work is Thrun's survey on robotic mapping BIB003 . This comprehensive survey classifies robot mapping methods and offers insight in each of the classes. However, this survey focuses almost exclusively on single robot mapping and only brief information is available about mapping with robot teams. On the matter of distributed mobile robotics a summarizing paper has been written by Parker  . Yet only a small part of this work is devoted to the multi-robot localization, mapping and exploration problem. Besides the section on this problem only discusses the usefulness of multirobot mapping compared to single robot mapping and doesn't try to immerse into multi-robot mapping problems. However, there are papers where mapping problems with multiple robots are considered. Initially the most research activity was dedicated to multi-robot mapping issues other than map merging. For this reason the situation in multi-robot mapping subfields, such as localization BIB004 , BIB005 , coordination and exploration BIB002 ,  , BIB001 , and rendezvous arrangement BIB007 , is better defined than in map merging. The subfield of the map merging is less familiar than other multi-robot mapping subfields mentioned above. Nevertheless there are several authors who have become acquainted and shortly described the situation in the map merging research area BIB006 ,  - BIB008 . However, these reviews are incomplete and often outdated. In most cases the map merging is considered in the context of the specific case study and only closely related works are reviewed. Still, several patterns are common in the existing classifications of map merging methods. Often map merging methods are grouped by the robots' knowledge of the relative positions or the reference frames BIB006 ,  - BIB008 . Other characteristic that is often used for the classification of map merging methods is the type of the maps used in the merging  , BIB008 . An exception is made by Konolige et al.  , who groups the methods by their ability to make a decision when maps can be safely merged and when the merging is not possible. There are several reviews of map merging methods. However, they all share a common trait -the situation in the area is considered in the context of the particular research. It is meant to show the reader why their work is important and not to comprehensively describe the existing state of the art in map merging. A couple of map merging characteristics have been identified (knowledge about the robot positions, type of the maps, decision making) but there are more properties that are important in the context of map merging. This paper describes the familiar characteristics of map merging as well as introduces less popular characteristics like structure of the environment, enabler of the map merging, and time required for the map merging. All these characteristics are important if one needs to choose the implementation of map merging.