Coping With Uncertainty in Map Learning

1 Introduction

Many of the problems faced by robots navigating in the environment can be facilitated by using expectations in the form of explicit models of objects and the spaces that they occupy: We use the term map to refer to any model of large-scale space used for purposes of navigation. Map learning involves exploring the environment, making ob­ servations, and then using the observations to construct a map. The construction of useful maps is complicated by the fact that observations involving the position, ori­ entation, and identification of spatially remote objects are invariably error prone. In this paper, we explore a number of problems involved in constructing useful maps from measurements taken with sensors subject to known errors.

·This work was supported in part by the National Science Foundation under grant IRI-8612644 and by the Advanced Research Projects Agency of the Department of Defense and was monitored by the Air Force Office of Scientific Research under Contract No. F49620-88-C-0132.

1 This work was supported in part by a National Science Foundation Presidential Young Investigator Award CCR8846714 with matching funds from IBM, and by National Science Foundation research grant CCR-8403613.

In previous work [Dean, 1988], we have looked at vari­ ous optimization problems related to constructing maps (e.g., construct the most accurate map consistent with a set of measurements) . Even in cases involving only a single dimension, such optimization problems can turn out to be NP-hard [Yemini, 1979]. In this paper, rather than look at problems that involve doing the best with what you have, we consider problems that involve going out and getting what you need to generate useful repre­ sentations. In particular, we consider a form of reliable and probably almost always useful learning [Rivest and Sloan, 1988] in which the robot gathers information to ensure that it nearly always (with probability 1- b) can provide a guaranteed perfect path from one location to another. A prerequisite to this sort of learning is that the robot, in moving around in its environment, can dis­ cern the local properties of space with absolute certainty with high probability having expended an amount of ef­ fort polynomial in i and n, where n is some measure of the size of the environment.

By eliminating local uncertainty, small errors incurred in making local measurements are not allowed to prop­ agate rendering global queries unacceptably inaccurate. In general, local uncertainty accumulates as the product of the distance in generating global estimates. One way to avoid this sort of accumulation is to establish strate­ gies such that the robot can discern properties of its environment with certainty. Most existing map learning schemes exploit this sort of certainty in one way or an­ other (see Section 4). The rehearsal strategies of Kuipers [1988] are one example of how a robot might plan to eliminate uncertainty. Once we have a method for elim­ inating uncertainty, the problem then reduces to one of planning out and executing the necessary experiments to extract certain information about the environment.

In situations in which it is not possible to eliminate local uncertainty completely, it is still possible to reduce the effects of accumulated errors to acceptable levels by performing repeated experiments. To support this claim, we describe a map-learning technique based on Valiant's probably approzimately correct learning model [Valiant, 1984] that, given small {J > 0, constructs a map to an­ swer global queries such that the answer provided in re­ sponse to any given query is correct with probability 1 - fJ. The techniques presented apply to a wide range of map-learning problems of which the specific problems addressed in this paper are meant to be merely illustra­ tive.

2 Spatial Representation

We model the world, for the purposes of studying map learning, as a graph with labels on the edges at each vertex. In practice, a graph will be induced from a set of measurements by identifying a set of distinctive loca­ tions in the world, and by noting their connectivity. For example, we might model a city by considering intersec­ tions of streets to be distinguished locations, and this will induce a grid-like graph. Kuipers [1988] develops a mapping based on locations distinguished by sensed fea­ tures like those found in buildings (see Figure 1) . Fig­ ure 2 shows a portion of a building and the graph that might be induced from it. Levitt (1987] develops a map­ ping based on locations in the world distinguished by the visibility of landmarks at a distance.

In general, different mappings result in graphs with different characteristics, but there are some properties common to most mappings. For example, if the mapping is built for the purpose of navigating on a surface, the graph induced will almost certainly be planar and cyclic. Other properties may include regularity or bounded de­ gree. In what follows, we will always assume that the graphs induced are connected and undirected; any other properties will be explicitly noted.

Following [Aleliunas et al., 1979), a graph model con­ sists of a graph, G = (V, E), a set L of labels, and a labeling, ifJ : {V x E} -+ L, where we may assume that L has a null element ..l which is the label of any pair (v E V, e E E) where e is not an edge from v. We will frequently use the word direction to refer to an edge and its associated label from a given vertex. With this nota­ tion, we can describe a path in the graph as a sequence of labels indicating the edges to be taken at each ver­ tex. We can describe a procedure to follow as a function from 11 -+ L indicating the preferred direction at each location.

