Relational Object Maps for Mobile Robots

1 Introduction

Building maps of indoor spaces is an extremely important task in mobile robotics. Over the last years, the SLAM (simultaneous localization and mapping) community has made tremendous progress in the development of ef�cient and highly accurate map building techniques. Most of these techniques focus either on capturing the metric layout of an environment with high accuracy [Eliazar and Parr, 2003; Konolige et al., 2005] or on representing the topological structure of an environment [Kuipers, 2000]. While metric maps have the advantage of being well suited for robot navigation tasks, they are typically unstructured and contain no information about the different types of places or objects in an environment. Topological approaches, on the other hand, are more compact and expressive in that they describe significant places in an environment. However, these techniques often ignore valuable metric information and they still lack the ability to describe individual objects in an environment.

Our goal is to build on the progress made in metric mapping and to enhance metric maps with semantic information about different objects in an environment. Object-based representations have much higher expressive power in that they combine metric accuracy with a semantic description of an environment. In addition to allowing more natural interfaces between humans and robots (�take the third door on the right�), they enable robots to perform better reasoning, especially about dynamic objects such as doors.

Recently, Anguelov and colleagues made important steps toward building such maps by developing techniques for detecting and labeling objects in metric maps. In [Anguelov et al., 2002], they showed how to learn models of nonstationary, free-standing objects such as rectangular or round boxes. To overcome the limitations of this technique, they then developed a generative Bayesian approach for detecting doors and walls in a hallway environment [Anguelov et al., 2004]. While this approach yields good results for labeling line segments extracted from laser range-scans, it has limited capabilities in modeling context information. Even though the approach can express information such as all doors share the same width and color, it can not model more complex, spatial relationships between objects. As [Murphy et al., 2003] showed for scene analysis in computer vision, such context information can be extremely useful for distinguishing between different types of objects. In mobile robot map building, for example, an object standing in the middle of a hallway cannot be a door, even if it has the same width and color as other doors in the hallway.

In this paper, we show how to reason about the appearance of and spatial relationships between objects so as to build metric maps with object representations. We denote the resulting mapping paradigm Relational Object Maps, ROMaps for short. RO-Maps build on Relational Markov Networks (RMN) to represent hierarchical structure and the relationships between objects. RMNs are undirected graphical models that are learned discriminatively [Taskar et al., 2002]. They provide an extremely �exible framework for describing and reasoning about relations. Our RO-Maps detect objects such as doors and walls by a combination of features, including appearance features such as the width of a door, neighborhood features describing what type of objects are next to each other, and spatial features such as the indentation of a door relative to the wall. In our experiments we show that the parameters of RO-Maps can be learned from a set of hallways and then be successfully applied to labeling the objects in a hallway of a different environment.

This paper is organized as follows. After providing background on RMNs, we will show how RO-Maps model object appearance and the spatial relationships between them. Inference and parameter learning will be discussed in Section 3. Experimental results are presented in Section 4, followed by conclusions and a discussion of future work.

2 Relational Map Building

This section describes RMNs and several extensions that make them applicable to the problem of mobile robot map building. We denote the resulting framework RO-Maps, short for relational object maps.

2.1 Relational Markov Networks

We will now brie�y review the basic ideas of relational Markov networks, more detailed information can be found in [Taskar et al., 2002]. RMNs are an extension of Conditional Random Fields (CRFs), which are undirected graphical models that were developed for labeling sequence data [Lafferty et al., 2001]. CRFs are discriminative models that have been shown to out-perform generative approaches such as HMMs and Markov random �elds in areas such as natural language processing [Lafferty et al., 2001] and computer vision [Kumar and Hebert, 2003]. RMNs extend CRFs by providing a relational language for describing clique structures and enforcing parameter sharing at the template level. Thereby RMNs are an extremely �exible and concise framework for de�ning features and relationships that can be used in our map building context.

Speci�cally, an RMN consists of three parts: a schema E for the domain, a set of relational clique templates C, and corresponding potentials Φ. The schema E speci�es the set of classes (i.e., entity types) and the attributes in each class. In the map building context, the classes are types of objects, such as walls or doors, and the attributes describe their physical properties. An instantiation I of a schema speci�es the set of entities for each class and the values of all attributes for each entity. In our case, I is an RO-Map consisting of line segments extracted from laser range-scans. A relational clique template C ∈ C is similar to a query in a relational database. It selects tuples from an instantiation I; the query result is denoted as C(I). In an RO-Map, for example, a clique template can select all wall or door objects on one side of a hallway.

