Qualitative Map Learning Based on Co-visibility of Objects

1 Introduction

Map learning problem of autonomous mobile robots has been a central issue in the field of artificial intelligence as well as robotics, because it contains several important as­ pects of intelligence such as recognition of environment and acquisition of internal representations. In fact, a variety of map building methods have been developed for a wide range of robots, tasks and environments so far. These meth­ ods are traditionally classified [Kortenkamp et al., 1998; Murphy, 2000] in terms of the way of map representation into metric map building methods[Moravec and Elfes, 1985; Uhlmann et al., 1997], topological methods[Mataric, 1992; Zimmer, 1996; Shatkay and Kaelbling, 1997], and hybrids of them[Thrun et al. , 1998].

On the other hand, when we tum our attention to a new trend of robot navigation called qualitative navigation[Levitt and Lawton, 1990; Schlieder, 1993], we can see there is an­ other way of qualitative map representation that is different from both the metric and topological representations. A most important point of the maps used in this qualitative navigation is that they are not required to be accurate in a metric sense as long as they correctly preserve the qualitative spatial relation­ ships (such as circular ordering) of the objects or landmarks in the actual environment.

A challenging problem in this paradigm is to construct au­ tonomously such qualitative maps from qualitative observa­ tion information robots obtain. A representative approach to this qualitative map learning problem is [Sogo et al. , 2001], in which qualitative information of "how object positions are classified to two sets with respect to arbitrary straight lines" is used to construct a map by propagating "three point" con­ straints.

In this paper, we also propose a map learning method for mobile robots based on qualitative observation information. It uses the information of "co-visibility" or whether two ob­ jects are visible or not at the same time from robot's positions, which is much more primitive than the information used in [Sogo et al., 2001] and the ordering information[Schlieder, 1993].

In this method, co-visibility of two objects is translated into an empirical distance based on a simple heuristics "closely lo­ cated objects are likely to be seen simultaneously more often than distant objects and vice versa" or "temporal and spatial proximities are approximately equivalent". Then, positions of all objects are calculated by well-known multidimensional scaling (MDS) technique.

A noteworthy feature of this method from a practical view­ point is that it does not require robots localize their own po­ sitions while mapping. Moreover, it is shown that it can learn qualitatively accurate maps without higher level information such as ordering, and is robust against observation errors. We also discuss the validity of the heuristics above from several viewpoints.

2 Problem Definition

2.1 Assumptions on Environment and Robot

we consider a map building task by a mobile robot, in which the robot estimates the positions of objects in the environ­ ment by repeated explorations and observations (Figure 1 ). More specifically, we make the following assumptions about the environment and robot.

Environment

The environment is a closed area containing a finite number of objects. Each object is assigned a unique ID. In addition, it is assumed that all objects are about the san1e size.

Environment

Figure 2: Definition of triangle orientation

Observation

The robot obtains a panoramic camera image at each observa­ tion point, and extracts a list of recognized or visible objects by some image processing and recognition technique. These lists of visible objects are accumulated over time and used to build a map later.

Exploration

The robot explores the environment with some randomness, avoiding collisions with objects.

2.2 Evaluation Criterion for Qualitative Maps

Though a constructed map is represented in the form of nu­ meric coordinates of the objects on 2-D plane as ordinary metric maps, its goodness is measured by the correctness of the qualitative spatial relationships rather than by the metric accuracy.

To evaluate the qualitative correctness of the ob­ tained maps, we employ the notion of triangle orientation[Schlieder, 1993; Sogo eta/., 2001] or counter­ clockwise order of three points. In short, triangle orientation of three points [p1p2p3] in 2-D plane is defined as + when the order p1,p2,p3 yields a counter-clockwise tum, and - otherwise (Figure 2).

When there are N objects in the environment, the number of all possible triangles formed by them becomes NC3 . So we define the orientation error Err ori of a constructed map as the percentage of triangles with wrong orientations, compared with the real configuration of the objects, i.e., We use this Err ori as an evaluation criterion of constructed maps in the later simulation study.

2.3 Co-visibility and Distance Between Objects

