Francesco Amigoni

Simone Gasparini

Maria Gini

Building Segment-Based Maps without Pose Information

Keywords: Map building, multirobot systems, scan matching, map merging, laser range scanners

Most map building methods employed by mobile robots are based on the assumption that an estimate of robot poses can be obtained from odometry readings or from observing landmarks or other robots. In this paper we propose methods to build a global geometric map by integrating scans collected by laser range scanners without using any knowledge about the robots poses. We consider scans that are collections of line segments. Our approach increases the flexibility in data collection, since robots do not need to see each other during mapping, and data can be collected by multiple robots or a single robot in one or multiple sessions. Experimental results show the effectiveness of our approach in different types of indoor environments.

I. INTRODUCTION

Several methods for allowing mobile robots to build maps of unknown environments have been proposed. To build a map, a robot incrementally integrates newly acquired sensor data within previously collected information using knowledge about its own pose or the path it followed since the last integration. Odometry and kinematic models of motion are used to estimate the robot pose (i.e., its position and orientation). Different types of sensors (sonars, laser range scanners, and panoramic cameras) have been used to collect information about the environment. Laser range scanners have become the sensor of choice because of their accuracy and wide availability.

In the last few years, as detailed in the extensive survey by Thrun [START_REF] Thrun | Robotic mapping: A survey[END_REF], most of the methods developed for mapping have been based on probabilistic techniques. The methods have in common the fact they use a Bayes filter to recursively compute the posterior probability over robot poses and maps, given the previous sensor measurements and motion commands. The methods differ in the assumptions they make and in how they compute the posterior probability. Some methods operate online, others require multiple passes through the data and so are used offline.

The approach we present in this paper differs from the methods mentioned above in the sense that we do not assume any knowledge of robot pose and we use exclusively range data to construct a bidimensional geometric map composed of line segments. In particular, we show how to build a global map of an environment by merging the post-processed results of the measurement operations performed by laser range scanners, which we call scans, without using any position information but relying only on geometric information in the scans. Our approach is similar in spirit to early work by Chatila and Laumond [START_REF] Chatila | Position referencing and consistent world modeling for mobile robots[END_REF] who used geometric descriptions of environments. The advantage of using geometric descriptions over the more common grid-based representations is that line segments can be represented with few numbers and produce maps that are easier to use, as recently discussed for example in [START_REF] Brunskill | SLAM using incremental probabilistic PCA and dimensionality reduction[END_REF]. Line segments are also easy to extract automatically from range data.

One might wonder why we do not use odometry, considering that odometric information is often available. The major reason is that we want to use multiple robots to build maps and we want to be able to interrupt the mapping process and resume it at a later time without having to reset the initial poses of the robots (this provides a solution to the socalled "kidnapped robot" problem [START_REF] Engelson | Error correction in mobile robot map learning[END_REF]). In addition, we are interested in building maps with miniature robots, such as the robots described in [START_REF] Rybski | Performance of a distributed robotic system using shared communications channels[END_REF], where no odometry is available. Even if odometry can be replaced in part by sensing (see, for instance, [START_REF] Rybski | Using visual features to build topological maps of indoor environments[END_REF]), we believe it is important to understand the implications of not having odometry (which is often unreliable) and to explore what are acceptable bounds on the error on the initial pose of the robots.

In the following, we call scan a collection of line segments obtained, as explained later in Section III-D, from the points returned by a 2D laser range scanner. Line segments approximate the points returned by laser range scanners. More precisely, a line segment is represented by its end points (extremes) (x 1 , y 1 ) and (x 2 , y 2 ) in the reference frame of the map. We call partial map the result of the integration of two scans, of a scan and a partial map, or of two partial maps. Thus, in the terminology used in this paper, a scan is a special case of a partial map. Both scans and partial maps are collection of line segments. The difference is that we assume the line segments in a scan are ordered (clockwise or counterclockwise), while they are not in a partial map. Range data can be collected by a single or different robots. We assume that the robots move indoor on a 2D surface and that walls and vertical objects are at the height of the laser scan. No other assumption is made about the environment to be mapped: the environment is supposed to be unknown and with no ground-truth maps available. Experiments demonstrate that our method works both in regular and in scattered environments.

This paper presents two main contributions. The first is a method for integrating two partial maps (and, in particular, two scans) relying exclusively on their geometry. We consider the angles between pairs of line segments in the maps as a sort of "geometric landmarks" [START_REF] Grimson | Object recognition by computer: the role of geometric constraints[END_REF] on which our matching process is based: the idea is to match angles of the two partial maps that are similar. This method is robust to large displacements between the partial maps, provided that the maps have an overlap containing at least an angle representing the same portion of the environment. The method integrates two partial maps, S 1 and S 2 , into a map S 1,2 in three major steps:

1) find the possible transformations of S 2 on S 1 ;

2) evaluate the transformations to identify the best transformation t of S 2 on S 1 ; 3) apply the best transformation t to S 2 (obtaining S t 2 ) and fuse the line segments of S 1 and S t 2 to obtain S 1,2 . When S 1 and S 2 are two scans, the first two steps above are known in literature as scan matching.

The second main contribution of this paper is the proposal of three methods for map merging that integrate a sequence S 1 , S 2 , . . . S n of n partial maps. The sequence defines the order in which the partial maps must be integrated; namely S 1 has to be integrated with S 2 , that in turn has to be integrated with S 3 , and so on. We reduce the merging of a sequence of partial maps to the iterated integration of two partial maps.

Our approach for scan matching and map merging without pose information has the advantage of being independent from how the data have been collected. It is indifferent if the scans are collected during a single session or multiple sessions, by multiple robots or a single robot. Robots can be added or removed at any time, and they do not need to know their own position. For the experiments in this paper we used scans acquired by a single robot but all the results are applicable to multirobots. In this case, the mapping process is centralized, with data collected to a location and assembled in a map. More precisely, in a multirobot scenario, our method can be applied at two levels: at the individual robot level, the method integrates the sequence of scans acquired by the robot and, at the global system level, the method integrates, less frequently, the partial maps built by the robots.

The paper is structured as follows. In the next section we outline previous work on scan matching and map merging and compare it with our approach. We present our scan matching method in Section III, and we illustrate our map merging method in Section IV. Section V covers the experimental validation of our contributions. Section VI concludes the paper.

II. RELATED WORK

Robotic mapping addresses the problem of acquiring spatial models of physical environments through mobile robots [START_REF] Thrun | Robotic mapping: A survey[END_REF]. These spatial models, or maps, are typically used for robot navigation, for example to plan paths. In order to build a map, robots use sensors like sonars, cameras, and laser range scanners. The range limitations of these sensors force the robots to navigate in the environment while building the map. As a consequence, maps are built incrementally, integrating the newly perceived information within the already available map. Usually, this integration exploits the (uncertain) knowledge about robot poses. Maps can be represented topologically (e.g., by graph-based data structures) or geometrically (e.g., by data structures storing grids, points, or line segments). Since grid-based maps require high-dimensional representations with thousands of numbers, segment-based maps have been recently advocated to reduce dimensionality [START_REF] Brunskill | SLAM using incremental probabilistic PCA and dimensionality reduction[END_REF].

Multirobot mapping has attracted attention in recent years because of the robustness of exploring in parallel with multiple robots and of the potential savings in the time needed to map large areas. A key challenge in multirobot mapping is merging the maps produced by independent robots. The methods proposed in the literature to address the map merging problem have been mostly based on building robot centric maps and merging them using the relative positions of the robots, which must be known.