Each clique template C is associated with a potential function φC(vC) that maps values vC of variables in the clique to non-negative real numbers. Using a log-linear combination of feature functions to de�ne these potentials, we get the following representation: φC(vC) = exp{wTC · fC(vC)}, where fC() de�nes a feature vector for C and wTC is the transpose of the correspondingweight vector. For instance, a feature could be the indentation of a door, de�ned on a clique template selecting a door and wall objects on one side of a hallway.

For a speci�c instantiation I, an RMN de�nes a conditional distribution p(y|x) over labels y given observations x. To compute the conditional distribution of a label vector y, the RMN generates an unrolled Markov network, in which the nodes correspond to the entities. The cliques of the unrolled network are built by applying each clique template C ∈ C to the instantiation, which can result in the generation of several cliques per template. All cliques that originate from the same template must share the same weights wC. The resulting cliques factorize the conditional distribution as

where the normalizing partition function Z(x) = ∑y′ ∏C∈C ∏v′C ∈C φC(v′C ). (3) follows by moving the products into the exponent and combining all summations into w and f .

For ef�cient inference in RMNs, [Taskar et al., 2002] suggest using (loopy) belief propagation. However, because of the extensions described below, we cannot apply belief propagation directly. Instead, we will show how to perform ef�- cient inference and learning using MCMC.

2.2 Relational Object Maps

In the most general form, RO-Maps represent an environment by a hierarchical collection of objects and relations between them. RO-Maps estimate the types of objects under the assumption that their locations are known. This assumption is justi�ed by the progress made by the SLAM community, which focuses on the problem of concurrently estimating the pose of a robot and the locations of sensor measurements. Such techniques generate well aligned laser range-scans even for large scale environments (e.g., [Eliazar and Parr, 2003; Konolige et al., 2005]).

We introduce an extension of the relational framework of RMNs to reason about physical objects in RO-Maps. The RO-Map of a speci�c environment is modeled by an unrolled Markov network. Each node in such a network corresponds to an object or geometric primitive, and the links between nodes represent relations between these objects.

Objects: The basic building blocks of RO-Maps are geometric primitives such as line segments extracted from sensor data. These primitives typically describe objects such as doors or wall segments. More complex objects can be generated from existing ones by a process we call physical aggregation. This process �rst selects all objects with a certain property (just like relational clique templates do in RMNs), and then computes the parameters of the aggregated object. For example, physical aggregation generates a wall object by selecting all wall segments on one side of a hallway, followed by the computation of the line parameters and color distribution describing the wall. The left and right wall of a hallway can be aggregated into a hallway object, which has parameters such as orientation and width.

Relations between objects can be spatial, such as �distance from each other�, or appearance based, such as �similar color�. Relations can be de�ned on basic objects and objects generated by (multiple) physical aggregations. Relational clique templates of RMNs can be used to de�ne RO-Map relations. For example, to consider the similarity between the widths of the doors in a hallway, RO-Maps use a clique template C that �rst selects all objects that are labeled as doors (such selections are de�ned via SQL queries on the objects [Taskar et al., 2002;

Liao et al., 2005]). The widths of the selected doors de�ne the value vector vC of this clique, which is then fed into the feature function fC() that computes the variance. The potential of the clique, φC(vC), is given by exp{wC · fC(vC)}, where wC is the feature weight.

RO-Maps are illustrated in Figure 1. The upper plot shows laser range-scans observed by a robot traveling down a hallway; the middle plot shows the labeled line segments extracted from these scans; and the lower plot shows the nodes in the corresponding RO-Map along with some of the undirected links generated by the clique templates for this labeling. Among others, the �gure shows two cliques generated by the template that measures the indentation of doors. The template generates pairs of doors and the corresponding wall object. The potential of the clique is then based on the distance of the door from the line representing the wall. More details on features for detecting doors and walls will be given in the experimental results section.

3 Inference and Learning

3.1 Inference: Labeling objects in RO-Maps

The goal of inference is to estimate the labels (types) of the objects represented in an RO-Map. Inference in RO-Maps is more complicated than in regular RMNs. This is due to the fact that the clique structure of the Markov networks generated by RO-Maps depends on the unknown labels of objects, and thus changes during inference. Since it is not clear how (loopy) belief propagation can be applied to such labelspeci�c cliques, we use Gibbs sampling, an MCMC technique, for inference [Gilks et al., 1996]. Whenever the label of an object is changed during sampling, we determine all (aggregated) objects and cliques that could be affected by this change and re-compute their parameters and potentials. To initialize a Markov chain, we randomly assign labels to the basic objects in the RO-Map. Based on these labels, we generate all aggregate objects and their parameters. Finally, the relational clique templates generate the cliques of the unrolled, fully instantiated Markov network.

At each MCMC step, we update the label of a randomly selected object by sampling from the conditional distribution