As previously mentioned, we use a heuristics "a pair of ob­ jects observed simultaneously more frequently is likely to be located more closely together" to estimate the distance be­ tween them. Though it is hard to prove the validity of this heuristics strictly in general cases, we consider it is approxi­ mately appropriate for the following reason.

First, we assume that an object becomes difficult to identify as the distance from the robot increases, because the image size of the object becomes smaller and the chance of occlu­ sion increases.

Given this assumption, the total area size of the region where the robot can observe two objects simultaneously de­ creases monotonically according to the distance between the objects. For example, consider the case the probability that an object can be observed from the robot at a distance of r is PI(r) = e-a·r 2 (Figure 3). If two object A and Bare located at (- ~, 0) and ( ~, 0) respectively, the probability that both objects are visible from an arbitrary robot position X (x, y) becomes

Then, the' expected size of area where both objects are visible simultaneously is

In the simplest case that the robot is located at any place in the environment with equal probability, the probability that the two objects are co-visible is expected be proportional to Scovis (l), which is a monotonic decreasing function of l.

In section 4, we will discuss this "co-visibility and dis­ tance" heuristics in a more general form: "temporal and spa­ tial proximities are approximately equivalent".

3 Proposed Method

3.1 Outline of CoviMap

Based on the assumptions above, we propose CoviMap - a map learning method based on the co-visibility of objects. In this method, the mobile robot obtains approximate posi­ tions of objects based on the co-visibility frequencies ofthem, which are updated repeatedly by explorations and observa­ tions. The outline of CoviMap is described as below:

1. The robot repeats the following behavior steps and up­ dates the number of observations of each object ( n;), and the number of simultaneous observations of every pair of objects ( n;,j ).
2. (a) The robot moves to the next observation position, avoiding collisions with the objects.

• (b) It obtains a list of visible objects £ 0 from the and updates ni and ni ,j as bellow:
• panoramic image captured at the current position, ni +- ni + 1 for each object i in £ 0 ni,j +- ni,j + 1 for each pair of i, j in L0
• After a specified number of steps, co-visibility frequen­ cies f i,j is computed for each pair of objects based on ni , n1, and ni ,j · Then empirical distance d?j of each pair is computed from fi.J .
• The robot obtains the estimated positions of all objects ( x1 , · · · , x N) by applying Multi-Dimensional Scaling (MDS) to the distance matrix D whose (i , j) element ' d'2 IS i,j·

In the remaining of this section, we explain the second and third parts in the above procedure.

3.2 Computation of Co-visibility Frequency and Empirical Distance

Co-visibility frequency Ai between two objects is defined as follows:

J;, j stands for the conditional probability that two objects are visible at the same time, given that at least one of them is visible. It takes a value between 0 and I . This definition of J;,j is also known as Jaccard's coefficient.

With the definition of co-visibility frequency fi ,j, the heuristics introduced in 2.3 can be rewritten as "distance be­ tween two objects di, j monotonically decreases as fi ,j in­ creases". Figure 4 (scattered points) illustrates the actual rela­ tionship between the real (squared) distance and co-visibility frequency Ai in the simulation environment in section 4. The result indicates that the heuristics is approximately valid.

Therefore, we introduce a notion of empirical (squared) distance d?j between an arbitrary pair of objects, which is defined by some monotonic decreasing non-negative function ¢, i.e.,