If the graph is a regular tessellation, we may assume that the labeling ofthe edges at each vertex is consistent, i.e., there is a global scheme for labeling the edges and the labels conform to this scheme at every vertex. For example, in a grid tessellation, it is natural to label the edges at each vertex as North, South, East, and West . In general, we do not require a labeling scheme that is globally consistent. You can think of the labels on edges emanating from a given vertex as local directions. Such local directions might correspond to the robot having a compass that is locally consistent but globally inac­ curate, or local directions might correspond to locally distinctive features visible from intersections in learning the map of a city.

In the following, we identify three sources of uncer­ tainty in map learning. First, there may be uncertainty in the movement of the robot. In particular, the robot may occasionally move in an unintended direction. We refer to this as directional uncertainty, and we model this type of uncertainty by introducing a probabilistic move­ ment function from {V x L} -+ V. The intuition behind this function is that for any location, one may specify a desired edge to traverse, and the function gives the loca­ tion reached when the move is executed. For example, if G is a grid with the labeling given above, and we as­ sociate the vertices of G with points ( i, j) in the plane, we might define a movement function as follows:

where the " ... " indicate the distribution governing movement in the other three directions. The probabili­ ties associated with each direction sum to 1. If all direc­ tions are equally likely regardless of the intended direc­ tion, then the movement function is said to be random. Throughout this paper, we will assume that movement in the intended direction takes place with probability better than chance.

A second source of uncertainty involves sensors, and in particular recognizing locations that have been seen before. The robot's sensors have some error, and this can cause error in the recognition of places previously visited; the robot might either fail to recognize some previously visited location, or it might err by mistaking some new location for one seen in the past. We refer to this type of uncertainty as recognition uncertainty, and model it by partitioning the set of vertices into equiv­ alence classes. We assume that the robot is unable to distinguish between elements of a given class using only its sensors.

A third source of error involves another manifestation of sensor error. In representing the world using a graph, some mapping must be established from a set of distin­ guished locations in the world to V. Error in the sensors could cause the robot to fail to notice a distinguished lo­ cation some of the time. For example, a robot taxi might use intersections as distinguished locations, leading to a grid-like graph. But if sensor error causes the robot not to notice that he is passing through an intersection, his map will become flawed. In exploring an office envi­ ronment, the point in a hallway in front of a door may correspond to a vertex in the induced graph. If the door is closed, there is some chance that the robot will not recognize the vertex in traversing the hall. We model this type of uncertainty by introducing a probabilistic movement function that can skip over vertices. We refer to this type of movement function as discontinuous and to the type of uncertainty modeled as continuity uncer­ tainty.

Apparently, the three types of uncertainty described above are orthogonal in the sense that none implies or precludes the others. The issues involved in modeling and reasoning about continuity uncertainty are complex and will not be treated further in this paper. In the following, we are concerned with directional and recog­ nition uncertainty.

3 Map Learning

For our purposes, a map is a data structure that fa­ cilitates queries concerning connectivity, both local and global. Answers to queries involving global connectivity will generally rely on information concerning local con­ nectivity, and hence we regard the fundamental unit of information to be a connection between two nearby loca­ tions (i.e., an edge between two vertices in the induced undirected graph). We say that a graph has been learned completely if for every location we know all of its neigh­ bors and the directions in which they lie (i.e., we know every triple of the form (u, l, v) where u and v are vertices and lis the label at u of an edge in G from u to v). We assume that the information used to construct the map will come from exploring the environment, and we iden­ tify two different procedures involved in learning maps: exploration and assimilation. Exploration involves mov­ ing about in the world gathering information, and as­ similation involves using that information to construct a useful representation of space. Exploration and as­ similation are generally handled in parallel, with assim­ ilation performed incrementally as new information be­ comes available during exploration. In this section, we are concerned with the conditions under which a graph can be completely learned, and how much time will be required for the exploration and assimilation.

3.1 Tessellation Graphs

It's not hard to see that any connected, undirected graph can be completely learned easily if there is no uncer­ tainty; [Kuipers and Byun, 1988] describes a way of do­ ing this by building up an agenda consisting of unex­ plored paths leading out of locations and then moving about so as to eventually explore all such paths. Noth­ ing about the graph need be known before the explo­ ration begins. Introducing the kinds of uncertainty de­ scribed in Section 2 complicates things considerably. If, however, the graph has additional structure, then that structure can often be exploited to eliminate uncertainty. In the following, . we sketch a proof that it is possible to efficiently learn maps that correspond to regular tes­ sellations with boundaries. It turns out that the ex­ ploration component of learning regular tessellations is quite simple; random walks suffice for polynomial-time performance. In the longer version of this paper, we describe an efficient incremental assimilation procedure that is called whenever the robot encounters a location during exploration, and then prove the following 1 .

