Using Local Information in a Non-Local Way for Mapping Graph-Like Worlds

1 Intr<,duction

The problem of exploring and mapping an unknown world in an autonomous way is becoming increasingly important especially for environments which are hostile or inaccessible (Almeida and Melin, 1989]. This explo­ ration/mapping !.ask appears to he simple if one imag­ ines an idealized Nror-fn'l' robot. with l'rror-fn·~· (allwit. limited) perceptual capacities. In practice, t.he progres­ sive accumulation of positional error 111akes t.lw construc­ tion of a map based on an absolute metric coordinate system problematic at best. Furthermore, the definition of a map in terms of specific locations or landmarks facili­ tates person-machine interaction; it is much easier to tell a robot to carry mail to the third office "down the hall"

or "to the foyer" than "to x-y coordinate (975,436)".

In this paper, we address the "worst-case" problem by assuming that our mobile robot can obtain no metric positional information whatsoever. We consider worlds that can be abstracted as graphs composed of distinct lo­ cations identified by limited sensory cues and connected by paths that provide only connectivity information. Of particular concern is the location identification problem: when visiting a given location in the world, how can the robot determine whether or not it was already visited and therefore a lready present. in the map prepared thus far? We demonstrate that by augmenting local informa­ tion about the location by inf'onnat.ion about its neigh­ hours and t.heir IH~ ighhours up t.o a given distance, it b!·comcs possible in 111arry IIOII-world,; to answer the loca­ tion identification problen1 correct ly [Corneil and Kirk­ patrick, 1980; Dr1d1·k el a/.,I!J!Jlb]. lrr thisway,amapof the world may h1· obtained which fait.hfully models the locations anrl t.flt'ir ronnert.ivit.y.

2 Problem context

VVe assume that. the robot world is composed of a fi­ nite number of distinguishable locations connected by bi-directional paths. Such an world may be represented as a graph where vertices correspond to locations and edges correspond to paths 1 .

For example, the world shown in Figure 1 may be represented by a graph G = (V, E) where Vis the set of vertices v1 , v2 , .. , v6 and E is the set of edges whe:e ei,j or (vi, v;) denotes the edge connecting .vertices Vi and .vi.

Locations are identified by a non-umque szgnahre, 1.e. a set of characteristic features which may be reliably ob­ tained from the robot's percepts. For our purposes here, we will further assume that upon arriving at a location, the robot can identify the number of paths leading to other locations . To simplify t.he exposition, we will con­ sider that t.he signat.ure of a lontt.ion is the degree of t.h(' corresponding \'f'rt I' X ( anot.lwr I'.'Oun pie might asso­ ciate signal.url' wit.h vertex ro lo11r) . In addition, we shall assume that at l'arh locat.iorr . t.hl' robot. is able t.o enu­ nwrat.e t.IH' irH·onJing/ollt.going paths in a syst.emat.ir way

I As conseque!ICC or this ~r<tpll rq>reseul.at.ion, there may only be one edge het.wecu adjaccut vnticc,,; a11d thus worlds in which there arc multiple paths hct.wceu adjacent locations cannot be considered cg. graphs wit.h cycles or length 2.

(eg. clockwise), relative to the path by which it arrived at the location.

As t.he robot performs t.he exploration, it. records all the information obtained whenever any action, sensing or motion (path traversal), is performed. By 'remem­ bering' all motion sequences, the robot may retrace any previously performed motion.

3 Related work

In contrast to a geometric map, a topological map can be defined [Davis, 1986] as a map including all fixed en­ tities of the world such as distinguishable locations and regions, linked by topological relations eg. connectivity, containment. Advantages of such an approach include it.s qualitative nature and attractive links to theories of hL.nan cognition and mapping. Such a map is often represented as a graph where vertices are locations and edges their adjacency relations.

Metric and topological information can be hierarchi­ cally related, within the context of a multilevel rep­ resentation theory of a large scale space 2 based on the observation and re-acquisition of distinctive visual events called landmarks [Chatila and Laumond , 198.5; Kuipers and Byun, 1988]. It is often assumed that dis­ tinctive locations can be robustly found, t.hat they are not too numerous, and that. no two locations can be con­ fused [Schwartz and Yap, 1987; Leonar·d and Durrant­ Whyte, 1991]. Clearly, this last. assumption is an ideal­ ization of a real robot. exploring a real world; not. 111aking it leads to serious complications [Basye and Dean, 1990].

