Active Mobile Robot Localization

1 Introduction

To navigate reliably in indoor environments, a mobile robot must know where it is. Over the last few years, there has been a tremendous scientific interest in algorithms for estimating a robot's location from sensor data. A recent book on this issue [Borenstein et al., 1996] illustrates the importance of the localization problem and provides a unique description of the state-of-the-art.

The majority of existing approaches to localization are pas­ sive. Passive localization exclusively addresses the estimation of the location based on an incoming stream of sensor data. It rests on the assumption that neither robot motion, nor the pointing direction of the robot's sensors can be controlled. Active localization assumes that during localization, the lo­ calization routine has partial or full control over the robot, providing the opportunity to increase the efficiency and the robustness oflocalization. Key open issues in active localiza­ tion are "where to move" and "where to look" so as to best localize the robot.

This paper demonstrates that active localization is a promising research direction for developing more efficient and more robust localization methods. In other sub-fields of artificial intelligence (such as heuristic search and ma­ chine learning), the value of active control during learning Dept. of Computer Science Carnegie Mellon University Pittsburgh, PA U.S.A.

and problem solving has long been recognized. It has been shown, both through theoretical analysis and practical exper­ imentation, that the complexity of achieving a task can be greatly reduced by actively interacting with the environment. For example, choosing the right action during exploration can reduce exponential complexity to low-degree polynomial complexity, as for example shown in Koenig's and Thrun's work on exploration in heuristic search and learning control [Koenig, 1992; Thrun, 1992]. Similarly, active vision (see e.g., [Ballard and Brown, 1982]) has also led to results supe­ rior to passive approaches to computer vision. In the context of mobile robot localization, actively controlling a robot is particularly beneficial when the environment possesses rela­ tively few features that enable a robot to unambiguously de­ termine its location. This is the case in many office environ­ ments. For example, corridors and offices often look alike for a mobile robot, hence random motion or perpetual wall fol­ lowing is often incapable for determining a robot's position, or very inefficient.

In this paper we demonstrate that actively controlling the robot's actuators can significantly improve the efficiency of localization. Our framework is based on Markov localiza­ tion, a passive probabilistic approach to localization which was recently developed in different variants by [Burgard et at., 1996; Kaelbling et al., 1996; Nourbakhsh et at., 1995; Simmons and Koenig, 1995]. At any point in time, Markov localization maintains a probability density (belief) over the entire configuration space of the robot; however, it does not provide an answer as to how to control the robot's actuators. The guiding principle of our approach is to control the ac­ tuators so as to minimize future expected uncertainty. Un­ certainty is measured by the entropy of future belief distribu­ tions. By choosing actions to minimize the expected future uncertainty, the approach is capable of actively localizing the robot.

The approach is empirically validated in the context of two localization problems:

1. Active navigation, which addresses the questions of where to move next, and
2. Active sensing, which addresses the problem of what

sensors to use and where to point them.

Our implementation assumes that initially, the robot is given a metric map of its environment, but it does not know where it is. Notice that this is a difficult localization problem; most ex­ isting approaches (see, e.g., [Borenstein et al., 1996]) concen­ trate on situations where the initial robot location is known and are not capable of localizing a robot from scratch. Our approach has been empirically tested using a mobile robot equipped with a circular array of 24 sonar sensors. The key experimental result is that the efficiency of localization is im­ proved drastically by actively controlling the robot's motion direction and by actively controlling its sensors.

2 Related Work

While most research has concentrated on passive localization (see e.g., [Borenstein et al., 1996]), active localization has received considerably little attention in the mobile robotics community. This is primarily because the majority of litera­ ture concerned with robot control (e.g., the planning commu­ nity) assumes that the position of the robot is known, whereas research on localization has mainly focused on the estima­ tion problem itself. In recent years, navigation under uncer­ tainty has beeri addressed by a few researchers [Nourbakhsh et al., 1995; Simmons and Koenig, 1995], who developed the Markov navigation paradigm. However, both their ap­ proaches do not aim at actively localizing the robot. Local­ ization occurs as a side effect when operating the robot under uncertainty. Moreover, as argued by Kaelbling [Kaelbling et al., 1996], there exist conditions under which the approach reported in [Simmons and Koenig, 1995] can exhibit cyclic behavior due to uncertainty in localization.