One way of doing this is to extend SLAM (Simultaneous Localization and Mapping) or CML (Concurrent Mapping and Localization) techniques [START_REF] Burgard | Collaborative exploration of unknown environments with teams of mobile robots[END_REF], [START_REF] Ko | A practical, decisiontheoretic approach to multi-robot mapping and exploration[END_REF], [START_REF] Fenwick | Cooperative concurrent mapping and localization[END_REF] to multirobots. SLAM and CML techniques are widely employed in the context of single robot mapping and refer to the problem of building a map and, at the same time, estimating the pose of the robot. Since odometric measurements are noisy [START_REF] Borenstein | Measurement and correction of systematic odometry errors in mobile robots[END_REF], robot localization cannot rely only on dead-reckoning, and a probabilistic machinery is employed to localize the robot in the map that is being constructed. A family of approaches adopts Kalman filtering [START_REF] Dissanayake | A solution to the simultaneous localization and map building (SLAM) problem[END_REF], [START_REF] Guivant | Optimization of the simultaneous localization and map-building algorithm for real-time implementation[END_REF] in an incremental process that estimates robot pose and landmarks' positions in the map. This solution requires a large computational effort as the number of features in the map grows and it is also not well suited to dynamic environments and environments with indistinguishable landmarks. Another probabilistic approach is based on the Expectation-Maximization (EM) algorithm [START_REF] Simmons | Coordination for multi-robot exploration and mapping[END_REF], [START_REF] Thrun | A probabilistic approach to concurrent mapping and localization for mobile robots[END_REF], [START_REF]A real-time algorithm for mobile robot mapping with applications to multi-robot and 3D mapping[END_REF], [START_REF] Thrun | A probabilistic online mapping algorithm for teams of mobile robots[END_REF] and is usually employed to build grid-based maps. Robot pose is tracked by a multimodal probability density function which copes well with the correspondence problem (i.e., having to associate sensor data with features in the map) and with failure recovery. To alleviate the computational burden, faster methods have been developed, including particle filters [START_REF] Ko | A practical, decisiontheoretic approach to multi-robot mapping and exploration[END_REF] and FastSLAM [START_REF] Thrun | FastSLAM: An efficient solution to the simultaneous localization and mapping problem with unknown data association[END_REF].

Most map merging techniques rely on the assumption that the robot poses are known. For example, in [START_REF] Burgard | Collaborative exploration of unknown environments with teams of mobile robots[END_REF], [START_REF] Simmons | Coordination for multi-robot exploration and mapping[END_REF] the pose of the robots is assumed to be known at all times; in [START_REF]A real-time algorithm for mobile robot mapping with applications to multi-robot and 3D mapping[END_REF] the robots don't know their relative starting positions but each robot has to start within sight of the team leader; in [START_REF] Thrun | A probabilistic online mapping algorithm for teams of mobile robots[END_REF] the robots must start in known nearby locations; in [START_REF] Howard | Multi-robot mapping using manifold representations[END_REF] the robots have to see each other from time to time. In [START_REF] Rekleitis | Multi-robot collaboration for robust exploration[END_REF] a stationary robot continuously tracks the motion of another robot which acquires sensory data from the environment. In [START_REF] Ko | A practical, decisiontheoretic approach to multi-robot mapping and exploration[END_REF], particle filters are used for partial map localization. The robots have to actively verify their relative poses before the maps are merged, and the integration of partial maps is not fully automated. In [START_REF] Hähnel | A highly efficient fast-SLAM algorithm for generating cyclic maps of large-scale environments from raw laser range measurements[END_REF] a single robot is used with FastSLAM to generate maps directly from laser range data. The method aligns a scan to the previous one by computing an occupancy grid map [START_REF] Moravec | Sensor fusion in certainty grids for mobile robots[END_REF]. The method, which requires a model of the odometry error, is robust and converges even in cases where the standard Rao-Blackwellized particle filter [START_REF] Doucet | Rao-Blackwellized particle filtering for dynamic Bayesian networks[END_REF] without odometry correction fails to converge.

An exception is the work reported in [START_REF] Konolige | Map merging for distributed robot navigation[END_REF] where map merging is done using a decision theoretic approach. The robots do not need to know their own position, but the maps have to be annotated with distinctive features. This step is currently done manually. The match is done not with individual scans but with patches made of 15 scans taken 0.5 m apart, each of them containing 2 to 8 distinctive features. This is an improvement over earlier work [START_REF] Gutmann | Incremental mapping of large cyclic environments[END_REF], where map merging was done by correlation of a patch over a partial map. The method required the scans to be taken close to each other (30 cm in the examples shown), and a very good scan matching algorithm, since map merging could not be undone.

The approach we present in this paper is based on building geometric maps, which are represented as collections of line segments, from scans, which are also collections of line segments. In the literature, scans are either based on line segments or on raw sensor data. Scan matching is the process of calculating the translation and rotation of a scan to maximize its overlap with a reference scan.

Lu and Milios [START_REF] Lu | Gloablly consistent range scan alignment for environment mapping[END_REF], [START_REF]Robot pose estimation in unknown environments by matching 2D range scans[END_REF] introduced the idea of consistent pose registration, where scans from a laser range scanner taken at different poses are matched using a priori information and odometry constraints between successive poses. The algorithm does multiple passes through the data, so it is not real-time. The algorithm iteratively minimizes an error measure by first finding a correspondence between points in the two scans, and then doing a least square minimization of all the point-topoint distances to determine the best transformation. An initial pose estimate is provided through odometry to avoid erroneous alignments. The method works very well when the errors in the initial position are small (< 20 cm).

Another well-known technique for scan matching is the iterative algorithm of Cox [START_REF] Cox | Blanche: An experiment in guidance and navigation of an autonomous robot vehicle[END_REF] for matching range scans to an a priori map of line segments. Since it assumes small displacements between a scan and the map, the algorithm first finds the correspondence between scan points and line segments and then calculates the translation and rotation that minimize the (square of all) point-to-segment distances. The two steps are repeated until the process converges. Each iteration returns a position correction vector and a variance-covariance matrix that evaluates the match. This approach has been extended in [START_REF] Gutmann | Amos: Comparison of scan matching approaches for self-localization in indoor environments[END_REF], where line segments are extracted from the previous scans and used as the reference model for matching, instead of using an a priori model of the environment, These methods can be applied only to polygonal environments, a limitation that our method tries to overcome.

With straight perpendicular walls, matching can be done using histograms, as in [START_REF] Weiss | Keeping track of position and orientation of moving indoor systems by correlation of range-finder scans[END_REF], where the orientation is computed by cross-correlation of the histograms of the angles between the actual and previous scans, and the translation by crosscorrelation of the distance histogram. This method is sensitive to large displacements between the maps and to changes in the environment. The improvement proposed in [START_REF] Röfer | Building consistent laser scan map[END_REF] deals with non-perpendicular walls and segment maps, even if it still assumes straight walls and has poor performance in scattered environments.