where k is the index of the object, yk is one of its possible labels, and y-k are the labels for the other objects. To compute the probabilities of the different labels yk, we update the cliques and the parameters of aggregated objects involving the object k. Even though this process can become inef�cient for highly complex RO-Maps, inference on our current test hallways is very ef�cient, as we will describe in Section 4. We expect further ef�ciency gains by more elaborate sampling techniques.

3.2 Learning: Determining feature weights

The parameters of RO-Maps are the weights w of the features that de�ne the clique potentials. The key idea of our technique is to learn these parameters from a set of labeled environments, and then apply the learned weights when the robot explores a new environment.

The details of our learning technique are beyond the scope of this paper, more information is given in [Liao et al., 2005]. In a nutshell, the weights are learned by minimizing the negative log-likelihood of the labeled training data collected in N environments:

Here, j is the index of map mj, and yj are the labeled objects in the j-th map. The rightmost term avoids over�tting by imposing a zero-mean, Gaussian shrinkage prior on each component of the weight vector [Taskar et al., 2002]. Since (5) is convex, we can determine the global minimum using a quasi-Newton method, where the value and gradient of L(w) are determined by MCMC sampling [Liao et al., 2005].

The outcome of the learning procedure is a set of feature weights that best represent the appearance and spatial constraints of the training maps by maximizing the classi�cation rate. RO-Maps inherit the important bene�t from RMNs of automatically enforcing parameter sharing between (aggregated) objects and relations of the same type. This �smoothing� over instances of classes provides a very powerful tool for dealing with sparse training data.

4 Implementational Details and Experiments

We evaluated RO-Maps on the task of labeling line segments extracted from laser range-�nder scans collected by a robot traversing a hallway. The data sets were taken from the Radish robotics data set repository [Howard and Roy, 2003]. We took two to three hallways from �ve different environments each and manually labeled the extracted and aligned line segments into the three categories Door, Wall, and Other. Line segments were extracted using the technique described in [Gutmann and Konolige, 1999]. Some of the test hallways are shown in Figure 2. To perform the labeling, we relied on our experience in typical layouts of hallways. In several cases, we were not sure about the labeling or were only able to label doors based on the fact that we knew the real buildings represented by the maps.

4.1 Features

To label the line segments in the hallways, we implemented various features. The features were represented by the loglikelihood of the measured values under a generative model. This approach allows our technique to automatically take variability between different features into account.

Physical aggregation Wall objects are the only physically aggregated objects in our current system. Wall objects are lines that are generated from line segments that are labeled Walls and are on the same side of a hallway (see Figure 1). The Wall object parameters can be computed ef�ciently from the parameters of the line segments.

Local features describe appearance properties of objects. In RO-Maps, such features are modeled by generating a clique for each object and the corresponding attribute. We use the length of line segments as a feature. The corresponding feature functions return the log-likelihood of a speci�c length given a Gaussian representing the distribution over lengths, conditioned on the object type. The means and variances of the Gaussians for Doors, Walls, and Others were estimated from the labeled maps. In our framework it is straightforward to add other features, such as the color of objects [Anguelov et al., 2004]. Unfortunately, the Radish data sets do not contain camera information.

Aggregated Wall objects have a feature that measures the alignment of the line segments that make up the wall object. Alignment is measured by the average distance of the line segments from the aggregatedWall line. This feature helps RO-Maps to label line segments as Walls only when they are well aligned with other Wall segments.

Neighborhood features describe which object types are located next to each other. For example, it is common to observe a Wall segment next to a Door, but uncommon to �nd many Doors in close proximity to one another. We compute a line segment's neighborhood by determining all other segments with endpoints within 40 cm. Neighborhood features are then modeled by binary indicator functions on the possible label pairs (e.g., �WW�, �WD�, �DO�).

Spatial features describe the relative position of objects. The indentation of a Door object is computed relative to the aggregatedWall object on the same side of the hallway. Indentation is given by the minimum distance between the Door line endpoints and the Wall line, thereby estimating indentation at the hinge point of a door. As with line width, the indentation feature function returns the log-likelihood under a Gaussian indentation model estimated from the training maps.

Unless an object is a Wall segment, it is highly unlikely to be both very close and well-aligned with a Wall object. RO-Maps detect Other objects by considering the distance and angle alignment of such objects relative to the closest Wall object. To compute the likelihood of speci�c distances and angles, we estimate discrete distributions from the training maps (these distributions are typically non-Gaussian).

Global features depend on multiple objects that are potentially far apart. In our experiments, we measure the similarity of the indentations of all doors in a hallway by computing their variance.

4.2 Experiments and Results

