Sensor data classication is very dependent on which features represent primitives. We consider line segments extracted from laser points as primitives, and focus on their collective classication into door or wall objects, so as to build semantic maps. Because features may have non-trivial characteristics, and sensor primitives may be inter-related in complex ways, we represent features of spatial relationships using a probabilistic description logic.
Introduction
Recent successes have raised expectations concerning the behavior of mobile
robots in dynamic environments [
Although there is no unique or precise denition for semantic maping in robotics, in the last ve years many researchers have turned to spatial representations tagged with information like: "This segment of laser data is a door" or "This area of the occupancy grid is a room". As such, a semantic map typically means a labeled spatial map, and not really a map interwoved with deep semantic information. Few proposals really include semantic information in their robotic architecture by means of an ontology that relates objects in the environment. Clearly a more detailed look at semantic mapping is worth the study, because through semantic information we may expect to create more natural ways for robots to interact with humans and its environments.
Semantic mapping could deal with dierent sensor data inputs and output
several dierent representations. Cameras could be employed to construct a
map representation based in clusters of images representing dierent rooms [
In this paper we focus exactly on the problem of laser data classication, using a combination of logic and probability to represent information extracted from sensor data. At the moment, we provide only probabilistic reasoning in our model while logic elements are used to describe the scenario and to obtain an ontology that could be explored in future applications. We chose to model this problem in a probabilistic description logic called crALC, as it seems to provide a reasonable balance between exibility and computational cost, to be explored in further developments. The next section briey describes the probabilistic description logic crALC. In Section 3, semantic mapping is discussed. Experiments are detailed in Section 4, followed by our conclusions. 2
A probabilistic description logic, called Credal ALC (crALC), has been
proposed recently [
The vocabulary of crALC contains individuals, concepts, and roles.
Concepts and roles are combined to form new concepts using a set of constructors
from ALC [
P (CjD) 2 [ 1; 2]; where D is a concept and C is a concept name. The semantics of such a probabilistic inclusion is, informally:
8x : P (C(x)jD(x)) 2 [ 1; 2]; where it is understood that probabilities are over the set of all interpretation mappings I for a domain D. If D is the concept > then we write P (C) 2 [ 1; 2]. Probabilistic inclusions are required to only have concept names in their conditioned concept (that is, inclusions such as P (8r:CjD) are not allowed). Yet another type of probabilistic assessement is possible in crALC: for a role r, we can have P (r) 2 [ 1; 2] to be made for roles, with semantics:
8x; y : P (r(x; y)) 2 [ 1; 2]; where again the probabilities are over the set of all interpretation mappings for a given domain.
Every ontology is assumed acyclic; that is, a concept does not use itself. If we write down an ontology as a directed graph where each node is a concept or role, and arcs go from concepts that are directly used to concepts that directly use them, we obtain that this graph must be acyclic. We refer to such a graph as an ontology graph. For instance, consider concepts A, B, C and the role r. C is a concept inclusion dened by C A u 9r:B. In Figure 1.a we have the ontology graph for this example. Note that exists a node for general role r (x; y) and another for the instantiation with concept B (x), 9r:B (x). Concept inclusion C (x) is composed by A (x) and 9r:B (x). (1) (2) a)
b)
In short, the sentences written in the underlying description logic (with added
probabilistic features) induce directed dependencies between instantiations of
concepts. Under some additional restrictions (unique-names assumption, known
and nite domain), any ontology expressed in crALC can be grounded into a
Bayesian network, possibly with attached probability intervals [
We have used crALC previously to model some aspects of robotic semantic
mapping. In [
The main limitation of that approach was that crALC models areas of the environment with relation to full objects detected by a image processing algorithm - inference does not start from sensor data itself. In our previous work, sensor data consisted of images that were processed by SIFT algorithm to detect objects whose signatures were trained previously.
But real robotic tasks must deal directly with uncertain sensor data. To do so, we wish to explore the exibility and relatively low cost of crALC; however, we do face some challenges to do so. In crALC we face a diculty because the language models concepts (set of individuals) and a hierarchy over them, and not relations between individuals. There is no direct way to include a probabilistic dependency between two arbitrary constants or individuals. Some description logic languages that accepts nominals, allow us to specify individuals, like ’Brazil’ and ’France’. But in semantic mapping domain it is impossible to consider in advance all the constants in the environment (all points, lines or planes that may exist).
The solution to this problem came from ideas presented in [
The scenario of interest is to take a bidimensional metric map, constructed
using a SLAM algorithm, based on distances from a laser sensor, and to
classicate each segment of the map in door or wall segments. Segments are extracted
from laser data points following [
The trivial way to do that is to consider the length of each segment: doors tend to be of the same size, and walls have very variable lengths. But to make a robust classication, we need to consider further features of the segments. For instance, we should include dependences related to spatial relationships: points or line segments produced by laser sensor that are near one from another likely has the same classication.
To illustrate the importance of some features in the classication results, Table 1 lists the percentage of correct classication in ve dierent environments, using only Length, Length+Neighbours, and all features together. As representative features are added (for instance spatial relationships), results are improved.
Some of the spatial features used by [
Figure 2 depicts a Bayesian network constructed around two segments near each other and aligned along a line. Dashed line separates variables belonging to each of the segments. White nodes represents hidden variables; gray and black nodes represent observable variables; black nodes are continuous observable variables that must be discretized and gray nodes are discrete. Each segment is represented by SegType variable. Each has the Length, Depth, SingleAligned and SharpTurn properties. The relationships Neighbours, Consecutive and Aligned appears between each possible pair of segments. Beyond these properties and relationships, each segment could be attached to a line composed of aligned segments of the same type. In the scenario, only Wall objects could align to form a corridor. Each segment or aggregate of segments are represented by a discrete variable that contains its type (in the case of gure is LineType ). StarLine, EndLine, PreviousAligned, NextAligned and PartOf characterize the properties of a segment inside a line.
This model, once implemented in crALC, generates a large Bayesian network including all line segments extracted from the laser sensor, and considering all possible relationships between each two segments whose proximity is below some threshold. Classication is done through probabilistic inference in the graph using a MAP-based algorithm to promote collective classication. Recall that in collective classication, the class of each segment is decided based on the class of its neighbours.
An inherent problem in spatial mapping is the size of indoor environments. As each wall could be formed by a dozen line segments, the number of constants to be considered, and consequently the number of spatial relations to put in the model, are prohibitive. In our experiments, we have decided to partition the dataset in smaller sets, so we could handle the problem with the tools available. Figure 3 shows a corridor extracted from a map. The corridor is formed by a set of segments that must be classicated in doors, walls and others. The experiments consist of teleoperation of a robot with a laser sensor through an indoor environment. As the robot navigates, laser readings and odometry are collected to be processed later, so as to produce a metric map. Any standard algorithm could be used to produce a consistent map. Basically, it is necessary to transform relative measures, obtained as the robot traverses the environment, into a global coordinate system, by dealing with uncertainty measures of the laser and the robot position. It is important to have line segments formed by laser points adequately positioned in the world, because crALC does not deal with uncertainty regarding spatial coordinates.
Although we collect some data with our own robot (Figure 4), and tested our model with it to determine the parameters, we have decided to report results for a dataset available online in the Radish repository, as other works that approached that same problem, using instead RMN and MLN models, used that dataset.
A restriction found in probabilistic models that incorporates logic elements is the type of random variables that are allowed. Often a continuous random variable for the length of the segment constructed from laser points must be discretized in a nite set of possible lengths. In our model, it was necessary to turn some numerical quantities into discrete values, as with variable Length. We considered six dierent values of lengths for doors and walls, based on our observed data.
The values for our conditional probability tables (the parameters of our model), were determined experimentally using our own experience in this kind of problem. These values are listed in Table 3.
Inferences were performed using the package SamIam (available at the address http://reasoning.cs.ucla.edu/samiam/ ). We selected MAP-based explanations generated by an approximate algorithm. Through MAP, we produced collective classication, and decided on each line segment label considering the labels of its neighbours.
Table 4 shows results obtained by MAP inference in a scenario with 70 line segments. In each column represents a range (i.e., 1-10 or 11-20) in the line segments considered. Rows indicate an exact line segment inside the range of the respective column. Observing the results, we have around of 75% accuracy, considering only Length, and Neighboor and Aligned features. It is hard to make a quantitative comparison between our results with Limketkai’s RMN and Wang’s MLN, because the features used in their experiments are not clearly given; nevertheless, qualitatively, results with crALC are similar to the ones obtained with their probabilistic logic models. This article proposes semantic mapping techniques based on the classication of line segments from a metric map into Doors, W alls, or Others elements, using crALC as a representation language. Metric maps are constructed by a standard SLAM algorithm, so as to obtain a precise spatial positioning of each line segment and then to determine features. To do so, we used constants formed by the combination of two simple constants. With these new constants, we included features of neighborhoods and properties of alignments.
We chose a probabilistic description logic due to its compact encoding of the needed knowledge; as a result less parameters must be specied. Collective classication proceeds as inference over an instantiated probabilistic graph using approximate reasoning; all labels are decided together in a single run.
Preliminary results obtained with crALC show that it can handle classication of robotic sensor data. The next step is to further extend this labeling to create an automatic topological map starting for the labels of the metric map, and also to use the same technique to create 3d maps. Besides that, we are trying to introduce DL reasoning in the model through extension of ALC to some description logic that accepts spatial reasoning.