On the forefront of localization driven navigation, [Kuipers and Byun, 1981] used a rehearsal procedure to check whether a location has been visited while learning a map. In [Klein­ berg, I994] the problem of active localization is treated the­ oretically in finding "critical directions within the environ­ ment'' under the assumption of perfect sensors.

In [Kaelbling et al., 1995], acting in the environment is modeled as a partially observable Markov decision process (POMDP). This approach derives an optimal strategy for moving to a target location given that the position of the robot is not known perfectly. In [Kaelbling et al., I996] this method is extended by actions allowing the robot to im­ prove its position estimation. This is done by minimizing the expected entropy after the immediate next robot control action. While this approach is computationally tractable, its greediness might prevent it from finding efficient solutions in realistic environments. For example, if disambiguating the robot's position requires the robot to move to a remote lo­ cation, greedy single-step entropy minimization can fail to make the robot move there. In our own work [Thrun et al., to appear], we have developed robot exploration techniques for efficiently mapping unknown environments. While such methods give better-than-random results when applied to lo­ calization, their primary goal is not to localize a robot, and there are situations in which they will fail to do so.

3 Active Localization by Entropy Minimization·

3.1 Markov Localization

This section briefly outlines the basic Markov localization al­ gorithm upon which our approach is based. The key idea of Markov localization is to compute a probability distri­ bution over all possible locations in the environment. Let l = (x, y, B) denote a location. The distribution, denoted by Bel(l), expresses the robot's subjective belief for being at l. Initially, Bel(/) reflects the initial state of knowledge: if the robot knows its initial position, Bel(l) is centered on the correct location; if the robot does not know its initial lo­ cation, Bel(l) is uniformly distributed to reflect the global uncertainty of the robot-the latter is the case in all our ex­ periments.

Bel(l) is updated whenever ...