2 A "large-scale" space is a space whose structure is at a significantly larger scale than the observations available at an instant [Kuipers and Byun, 1988] .

For example, the TOTO robot [Mataric, 1990] is a real device that creates a topological map (a graph) as it explores it.s world. As landmarks are detected, they become nodes in the graph along with their qualita­ tive properties, i.e. type (left wall, right. wall, corridor) and associated compass bearing. A clever "truth main­ tenance" protocol is invoked to ensure that the same landmark does not become multiple nodes in the graph. This approach illustrates several important components of topological mapping and involves substantial domain­ dependent processing.

The work of [Dudek et al., 199la] deals with explo­ ration using markers and is directly related to the ap­ proach described here. The same assumptions apply as to the nature of the world to be explored and the percep­ tual capabilities of the robot but in addition, the robot is equipped with at least one recognizable marker which can be put down or picked up. This physical marker makes Vi distinctive according to the others vertices, and therefore represents a 'temporary' signature of that loca­ tion. It is shown that such worlds can be fully explored and described in limited complexity using a single mov­ able marker (like a pebble) even if there are no spatial metrics and almost no sensory abi lity on the part of the robot.

The marker-based analysis requires that the robot be able to reliably place, identify and recover the markers it uses for exploration. In t.h is paper , we show how map­ ping can be accornplished witlroul. such markers even though i nd i vidual locations rnay not. bP uniquely identi­ fiable.

4 The mapping algorithm

The exploration and mapping a lgor it.lrrn has essentially two stages. First, the robot, st.art. ing from an arbitrary locat ion, explores its (unknown) world by visiting all lo­ cations. Information thus obtained is then used to gen­ erate a model of the observed connectivity 3 .

As described above, we shall assume that the robot is equipped with a sensing dev ice which is used, at each location, to determine the number of incoming/outgoing paths and enumerate them in a consistent manner eg. clockwise. The number of paths then defines the signa­ ture of the location, i.e. the degree of the corresponding vertex in the map. Since this is often inadequate to uniquely identify a vertex (or equivalently, to uniquely specify connectivity) we shall also exploit signature in­ formation about the location's neighborhood.

While the exploration t.akcs place, the robot con­ st.ruct.s a dat.a repn~scntat. ion calbl t.he "exploration tree" which includes, at. the end of t.he exploration, the set. S of all possi hi<· world nwd<~ls (i.e maps) consistent with the robot's ohservat.ions. Tlr is set of solu t.ions is called the "solution universe".

If .S' contains rrHH<' tlr11n rrrodd. tlwrr t.lw robot. must rely on additional knowl edpp al>cllrt. t.lw world such as t.he total number of locations, information about the prob­ ability distribution of location signatures, or perhaps some compass measurements, to identify that model which best represents the connectivity information in the world.

3 Recall tha.t between any two a.dj;u:eut locations, there is at most one edge.

4.1 The exploration tree

The exploration tree refers to the collection of possible hypotheses about the world the robot is exploring, given the data accumulated thus far in the exploration. It is incrementally constructed while the exploration takes place. The root of the tree is just the initial location from which the exploration began. A level in the tree corre­ sponds to the traversal of a previously unexplored edge. The nodes belonging to a given level of the exploration tree represent possible partial models of connectivity in the world, according to the locations visited thus far. Nodes corresponding to the current level of exploration are called frontier nodes. Leaf nodes represent possible models (complete configurations) of world connectivity. A given node in the exploration tree is consirlPrPO to tw a leaf node (i.e. a possible model) if there are no paths sti II to be traversed 4 .

Our notation is as follows:

• vertices corresponding to locations in the woriJ are denoted by v1 , v2 , ...
• vertices associated with nodes in the exploration tree are denoted by v{, vt ... , where v{ corresponds to the jlh visit of location v;. Since a given location may be visited several times as part of the explo­ ration, we can have several associated vertices in the exploration tree nodes corresponding to differ­ ent visits of that vertex.

A correct model is characterized by the fact that when the robot visits a given location multiple times, it 'rec­ ognizes' that these are all visits to the same location. That is, there exists a correspondence between vf (the first visit to the location corresponding to vertex v;) and vf (the kth visit) for all k, and an absence of other (in­ correct) correspondences. To guarantee successful ex­ ploration, i.e. exploration leading to the creation of a solution universe S which necessarily contains a model of existing connectivity in the world, two problems must be arldressed :

• I . How can the robot know when all of the locations in the world have been visited ?
• When a location is visited, how can the robot know whether or not it represents a location previously visited and is therefore already present in the ex­ ploration tree ? We shall call this the location iden­ tification problem.

l'v1 any possible exploration strategies are possible (even stochastic ones) but for simplicity, we will consider a FIFO (first-in first-out) traversal of new edges . This guarantees that all edges will be explored, although per­ haps not optimally. In Figure 2, we illustrate how the robot explores the world shown in Figure 1, by showing the robot motions and the associated actions to con­ struct the exploration tree. In this example, the explo­ ration tree has only one branch and the solution universe contains just one possible solution which is the leaf of the tree, the framed node.

4 This is because in the exploration tree, the robot only 'knows' whether br not there are paths still to be traversed associated with a location previously visited, not whether or not. there are extra locations t.o visit ..

The second problem is more complex since location identification must be performed with very limited infor­ mation. Indeed, by associating the signature of a loca­ tion with vertex degree, the robot cannot always know when it is visiting a location for the first time or not. For example, in a world which contains cycles, the robot will inevitably re-visit some locations. That is, when the robot visits a given location, it. could either be the first visit to a new (previously un-visited) location, or are­ visit to any of the locations that. have the same signature (i.e. that appear the same) . Thus, when the robot visits a location, it must consider all possible ways of adding vertices to t.hP front iPr no ell's in t.lw exploration tree.

Three classes of errors or mis-identifications can be defined when the robot. visits a given vertex v;. (Errors associated with paths (edges in the exploration tree) are subsumed within this classification.) These are as fol­ lows.

• El Errors of type OLD-LOOI<S-N8W. A vertex v; is as­ sumed to be a new vertex even though it has been visited before (i .e. a failure in correspondence). In this case, an additional vertex is added to represent the current location even though a vertex for the current location has already been created .
• E2 Errors of type MIS-CORRESPONDENCE. A vertex v; is "recognized" as a known vertex Vj (j =f i) even though, in reality, it is another old vertex VJc (i.e. the robot has confused two existing nodes) . Thus, an erroneous edge is added to the world .
• E3 Errors of type NEW-LOOKS-OLD. A vertex v; is as­ sumed to be an already visited vertex - an old vertex - even though it. is new. In t.his case, t.he map will have a missing vertex relative to the real world.

Branches in the exploration tree are creat.eJ as a re­ sult of modelling the truP topological strncture of the worlrl, or by rnak i ng one or mon· corr('spondence errors of different types. In rnost. cases, branches arising from errors eventually terminate d1w to inconsistencies result­ ing from the incorrect topology induced by the error(s) . For example, the robot conn~cts two vertices VJ and v2 during the exploration of v1 and then realizes that it is a wrong connection during the exploration of v2 . Of course, the development of any branch is halted once the frontier node has no more paths to traverse.

The exploration tree will always contain a branch for which no errors are committed, i.e. a branch leading to a leaf which faithfully describes the connectivity in the world.

4.2 The extended signature

Typical exploration trees usually include branches that are subsequently pruned (i.e. they develop inconsistencies before they lead to a complete model) . This can be observed in the tree shown in Figure 3. The major rea­ son for this is the weakness of the signature information used by the robot for addressing the location identifi­ cation problem; incorrect hypotheses regarding vertex correspondences cannot be avoided based on local per­ ceptual input . To make the exploration more robust and effective, we shall now exploit non- local information by defining an extended signature incorporating signature information about a location's neighbours .

We begin by defining the initial (zero'th) neighbours N0 (u) of a vertex u as follows :

(2)

Then its immediate neighbours N1 (u) may be defined as follows :

We can then define the immediate 'outgoing' neighbours N2(u) of those vertices in N1 (u) as follows:

Note that we take rare to exc l11de 11 frorn this list, in the case where tlwrc ex ists a ryclc involving u and some vertex in N 1(NJ(u)).

More generally, we defin e N,(u) t.o be t.he m'h neigh­ bours of u :

To make the vertex matching in the exploration tree more robust, we will now go beyond local signature infor­ mation (vertex degree) to consider an extended signature defined in terms of the signatures of the neighbours of a location. For example, suppose that we have two vertices u and v and we wish to establish whether they refer, in fact, to the same physical location. If they have identical signatures (degrees), then we consider their immediate neighbours, N1(u) and N1(v) . If the immediate neigh­ bours also have identical signatures and appear in the same configuration, then we consider N2(u) and N2(v), and so on.

We may define the extended signature of a vertex u in terms of the signatures of its neighbours up to a given distance m as follows:

where deg(v) denotes the degree of vertex v. For exam­ ple, for the graph in Figure 1, the extended signatures of the vertex v1 are as follows :

This extended signature may be also be viewed as a sig­ nature tree, where the root. represents the degree of ver­ tex u and nodes belonging t.o a level i in this tree rep­ resent the degrees of the i 1 h neighbours of u; see Figure 4.

Note that a node's extended signat.ure is generally only unique with respect t.o a specific reference edge. Consider as root a vertex with degree d, with d possible extended signatures. In Figure 5, we illustrate how any extended signature may be obtained from any other extended sig­ nature by circularly re-ordering its edges . Consequently, when comparing two vertices, the robot must take into consideration all possible re-orderings of their extended signatures. More precisely, if the extended signatures are isomorphic, then the two vertices might correspond to the same location, i.e. we must consider extended signatures involving more neighbours.

4.3 Algorithm details

The exploration algorithm functions by creating a sub­ section of the world for whirh there exists a known map. Initially, this is sintply the robot's starting locat.ion. As the exploration proceeds, this map is gradually expanded by adding new vertices and t.lwir connectivity to the rnap already estahl islwd . When a location is visited and a new vertex in the rnap is postnlr~tcd, its relat.ionship to the Three distinct representations for the stqnature of vertex "2

Figure 5: An example illustrating that the signature tree is invariant under circular re-ordering.

set of known vertices must be established and the corre­ spondence (if any) with any other vertex must be verified (using the signature and extended signature analysis).

When the robot visits a location corresponding to a new vertex u, it starts by ordering the incident edges e; according to the "reference" edge e0 by which it arrived at u (eg. using a clockwise ordering). (Note that the "reference edge" is only defined by the robot's own his­ tory - the reference edge is not perceptible in the graph itself.) The robot then examines these edges (except eo) sequentially by traversing each one to visit the vertex at the other end. The process of traversing the ith edge e; may be described as follows:

1. Traverse edge e; to reach the other vertex v and compute deg(v).
2. Verify if edge e; is already connected to another vertex w in the exploration tree (for each model). If yes, verify the validity of the connection by comparing the extended signatures or v and w: Sig(v)andSig(w); if they are different., then reject. the proposed connection.
3. If edge e; is 'free', i.e. not already connected to an­ other vertex, compute C(ei), the set of all possible connections, which includes:
4. connections to previously visited vertices v; with Sig(v;) = Sig(v) and with a 'free' inci­ dent edge. For each such v; found, create a new node in the exploration tree by adding an edge connecting v to v;.
5. a connection to a new vertex w. A new node is created in the exploration tree by adding an edge connecting v to w.

The cost of this exploration process in terms of actual edge traversals by the robot (mechanical complexity) de­ pends only to the search strategy used by the robot in moving through the world. The algorithm is compati­ ble with almost any strategy that progressively traverses new edges. Breath-first. search provides a simple exam­ ple.

The computational cost of the mapping algorithm is a function of the number of nodes (possible world mod­ els) in the exploration tree; the actual generation, main­ tenance and comparison operations for extended signa­ tures have low-order polynomial complexity. The num­ ber of nodes in the exploration tree depends on the dis­ tinctiveness of the perceptual information extracted at each location. When insufficient perceptual information is available to constrain the growth in the e~ploration tree various pruning or deferred expansion strategies are possible.

Full details about the al~orithm with some complete examples may be found in lDudek et a/., 1993].

5 Coping with ambiguity m location identification

Despite the availabilit.y of an cxt. end<~d signature, am­ biguity may still remain in location identification. As a result, the universe of possible solut.ions S' may con­ tain various models which <H<' equivalent. insofar as the extended signattJr<~ is roncPrll<'d. of which just. onf' faith­ fully reflects the conrwct.ivit.y in t . h<~ world (for example a simple cycle of either three or four vertices). In this section, we consider additional inforlllation (in addition to location signature) that Jtta.kes it possible t.o identify the the correct model in S.

As we have shown, the presence of cycles in the world gives rise to an exploration tree of infinite size, due to the existence of a branch of infinite length, corresponding to the case where every visited vertex is considered to be new. Hence, the exploration procedure must elect to cease exploration even though some possible models have not been fully explored.

One cue as to when to stop exploration and select appropriate model(s) is prior knowledge of the number of locations N in the world. For example, this might be the case when the robot is exploring a multi-floor building where all floors have the roughly the same number of offices. This implies that the exploration process can terminate as soon as all nodes in the exploration tree have at. leilst. N VNt.ir<~s. J.<'. as soon iiS nodes which contain edges st.ill t.o be traversed have more than N vert. ices.

Another possihl<' cue is prior knowledg<' of the pla­ narity of the world being explored. \V<~ may often assume that the world t.o be explored is planar (topologically speaking) and hence a simple planarity test. may suffice t.o distinguish bet.wPNJ equivale111. rnodels. Indeed, if N is also known, then we demonstrate elsewhere [Dudek et a/., 1993] that our algorithm leads to a unique (correct) solution (or multiple isomorphic correct solutions).

Perhaps most important. is the fact. that alternative branches in the exploration tree correspond to assumptions regarding the existence (or non-existence) of mul­ tiple locations in the world that are perceptually indis­ tinguishable. If the likelihood of such occurences can be estimated then alternative worlds in the exploration tree can be ranked in terms of their overall likelihood .

6 Discussion and Conclusions

In this paper, we have described how a robot with limited perceptual capacities may explore and faithfully map the topology of unknown graph-like worlds. The approach is based on aggregating non-local information to com­ pensate for potentially ambiguous local perceptual in­ formation. Locations in the world are identified by a non-unique "signature" that serves as an abstraction for a percept that might be obtained from a robotic sensor. While the signature of any single location may not be unique, under appropriate conditions the distinctiveness of a particular set of signatures in a neighborhood in­ creases with neighborhood size. By using a collection of non-unique local signatures we can thereby construct an "extended" signature that uniquely determines the robot's position (although in certain i nsufllciently rich worlds additional information is also required). The al­ gorithm makes use of no metric information such as the distances of the paths traversed, but the availability of such measurements would simplify the mapping prob­ lem.

The worst case behavior of the algorithm is clearly problematic. For example, there can be multiple embed­ dings of the same graph, leading to multiple topological models of the unknown world. For example, for regu­ lar graphs every location is identical to every other and the number of possible models grows initially as O(k 1) for level k of the exploration tree (although keeping only one or two models is sufficient to express both all the st.ruct.ure t.hat. the rohot. hils ohsr~ rved and all t.lrilt. it can accomplish given the limited percepts it has made). This initi al explosive growth is reduced once the tree depth exceeds the vertex degree (i.e. very early for pla­ nar graphs). This difficulty 'is not surprising since un­ der such circumstances we are attempting to construct a map from no knowledge about. where we are or how we are moving - anything is possible. Thus the difficulty is not. intrinsic to this algorithm but rather to the im­ poverished stimuli. In worlds where more information is ilvailable and various places are distinguishable the tree grows much more slowly and there are several signifi­ cant sub-cases of interest. One notable class of worlds are those where a pair of uniquely distinguishable ver­ tices exist. In such cases a single unique solution will be produced [Dudek et a/., 1 993]. We are now using an im­ plementation of our algorithm written in C to examine issues relating to the growth of the exploration tree and the solution space for different kinds of environments.

7 Acknowledgments

The idea of using an extended signature evolved partly from discussions wit.h M. R . .J enkin , E. Milios, and D. \Vilkcs .

The authors gratefully acknowledge the financial sup­ port of the Natural Sciences and Engineering Research Council and the Centre de recherche informatique de Montreal.