Lemma 1 The assimilation algorithm provided will learn a finite tessellation completely if the exploration tour traverses every edge in the graph. The overall cost of assimilation is 0( m) where m is the length of the tour.

We now have to ensure that during exploration the robot traverses each edge in the graph at least once with high probability. The following two lemmas establish that, for any connected, regular, undirected graph G and any 8 > 0, a random walk of length polynomial in t and the size of G is sufficient for traversing every edge in G with probability 1 - 8.

Lemma 2 For any d > 1, there exists a polynomial p( d, t) of order 0( d log%) such that with probability 1-8, p visits to a vertez of order d result in traversing all edges out of the vertez at least once.

Lemma 3 For any connected, regular, undirected graph G = (V, E) with order d, any 8 > 0, and any m 2: 1, there ezists a polynomial p(IEI, m, j) such that with probability 1 - 8, a random tour on G of length p vis­ its every vertex in 11 at least m times.

In most cases, we can do better than random exploration. If the robot moves in the direction it is pointing with probability better than chance, then the robot can tra­ verse every edge in the graph with high probability in time linear in the size of the graph. Using the above three lemmas it is easy to prove the following.

Theorem 1 Any finite regular tessellation G = (11, E) can be reliably, probably almost always usefully learned.

The lemmas and form of the proof described above provide a framework for proving that other kinds of graphs can be reliably probably almost always usefully learned in a polynomial number of steps. In general, all we require is that a polynomial number of visits to every vertex provides enough information to learn the graph. Perhaps, the most important lesson to extract from this exercise is that the effects of multiplicative error in learn­ ing maps of large-scale space can be eliminated if there is a reliable method for eliminating local uncertainty that works with high probability. The above approach to map learning was inspired by Rivest's model of learn­ ing [Rivest and Sloan, 1988], in which complex problems are broken down into simple subproblems that can be learned independently. In order to learn a useful repre­ sentation of the global structure of its environment, it is sufficient that a robot have reliable and usually effective methods for sensing the local structure of its environ­ ment and a method for composing the local structure to generate an accurate global structure. The sensing meth­ ods need not always provide useful answers; they need only guarantee that the answer returned is not wrong. The problem then becomes largely one of determining a sequence of sensing and movement tasks that will pro­ vide useful answers with high probability. There are sit­ uations, however , in which reliable sensing methods are not available, and it is still possible to learn useful maps of large-scale space.

1 To meet the submission length requirements, all proofs have been omitted. The longer version of the paper, including all proofs[Basye et al., 1989], is available upon request.

3.2 General Graphs

The next problem we look at involves both recogni­ tion and directional uncertainty with general undirected graphs. We show that a form of Valiant's probably ap­ proximately correct learning is possible when applied to learning maps. In this section, we consider the case in which movement in the intended direction takes place with probability better than chance, and that, upon en­ tering a. vertex, the robot knows with certainty the local name of the edge upon which it entered. We call the latter requirement reverse movement certainty. Results for related models are summarized in the next section.

At any point in time, the robot is facing in a direction defined by the label of a particular edge/ vertex pair- the vertex being the location of the robot and the edge being one of the edges emanating from that vertex. We assume that the robot can turn to face in the direction of any of the edges emanating from the robot's location. We also assume that upon entering a vertex the robot can de­ termine with certainty the direction in which it entered. Directional uncertainty arises when the robot attempts to move in the direction it is pointing. Let 1' > 0.5 be the probability that the robot moves in the direction it is currently pointing. More than 50% of the time, the robot ends up at the other end of the edge defining its current direction, but some percentage of the time it ends up at the other end of some other edge emanating from its starting vertex. While the robot won't know that it has ended up at some unintended location, it will know the direction to follow in trying to return to its previous location.

To model recognition uncertainty, we assume that the vertices V are partitioned into two sets, the distinguish­ able vertices D and the indistinguishable vertices I. We are able to distinguish only vertices in D. We refer to the vertices in D as landmarks and to the graph as a landmark graph. We define the landmark distribution parameter, r, to be the maximum distance from any ver­ tex in I to its nearest landmark (if r = 0, then I is empty and all vertices are landmarks). We say that a procedure learns the local connectivity within radius r of some v E D if it can provide the shortest path between v and any other vertex in D within a radius r of v. We say that a procedure learns the global connectivity of a graph G within a constant factor if, for any two vertices u and v in D, it can provide a path between u and v whose length is within a constant factor of the length of the shortest path between u and v in G.