To test the performance of our learning method, we used 5fold cross-validation on the �ve environments extracted from the Radish repository. To do so, the model parameters were trained on labeled hallways from four environments and then tested on the remaining one. Training on a set of 10 hallways took 2-3 hours. To generate the statistics needed for each iteration of the quasi-Newton optimization technique, we ran a Gibbs sampler for 1,000 iterations on each training map. The �nal 200 samples from each chain were used to compute differences between the sampled feature values and the feature values extracted from the labeled maps. These differences were then used to compute the relative, negative log-likelihood (5) and the gradient.

Testing, that is, labeling of the objects in an unknownmap, was very ef�cient and took around one minute or less on average. For each environment, the labeling error rate was determined by comparing the most probable assignment to the manually generated label. Most probable assignments were extracted from the Markov chains by counting the different labels for each object. The label with the highest count was compared to the ground truth. To gauge the importance of different features for labeling the objects in these hallways, we varied the set of features we used.

Table 1 summarizes the results. The numbers give the accuracy rates of the labels, averaged over the two hallways of each test environment. The leftmost result column gives the accuracy rates achieved when using only the lengths of line segments to distinguish between the different object types. The next column summarizes results obtained when considering length and neighborhood features. The resulting models are similar to standard HMMs or MRFs in that they consider local appearance features (length) and connect neighboring objects. As can be seen, object neighborhood improves the results signi�cantly. Furthermore, these results indicate that the labeling task is by far not trivial. The last column presents the accuracy rates achieved when using all features discussed in the previous section. The results show that the additional consideration of spatial constraints such as door indentation improves the classi�cation performance by a large margin.

Figure 3 shows the hallway with the highest classi�cation error (environment 5). As can be seen, most of the doors along the lower wall of the hallway are mislabeled as Other. However, this is not surprising given that the indentation of these doors is far larger than in the other training maps. Furthermore, most of these double doors are closed, which results in very long line segments. Thus, the labels are very reasonable, given the training data available to the approach.

Table 2 shows the confusion matrix summarized over all test environments using all features. The table shows that most errors are due to confusion between Others and Walls, and Others and Doors. Walls and Doors are rarely confused. The overall accuracy rate is 88.4%. This is a very encouraging result, especially since several maps contained objects for which even humans were uncertain about the correct labeling.

It should be noted that [Anguelov et al., 2004] achieved relatively high accuracy using a hierarchical Bayesian approach without spatial constraints. This is due to the fact that they trained model parameters in the same environment and took visual color information into account. Adding such appearance information to RO-Maps is straightforward and we expect strong improvements from such additional information.

5 Conclusions and Future Work

We introduced relational object maps for mobile robot mapping. RO-Maps use relational, discriminative techniques to generate metric maps with semantic object representations. RO-Maps build upon and extend Relational Markov Networks so as to reason about the appearance of and the spatial constraints between objects in an environment. In order to distinguish between different types of objects, RO-Maps can incorporate a variety of features, ranging from global, such as the width of all doors in a hallway, to spatial, such as the indentation of a door. To handle the changing structure of the Markov networks instantiated by RO-Maps, we showed how to perform inference and parameter learning using MCMC. During learning, RO-Maps bene�t from automatic parameter sharing provided by relational clique templates. This allows the models to be trained from relatively sparse training sets.

Experiments in �ve different environments demonstrate that RO-Maps are able to achieve high accuracy in labeling objects in previously unknown hallways. We show that the accuracy is improved drastically by taking spatial constraints between objects into account. These results are particularly encouraging given that objects are labeled based on laser range-data only.

RO-Maps provide an extremely �exible framework for combining metric accuracy with the representation of individual objects and structures in an environment. We believe that RO-Maps are an important step toward more expressive, semantic representations of environments. However, the work presented here is only the �rst step in this direction, laying the foundation for future research projects.

Our current implementation relies on line segments extracted from laser range-scans as the building blocks of ROMaps. As shown by [Anguelov et al., 2004], color information extracted from cameras strongly improves the performance of object classi�cation. The �exibility of our framework allows us to integrate such additional appearance information without modi�cations to the underlying RO-Map concept. We observed signi�cant improvements in initial experiments with a camera pointed toward the walls. We additionally plan to improve line segmentation by incorporating segmentation into the RO-Map inference process. Thereby, high-level information provided by the RO-Map can guide range-scan segmentation.

The RO-Maps presented here model objects in individual hallways only. A key next step will be the extension to more object classes and multiple, connected hallways, rooms, and open spaces. The RO-Map framework enables the de�nition of high-level structures such as hallways or rooms using the notion of physical aggregation. We are currently developing hierarchical representations and inference techniques that label both high-level structures and individual objects within these structures.

6 Acknowledgments

The authors would like to thank Jeff Bilmes for fruitful discussions during the early stages of this project. This research is sponsored in part by the National Science Foundation (CAREER grant number 0093406).