Multi-Robot Exploration of an Unknown Environment, Efficiently Reducing the Odometry Error

1 Introduction

The problem of exploring an unknown environment and constructing a map is central to mobile robotics. The ability to build an internal representation of the environ­ ment is also critical to most intelligent organisms. Exist­ ing approaches that have been proposed for this problem range from idealized solutions involving perfect virtual robots to practical solutions of indeterminate complexity with real robots. The range of environment and terrain types that have been considered has been similarly var­ ied. These range from sets of polygons on the plane and abstract 3D shapes used in geometric explorations, up to real world environments, such as office buildings, lunar surfaces, underground mines, and underwater terrains. This work deals with questions of efficiency and feasibil­ ity from a theoretical standpoint. We model the world as a collection of closed 2-dimensional curves. For simplic­ ity, we approximate free space as a polygon with holes, and then we extend the work to general shapes.

The simplest robot that can perform exploration is one equiped only with a contact sensor and internal odome­ try sensors. In this case, an environment can be explored (assuming free space is entirely reachable) by having the robot traverse a space filling-curve, covering the whole free space while avoiding obstacles on the way. The ob­ vious disadvantages of this approach are:

• the long path length that must be traversed (of in­ finite length for a point robot, of finite length for a robot of finite size or sensing range);
• the inaccuracy of the map due to accumulated po­ sition errors (dead reckoning error).

In the case of an ideal robot with no odometry error and an ideal range scanning sensor, Lumelsky [Lumel­ sky et al., 1990] was one of the first to develop prov­ ably correct exploration strategies, which fully map ev­ ery object in the environment by circumnavigating it . Other techniques [Rao, 1995; Oommen et al., 1987], rep­ resentative of existing approaches, assume a polygonal world, which the robot maps by traversing the visibil­ ity graph ensuring every part is visited. Other ideal­ ized models deal with the world at a purely topological level [Deng and Mirzaian, 1996; Kuipers and Levitt, 1988]. Experimental approaches to environment explo­ ration have also been developed [Balch and Arkin, 1994; Walker et al., 1993; Bulata and M.Devy, April 1996; Elfes, 1987], demonstrating satisfactory performance in limited environments but without a performance guaran­ tee. In contrast to these approaches, we present theoret­ ical results but deal explicitly with the need to compen­ sate both for odometric error and for sensing the accu­ racy of which deteriorates with increasing distance. We compensate for these problems by using multiple coop­ erating robots to explore the environment .

The organisation of this paper is as follows . In Sec­ tion 2 we present the description of the world and the robot model. In Section 2.1 we analyze the advantages of cooperative robots versus a single one. In Section 3 an algorithm for exploring large areas (compared to the sensing range of the two robots) is presented. In Section 4, a performance analysis is presented, and in Section 5 the triangulation algorithm for exploring small areas is analysed. Section 6 has the conclusions and suggests possibilities for future work.

2 Model description and terminology

A fundamental model for the world is a simple polygon in 2D with holes. A polygon is simple if there is no pair of non-consecutive edges sharing a point [Preparata and Shamos, 1985]. The model of the world is essentially a set of simple polygonal obstacles contained within a larger polygonal boundary.

Our model for robots is minimal but easily general­ ized: robots are points that can move in any direction, and they are equipped with two sensors. The first sen­ sor is an object detector, able to detect any object in the immediate vicinity of the robot. The object detector allows wall following and object avoidance, and, in prac­ tice, the detector would be implemented by a sonar ring, an infra-red device, or even a tactile sensor. The range of the object detector is limited. The second sensor is a robot tracker, with the ability to locate another robot when there is a free line of sight between them, and to report accurately the distance to the second robot and its orientation. Examples of this type of sensor are a vision system that could locate a pattern on the other robot [Dudek et al., 1995] (see Figure 1) or a laser range finder with a retroreflective target on the other robot. We assume that the range of the robot tracker is much larger than that of the object detector (i.e., we can see further than we can reach).