We begin by showing that the multiplicative error in­ curred in trying to answer global path queries can be kept low if the local error can be kept low, that the tran­ sition from a local uncertainty measure to a global un­ certainty measure does not increase the complexity by more than a polynomial factor, and that it is possible to build a procedure that directs exploration and map building so as to answer global path queries that are ac­ curate and within a small constant factor of optimal with high probability.

Lemma 4 Let G be a landmark graph with distribution parameter r, and let c be same integer > 2. Given a pro­ cedure that, for any 61 > 0, learns the local connectivity within cr of any landmark in G in time polynomial in f,- with probability 1- 61, there is a procedure that learns the global connectivity of G with probability 1 - 6 9 for any 6 9 > 0 in time polynomial in f- and the size of the 9 graph. Any global path returned as a result will be at most c~ 2 times the length of the optimal path.

The procedure presented in the proof of Lemma 4 searches outward from a vertex v E D to a distance cr , and then uses the edges found while entering vertices on the outward path to attempt to return to v. The direc­ tions used on the way out form an expectation for the labels observed on the way back. When these expecta­ tions are not met, the traversal is said to have failed, and the procedure tries again. The procedure keeps track of the edge/vertex labels associated with vertices visited during exploration in order to ensure that it explores all paths of length cr or less emanating from each ver tex in D with high probability.

There is a possibility that some combination of move­ ment errors could result in false positive or false nega­ tive tests. But we show by exploiting reverse certainty that we can statistically distinguish between the true and false test results. By attempting enough traversals, the procedure can ensure with high probability that the most frequently occurring sets of directions correspond­ ing to perceived traversals actually correspond to paths in G. What is required, then, is for the learning pro­ cedure to do enough exploration to identify all paths of length cr or less in G with high probability.

Lemma 5 There ezists a procedure that, for any 61 > 0, learns the local connectivity within cr of a vertez in any landmark graph with probability 1-61 in time polynomial in f.-, 1 _ 1 2 -r and the size ofG, and ezponential in r.

Theorem 2 It is possible to learn the global connectiv­ ity of any landmark graph with probability 1 - 8 in time polynomial in }, 1 _\1', and the size of G, and exponen­ tial in r.

Theorem 2 is a simple consequence of Lemma 4 and 5. It has an immediate application to the problem of learning the global connectivity of a graph where all the vertices are landmarks. In this case, the parameter r = 0, and we need only explore paths of length 1 in order to establish the global connectivity of the graph. This process works even if there is no reverse certainty.

Corollary 1 It is possible to learn the connectivity of a graph G with only distinguishable locations with proba­ bility 1 - fJ in time polynomial in i, 1 _ 1 2 1', and the size of G, even if there is reverse uncertainty.

Given the notion of global connectivity defined above, no attempt is made to completely learn the graph (i.e., to recover the structure of the entire graph). It is assumed that the indistinguishable vertices are of interest only in so far as they provide directions necessary to traverse a direct path between two landmarks. But it is easy to imagine situations where the indistinguishable vertices and the paths between them are of interest. For instance, the indistinguishable vertices might be partitioned fur­ ther into equivalence classes so that one could uniquely designate a vertex by specifying its equivalence class and some radius from a particular global landmark (e.g., the bookstore just across the street from the Chrysler build­ ing).

We shall apply our above approach and try to com­ pletely learn the graph by first completely learning local neighborhoods of each landmark. Let us define Gd( v) to be the subgraph of G consisting of all vertices and edges within radius d of v.

Lemma 6 Let G be a landmark graph with distribution parameter r. Given a procedure that, for any 61 > 0, completely learns G2r+l in time polynomial in t with probability 1 - 81, there is a procedure that completely learns G with probability 1 - 8 9 for any 8 9 > 0 in time polynomial in f- and the size of G. ·

The above algorithms used for determining the local connectivity of landmarks can be thought of as building a search tree emanating from each landmark, in which each indistinguishable node in G may correspond to sev­ eral nodes in the search tree. In order to completely learn G2r+1 ( v) (as opposed to just learning the local con­ nectivity), we must avoid this redundant representation.

It turns out that we can extend our methods to com­ pletely learn G2r+1 ( v ). The algorithm builds G2r+1 via an incremental breadth-first search in which each vertex encountered is tested via repeated walks from v to deter­ mine with high probability if it has already been added to G2r + 1· The proof requires a careful examination of the probabilities of true and false test results.

Lemma 7 There exists a procedure that, for any 81 > 0, completely learns G2r+l(v) for any landmark v in a land­ mark graph with probability 1 - 81 in time polynomial in *' 1_\1' and the size of G2r+l, and exponential in r.

Theorem 3 It is possible to completely learn any land­ mark graph with probability 1 - 8 in time polynomial in t, 1 _ 1 2 1', and the size of G, and exponential in r.