In [START_REF] Zhang | Line segment based map building and localization using 2D laser rangefinder[END_REF] line segments are extracted from range points and a special "center of gravity" representation is used to describe the uncertainty of line segments. Pairs of line segments are matched and the translation is computed by least square minimization, using an initial estimate for the displacement provided by odometry. The technique proposed in [START_REF] Tovar | Robot motion planning for map building[END_REF] refines the alignment of scans collected by multiple robots using the partial Hausdorff distance to compute the best transformation between a new scan and a point map of the previously explored region. This method also requires an initial estimate of the pose of the scans. The method proposed in [START_REF] Martignoni | Localizing while mapping: A segment approach[END_REF] is similar to our approach in that it extracts line segments from laser range scanner readings and builds incrementally a global map. It first determines the relative orientation of the two maps by computing the histogram of the angle differences and then adjusts the translation by overlapping the line segments using least square minimization. The method works for linear and static environments and for very small displacements. Our method is more general and allows for significant displacements between two partial maps, provided that they have at least a corresponding angle representing the same portion of the environment.

There have been a few attempts to match scans independently of odometry. For example, [START_REF] Einsele | Real-time self-localization in unknown indoor environments using a panorama laser range finder[END_REF] proposes to use a panoramic range finder to build segment maps. It identifies line segments representing walls or other boundaries of the environment and matches the scans taken from different positions without relying on any additional source of information. This is accomplished by applying a dynamic programming algorithm to the vertical lines of the map. The method operates in polygonal or rectilinear environments, but does not work well in scattered environments and it (implicitly) relies on small displacements of the robot. In [START_REF] Latecki | Building polygonal maps from laser range data[END_REF], segment maps are matched by establishing a correspondence between their features. This is reduced to measure shape similarity between polylines according to their maximal convex arcs, following a method originated in computer vision. Although no data are reported about the displacement of the maps, from the reported experiments it can be inferred to be around 0.5 m.

In [START_REF] Tomono | A scan matching method using euclidean invariant signature for global localization and map building[END_REF], a scan matching algorithm extending geometric hashing is proposed. The main idea is a signature representation of the local region around each point of the scan. The search for the best alignment between two scans is performed with a voting system in the Hough space containing all the signatures. The candidate alignment is then applied to the measurement model of the SLAM framework. From the reported experimental data, it seems that the system is implicitly based on small displacement between two scans, about 20 -30 cm. The scan matching method proposed in [START_REF] Zezhong | Scan matching based on CLS relationships[END_REF] does not use information about odometry to compute the alignment between two scans. It is based on geometric features of the maps, the so-called Complete Line Segment relationships. All the line segments that completely represent real objects in the environment are singled out and their relative position is used to find a correspondence with the Complete Line Segments of the old map. The method has been shown to be fast and accurate, even if it is not clear how it can deal with ambiguity and the case of non-occluded but partially visible line segments (features that go beyond the visibility region of the sensor). It also seems that it cannot be extended to multirobot map building with unknown position of the robots, since it is weakly based on a sorting order of the line segments to improve search efficiency.

III. METHOD FOR SCAN INTEGRATION

In this section, we present our method for integrating two scans. The method works in the three steps outlined in Section I. Our algorithm INTEGRATE (reported as Algorithm 1) is exclusively based on the geometric information and constraints [START_REF] Grimson | Object recognition by computer: the role of geometric constraints[END_REF] contained in the scans. In particular, we consider angles between pairs of line segments in the scans as a sort of "geometric landmarks" on which the matching process is based. This use of "local" geometric features is significantly different from other related works in map building that use "global" geometric features (e.g., those represented by an histogram of angle differences).

INTEGRATE integrates two scans into a partial map. Let's call S 1 and S 2 the two scans and S 1,2 the resulting partial map. Although in the following we discuss, for simplicity, the integration of two scans, all the methods are applicable to the integration of two partial maps. In the algorithms below, two points are considered to coincide when they are closer than POINTDISTANCETOLERANCE (in our experiments we set this parameter to 15 mm) and two angles are considered equal when their values differ of less than ANGLEDIFFER-ENCETOLERANCE (in our experiments we set this parameter to 0.2 rad).

Algorithm 1 INTEGRATE

Input: two scans S 1 and S 2 Output: a map S 1,2 1: T ← all transformations of S 2 on S 1 ⊲ see Algorithm 2 2: t ← best transformation in T ⊲ see Algorithm 4 3: S 1,2 ← fusion of S 1 and S t 2 ⊲ see Algorithm 5

A. Find Transformations

This step, given the scans S 1 and S 2 , first finds the angles between the line segments in S 1 and between the line segments in S 2 and, second, finds the possible transformations (namely, the rotations and translations) that superimpose at least one angle α 2 of S 2 to an equal angle α 1 of S 1 . We use the angles between pairs of line segments as geometric landmarks and we try to match equal angles in the two scans. The pseudo-code is reported as Algorithm 2. Finding the possible transformations is a difficult combinatorial problem since in principle, without any information about the relative poses of the two scans, there are O(n 2 1 n 2 2 ) possible transformations, where n 1 and n 2 are the numbers of line segments in S 1 and S 2 , respectively. We have therefore devised three heuristics for reducing this complexity and finding a set of (hopefully) significant transformations between two scans. They are described in the following.

1) Consider Angles between Consecutive Line Segments in a Scan:

In each scan, we select the angles between two consecutive line segments; let A c 1 and A c 2 be the sets of such angles for S 1 and S 2 , respectively. Two line segments are consecutive when they have an extreme point in common. Then, we find the set of all the transformations that make

Algorithm 2 Find transformations

Input: two scans S 1 and S 2 Output: a set of transformations T 1: A 1 ← empty 2: for all pairs of line segments s 1 and s

′ 1 (s 1 = s ′ 1 ) in S 1 do 3:
add to A 1 the angle between s 1 and s ′

if α 1 = α 2 then 12:
add to T the rototranslation that superimposes α 2 to α 1 13: end if 14: end for an angle in A c 2 to correspond to an equal angle in A c 1 . This amounts to change the step 3 (respectively, 7) of Algorithm 2. The modified step adds an angle to A 1 (A 2 ) only when s 1 and s ′ 1 (s 2 and s ′ 2 ) are consecutive. The number of possible transformations found by this method is O(n 1 n 2 ). We note that finding the sets A c 1 and A c 2 is greatly facilitated when the line segments in S 1 and in S 2 are ordered. This is usually the case when scans are acquired with laser range scanners, since the points returned by the sensor are ordered counterclockwise and it is straightforward to maintain the same order in the line segments that approximate the points.

Although this heuristic seems to perform well in indoor environments where consecutive walls are usually perpendicular, the errors introduced by the sensor (for example due to irregular reflection patterns) and by the algorithm that approximates points with line segments may alter the representation of these angles. Hence, the angles between consecutive line segments sometimes do not constitute a good model of the environment angles.

To improve the performance of this heuristic, we can consider angles between consecutive line segments even when the line segments do not have a common extreme point (this could be done only if the line segments of the scans are ordered). Moreover, consecutive line segments can be considered to form a significant angle only if they are longer than a fraction (specified by the parameter SEGMENTLENGTHPERCENTAGE, set to an average value of 20 in our experiments) of the longest line segment in the scan. The implicit assumption is that long line segments are more reliable than short line segments in representing the environment. Although this improvement gives good results with scans, it is not easily applicable to partial maps in which an order on the line segments is often hard to define.

