In this paper, we present an approach to human navigation and mapping using semantic techniques. The main idea is to enhance a map produced by a mapping algorithm with additional contextual information. The key advantage of our approach is the presence of a human in the loop, that can provide reliable semantic information. Several simulations of the proposed algorithm were conducted using a simulation framework developed particularly for this research.
Human navigation attracts some attention over the last decade. A number of works addressed this problem by applying various techniques from different research fields such as Mobile Robotics and Artificial Intelligence. In this work we focus on the application of semantic techniques in human navigation and mapping.
A number of works were using semantic techniques in various forms and have
achieved significant results. For instance, the authors of [
The above mentioned works focus on mobile robots mapping and
navigation, whereas [
In this paper, we propose an approach which tends to solve the correspondence (also known as loop-closing) problem in mapping process applying semantic techniques. Our approach uses graph structure as representation of places and spatial relations between them. By these means, it can be identified as topological mapping with the use of semantic techniques. The key advantage of our approach is the presence of a human in the loop, that can provide semantic information in reliable way. In order to test our approach, a naive algorithm for topological map-building has been adopted: this allows us to measure the impact of semantic information on loop closure even in absence of complex SLAM optimization techniques. 2
Semantic Mapping In our approach we model a world as a graph G. This graph contains nodes which represent places of the environment that the agent explores. More formally G = (N, E), where N denotes a set of nodes N = { n1, n2, n3 . . . ni }, and E is a set of directed edges that signify a path traveled by an agent and a linkage between semantic objects on a map. Each node ni carries supplementary information about its position Xi in a Cartesian coordinate system, and a set of labels Li denoting objects or environmental features discovered in this place. For instance, the label may include the typology of relevant buildings that can be found in the corresponding place (e.g. Church, Hospital, Shop). As the reader can imagine, one purpose of such structure is that the information labeling nodes might be used to minimize the possible errors in localization of a person on a map, by recognition of already visited or known objects, buildings and other environmental features.
Knowledge base The presence of a human in the loop cannot guarantee an absolute precision in semantic information. In different time steps, the human may describe the same place at different levels of abstraction, she may use synonyms for the same environmental feature or even another feature. Some examples are "shop", "bakery ", "traffic lights " and so on. At the first visit, the human may detect a "shop", at the second visit to the same place she may recognize a "bakery " (subclass of shop), at the third visit a "traffic lights " (a different feature in the same place). To handle ambiguities and hierarchical relationships between semantic objects, we suggest to use ontology techniques, modeling an environment as a hierarchy of environmental features connected to each other depending on the topology of the environment. We use the structure of the ontology to define a metrics that measures "how far" two labels are in a semantic sense comparing the classes that these labels belong to. The rationale is that the farther two classes are in the ontology tree, the less likely it is that the two labels are meant to represent the same environmental features in the real-world.
Localization algorithm The approach proposed in this article may be adapted to different starte-of-the-art SLAM approach: however, for sake of simplicity, here we suggest an algorithm that is based on Markov Localization for detecting the most probable node in which the person is located, and simply add a new node to the map whenever the probability of being in a pre-existing node is below a given threshold. As usual in Markov Localization we estimate the pose of the agent in two steps: action prediction and observation update.
In the first step, the probability distribution over the nodes at time t is updated by applying the control AT starting from each node Nt 1. Notice that, as the agent moves in the real world, the path is updated using dead reckoning; however, the probability distribution is updated only when the agent thinks to have reached a new node, i.e., the agent recognizes environmental features that are worth being recorded and tells the system what she can see in its current location.
Nt 1 P (Nt = nijO0:T ; A1:T ) = X P (Nt = nijNt 1; AT ) P (Nt 1jO0:T 1; A1:T 1) (1)
The second step is an update phase, when we obtain posterior probability (observation update vector), incorporating measurement acquired by the agent according to the observation model. At this stage, the probability of the observation at time t does not depend on previously acquired observations. We use our ontology as the reference for observation model.
P (Nt = nijO0:T ; A1:T ) = 0P (OT jNt = ni) P (Nt = nijO0:T 1; A1:T ) (2)
From a practical point of view, if the pre-existing and observed labels belong to the same class in the ontology (e.g., Shop-Shop), the probability of the observation is equal to 1.0. If the two labels have a direct parent-child relationship (e.g., Supermarket-Shop), the probability of the observation is 0.5. If the two labels have a sibling relationship (e.g., Supermarket-Bakery ) the probability of the observation is 0.25. In those cases when the two labels do not have any relationship the probability is relatively small value that leaves a minimum probability of observation, which we set to 0.05.
Notice also that whenever a new label is observed in a node ni, the new label is added to the set Li, thus increasing the probability of a matching during future observations. 3
In order to assess the difference between using and not using semantic information during the mapping process, we have performed over 140 experimental simulations in our specialized simulation framework. We have created 18 artificial maps simulating a real world. These maps may be classified according to their difficulty level from simple to complex on the basis of their topology. We consider those maps containing many places situated close to each other as complex. Vice versa, simple map’s nodes are rather distant from each other.
The agent explores the environment moving in a Manhattan-like way, horizontally and vertically. We assume that the agent has sensors for measuring odometry, which return its heading and path with a given error. The errors in measurements are generated randomly, basing on the angle deviation (e.g. from -3.0 to 3.0 degrees). We repeated the experiments with different error distributions, with a 0 mean and a standard deviation ranging from 1 to 7. The error is accumulated during the entire process, thus making localization more complicated. Once the agent reaches a place, it updates the system with a label describing it. We assume that the user should provide the system with verbal information through a microphone, however for the simulation process we have implemented an algorithm which randomly generates the labels from a prepared list that contains the labels for all classes that we have in our knowledge base. Figure 1 shows that our algorithm recognizes previously visited places (orange circle) also in those cases when a node has multiple environmental features belonging to the different classes. In the current example, the node 4 contained a set of labels Pizzeria, Pizzeria, Clinic. The new label Pizzeria is equal to at least one label in the set, thus the observation probability in this case is equal to 1.0.
In order to evaluate the performance of the map building algorithm in presence of semantic information we use the number of created nodes. We assume that, if all loops are correctly closed, the number of nodes in the map shall be equal to the nodes in the environment after the whole environment has been explored. In presence of errors, the map will likely contain a higher number of nodes, since the algorithm adds a new node to the map whenever a node is not recognized as an already visited node. The results of the simulations for each type of maps are presented in the Table cFlaigss.e1s. The labels belonging to the multiple 1. Each cell of the Table reports the ratio between the number of nodes created with or without Semantic information divided by the actual number of nodes in the map after a number S of "node-to-node" navigation steps: a lower ratio means better performance. Notice that this ratio may increase by increasing the number of navigation steps: then the number S is set to a value which is proportional to the number of nodes in the map, i.e., if a map has N nodes the number of steps will be 5 N . 4
In this extended abstract, we briefly presented a method for enhancing the process of topological mapping with semantic information. The results obtained from the simulation process show that the presence of semantic information allows for improving the number of loops that are correctly closed during navigation. Thus, we can state that the implementation of semantic information can significantly improve the quality of localization and mapping process.