• .·· the robot moves. Robot motion is modeled by a condi­ tional probability, denoted by Pa(l I l'). Pa(l I l') denotes the probability that action a, when executed at l', carries the robot to l. In the remainder of this sec­ tion, actions a are of the type "Move to a location I meter in front and 2 meters to the right." Applied to l' = (Om, Om, goo), Pa(l I L') is centered around the expected new location l = (2m, lm, goo).

Pa(lll') is used to update Bel(l) upon robot motion:

In our implementation, Pa(l I l') is obtained from a model of the robot's kinematics.

.·· the robot senses. Let s denote a sensor reading, and P(s I l) the likelihood of perceiving s at l. P(s I l) is usually referred to as map of the environment, since it specifies the probability of observations at the different locations in the environment. When sensing s, Bel(l) is updated according to the following rule:

Here P(s) is a normalizer that ensures that the Bel(l) sum up to 1.

In general, Bel(l) can be represented by Kalman filters [Smith et al., 1990] or discrete approximation [Burgard et al., 1996; Nourbakhsh et al., 1995; Simmons and Koenig, 1995; Kaelbling et al., 1996]. P(s I l), the map of the environ­ ment, is a crucial component of the update equations. It specifies the likelihood of observing s at location l, for any choice of sand l. In [Moravec, 1988] and our previous work

[Burgard et al., 1996], P(s J l) is obtained from a metric model of the environment, and a model of proximity sen­ sors. Whereas our approach is able to exploit arbitrary geo­ metric features of the environment, [Nourbakhsh et at., 1995; Simmons and Koenig, 1995; Kaelbling et at., 1996] first scan sensor data for the presence or absence of certain landmarks.

While our description of Markov navigation is brief, it is important that the reader grasps the essentials of the ap­ proach: The robot maintains a belief distribution Bel(l) which is updated upon robot motion, and upon the arrival of sensor data. Probabilistic representations are well-suited for mobile robot localization due to its ability to handle ambi­ guities and to represent degree-of-belief. Recently, Markov localization has been employed successfully at various sites. However, Markov localization is passive. It does not provide means to control the actuators of the robot.

3.2 Active Localization

To eliminate uncertainty in the position estimate Bel(l), the robot must choose.actions which help it distinguish different locations. The entropy of the belief, obtained by the follow­ ing formula

measures the uncertainty in the robot position: If H = 0, Bel(l) is centered on a single position, whereas His maximal, if the robot is completely uncertain and Bel(l) is uniformly distributed. The general principle for action selection can be summarized as follows: Actions are selected by minimizing the expected future entropy.

To formally derive the expected future entropy upon exe­ cuting an action a, we have to introduce two auxiliary nota­ tions: Let Bela(l) denote the belief after executing action a, and let Bela,s(l) denote the belief after executing a and sens­ ing s. Both Bela(l) and Bela,s(l) can easily be computed from Bel(l) using the Markov positioning update equations (1) and (2). The expected entropy, conditioned on the action, can then be expressed by the following term:

The expression (6) is obtained from the definition of the entropy, by integrating over all possible sensor values s, weighted by their likelihood, and by applying the update rule (2). This simple, greedy principle- minimizing the expected future entropy-is the cornerstone of our active localization methods. For example, in active sensing, different actions a correspond to different pointing direction of the robot's sen­ sors. Whenever the robot senses, this pointing direction is determined by minimizing the expected entropy Ea[H].

3.3 Active Navigation

Active navigation addresses the problem of determining where to move so as to best position the robot. At first glance, one might use simple motor control actions (such as "move 1 meter forward") as basic actions in active navigation. How­ ever, just looking at the immediate next motor command is often insufficient. For example, a robot might have to move to a remote room in order to uniquely determine its loca­ tion, which might involve a long sequence of individual motor commands.

For this reason, we have chosen to consider arbitrary target points as atomic actions in active navigation. Target points are specified relative to the current robot location, not in abso­ lute coordinates. For example, an action a = move( 12m, 2m) will make the robot move to a location 12 meter ahead and 2 meters to the left, relative to its current location and heading direction. Additionally we take into account the cost of reach­ ing a target point, which substantially depends on the length of the path and the obstacies on the path. The remainder of this section specifies the computation of the costs, the cost­ optimal path, and demonstrates how to incorporate costs into action selection.

Occupancy probabilities: Our approach rests on the as­ sumption that a map of the environment is available, which specifies which point l is occupied and which one is not. Let Pocc(l) denote the probability that location lis blocked by an obstacle. The robot has to compute the probability that a tar­ get point a is occupied. Recall that the robot does not know its exact location; thus, it must estimate the probability that a target point a is occupied. This probability will be denoted Pocc(a). Simple geometric considerations perinit the "trans­ lation" from Pocc(l) (in real-world coordinates) to Pocc(a) (in robot coordinates):

Here Ia (l) is the coordinate transformation for transform­ ing a from robot-centered coordinates to global coordinates, assuming that the robot is at l . In essence, (7) computes, for any l, the point a into real-world coordinates Ia (l), then considers the occupancy of this point <PoccUa(l))). The ex­ pected occupancy is then obtained by averaging over all loca­ tions l, weighted by the robot's subjective belief of actually being there Bel(l). The result is the expected occupancy of a point a relative to the robot.

Cost and cost-optimal paths: Based on Pocc(a), the ex­ pected path length and the cost-optimal policy can be ob­ tained through value iteration, a popular version of dynamic programming (see e.g., [Littman et al., 1995] for details). Value iteration assigns to each location a a value v(a) that represents its distance to the robot. Initially, v(a) is set to 0

for the location a = (0, 0) (which is the robot's location), and oo for all other locations a. The value function v(a) is then updated recursively according to the following rule:

Here v(b) is minimized over all neighbors of a, i.e., all locations that can be reached from a with a single, atomic motor command. (8) assumes that the costs for traversing a point a is proportional to the probability that a is occupied <Pocc(a)). Iteratively applying (8) leads to the cost function for reaching any point a relative to the robot, and hill climbing in v (starting at a) gives the cost-optimal path from the robot's current position to any location a.

Action selection: Armed with the definition of the expected entropy and the expected costs, we are ready to set the policy for selecting actions in active localization. At every point in time, the robot chooses the action a* that maximizes

Here a ~ 0 determines the relative importance of certainty versus costs. The choice of a depends on the application. In our experiments, a was set to 1.

This completes the description of active navigation with the purpose of localization. Note that active sensing is realized simply by pointing the sensor into the direction which minimizes the expected entropy of the action a = move(O, 0) . To summarize, actions represent arbitrary tar­ get points relative to the robot's current position. Actions are selected by minimizing a weighted sum of ( 1) expected un­ certainty (entropy) and (2) costs of moving there. Costs are considered because they may vary drastically between differ­ ent target points.'

3.4 Efficient Implementation

The active navigation and sensing methods described here have been implemented and tested using position probabil­ ity grids [Burgard et al., 1996]. This technique represents the location of the robot by a discrete three-dimensional grid. To achieve the level of accuracy necessary for predicting robot motion, the resolution of robot orientation is typically in the order of 1°, and the resolution of longitudinal information is often as small as lOcm.

While position probability grids are capable of approxi­ mating most probability functions of practical interest, they are computationally too expensive for active navigation. The complexity of computing the expected entropy is in O(ILI . lSI), where L denotes the set of grid-cells in the position probability grids, and S the set of distinguishable sensations. For example, for a mid-size environment of size 100m 2 , ILl = 3, 600, 000 for the resolution specified above. If the number of possible sensations is large, computing the ex­ pected entropy is infeasible in real-time.

We have modified the basic algorithm in a variety of ways, to ensure all necessary quantities can be approximated in realtime. Most importantly, instead of integrating over all loca­ tions L , only a small subset of L is considered, assuming that L can be approximated by a set Lm of m Gaussian densi­ ties with means 11-m E L. The center of the Gaussians J.Li are computed at runtime, by scanning locations whose probabil­ ity Bel(l) exceeds a certain threshold. Our simplification is somewhat justified by the observation that in practice, Bel(l) is usually quickly centered on a small number of hypothesis and approximately zero anywhere else. Without this modifi­ cation, action selection could not be performed in real-time.

4 Experimental Results

The central claim of this paper is that by selecting actions thoughtfully, the results of localization can be significantly improved. The experiments described in this section were carried out using the mobile robot RHINO, an RWI B21 equipped with 24 sonar sensors.

4.1 Active navigation

Active navigation was tested by placing the robot in an office environment (see Fig. I). Notice that the corridor in this envi­ ronment is basically symmetric and possesses various places that look alike, making it difficult for the robot to determine where it is. In this particular case, the robot must move into one of the offices, since only here it finds distinguishing fea­ tures.

In a total of 10 experiments, random wandering and/or wall following consistently failed to localize the robot. This is be­ cause our wandering routines are highly unlikely to move the robot through narrow doors, and the symmetry of the corri­ dor made it impossible to uniquely determine the location. In more than 20 experiment using the active navigation ap­ proach presented here, the robot always managed to localize itself in a considerably short amount of time.

Fig. I shows a representative example of the path taken during active exploration, and also defines the positions and office names (1, 2, 3, A, B, C) used in the text. In this par­ ticular run we started the robot at position I in the corridor facing south-west. The task of the robot was to determine its position within the environment, and then to move into room A (so that we could see that localization was successful). Af­ ter about ten meters of robot motion, it reached position 2

shown in Fig. I. Fig. 2 depicts the belief Bel(l) at this point in time (more likely positions are darker). The positions and orientations of the six local maxima are marked by the six cir­ cles. The expected occupancy probabilities Pocc(a), obtained by (7), are depicted in Fig. 3. High probabilities are shown in dark colors. Note that this figure roughly corresponds to a weighted overlay of the environmental map relative to the different local maxima, where the weights are given by the probabilities of the local maxima. Fig. 3 also contains the origin of the corresponding coordinate system. In this coor­ dinate system a coordinate (x, y) represents a target point x meters in front of the robot and y meters to the left. Fig. 4 shows the expected entropies of the target points, according to (6). As can be seen there, the expected entropy of loca­ tions in rooms is low, making them favorable for localiza­ tion. It is also low, however, for the two ends of the corridor, since there the uncertainty can be further reduced. Finally, Fig. 5 displays the expected costs for reaching the different target points. (c.f., (8)). Based on the entropy-cost trade-off c.f. (Fig. 6), the robot decided at first to move to the end of the corridor and progressed to position 3.

At this point it is important to notice that the trajectory to the target point cannot be computed off-line. This is due to unavoidable inaccuracies in the world model and to unfore­ seen obstacles in populated environments such as our office. These difficulties are increased if the position of the robot is not known, as is the case during localization. To overcome these problems the robot must be controlled by a reactive col­ lision avoidance technique. In our implementation a global planning module uses dynamic programming as described in section 3.3 to generate a cost minimal path to the target lo­ cation (see [Thrun and Biicken, 1996]). Intermediate target points on this path are sent to our reactive collision avoid­ ance technique described in [Fox et al., 1997]. The collision avoidance then generates motion commands to safely guide the robot to these targets. An overview of the architecture of the navigation system is given in [Buhmann et al., 1995; Thrun et al., to appear].

Fig. 6. Ea[H] + v(a) at pos. 2

After reaching the end of the corridor (position 3) the be­ lief state contained only two local maxima (see Fig. 7). Note that this kind of ambiguity can no longer be resolved with­ out leaving the corridor. Accordingly the expected entropy of target points in the corridor is high compared to the expected entropy of actions which guide the robot into the rooms. Be­ cause of the state of the doors, which only influences the cost of reaching target points, the overall payoff (displayed in Fig. 8) is maximal for target points in rooms B and C. This is why the robot decided to move into the room behind him on the right, which in this case turned out to be room B. After resolving the ambiguity between the rooms Band C the robot moved straight to the target location in room A. Fig. 9 shows the belief state at this final target point.

In addition to runs in our real office environment we did ex­ tensive testing in simulated hallway environments taken from [Kaelbling et al., 1996]. Our active navigation system suc­ cessfully localized the robot in every case by automatically detecting junctions of hallways and openings as crucial points for the localization task, and was uniformly superior to pas­ sive localization. The exact results are omitted for brevity.

4.2 Active Sensing

Our positive results were confirmed in the context of active sensing. Here we placed the robot in the corridor shown in Fig. I 0. This corridor ( 23m x 4.5m, all doors closed) is symmetric except for a single obstacle on its side. Thus, to determine its location, the robot has to sense this obstacle.

To simulate active sensing, we allowed the robot to read only a single sonar sensor at any point in time. As a passive method, we chose a sensor at random (a new sensor was cho­ sen randomly for every reading, which was the best passive approach out of a number of alternatives that we tried). This passive method was compared to our active approach, where sensors are chosen by minimizing entropy.

The results are depicted in Figures 11 and 12. Fig. 11 plots the entropy of Bel(l) as a function of the number of sensor measurements, averaged over 12 runs, along with their vari­ ances (bars). As can be seen here, the entropy (uncertainty) decreases much faster when sensors are selected actively. Of course, minimizing entropy alone is not an indicator of suc­ cessful localization; even a low-entropy estimate could be wrong.

Fig. 12 plots the error in localization (measured by the L1 norm, weighted by Bel(l)) for both approaches as a function of the number of sensor measurements. Here, too, the active approach is more efficient than the passive one. These results demonstrate the benefit of active localization.

5 Conclusions

This paper advocates a new, active approach to mobile robot localization. In active localization, the robot controls its var­ ious effectors so as to most efficiently localize itself. Based on Markov localization [Burgard et at., 1996; Kaelbling et al., 1996; Nourbakhsh et al., 1995; Simmons and Koenig, 1995; Smith et al., 1990]. a popular passive approach to mobile robot localization, this paper describes an approach for deter­ mining the robot's actions during control. In essence, actions are generated by minimizing the future expected uncertainty, measured by entropy. This basic principle has been applied to two active localization problems: active navigation, and active sensing. In the case of active navigation, an exten­ sion has been developed that incorporates expected costs into the action selection, and also determines cost-optimal paths under uncertainty using a modified version of dynamic pro­ gramming. Both approaches have been verified empirically using an RWI B21 mobile robot.

The key results of our experiments are:

1. The efficiency of localization is increased when actions are'selected by minimizing entropy. This is the case for both active navigation and active sensing. In some cases, the active component enabled a robot to localize itself where the passive counterpart failed.
2. The relative advantage of active localization is particu­ larly large if the environment possesses relatively few features that enable a robot to unambiguously determine its location.

Despite these encouraging results, there are some limitations that deserve future research. One of the key limitations arises from the algorithmic complexity of the entropy prediction. While a Mixed-Gaussian approximation made the computa­ tion of the entropy feasible for the type environments studied here, more research is needed to scale the approach to envi­ ronments that are significantly larger (e.g., lOOOmx 1000m). A second limitation arises from the greediness of action selec­ tion. In principle, the problem of optimal exploration is NP hard, and there exist situations where greedy solutions will fail. However, in none of our experiments we ever observed that the robot was unable to localize itself using our greedy approach, something that often happens using only random motion during localization.