2) Consider Angles between Randomly Selected Line Segments in a Scan: In each scan, we examine a number of angles between pairs of line segments selected randomly. We assign a higher probability to be selected to longer line segments, since they provide more precise information about the environment. Let A r 1 and A r 2 be the sets of the selected angles for S 1 and S 2 , respectively. We find the set of all the transformations that bring an angle in A r 2 to correspond to an equal angle in A r 1 . The number of transformations generated by this method is O(a 1 a 2 ), where a 1 = |A r 1 | and a 2 = |A r 2 | are the number of angles in A r 1 and A r 2 , respectively. Instead of assigning directly to each line segment the probability of being selected (according to its length) and of selecting a number a 1 (respectively, a 2 ) of pairs, the following approximate and easy-to-implement technique is employed. Initially only line segments longer than SEGMENTDIVISION-FACTOR (set to 0.5 in our experiments) times the length of the longest line segment in S 1 (respectively, S 2 ) are considered for selection. All the line segments considered have equal probability of being selected. Then, we proceed to iterate with k = 1, 2, . . . , K. In the k-th iteration, we use a threshold equal to SEGMENTDIVISIONFACTOR k times the length of the longest line segment in S 1 (respectively, S 2 ). Out of the line segments longer than this threshold we select one with equal probability. Thus, the parameter SEGMENTDIVISIONFACTOR determines the length of the line segments that are considered for selection and, implicitly, the probability of selection. The pseudo-code of the algorithm is reported as Algorithm 3. This technique tries first to find transformations based on angles between long line segments; then it progressively considers transformations based on angles between shorter and shorter line segments. The above technique can be further improved by stopping the generation of transformations when a "good enough" transformation is found. (The evaluation of the quality of a transformation is discussed in Section III-B.)

3) Consider Angles between Perpendicular Line Segments in a Scan: In each scan, we select only angles between perpendicular line segments. This amounts to change step 3 (respectively, 7) of Algorithm 2. The modified step adds an angle to A 1 (A 2 ) only when s 1 and s ′ 1 (s 2 and s ′ 2 ) are perpendicular. This heuristic is particularly convenient for indoor environments, where the presence of regular walls usually involves perpendicular line segments. To make this heuristic more efficient, we used histograms. The histogram of S 1 (and, in similar way, that of S 2 ) has nslots buckets. Each bucket L i (i = 0, 1, . . . , nslots -1) contains the line segments with orientation comprised between π × i/nslots and π × (i + 1)/nslots, measured with respect to a given reference axis. To each element L i of the histogram is associated a value calculated as the sum of the lengths of the line segments in L i . The principal direction of an histogram is the element with maximum value. The normal direction of an histogram is the element that is π/2 rad away from the principal direction. In Fig. 1, the histogram of a scan taken in an indoor environment is shown (with nslots = 18). The principal direction is the element L 9 and the normal direction is the element L 0 . Let A h 1 and A h 2 be the sets of angles formed by a line segment in the principal direction and by a line segment in the normal direction of the histograms of S 1 and S 2 , respectively. The set of possible transformations is then found comparing the end for 12: end for

angles in A h 1 and A h 2 .
The number of possible transformations generated by the above heuristic is O(p 1 q 1 p 2 q 2 ), where p i and q i are the number of line segments in the principal and normal directions of the histogram of scan S i .

1: The histogram of a scan

B. Evaluate Transformations

Every transformation found in the previous step needs to be evaluated in order to identify the best one. To determine the goodness of a transformation t we transform S 2 on S 1 (in the reference frame of S 1 ) according to t (obtaining S t

2 ), then we calculate the approximate length of the line segments of S 1 that correspond to (namely, match with) line segments of S t 2 . The transformation value is the length of the corresponding line segments that the transformation produces. More precisely, the value of a transformation is the sum of all the matching values calculated for every pair of line segments s 1 ∈ S 1 and s t 2 ∈ S t 2 . The matching value between two line segments s 1 and s t 2 is calculated as follows. We project s t 2 on the line supporting s 1 thus obtaining a projected line segment s t 2p and then we compute the length l 1 of the common part of s 1 and s t 2p ; we do the same but projecting s 1 on s t 2 , obtaining l 2 . The matching value of s 1 and s t 2 is calculated as the average of l 1 and l 2 . When s 1 and s t 2 do not intersect, the matching value is multiplied by 0.95 d(s1,s t 2 )/POINTDISTANCETOLERANCE to penalize the match between line segments that are far away. Note that 0.95 is an empirical constant whose value has been determined during experimental activities. d(s 1 , s t

2 ) is the distance between two line segments, calculated as in [START_REF] Grimson | Object recognition by computer: the role of geometric constraints[END_REF]:

d(s 1 , s 2 ) = min(max(dist(s 1 , start(s 2 )), dist(s 1 , end(s 2 ))), max(dist(s 2 , start(s 1 )), dist(s 2 , end(s 1 ))))
where start and end are the extremes of a line segment and dist(s, p) is the Euclidean distance between point p and the line supporting segment s (Fig. Finally, two special cases can appear during the evaluation of the matching value of s 1 and s t 2 . The matching value is set to 0 when the two line segments are too far away, namely when the ratio of d(s 1 , s t

2 ) to POINTDISTANCETOLERANCE is larger than SEGMENTDISTANCETHRESHOLD. SEGMENT-DISTANCETHRESHOLD is usually set to 5 to obtain good experimental results. The transformation is discarded when the two line segments intersect and are longer than SEG-MENTLENGTHREFUSE (usually set to 80 cm or 100 cm in our experiments). The pseudo-code of the algorithm is reported as Algorithm 4. (Steps 24-30 are explained in the next section.) The above algorithm evaluates a single transformation by considering all the pairs of line segments of the two scans that are O(n 1 n 2 ). A way to limit this computational effort is to stop the evaluation of a transformation t when its value cannot be larger than the current maximum, namely when the length of the line segments of S 1 (or S t

2 ) whose matching value has been not yet calculated is less than the difference between the current value of t and the current maximum.

C. Apply the Best Transformation and Fuse the Scans

Once the best transformation t has been found, the third and last step of our scan integration method transforms the second scan S 2 in the reference frame of S 1 according to t, obtaining S t 2 .

Because of calculation, scan, and matching errors the scans might not align exactly. To produce the output map S 1,2 we first replace each matching chain created in steps 24-30 of Algorithm 4 with a polyline, and we add the resulting polylines to the unmatched line segments of S We explicitly note that, given an element s 1 , s t 2 , the matching chain C that contains (that is generated by) s 1 , s t 2 is uniquely identified. It is easy to see that a transformation t generates a set of (disjoint) matching chains.

Each matching chain (i.e., each set of pairs of corresponding line segments) is fused in a single polyline, which then replaces the corresponding line segments in the final map. Therefore, the final map is obtained by adding the polylines that represent the matched line segments (i.e. the line segments in the matching chains) to the unmatched line segments of S 1 and S t 2 . The pseudo-code is in Algorithm 5 and an example is shown in Fig. 4.

We build the polyline that approximates the line segments in a matching chain C by iteratively building a sequence of approximating polylines P 0 , P 1 , . . . that converges to the polyline P that adequately approximates (and substitutes in the resulting map) the matching line segments in C. The polyline P 0 is composed of a single line segment connecting the pair of farthest points (extremes of the line segments) in C. Given the polyline P n-1 , call s the line segment in (a pair belonging to) C that is at the maximum distance from its (closest) corresponding line segment s in P n-1 . If the distance d(s, s) is less than the acceptable error FUSIONTOLERANCE (set to 15 mm in our experiments), then P n-1 is the final approximation P . Otherwise, s is inserted in P n-1 to substitute s and s is connected to the two closest line segments in P n-1 to obtain the new polyline P n .

The above algorithm is not guaranteed to terminate within a given time bound, because line segments in C can be considered an unpredictable number of times in building the approximating polyline. For this reason, we implemented a 4: An example of iterative construction of an approximating polyline, shown in black, for a matching chain, shown with two levels of gray greedy version of the above (plain) algorithm in which a line segment s in (a pair in) C is considered only once for insertion in the polyline. The greedy method produces approximate polylines that are more "clean" than those produced by the plain method (Fig. 5). Moreover, given a matching chain C, the greedy version of the algorithm is guaranteed to terminate in O(c) iterations, where c is the number of pairs in C. Note that, strictly speaking, the fusion of the scans presented in this section is not part of scan matching., as it is intended in literature. However, we use it in INTEGRATE to reduce the complexity (i.e., the number of line segments) of the resulting map.

D. Analysis of Approximation Errors

In this section, we present an analysis of the approximation errors introduced by the scan integration method described above. We assume that the points acquired by the laser range scanner are affected by an error of σ (typically, this value is around 1 cm). This means that the real point in the environment lies within a circle centered in the point returned by the sensor and with radius σ.

The points returned by the sensor are approximated with a set of line segments following the approach described in [START_REF] Gonzáles-Baños | Navigation strategies for exploring indoor environments[END_REF]. We operate in two steps: (1) the points are grouped into clusters and (2) a polyline is generated to fit the points in each cluster. In (1), we consider the acquired points in counterclockwise order and we group in the same cluster the consecutive points whose distance is less than a threshold τ (set to 20 cm in our experiments) from their successors. In (2) we approximate the points in a cluster by recursively building

Algorithm 5 Fusion of two scans

Input: two scans, S 1 and S t 2 , and a set of matching chains {C} relative to t Output: the map S 1,2 1: S 1,2 ← empty 2: add to S 1,2 the unmatched line segments of S 1 and S t a polyline: initially it connects the first and the last point in the cluster, then the farthest point from the current polyline becomes a new endpoint of the polyline; the process continues until all points in the cluster are within a distance κ (set to 25 mm) from the polyline. Hence, the line segments in a scan approximate the points perceived by the laser range scanner. The polyline generation presented above resembles that of [START_REF] Canou | A local map building process for a reactive navigation of a mobile robot[END_REF] that builds clusters on the basis of angles instead of distances. (Note that these polylines approximate perceived points in the post-processing of scan acquisition and are different from the polylines approximating matching chains in the fusion of scans.)

The clustering of points does not introduce any approximation error. The threshold of the clustering algorithm influences the number of polylines that are created but not the precision with which the points are approximated by these polylines. Since, in our experiments, the maximum range of the laser sensor has been set to 8 m and its angular resolution to 1 • , two consecutive points at the end of range of the sensor are separated by about 14 cm (obtained from 8 m × sin(1 • )). Hence, the clustering threshold τ has been set to 20 cm in order to keep in the same cluster two consecutive points at the end of the range. Once the points have been separated in clusters, the generation of the polyline approximating the points in a cluster introduces, by definition, a maximum (worst-case) error of κ.

During scan integration, the fusion (see Section III-C) of the line segments of two scans introduces other approximation errors. More precisely, given a matching chain C, the maximum (worst-case) distance between a line segment of the resulting polyline and a line segment belonging to a pair in C (namely, a line segment of S 1 or S t 2 ) is FUSIONTOLERANCE in the plain version of the fusion algorithm. Our greedy implementation introduces a larger approximation error that has been experimentally evaluated (on a sample of scans from Section V) to be almost always less than 40 mm.

Globally, the approximation error introduced by our scan integration approach is, in the worst case, κ + 40 mm, given that the points returned by the sensor (on which the algorithms work) are affected by an error of σ.

IV. METHODS FOR MAP MERGING

The scan integration method discussed in the previous section produces a map S 1,2 = INTEGRATE(S 1 , S 2 ). The reference frame of S 1,2 coincides with the reference frame of S 1 , since t is a transformation that brings the reference frame of S 2 in the reference frame of S 1 . The main advantage of INTEGRATE is that, since it is not based on information about the relative position of S 1 and S 2 and it works with collections of line segments, it is applicable indifferently to situations in which S 1 and S 2 are scans and to situations in which S 1 and S 2 are partial maps. Obviously, in this second case, the partial maps could contain a larger number of line segments and the computational time would be larger.

In this section, we describe three proposed methods (schematically shown in Fig. 6) for integrating a sequence S 1 , S (c) Pivot method 6: A schematic representation of the three map merging methods Note that our contribution to the solution of the problem of integrating a sequence of partial maps is a step towards the solution of the more general (and complex) problem of integrating a set of partial maps. Some issues about this general problem are discussed in Section V-C.

A. Sequential Method

The simplest method is the sequential method. It operates as follows. The first two partial maps in the sequence are integrated, the obtained map then is grown by sequentially integrating the third partial map, and so on. Hence, S 1 is integrated with S 2 to obtain S 1,2 , S 1,2 is integrated with S 3 to obtain S 1,2,3 , and so on. Eventually, the final map S 1,2,...,n is constructed. In order to integrate n partial maps, the sequential method requires n -1 calls to INTEGRATE. A problem with the sequential method is that, as the process goes on, INTEGRATE is applied to a partial map that grows larger and larger (it contains more and more line segments). This will cause difficulties in the integration of S i with large i, since S i could match with different parts of the larger map S 1,2,...,i-1 .

B. Tree Method

To overcome the above problem, the integration of a small partial map with a large partial map should be avoided. This is the idea underlying the tree method, which works as follows. Each partial map of the initial sequence is integrated with the successive partial map of the sequence to obtain a new sequence S 1,2 , S 2,3 , . . . , S n-1,n of n -1 partial maps. Then, each partial map of this new sequence is integrated with the successive one to obtain a new sequence S 1,2,3 , S 2,3,4 , . . . , S n-2,n-1,n of n -2 partial maps. The process continues until a single final map S 1,2,...,n is produced.

The tree method always integrates partial maps of similar size, since they approximately contain the same number of line segments. The number of calls to INTEGRATE required by the tree method to integrate a sequence of n partial maps is n(n -1)/2. Note also that, while it is quite obvious that the sequential method can be applied online (i.e., while the robot is moving), the most natural implementation of the tree method is offline, since it is not straightforward to devise an online algorithm for the tree method that requires constant time, as n grows, to update the tree (some results about online implementation are reported in Section V-B).

To speed up the tree method we have developed a heuristic that, given a sequence of partial maps at any level of the tree (let us suppose at level 0 for simplicity), attempts to integrate the partial maps S i and S i+2 ; if the integration succeeds (for example, a success can be experimentally determined by calculating if the value of the best transformation returned by INTEGRATE is above a threshold), the final result S i,i+2 represents the same map that would have been obtained with three integrations: S i with S i+1 to obtain S i,i+1 , S i+1 with S i+2 to obtain S i+1,i+2 , and S i,i+1 with S i+1,i+2 to obtain S i,i+1,i+2 . The number of partial maps in the new sequence is reduced by one unit, because S i,i+2 substitutes both S i,i+1 and S i+1,i+2 . This heuristic finds its natural applicability when the partial maps S i and S i+2 are already the result of a number of integrations performed by the tree method and their common part is significant. For example, in the sequence produced at the level 3 of the tree technique the first (S 1,2,3,4 ) and the third (S 3,4,5,6 ) partial maps have a significant common part, since approximately half of the two partial maps overlaps. This improves the robustness of the method, since corresponding angles are likely to be found in the two partial maps.

A problem with the tree method is caused by the presence of "spurious" line segments in the integrated maps, namely line segments that correspond to the same part of the real environment but that are not fused together with the procedure of Section III-C, for example because their alignment is imprecise (Fig. 7). This problem is exacerbated in the tree method since the same parts of the partial maps are repeatedly fused together and errors accumulate.

C. Pivot Method

To avoid the problems of the sequential and tree methods, we devised the pivot method that combines the best features of the two above methods. This method starts as the tree method and constructs a sequence S 1,2 , S 2,3 , . . . , S n-1,n of n -1 partial maps starting from the initial sequence. At this point, we note that S 2 is part of both S 1,2 and S 2,3 and that the transformation t1,2 used to integrate S 1 and S 2 provides the position and orientation of the reference frame of S 2 in the reference frame of S 1,2 . It is therefore possible to transform S 2,3 according to t1,2 and fuse the line segments of the partial 1m 7: Spurious line segments that have not been fused together in the final map maps S 1,2 and S t1,2 2,3 to obtain S 1,2,3 . In a similar way, S 1,2,3,4 can be obtained from S 1,2,3 and S 3,4 by applying to the latter the transformations t2,3 and t1,2 and fusing the line segments of S 1,2,3 and S t2,3 t1,2 3,4

. Iterating this process, from the sequence S 1,2 , S 2,3 , . . . , S n-1,n the final map S 1,2,...,n is obtained.

The pivot method integrates partial maps of the same size, like the tree method, and requires n -1 calls to INTEGRATE, like the sequential method. (In addition it requires n -2 executions of the not-so-expensive step 3 of INTEGRATE, see Algorithm 1.) Integrating the line segments of two scans only once, the pivot method reduces the problem of spurious line segments. The pivot method is also naturally implementable in an online system. The problem of spurious line segments is reduced but not completely eliminated by the pivot method; a way to further reduce this problem is to fuse not S 1,2 and S t1,2 2,3 , but S 1,2 and S t1,3 3 , where t1,3 is the composition of t1,2 and t2,3 . The pseudo-code of the algorithm for this pivot method is reported as Algorithm 6.

Algorithm 6 Pivot method for map merging

Input: a sequence of scans, S 1 , S 2 , . . . , S n Output: a final map S 1,2,...,n 1: S 1,2 ← INTEGRATE(S 1 , S 2 ) and store t1,2 2: for i = 3,4,. . . ,n do 3:

S i-1,i ← INTEGRATE(S i-1 , S i ) and store ti-1,i 4: t1,i ← compose t1,i-1 and ti-1,i 5: S t1,i i ← transform S i according to t1,i 6:
S 1,2,...,i ← apply the fusion procedure (Algorithm 5) to S 1,2,...,i-1 and S t1,i i 7: end for

V. EXPERIMENTAL RESULTS

The experimental validation of our methods has been done both with data collected in our laboratory (Sections V-A and V-B) and with data publicly available on the Internet (Section V-C). In our laboratory, we used a SICK LMS 200 laser range scanner (mounted on a Robuter mobile platform at a height of approximatively 50 cm) to acquire a sequence of distance measurements along directions separated by a programmable angle (1 • , in our case) sweeping 180 • . The result of a sensing operation is thus a set of points expressed in polar coordinates, with the origin of the coordinate frame in the sensor itself. These points are approximated by line segments, as described in Section III-D.

For the experiments of Sections V-A and V-B we acquired 31 scans (Table I). The scans have been acquired in different environments (forming a loop about 40 m long) by driving the robot manually and without recording any odometric information. We started from a laboratory, a very scattered environment, then we crossed a narrow hallway with rectilinear walls to enter a department hall, a large open space with long perpendicular walls, and finally we closed the loop re-entering the laboratory (see the dashed path in Fig. 12). The experiments have been designed to include a variety of cases and to stress the algorithms we propose. The correctness of the integrations has been determined by visually evaluating the maps with respect to the real environment. The displacements (both translational and rotational) between the scans are significant. The translational displacements are between 34 cm and 2.8 m, with an average of 1.2 m. The rotational displacements are between 0.0035 rad and 1.73 rad, with an average of 0.33 rad. (These values have been derived from the automated matching of the scans performed by our method.) These displacement values are much more than those usually reported in literature. We note that large displacements allow the mapping process to quickly cover the environments with few steps.

The programs have been coded in ANSI C++ employing the LEDA libraries 4.2 and have been run on a 1 GHz Pentium III processor with Linux SuSe 8.0. We stress that our approach is independent of the robots used to acquire the scan data, as shown in Section V-C; thus can be naturally applied in a multirobot context, provided that the scans are taken at the same height.

A. Scan Integration Experiments

For every pair of consecutive scans acquired in our laboratory, we tested the basic method for scan integration and the three heuristics, sometimes modifying the values of the parameters. SEGMENTLENGTHPERCENTAGE ranged from 2 (for scans with long line segments) to 40 (for scans with short line segments). SEGMENTLENGTHREFUSE ranged from 80 cm (for scans with short line segments) to 140 cm (for scans with long line segments).

In general, our experimental results demonstrate that the proposed scan integration method performs well (Table II), but not all the pairs can be integrated. 28 pairs of scans out of 31 possible pairs (S 31 is integrated with S 1 ) have been correctly matched with at least one of the heuristics presented in Section III (last row of Table II). Unsurprisingly, the histogrambased heuristic worked well with scans containing long and perpendicular line segments, like those taken in the hallway and in the hall. The heuristic that considers consecutive line segments seems to work well in all three kinds of environment, even if sometimes it needs some parameter adjustments.

Table III shows the results obtained by integrating three interesting pairs of scans (see also Fig. 8). S 4 and S 5 were I: Scans acquired in our laboratory (line segment lengths are in mm) taken inside the laboratory: they contain a large number of short line segments since the environment is highly scattered. The heuristic that works better is that based on consecutive line segments: it was able to find a good transformation evaluating only two transformations. On the other hand, the evaluation of all the possible transformations is infeasible (over 40, 000 matches to evaluate!). S 18 and S 19 were taken along the hallway: they contain fewer line segments than the previous scans and are characterized by long rectilinear line segments. Even in this case, evaluating all the transformations is expensive, while the consecutive line segments heuristic performs well. S 25 and S 26 were taken in the hall: they contain only few line segments since the environment is characterized by long rectilinear and perpendicular walls. All the heuristics perform well in this case because, starting from a small number of line segments, there are only few transformations that are easy evaluated.

For scan pairs S 1 -S 2 and S 2 -S 3 our method was not able to find the correct transformation. As shown in Fig. 9, these scans contain many short line segments representing scattered small objects (chairs, tables, robots, and boxes). It is almost impossible, even for a human being, to find the correct match between these scans without any prior information about their relative positions. Similar problems emerged in the hall. For example, Fig. 10 shows scans S 27 and S 28 , where the second one has been taken after rotating the robot of about 100 degrees. Since the environment is large and has only few objects that can be used as reference, a drastic change of the field of view eliminates any common reference between scans, thus automatic matching is impossible.

We now discuss the role of the parameters that influence the performance of our scan integration method. POINTDIS-TANCETOLERANCE affects the matching value of two line segments and the corresponding transformation. In the same way, large values for SEGMENTDISTANCETHRESHOLD make line segments that do not represent the same object in the environment to match; small values reduce the number of matching line segments thus making the method more sensitive to measurement errors. Large values of ANGLEDIFFERENCE-TOLERANCE facilitate the search of the best transformation by allowing many possible transformations to be considered, but their evaluation requires more time.

B. Map Merging Experiments

The sequence of scans we considered for validating our map merging methods is composed of 29 scans S 3 , S 4 , . . . , S 31 . We have excluded the three initial scans from the sequence acquired in our laboratory because, as discussed in Section V-A, they could not be integrated. Moreover, in order to close the loop and complete the experiments, scans from S 27 to S 29 (Fig. 10) were manually integrated. In the following, we discuss the integration of this sequence of scans done offline to test and compare all the three methods presented above.

Fig. 11 shows the final map (composed of 278 line segments) obtained with the sequential method. The sequential method could not integrate all the scans in order to close the loop: the method suddenly failed when we tried to integrate S 23 . It is evident that S 23 has only a few short line segments in common with the rest of the map. Furthermore, as already discussed, when the global map grows during the sequential integration, the scan matching becomes computationally very difficult because the large number of line segments requires a high effort for evaluating the possible transformations. For example, the integration of S 19 (composed of 28 line segments) with S 3,4,...,18 (composed of 247 line segments) takes 5.17 s. Fig. 12 shows the final map (composed of 519 line segments) obtained with the tree method. We applied the standard tree method until level 3 of the tree, then we applied the heuristic presented in Section IV-B to speed up the process. As we went down in the tree, the size of the maps grew larger and larger and the execution of INTEGRATE slowed down. For example, the integration of two partial maps (composed of 108 and 103 line segments) at level 3 of the tree requires 12.8 s. Furthermore, as already noted, when we integrate large-sized maps with many redundant spurious line segments that represent the same part of the environment, the resulting maps are noisier because of the error introduced when attempting to integrate maps with many overlapping line segments. Fig. 13 shows the final maps obtained with the pivot method. The map on the left is composed of 441 line segments and has been built by fusing the partial map S i-1,i with S ti-1,i i,i+1 , while the map on the right is composed of 358 line segments and has been built by the optimized method that fuses the partial map S i-1,i with S ti-1,i+1 i+1 . The second map presents fewer spurious line segments and appears more "clean".

We have preliminary tested the performance of the online implementation of the map merging methods, considering the sub-sequence of scans S 3 , S 4 , . . . , S 9 and the consecutive line segment heuristic. Results are shown in Table IV in which the time needed to integrate a newly acquired scan in the previous global map is reported. The sequential and the pivot methods are the best options for online implementation.

Given the nature of our approach, there is no a priori

(a) Fusion of S i-1,i with S ti-1,i i,i+1 1m (b) Fusion of S i-1,i with S ti-1,i+1 i+1
13: The final maps obtained with the pivot method guarantee that the final map is consistent. Actually, this is a critical issue for all map merging methods. In our case, the consistency of the final map can be ensured by the user who can validate each integration performed by the method. A more flexible solution is to let the user set a threshold for the value of the best transformation in INTEGRATE. An integration is considered to be valid only when its value (i.e., the value of its associated best transformation, see Section III-B) is above the threshold. By setting the values of the threshold smaller or larger, the user can decide to be more or less confident with the results produced by our method.

C. Further Experimental Results

To further validate our approach and to show that it works also with different data, we applied it to the stanford-gates1 data set available in the Robotics Data Set Repository (Radish) [START_REF] Howard | The robotics data set repository (radish)[END_REF] (thanks to Brian Gerkey for providing these data). This data set is a 30-minute tour through the first floor of the Stanford's Gates Computer Science Building. The robot used to collect the data is a Pioneer 2DX with a forwardpointing SICK LMS 200. The laser was running at high speed (75 Hz scans) in the 10 mm, 1 • mode. The data set includes both laser data and odometry data. We considered only laser data (about 115, 000 laser scans!). For each scan of the data set, we approximate the points acquired by the laser range scanner by line segments, as described in Section III-D. We call scans S x , where x is the time (in seconds) at which a scan has been acquired, according to the timestamps reported in the data set. To obtain good experimental results, we set some parameters to values different from those used in the previous sections: POINTDISTANCETOLERANCE has been set to 10 mm and SEGMENTDISTANCETHRESHOLD to 10.

The first set of experiments we performed with the stanford-gates1 data set is devoted to show that our method can always find the correct integration between two scans, provided that the two scans are taken close enough. For example, scans S 518 and S 522 (taken 4 s apart) are not correctly integrated with our method but, when considering also S 520 , our method correctly integrates S 518 with S 520 and the result of this integration with S 522 (Fig. 14). The same happens for scans S 316 , S 318 , and S 320 (Fig. 15).

To corroborate the results of Table II and to compare the heuristics for scan integration of Section III-A in a different environment, we applied them to 15 pairs of scans (the scans of each pair has been taken at 4 s from each other) randomly selected from the stanford-gates1 data set. Results are reported in Table V. An interesting future research direction could be the automatic identification, given an environment, of the best heuristic.

V: Scan integration results over 15 pairs of scans of the stanford-gates1 data set We also analyzed the robustness of our method with respect to variations of the parameter values. To this end, we considered three randomly selected pairs of scans of stanford-gates1 data set and we applied our scan integration method (with the consecutive line segment heuristic) varying the values of POINTDISTANCETOLERANCE, ANGLED-IFFERENCETOLERANCE, and SEGMENTDISTANCETHRESH-OLD. The method has been able to correctly integrate the pairs when the above parameters had values within 3 mm and 13 mm for POINTDISTANCETOLERANCE, 0.16 rad and 1.53 rad for ANGLEDIFFERENCETOLERANCE, and 8 and 131 for SEGMENTDISTANCETHRESHOLD.

The last experiment we performed with the stanford-gates1 data set is a simulation of a realistic multirobot setting. We assumed that four mobile robots had individually acquired four local maps of the environment (Fig. 16). According to the twolevel multirobot scenario depicted in Section I, we built these

VI. CONCLUSIONS AND FUTURE WORK

In this paper we have presented an approach for integrating pairs of partial maps composed of line segments and for merging a sequence of partial maps in order to build a global map. Our method works without any information about the relative poses of the partial maps but relies exclusively on their geometric features. The advantage of using geometric features is that the representation based on line segments is very compact and the maps produced are easy to use. This is the major aspect which distinguishes our approach from other robot mapping methods reported in the literature. The methods presented in this paper provide an elegant solution to the problem of multirobot mapping since they are independent from where and by which robot the partial maps have been acquired. Experimental results validate the effectiveness of the approach for indoor environments.

In future research we plan on generalizing these methods following the preliminary results of Section V-C, to cases where the order in which the partial maps have to be integrated is not known. This would happen, for instance, when maps are created by different robots since we cannot assume the order in which the merging will be done is the same as the order in 17: The result of the integration of local maps which they have been acquired. Note that the problem is not as severe as it might appear unless the number of robots is very large. We will also explore how adding positional information will affect the performance of the methods and examine how sensitive they are to pose errors.

Francesco

  Amigoni and Simone Gasparini are with the Dipartimento di Elettronica e Informazione of the Politecnico di Milano, Milano, Italy. Maria Gini is with the Department of Computer Science and Engineering of the University of Minnesota, Minneapolis, USA.

1 4: end for 5 : 2 8: end for 9 :

 1529 A 2 ← empty 6: for all pairs of line segments s 2 and s ′ 2 (s 2 = s ′ 2 ) in S 2 do 7: add to A 2 the angle between s 2 and s ′ T ← empty 10: for all pairs of angles α 1 ∈ A 1 and α 2 ∈ A 2 do 11:

2 :

 2 The distance between s 1 and s 2 is d(s 1 , s 2 ) = min(max(a, b), max(c, d)), where the marked angles are equal to π/2

3 :Algorithm 4

 34 Different values for the penalization for the pair of line segments shown Find

2 3 : 9 :

 39 for all C ∈ {C} do 4: P 0 ← line segment connecting the pair of farthest points (extremes of line segments) in C 5: s ← line segment in (a pair in) C that is at maximum distance from the line segment s in P 0 P n ← P n-1 after substituting s with s and adding line segments that connect s to the closest line segments in P n-1 10: s ← line segment in (a pair in) C that is at maximum distance from its closest line segment s in P n 11: end while 12: add the polyline P n to S 1,2 13: end for (a) Matching chain (b) Polyline with plain method (c) Polyline with greedy method 5: A matching chain (in black and gray) and the resulting polyline (dotted line)

8 :

 8 Pairs of scans and resulting final maps (the arrows show line segments corresponding to the same object in the environment)

1m 12 :

 12 The final map obtained with the tree method (with the dashed path followed by the robot) IV: Computing time (in s) for online map merging

1m (a) Scan S 1 1m(b) Scan S 2 1m(c) Scan S 3 9:(a) Scan S 27 1m(b) Scan S 28 1m(c) Scan S 29 10:

 123272829 Scans taken in the lab entrance 1m Scans taken in the hall 1m (a) Sequential method 1m (b) Scan S 23

14 :

 14 Scans and the map resulting from their integration 1m (a) Scan S 316 1m (b) Scan S 318 1m (c) Scan S 320 1m (d) Resulting map 15: Scans and the map resulting from their integration

  1m

(a) Local map L 1 1m

 1 (b) Local map L 2 1m (c) Local map L 3 1m (d) Local map L 4 16: Local maps that could have been acquired by four different robots local maps, called L 1 , L 2 , L 3 , and L 4 , by integrating four sequences of 10 scans (taken at 4 s from each other). Each local map L i has two scans in common with the local maps L i-1 and L i+1 (when they exist). The total length of the line segments in each local map is about 35 m. Our scan integration method has been able to integrate correctly the pairs of local maps, as shown in Fig.

17

 17

  . The time required to integrate (with the heuristic that considers consecutive line segments) two local maps is about 20 s. Note that we tried to integrate all the pairs of local maps. The correct matches have a best transformation value of about 10 m, while the wrong matches have a best transformation value of about 5 m. For example, the best transformation value between L 3 and L 4 is 14.8 m, while the best transformation value between L 1 and L 4 is 4.3 m.

  1m (a) Integration of L 1 and L 2 1m (b) Integration of L 2 and L 3 1m (c) Integration of L 3 and L 4

Algorithm 3

 3 Find transformations based on angles between pairs of randomly selected line segments Input: two scans S 1 and S 2 Output: a set of transformations T 1: T ← empty 2: for k = 1, 2, . . . , K do 3: for i = 1, 2, . . . , N k do ⊲ N k has been set to 20 • 2 k

		in our experiments
	4:	pick up randomly two line segments s 1 and
		s ′ 1 (s 1 = s ′ 1 ) from S 1 that are longer than SEGMENTDIVISIONFACTOR k times the length of the
		longest line segment is S 1
	5:	α 1 ← angle between s 1 and s ′ 1
	6:	pick up randomly two line segments s 2 and
		s ′ 2 (s 2 = s ′ 2 ) from S 2 that are longer than SEGMENTDIVISIONFACTOR k times the length of the
		longest line segment is S 2
	7:	α 2 ← angle between s 2 and s ′ 2
	8:	if α 1 = α 2 then
	9:	add to T the rototranslation that superimposes
		α 2 to α 1
	10:	end if
	11:

  the best transformation Input: two scans, S 1 and S 2 , and a set of transformations T Output: the best transformation t in T 1: btv ← 0 ⊲ current best transformation value 2: for all t ∈ T do

	3:	S t 2 ← transform S 2 according to t
	4:	tv ← 0		⊲ value of t
	7:	consider the next transformation	⊲ next
		iteration of the outer for
	8:	end if
	9:	if d(s 1 , s t 2 )/POINTDISTANCETOLERANCE	>
		SEGMENTDISTANCETHRESHOLD then
	10:	consider the next pair of line segments ⊲ next
		iteration of the inner for
	11:	end if
	12: 13:	s t 2p ← projection of s t 2 on line supporting s 1 ; s 1p ← projection of s 1 on line supporting s t 2 l 1 ← length of common part of s 1 and s t 2p ; l 2 ← length of common part of s t 2 and s 1p
	14:	mv ← (l 1 + l 2 )/2	⊲ matching value
	15: 16:	if s 1 and s t 2 do not intersect then mv ← mv * 0.95 d(s1,s t 2 )/POINTDISTANCETOLERANCE
		⊲ penalization
	17:	end if
	18:	tv ← tv + mv
	19:	end for
	20:	if tv > btv then
	21:	t ← t; btv ← tv
	22:	end if
	23: end for 24: for all pairs of line segments s 1 ∈ S 1 and s t 2 ∈ S t 2 do 25: if (s 1 , • ) or ( • , s t 2 ) already belongs to a matching chain C relative to t then 26: add to C the pair (s 1 , s t 2 )
	27:	else
	28:	create a new matching chain relative to t and add to it the pair (s 1 , s t 2 )
	29:	end if
	30: end for

5:

for all pairs of line segments s 1 ∈ S 1 and s t 2 ∈ S t 2 do

6:

if s 1 and s t 2 intersect and both are longer than SEGMENTLENGTHREFUSE then

  1 and S t 2 . A matching chain relative to transformation t for the pair of scans S 1 and S t 2 is the set C = { s 1 , s t 2 |s 1 ∈ S 1 and s t 2 ∈ S t 2 have a positive matching value for t} algebraically closed under line segment belong-to relation. Specifically, a matching chain C is such that if s 1 , s t 2 ∈ C, then all the line segments s that have a positive matching value (namely, have matched with) s 1 or s t

2 belong to C; i.e., s 1 , s ∈ C and s, s t 2 ∈ C.

1m Door that has been closed after the passage of the robot

	Scans	S 4	S 5	S 18	S 19	S 25	S 26
	# of line segments	47	36	24	24	10	12
		Time	# tried	Time	# tried	Time	# tried
	All transformations	936	41,260	32	3,096	0.38	231
	Consecutive line segments	1.25	2	0.73	27	0.13	4
	Random line segments	7.69	∼20,000	2.51	∼20,000	0.78	∼20,000
	Histogram	3.29	73	1.97	192	0.15	32

11:

The final map obtained with the sequential method for scans S 1 to S 22 and scan S 23 III: Interesting scan integration examples (times are in s)

ACKNOWLEDGMENTS

The authors would like to thank Jean-Claude Latombe for his generous hospitality at Stanford University where this research was started, Héctor Gonzáles-Baños for sharing his programs and expertise with collecting laser range scan data, Brian Gerkey for providing the Stanford data set, Paolo Mazzoni and Emanuele Ziglioli for the initial implementation of the fusion algorithm, Daniele Menotti for contributions to error analysis, and Igor Giussani for some experimental results. Francesco Amigoni was partially supported by a Fulbright fellowship and by "Progetto Giovani Ricercatori" 1999 grant, Maria Gini by NSF under grants EIA-0224363 and EIA-0324864.