3.3 Related Models

We can get the same results as in the last section if we allow movement uncertainty in the reverse direction, but demand forward movement certainty. The algorithms are similar, the justifications different. In this case, the graph can be reliably navigated by the same agent that did the map learning.

We are also investigating ways to remove the require­ ment of either reverse certainty or forward certainty. Re­ verse certainty is used in the last section to help distin­ guish probabilistically between true and false results in our testing procedures. We can show, for example, that if r( 1 -")') is bounded by a small constant, then efficient map learning is possible without either the reverse cer­ tainty or forward certainty requirement. Another way around this restriction is to allow the exploring agent to drop pebbles or beacons to remember where it has been.

4 Related Work

There have been many approaches to dealing with un­ certainty in spatial reasoning [Brooks, 1984, Davis, 1986, Durrant-Whyte, 1988, Kuipers, 1978, Lozano-Perez, 1983, McDermott and Davis, 1982, Moravec and Elfes, 1985, Smith and Cheeseman, 1986], but most of these methods suffer from the effects of multiplicative error in estimating relative position and orientation. This paper is concerned with eliminating the effects of multiplicative error by either eliminating local uncertainty altogether or by taking enough measurements to ensure that such effects are reduced to tolerable levels. In this section, we consider two related approaches.

Kuipers defines the notion of "place" in terms of a set ofrelated visual events [Kuipers, 1978). This notion pro­ vides a basis for inducing ~raphs from measurements. In Kuipers' framework [1988j, locations are arranged in an unrestricted planar graph. There is recognition uncer­ tainty, but there is no directional uncertainty (if a robot tries to traverse a particular hall, then it will actually traverse that hall; it may not be able to measure exactly how long the hall is, but it will not mistakenly move down the wrong hall). Kuipers goes to some length to deal with recognition uncertainty. To ensure correctness, he has to assume that there is some reference location that is distinguishable from all other locations. Since there is no directional uncertainty, any two locations can be distinguished by traversing paths to the reference lo­ cation. Given a procedure that is guaranteed to uniquely identify a location if it succeeds, and succeeds with high probability, we can show that a Kuipers-style map can be reliably probably almost always usefully learned using an analysis similar to that of Section 3. In fact, we do not require that the edges emanating from each vertex be labeled, just that they are cyclically ordered.

Dudek et al [1988) consider the problem of learning a graph in which all vertices are indistinguishable and upon entering a vertex the robot can leave by any arc indexed from the one it entered on. The robot can always retrace its steps if it remembers the directions it took at each point during exploration. The authors show that the problem is unsolvable in general, but that by provid­ ing the robot with a number of distinct markers ( k 2: 1) the robot can learn the graph in time polynomial in the graph's size. In order to place a marker on a particu­ lar vertex, the robot must visit that vertex; in order to recover the marker at later time, the robot must return to the vertex. A vertex with a marker on it acts as a temporary landmark. No assumption is made regarding the planarity of the graph. The problem with a single marker that can be placed once but not recovered is also unsolvable, but, if you allow a compass in addition, the problem can be solved in polynomial time.

Levitt et al [1987] describe an approach to spatial rea­ soning that avoids multiplicative error by introducing lo­ cal coordinate systems based on landmarks. Landmarks correspond to environmental features that can be ac­ quired and, more importantly, reacquired in exploring the environment. Given that landmarks can be uniquely identified, one can induce a graph whose vertices corre­ spond to regions of space defined by the landmarks vis­ ible in that region. The resulting problem involves nei­ ther recognition nor movement uncertainty. Our results in Section 3 bear directly on any extension of Levitt's work that involves either recognition or movement un­ certainty.

5 Conclusion

This paper examines the role of uncertainty in map learning. We assume an environmental model that pro­ vides for a finite set of distinctive locations that can be reliably detected and repeatedly found . Under this as­ sumption, the problem of map learning reduces to one of extracting the structure of a graph through a process of exploration in which only small parts of the struc­ ture can be sensed at a time and sensing is subject to error. We are particularly interested in showing that cu­ mulative errors in reasoning about the global properties of the environment based on local measurements can be reduced to acceptable levels using a polynomial (in the size of the graph) amount of exploration. The results in this paper shed light on several existing approaches to map learning by showing how they might be extended to handle various types of uncertainty. Our basic frame­ work is general enough to be applied to a wide variety of map learning problems. We have identified one particu­ lar source of uncertainty, namely continuity uncertainty (see Section 2), that we believe of particular interest in learning maps of buildings and other environments pos­ sessing an easily discernable structure.