The robots explore the unknown environment by pro­ gressively covering free space in the polygonal world. Several planar decompositions have been proposed in the computational geometry literature [O'Rourke, 1987; Preparata and Shamos, 1985]. Although they apply to worlds that are completely known, they can be used as a starting point to develop "on-line" versions that con­ struct the decomposition as part of the exploration pro­ cess. The advantage offered by this approach is guaran­ tee of full coverage without duplication, and a standard description for use in higher level reasoning.

One such systematic method is to cover free space with trapezoids. see Figure 2a. 1 An alternative decomposi­ tion of a simple polygon is by triangulation. The inte­ rior of the polygon is decomposed into triangles without adding vertices by using non-intersecting diagonals (see Figure 2b). 2

2.1 Why Use Multiple Robots (Aren't Single Robots Trouble Enough)?

The use of multiple agents provides distinct advantages over single-agent systems in several contexts (this les­ son has not been ignored by many insect species). The design of a robust error-free general-purpose range sen­ sor has remained a difficult challenge. In general, high accuracy entails a limited range of operation for most devices. This in turn imposes serious constraints on the classes of mapping algorithm a robot can execute. It is possible in many applications to consider the robot and its sensor range as a point or a small disk that covers the space by moving through it. In that case the over­ all path necessary to be travelled before the whole map is constructed defines an area-filling curve swept by the robot/sensor system.

On the other hand, having one robot of a two-robot team observe and track another cooperating robot is a comparatively simple task (since there is no need to mea­ sure reflected energy from unpredictable materials in the environment, as is the case with a range sensor). If we use a pair of robots with the above described tracking sensors, then by moving one of them across the base of a triangle (for example AB) with the other at the op­ posite corner (for example C), they would map as free the area inside the triangle ABC ( ~lABia where a the distance of C to AB) by travelling only the distance d = IABI. This can constitute an arbitrarily large im­ provement over a space-filling sweep algorithm 3 .

Another major problem that arises in practice is odometry error. Due to imperfections in the construc­ tion of a real robot and the properties of the environment, mobile robots cannot avoid building up small er­ rors in their position and orientation estimates when they move. After several steps, the robot's estimate of its position can be very different from the actual position. The traditional self-contained solution for the localisa­ tion problem is to correct the robot's position estimate by making reference to external landmarks observed us­ ing the robot's sensors. Detecting and recognizing land­ marks is a difficult task in general, especially when the environment is much larger than the sensing range, and therefore the landmarks are far apart from each other.

1 For a simple polygon known a priori there are algorithms that construct the trapezoid decomposition in worst case O(nlog(n)) time.

2 The worst case time complexity of triangulating a known polygon is O(n) [Chazelle, 1990].

3 1n practice, even line of sight tracking is range limited and can be described as a sweep, but in this case the sweeping figure can be extremely large.

In our work, two or more robots are used in conjunc­ tion to limit the size of odometry errors. This is accom­ plished by having only one robot move at any time, while the other robot(s) observes it. This allows the station­ ary robot to track the moving one and measure its posi­ tion with higher accuracy than using simple dead reck­ oning. Later on, the roles are reversed: the robot that had been moving becomes the observer while another robot can move. This approach reduces the odometry error and guarantees better performance than a single robot. 4 For now, full communication is assumed as the . , movmg robot can obtain its current position from the observer's at any time [Dudek et al., 1995]. This allows positioning to be accomplished based on the observing robots positions and independent of any environmental characteristics.

3 Exploring a large environment with two robots

When the size of the free space is much larger than the sensing range of the robots, then the trapezoid decompo­ sition guides the exploration strategy. At any time only one robot moves, and it maps a part of the free space; then the two robots exchange roles; then the other robot moves with another part of the free space being mapped. The exploration algorithm consists of two logical parts: the local exploration, which sweeps a horizontal stripe of free space inside one trapezoid, and the global one, which connects the stripes together and decides which part to explore next.

3.1 Local exploration

When one robot moves in a straight line, then the area mapped has the shape of a triangle as in Figure 3. If the only parameter to be optimized was the total path trav­ eled, then each robot would move by a ol at distance d = R, and then the two robots would exchange roles and the other one would move by a ol, continuing in this way up until they reach a wall. In terms of path trav­ elled, the algorithm would be optimal because each time they cover the maximum area possible, and no area is covered twice. Unfortunately, the exchange of roles has some cost, associated with acceleration/deceleration and location update. Therefore, the number of exchanges should be taken into account. We model the cost as a function of the angle () as in Figure 3. The simplest way to explore a stripe is by moving the robots into two parallel lines, at a distance appropriate for the number of exchanges that are considered acceptable (the closer they come the smaller the number of exchanges). In this model, each time one robot moves a triangular area is covered. Table 1 presents the number of exchanges, the total path travelled, and the number of rotations for the e~ploration of a rectangular area XY. While that algo­ nthm has good performance, it is not optimal in terms of path length or the number of exchanges. The opti­ mal length path [Rekleitis et al., 1997] occurs when the two robots explore the maximum area possible at any time without overlaps. An example of the optimal path can be seen in Figure 4, where the area explored each time is forming a diamond shape (e.g. T2T0T3 ). Table 1 presents the number of exchanges, the total path trav­ elled, and the number of rotations for the exploration of a rectangle XY, when each robot move covers a diamond shaped area.

. 4 The_ corrections from the stationary robot could be com­ bu~ed With_ the dead reckoning technique, using Kalman fil­ termg to gtve more accurate estimates.

More precisely, in the example in Figure 4, the two robots are "awakened" at time To next to each other. After an initial scan of the environment, the robot R2 moves away from robot R1 , which remains stationary until R2 reaches a distance d = R, distance that gives the maximum covered area while accurately locating the position of R2, (time T1). Then the robotR2 moves to a new position (time T2), mapping the area T0T1T2 as free space. Consequently, the robot R2 becomes stationary and the robot R1 maps a new area T0T2T3 (time T3 ). Then they exchange roles again and continue. When the two robots reach the end of the stripe, (time Tn), they move to the new positions (time Tn+I) and explore the next stripe in the opposite direction. It is worth noting the effect of the reflex vertices in the order of exploration.

3.2 Global exploration

The order in which the stripes are explored is given by a depth first search algorithm. From the collection of the stripes we construct the dual graph by matching every explored stripe to a vertex of the graph and ev­ ery pair of adjacent stripes to an edge connecting the two corresponding vertices. At any point, after visit­ ing a node in the graph (in other words, after explor­ ing the corresponding stripe of free space), there are a maximum of two choices (except for the initial step) for which stripe/node is to be explored next . In general every stripe is connected to one above and one below. If, during the exploration, a robot encounters a reflex vertex, 5 then a decision point is introduced and conse­ quently an extra edge is added on that node (see Figure 5). Every time a reflex vertex is encountered a decision is made, and one branch of the graph is followed. In our approach a depth first search strategy is used in order to determine which edge of the dual graph the robots are going to follow in the exploration. It is worth not­ ing that, in order to have optimal results, the deepest branch of the graph should be explored last, but with­ out a-priori knowledge this is impossible to determine in advance. Various heuristics could be applied, such as exploring the narrowest or the widest opening first, de­ pending on previous environmental knowledge. Regard­ ing the complexity of the dual graph, if the environment has obstacles in it (modeled as holes in the simple poly­ gon), then the graph contains cycles; otherwise it is a tree.

The area exploration problem now is equivalent to a graph exploration, and the complexity (in terms of robot edge transitions) is linear in the number of reflex vertices in the environment.

5 For a single polygon P a reflex vertices are the concave vertices. For obstacles, inside the polygon, reflex vertices are the convex vertices of the obstacle (see for example Figure 4) .

3.3 More than two robots

An immediate extension of the previous algorithm can be obtained by the addition of more robots. When the two robots sweep one stripe of width d then by adding an ex­ tra robot (50% increase) we could double the area swept. In the original algorithm, every robot has only one de­ vice to track the other robots; in this case a scheduling algorithm should be applied in the order the robots are moving. If we add a second tracking device, one robot could track robots on both sides, allowing a parallel cover of double the area at the same time.

In the example in Figure 6 we use five robots (R1 ... R5) that are positioned in two lines at time T0 , and we assume that each robot can track only one other robot at a time. First the robots R1 , R3 move forward, tracked by R4 and R5 accordingly, mapping the two tri­ angles as free space, then both R4, R5 track R2 , which moves forward at the position (marked as time) T2 . Then it is time for the next column of robots (R4 , R5 ) to ad­ vance (one at a time due to the tracking devices), mark­ ing more area as free space. The tracking is marked with the dotted lines of sight. The same pattern is followed as the two columns alternatively advance, marking a stripe of free space much wider than that possible with only two robots.

The second part of the algorithm concerning the ex­ ploration strategy for the whole space and the order in which the trapezoids should be explored is identical to the previous algorithm where only two robots were used. 6

4 Complexity analysis

The algorithm consists of two states: the local explo­ ration of a stripe, and the global exploration that de­ termines the order in which the adjacent stripes are ex­ plored. Consequently the complexity of the algorithm reflects these two states. The exploration is performed in stripes that are covered one after the other, form­ ing trapezoids. The trapezoids then are joined together to form the complete map. The total travel of the two robots while they explore new space is the sum of the perimeters of the different stripes. For a single rectan­ gle, analytical results are given in Table 1. Details of this procedure and associated bounds appear elsewhere [Rekleitis et al., 1997]. The second quantity is the net travel inside known territory to visit the boundaries of the unmapped territory. This is a function of the num­ ber of reflex vertices of the free space polygon (given by a depth first search algorithm). The trapezoid decom­ position covers all of the free space with a finite number of stripes (trapezoids). The algorithm methodically ex­ plores every one of these stripes, and it never repeats the exploration. Therefore, after the two robots explore all the stripes the algorithm is guaranteed to terminate with a complete map.

5 Small Environments - Triangulation

This specialized algorithm operates in an environment where the visual sensing range is at least as large as the diameter of the polygon. The output of this algorithm is a map of the free space decomposed into triangles.

6 There is a possible speedup by splitting up the group in order to explore different parts in critical points, but that would in the end spread the robots too thin.

Our proposed exploration algorithm starts from an ar­ bitrary position in the environment and proceeds to map it as a set of convex polygon/shapes of free space con­ nected as a graph, in the case of a simple polygon with holes, or as a tree, in the case of a simple polygon. As an initial step, the two robots sense the closest wall pro­ ceed to move to it and position themselves in opposite corners. The triangulation algorithm then moves one robot by following the walls, maintaining line of sight contact with the other robot, which remains stationary at a corner of the polygon. Again the complexity in­ creases linearly with the number of reflex vertices. Every triangle represents a node in the dual graph, and adja­ cent triangles represent edges among the corresponding nodes. Every time the line of sight is broken by a reflex vertex, a decision is made and another edge is added to the graph. The total path traveled again depends on two measures. The exploration cost is equal to the perimeter of the polygon. The cost of traversing some edges of the path twice, is linear with the number of reflex vertices, and the path length is bounded by the maximum dis­ tance between any two points in the polygon for every edge traversed twice.

An example is presented in Figure 7, the two robots start at the two positions marked T0 , and robot R2 then starts exploring the free space, following the walls of the polygon up until the line of sight is broken by a reflex vertex upon which it switches roles with robot R1 . All of the free space is mapped, except for the areas in which a bifurcation in the sweep was forced due to a reflex vertex.

Figure 8 illustrates the final stage of the algorithm which is used to map the remaining areas. The robots plan their path through the mapped area for the fastest route that will take them to the unmapped areas and then proceed to reach these areas and explore them.

In the general case, the two algorithms should be used together: when the robots approach a closed space where they can "see" each other from wall to wall, the triangu­ lation algorithm should be used to map it. When they move into an open area, the trapezoid decomposition al­ gorithm should then be used to sweep the area.

6 Conclusions

Different techniques for mapping the environment have been used since ancient times in·Egypt and Rome. Most of them involved collaboration among different observers in order to improve their accuracy. In this paper, a new algorithm for exploring an unknown environment is pro­ posed. Our algorithm uses a well-known planar decom­ position form in order to systematically explore the free area of of an unknown environment modelled as a sim­ ple polygon with holes. The trapezoid decomposition is used for large areas ensuring an exploration strategy that finishes with the total free space mapped as a set of trapezoids. For small areas, a triangulation of the free space is returned.

Realistic assumptions, such as odometry error, and sensing that deteriorates with distance, are used. Both algorithms return a complete map, while a single robot would encounter great difficulties in such a case. The approach acts to minimize the effects of inherent navi­ gation errors, while providing a performance guarantee (unlike heuristic methods). We are currently involved in experimental evaluation of these algorithms.