Recent successes have raised expectations concerning the behavior of mobile robots in dynamic environments [21]. State-of-the-art applications construct precise spatial maps of static environments; however, autonomous robots need more than accurate spatial information when dealing with people or objects that display dynamic change. Semantic mapping focuses on the representation of an hierarchy of general objects in the environment, with their individual properties and inter-relationships. Broadly speaking, semantic maps must compactly encode rich information in a scalable manner.
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 [24].
Other proposals use 3D laser sensors to produce point cloud representations, that allows for object recognition [22], environment segmentation in oor and walls [1], and even the construction of a real map [15]. One interesting application relies in laser sensors that obtains horizontal slices at a xed height of the environment to create bidimensional spatial maps. Semantic mapping in this context envolves the classication of line segments from already constructed 2D maps of indoor environments. This scenario was rstly proposed by Limketkai et al. [12] and latter was also approached by Wang and Domingos [19]. It is a scenario where one can explore dierent kinds of dependencies between the data, including spatial relationships and appearance. Both previous cited work employed models that combines rst-order or relational logic with probabilities to produce line segments classication. The use of probabilities is justied because there is considerable uncertainty in associating dependencies with the possible classes of line segments, both due to the uncertain process of creating line segments from laser points and to changes in sensed objects [20]. And rst-order logic is an expressive language that allows for a rich representation of complex relationships between dierent object in a compact way.
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.
A probabilistic description logic, called Credal ALC (crALC), has been proposed recently [4,5,16], in a wave of related eorts [14]. In fact, the literature brings a variety of probabilistic description logics [7,9,10,11,13,3,18]; crALC is based on the popular ALC logic, adopts an interpretation-based semantics and resorts to the theory of Bayesian networks to allow for judgements of stochastic independence and to obtain inference algorithms.
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 [17]: conjunction (C D), disjunction (C D), negation (¬C ), existential restriction (∃r.C ) and value restriction (∀r.C ). A concept inclusion is denoted by C D and a concept denition is denoted by C ≡ D, where C and D are concepts; we assume in both cases that C is a concept name. We then say that C directly uses D; the relation uses is the transitive closure of directly uses. Also, the concept denotes C (¬C) for some concept C. As in ALC, the semantics is given by a domain D, a set of elements, and an interpretation mapping I that assigns an element to an individual, a set of elements to a concept, and a binary relation to a role. An interpretation mapping must also comply with constructs of the language; for instance, the interpretation of concept C D is I(C) ∩ I(D), while the interpretation of concept ∀r.C is {x ∈ D | ∀y : (x, y) ∈ I(r) → y ∈ I(C)}. Additionally, crALC accepts probabilistic inclusions as follows. A probability inclusion reads
where D is a concept and C is a concept name. The semantics of such a probabilistic inclusion is, informally:
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) ∈ [α 1 , α 2 ]. Probabilistic inclusions are required to only have concept names in their conditioned concept (that is, inclusions such as P (∀r.C|D) are not allowed). Yet another type of probabilistic assessement is possible in crALC: for a role r, we can have P (r) ∈ [β 1 , β 2 ] to be made for roles, with semantics: ∀x, y :
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 ∃r.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), ∃r.B (x). Concept inclusion C (x) is composed by A (x) and ∃r.B (x). 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 [4,5,16]. That is, grounding an ontology with a nite and known domain leads to a credal network [6]. In 3 Semantic mapping with crALC
We have used crALC previously to model some aspects of robotic semantic mapping. In [2] we proposed to segment robotic sensor data (odometry, gyro and distance measures) obtained from navigation through an indoor environment, based on the objects found in each dierent area. Rooms and Corridors are examples of possible areas to be found in an indoor environment. Such segmentation of the sensor data provides a scalable way to map larger environments, as each area could be mapped independently: as a result, several smaller areas are mapped and then merged together to construct the map.
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 [19]. The trick is to include in the model, individuals or constants that are created from the combination of two segments; for example, there are two distinct segment lines, a and b. Then, if one is near the other, the constant ab is created (ba could also be created, but is identical to the rst one). One way to specify in the model the conditional independences using the description logic language, is to create those kind of constants only when there is some dependency between the constants. Thus, it is not necessary to instatiate all possible combinations of segments. With that modication, it is necessary to dierentiate concepts with primitive constant and concepts with composed constants. We now consider our application in more detail.
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 [8]. We do not propose to classify laser segments in real time as the robot constructs the map and localizes itself. Inferences are done oine, after the map has been obtained.
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 [23] are considered in our model and listed in Table 2. 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. 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.