We also define an empirical distance matrix D whose (i , j) element equals to d~7j . D is a symmetric matrix (i.e., d~7j = d'li ), and its diagonal components (d~7i) equal to zero.

A possible solution to the problem of deciding a suitable combination of function and parameter values for cjJ is to se­ lect the one which minimizes the stress value of the MDS re­ sults described later. Furthermore, if no appropriate empirical distance functions are provided, non-metric MDS (or ordinal MDS) can be used instead.

Another problem is that d~7j cannot be computed properly for the pairs whose co-visibility frequencies are zero, because ¢ becomes some constant value. In this case, CoviMap uti­ lizes the triangular inequality constraint (TIC) to correct the value of d~7j as follows:

3.3 Map Construction Based on Multi-Dimensional Scaling (MDS)

Multi-dimensional scaling (MDS)[Young and Householder, 1938] is a multivariate data analysis technique used to visu­ alize a potentially high-dimensional data structure by map­ ping it into a relatively low dimensional space[ Cox and Cox, 200 1]. The purpose of MDS is to find an optimal configura­ tion of objects in a low-dimensional space, when dissimilari­ ties or distances among them are given.

While there are several kinds of MDS methods[ Cox and Cox, 2001], CoviMap employs classical scaling[Young and Householder, 1938] method that is a kind of metric MDS to reproduce a map of objects in 2-D plane from the set of empir­ ical distances. In brief, it obtains a set of 2-D coordinates of N objects Xi (i = 1, · · ·, N) by applying Young-Householder transformation and spectral decomposition to the empirical distance matrix D .

A non-trivial problem of using MDS in CoviMap is that there is a fifty percent chance of obtaining the mirror image of the expected map. However, if any correct triangle orien­ tation of three objects is given, CoviMap can detect the mirror map and get the right map by turning it over.

4 A Simulation Study

We conducted a simulation study to examine the effective­ ness of our method with Cyberbotics' WEBOTS simulator (ver.2.0).

4.1 Settings

Environment and Objects

The environment is a square field of 1.5[m] x 1.5[m] con­ taining 5- 30 objects. Each object is cylinder-shaped (height: 160[mm], diameter: 48[mm]), and is given a unique ID num­ ber like obO, obi, · · · ..

Observation and Object Recognition

The robot has a camera with a resolution of 160 x 120 pix­ els, and obtains a panoramic image by rotating and capturing several images at each observation position. We make a sim­ plified assumption that the robot can recognize an object if its image is wider than 10 pixels.

Exploration Strategy

At each observation position, the robot chooses its next mov­ ing direction randomly within the range of ±Or = 45[deg], and proceeds lr = lOO[mm] in the direction. In addition, the robot has 8 proximity sensors to detect nearby obstacles (objects and walls) around it, and avoids collisions with them.

Empirical Distance Function

We chose a logarithmic function as the empirical distance function cf> as below:

where, a, c5t, c5,. are parameters which take positive values. In this simulation, we set them as: a= 0.3, c5t = 0.1, c5,. = 2.0, because the stress values of MDS were relatively small with this combination compared with others. Figure 5 shows the shape of this empirical distance function. In addition, triangular inequality constraint (TIC) mentioned in 3.2 was used to correct the empirical distances for the object pairs whose co-visibility frequencies were zero.

4.2 Experiment 1 : Varying Number of Objects

First, we examined the basic map building capabilities of CoviMap with varying number of objects in the environment from 5 to 30. In each case, the robot repeated the observa­ tion and exploration steps for 1000 times, and built a map eachtime the number of steps reached one of specified num­ bers (20,50, 1 00, ... , 1 000). For each case, we prepared 5 lay­ outs of objects which are randomly generated and averaged the orientation errors.

Figure 6 and Table 1 show how the average orientation er­ ror Err ori changes according to the number of steps for each number of objects. As can be seen from this, Err ori con­ verges to a narrow range (approximately between 2.5[%] and 3.0[%]) after several hundreds of steps, when the number of objects varies from 10 to 30. This means that CoviMap is not affected drastically by the increase in the number of objects.

Figure 7 illustrates an example of real configuration which contains 30 objects, while Figure 8 illustrates a map con­ structed by CoviMap after 500 steps. In this case, out of total 4060 triangles, the number of triangles whose orientations are inconsistent between the real map and the constructed map is 98 (Errori = 2.4[%]). Interestingly, if we consider only the triangles whose largest angles are smaller than 170[ de g) in the real map (the number of such triangles is 3835), the num­ ber of inconsistent triangles falls to 27 (Errori = 0.70[%]). This means our method is able to acquire very accurate qual­ itative layouts of the objects, unless the objects are almost on a line. Dotted lines in the figures represent De/aunay graphs of the configurations. A comparison of them also tells that the constructed map is qualitatively very accurate.

4.3 Experiment 2: Robustness Against Object Recognition Errors

In the previous experiment, it was assumed that there are no errors in the object recognition process. In the real environ­ ment, however, it is almost inevitable to fail in recognizing objects occasionally, due to various uncertainties. Therefore, we examined how the recognition errors affect the quality of maps constructed by CoviMap.

More specifically, we considered two kinds of recognition errors - non-recognition and mis-recognition. These errors were artificially generated as follows:

Non-recognition : Randomly chosen elements in L0 are re­ moved

Mis-recognition : Randomly chosen elements in L 0 are re­ placed with other object IDs.

In this experiment, we fixed the number of objects to 15 and conducted 5 trials for each of 5 different object configu­ rations.

Result with Non-recognition Error

Figure 9 shows the average orientation errors of the con­ structed maps when the percentage of non-recognition er­ ror is set to 0.0 (no errors), 3.0, 10, 20[%] respectively. In an early stage of learning, i.e, with fewer steps, the map error Err ori becomes larger according to the magnitude of the non-recognition error. However, the difference becomes smaller and almost negligible as the number of steps m­ creases.

Result with Mis-recognition Error

Next, Figure 10 shows the results when mis-recognition er­ ror is set to 0.0, 0.5, 2, 10[%] respectively. Not surprisingly, the influence of this kind of error on the map error Err ori is relatively larger than the non-recognition error.

In both cases, however, we can conclude CoviMap is robust against those recognition errors, in that the map error steadily decreases according to the increase of the number of steps.

5 Related Works

As mentioned before, the central idea of our map building method is a simple heuristics - "a pair of objects observed simultaneously more frequently is likely to be located more closely", which is used to estimate the distances and quali­ tative configuration of objects from the co-visibility informa­ tion of them. In this section, we discuss the meaning of this heuristics from other viewpoints, especially, considering sev­ eral related works in other fields.

First, as co-visibility of objects can be regarded as co­ occurrence of events that objects are visible, a lot of stud­ ies on learning of behavior and models based on the co­ occurrence information have been made. The most basic principle related to this issue is Hebb 's rule which postu­ lates that if two events co-occur often, the connection of them should be strengthened. Many recently developed rein­ forcement learning methods such as Q-learning[Watkins and Dayan, 1992] are also considered to be based on the co­ occurrence or temporal proximity between behavior and re­ ward events. Interestingly, there is another similarity between reinforcement learning and our CoviMap. That is to say, the former learns a complicated behavior system from discrete events of rewards, while the latter learns a qualitatively accu­ rate map from discrete events of co-visibility among objects.

The heuristics above can also be regarded as a special case of more general one - "temporal and spatial proxim­ ities are approximately equivalent in many environments". In the research of human spatial memory, it has been re­ ported that humans often rely on the temporal proximity rather than the spatial proximity to memorize spatial struc­ tures of environments[ Curiel and Radvansky, 1998]. This might suggest that the principles and results of CoviMap pre­ sented in this paper are helpful to understand some aspects of human spatial memory and cognitive mapping process, al­ though we doubt that an MDS-like algorithm exists in human brain.

6 Conclusion

In this paper, we proposed a unique map building method for mobile robots named CoviMap which is based on the co­ visibility information of objects in the environment. It can learn qualitatively accurate maps from such primitive infor­ mation using a simple heuristics "temporal and spatial prox­ imities are approximately equivalent" and multidimensional scaling (MDS) technique. It was also shown by the simula­ tion results that CoviMap is applicable to large environments containing dozens of objects, and robust against observation errors such as non-recognition and mis-recognition.

A most important theoretical issue to be studied is to vali­ date and generalize the heuristics on the equivalence of tem­ poral and spatial proximities. Especially, we need to investi­ gate how our method will be affected if the camera image is not panoramic but more restricted, or the object recognition rate is not isotropic but dependent on the direction. On the other hand, future works from a practical point of view will include experiment with real robots, integration of CoviMap with qualitative navigation[Levitt and Lawton, 1990], and ex­ tension or replacement[Faloutsos and Lin, 1995] ofMDS.