A topological navigation system for indoor environments based on perception events

Abstract

The aim of the work presented in this article is to develop a navigation system that allows a mobile robot to move autonomously in an indoor environment using perceptions of multiple events. A topological navigation system based on events that imitates human navigation using sensorimotor abilities and sensorial events is presented. The increasing interest in building autonomous mobile systems makes the detection and recognition of perceptions a crucial task. The system proposed can be considered a perceptive navigation system as the navigation process is based on perception and recognition of natural and artificial landmarks, among others. The innovation of this work resides in the use of an integration interface to handle multiple events concurrently, leading to a more complete and advanced navigation system. The developed architecture enhances the integration of new elements due to its modularity and the decoupling between modules. Finally, experiments have been carried out in several mobile robots, and their results show the feasibility of the navigation system proposed and the effectiveness of the sensorial data integration managed as events.

Introduction

Navigation has been a main field of study in mobile robotics since its beginning and it is still a challenge. Navigation and mobility have been fundamental in animal development, especially in humans ¹ ; from bees and ants localization behaviours, to birds migration and humans daily life translations, animals navigation complexity is remarkable. In the case of humans, navigation is not only determined by physiological needs, it depends on several complex abstraction levels. ² In this work, a robot is provided with navigation and perception capabilities similar to the ones of humans from a topological approach. Topological representations of the environment ³ consist of the identification of the significant elements configuring the environment and the translations connecting these elements.

Navigation is a very wide research field due to the implication of different mechanisms and technologies. ⁴ It can be addressed by the mechanical imitation of human or animal navigation (as humanoid robots), ⁵ by the imitation of human or animal behaviours (e.g. navigation combined with interaction) ⁶ or by the combination of both imitation methods. ⁷ This work is focused on approaching topological navigation ^8,9 from the behavioural point of view.

Referring to a topological perceptive navigation system, different types of perceptions have to be taken into account in order to manage navigation as a multiple event integrated system. The main perceptions used are based on natural and artificial landmarks. Natural landmark navigation consists in detecting the natural objects of an environment, while artificial landmarks require a modification of the environment, although they enable the abstraction of the object’s meaning. Taking this background into account, the main objective of this work is to provide a mobile robot with the capabilities required in order to navigate autonomously through an indoor environment using mainly topological representations, being able to detect different kinds of perceptions from the environment and associate this information with events to drive its navigation.

Previous works have focused on the combination of navigation, vision and event strategies. Some works tackle topological navigation using only artificial landmarks, ¹⁰ while others use only natural landmarks. ^11,12 Other works have settled the first steps towards advanced topological navigation, by involving specific natural and artificial landmark detection. ¹³ More advanced works refer to event-driven navigation to characterize obstacles ^14,15 This work is a stand-alone regarding the integration of artificial landmarks and object detection, with simulated perceptions and odometrical perceptions to guide the navigation. All this information is characterized as events and obstacles so the robot can topologically navigate and define the environment.

Topological navigation system

There are basically two types of topological representations ¹⁶ of the environment: topological representations based on movements ¹⁷ and topological representations based on geometrical maps. ¹⁸ The main difference between these two conceptions is the spatial relation amid the real world and the representation created. Regarding topological maps based on geometry, there is a mandatory relation between the environment and the representation (it is compulsory that every topological node is associated with a geometrical coordinate). Whereas, in topological representations based on movements, this exact relation is not necessary. The developed topological navigation model is categorized as a topological representation based on movements, so the relation between nodes (In this work, nodes are associated with sensorial events, while arches or edges with sensorimotor abilities.) has no geometrical meaning, being a qualitative relation instead of a quantitative.

The global navigation system is formed by different modules: a perception interface, an event manager, a planner and a navigator, as shown in Figure 1. The distribution shown illustrates how the perception interface is uncoupled from the rest of the system and the topological system is generic and invariant. The developed structure enhances the robustness and versatility of the system and simplifies the addition of new event implementations.

Figure 1.

General topological design and modules.

The perception interface is in charge of receiving the sensorial information from the exteroceptive events and translating it into a general structure. The event manager deals with the processing of every event received and determines when a desired event has been reached. The planner determines the path to get to the target using a Dijkstra algorithm. The planner has an element called map that conforms the topological map at the beginning of each planification stage. Finally, the navigator performs the required behaviours until the robot gets to the target. This system is provided with several user interfaces (graphical interface and voice interface) in order to enhance human–robot interaction and user comfortability during the commanding stage.

The main process of this system is represented in Figure 2. First, the planner acquires the corresponding topological map from the environment, as environment exploration is not already available. Afterwards, the user or a higher level decision entity indicates which goal is to be reached, so the path to follow is calculated. Then, the navigator executes the corresponding ability, while the perception system is searching for new events in the environment. As a result, different nodes are perceived and reached. When the final target is reached, the navigation execution is concluded successfully and the robot waits for new commands.

Figure 2.

General representation of the system’s behaviour.

Topological software scheme

In order to guarantee hardware and software integration, the proposed navigation system is developed under robot operation system (ROS), ¹⁹ using C++ and Arduino programming languages, combined with several specific libraries. The detailed software scheme of the system is shown in Figure 3; it is modularized according to the functionality of each ROS node. It includes the topological navigation modules, the sensorial event modules, the basic motor and camera configuration modules and multiple interfaces to enhance the interaction with the system.

Figure 3.

Detailed diagram of the topological model proposed and module’s communications.

Topological graph

The topological graph ²⁰ is known and it is given to the system as an a priori text file. In Figure 4, the map text file structure and its graphical interpretation are shown. As it is a topological representation based on movements, the position of the nodes in the graph is not necessarily linked to the position of reference elements in the environment.

Figure 4.

Topological map file example and graphical representation.

From this text file, the system can obtain all the information required for navigation. Nodes are identified with their numbers and they are associated with the corresponding event type (odometry, marker, closet, etc.), while arches are associated with the ability they represent (GP, go to point; R, turn; etc.).

Topological planification and navigation

Topological navigation behaviours are determined mainly by the path-planning and navigation (meaning strict motor abilities execution) strategies. ²¹ The system proposed in this article is considered to be perceptive navigation because both path-planning and navigation are strictly related to perceptions from the environment. The different nodes that conform the path are associated with the topological place where the robot perceives a sensorial stimulus or where the perceived stimulus is located. In addition, while navigating, the behaviour of the robot is subjugated to the real-time perception of the environment.

The planner is the path-planning system in charge of finding the topological route that the robot has to follow. In order to plan a trajectory, a graph path-planning algorithm has to be used: Dijkstra algorithm was chosen. ²² Dijkstra algorithm is designed in order to obtain the shortest path between nodes in a graph. Given an initial node, it evaluates adjacent nodes, giving priority to the ones with shorter distance, and iterates until the goal node is reached or every connection between nodes has been explored. The topological planification algorithm implemented is a modified Dijkstra, in which the cost of a translation can be varied. It can be used as feedback of previous executions, such as a personality factor. ²³

The navigator is the navigation system, ²⁴ and it is in charge of performing the path and reaching the goal node analysing events and abilities. An ability is the order the robot has to execute to reach coming nodes, and it is intrinsically related to motor control. An event is the sign indicating the robot has reached a node, through sensorial information. A multiple behaviour system is formed by several kinds of abilities and events. Several strategies and abilities were developed in order to perform navigation behaviours, but the system is open to other modules and the inclusion of new strategies. The abilities implemented are go to point, turn, contour following and go to object. The navigation system is complemented with a reactive obstacle avoidance module to guarantee safe operation.

The designed navigator receives the path as a subgraph of the original map. It gets the ability of the first transition and executes it until the event corresponding to the second node is received. It iterates this functionality until the event corresponding to the last node of the path is received.

In Figure 5, the flow chart for navigation is shown. First, the system waits until it receives a valid target from the user. Once the goal is received, the planner calculates the path and asks the navigator to perform it. The system is continuously checking whether the path is free of obstacles before moving. If there is an obstacle in the way, the robot will check whether it is avoidable or not, meaning that the path is blocked. If it is blocked, the system will ask the planner for an alternative path, if it exists. Whereas, if the obstacle is avoidable, the robot will avoid it and continue with the execution. If the path is free or the robot has overtaken an obstacle, in order to start navigation, the system will check whether the robot is located in a known node. In case it is not, the robot will move towards one. While the robot navigates, if it detects the desired perceptive event, it marks that node as reached. If that node is the goal node, the execution will end successfully; if it is not, the system will refresh the next node to reach. If the desired event is not detected, the robot will execute the corresponding ability until it is detected. Whereas, if the robot detects the event but it is not located in the desired position, it will execute ability go to object to reach the node’s position.

Figure 5.

Topological navigation flow chart.

Perception interface and event manager

The topological system is designed to work with multiple exteroceptive ^25,26 and proprioceptive events, handling them simultaneously through a perception interface and an event manager. This innovative concept is based on human perception when navigating, rotating the system with a multi-sensorial navigation strategy. The structure of this system is shown in Figure 6, where exteroceptive events are associated with the perception interface and proprioceptive events with the event manager.

Figure 6.

Perception interface and event manager modules distribution.

The perception interface is decoupled from the system translating the specific information of each perception module to a general structure which interacts with the other modules of the topological system. Perception modules are mainly based on vision, ROS depth images and RGB images from the environment and used for event characterization leading to a multiple event interface.

The function of the event manager is to centralize every process involving event communication between modules. This module receives information from the perception interface, the odometry and the intrinsic state of the robot and manages the concurrent communication and execution of the whole system. The module publishes the required information about the events received and determines when an event has been reached.

Multiple event integration

Multiple event integration consists in perceptions of multiple sources that are brought together in a system disregarding its source type. In this way, it is not necessary for the navigation system to process each perception type individually. This integration offers many conceptual and computational advantages as events are totally abstracted from their source type. This system enables the potential integration of numerous types of events through the same interface.

This system integrates the resulting perceptions from several processing modules. They are compared with the information from the desired events of the path to follow; so perceptions are the main elements for the guidance of the navigation. The more events and perceptions are integrated in the system, the more accurate and intelligent the navigation will be.

As it is a real-time system, the perceived information is available and continuously published by each event module. The system integrates this information and compares it with the specific event associated with the node to reach. As a result, undesired perceptions are discarded and the system only processes the perceptions that correspond to the actual state of the robot. Through this method, concurrency problems are avoided and there is no need to set a prioritization. If the robot is expecting to reach a chair and the perception modules simultaneously detect a chair and an artificial landmark, the artificial landmark will be discarded, whereas the chair will be processed. The integration of events, as shown in Figure 7, handles artificial landmarks, detection of objects, odometry and external events simulated by the user:

Figure 7.

Multiple event integration modules and perception elements.

• Perception of artificial landmarks, sourced by ArToolKit. It is in charge of the detection of artificial markers that are added to the environment and the system detects them as the event associated with them. ArToolKit is a software library for augmented reality that tracks in real time the position of markers to add virtual reality to them. Each marker placed in the environment has a different pattern which is associated with an identifier; in higher abstraction levels, these identifiers can be related to different concepts. In this work, the marker is identified and stored within its position.

• Object detection module in charge of natural landmark perception. ²⁷ Natural landmarks vision is related to the detection of objects and elements that are naturally in a room. This module uses computer vision techniques in order to classify several objects commonly found in human-usual environments, without introducing any modification to them. Real-time images are captured from the environment using the camera installed in the robot; they are processed extracting the main features of the objects. These features are introduced in a classifier to detect the corresponding object. The classifier used in this case is a support vector machine. Once the object is detected, it is located relatively to the robot in order to know its approximate position.

• Odometrical positions, absolute and relative coordinates to different places are handled as an internal event source, for example, in order to go back to the starting position.

• Simulated perception, a module designed to generate external perceptions from a keyboard, voice or other simulation environments, allowing the user to interact with the robot. Interaction is managed regarding command of targets and initial position or even stop the robot in case of emergency.

Experimental results

Work environment and previous perception results

Experiments were made in several indoor environments, all of them settled in a laboratory, using two robots: mob-E, a developed robotic platform, ²⁸ and a Turtlebot 2 platform, as shown in Figure 8. Both robots were provided with an Asus Xtion sensor and managed through the same software using ROS framework. Thanks to the modularized development of the system, it was possible to integrate it in both robots without the need to change anything.

Figure 8.

Robotic platforms tested.

Individual perception results of the different modules are presented as background of the global navigation results. Both natural and artificial landmark detection results are briefly explained through the analysis of their confusion matrix. In a confusion matrix, true and false classification rates are indicated. From this information, several measures can be obtained, such as accuracy, misclassification rate, sensitivity and specificity. In Table 1, results for several markers that are associated with their specific identifier are shown. In addition, in Table 2, results for the detectable objects are shown.

Table 1.

Evaluation of the artificial landmark detection system, ArToolKit.

Evaluations	0	1	2	3	4
Model accuracy	91.2%	90.4%	80.8%	96%	95.2%
Misclassification rate	8.8%	9.6%	19.2%	4%	4.8%
True positive rate = sensibility	72%	56%	80%	80%	80%
True negative rate = specificity	96%	99%	85.26%	100%	99%

Table 2.

Evaluation of the object detection system.

Evaluations	Closets	Chairs	Screens
Model accuracy	81.97%	76.56%	60.13%
Misclassification rate	18.03%	23.44%	39.87%
True positive rate = sensibility	81.08%	100.00%	29.63%
True negative rate = specificity	82.81%	53.13%	90.63%

Overall results for artificial landmark detection are more satisfactory than natural objects detection, producing accuracy values between 80% and 100%. This is not surprising because artificial markers are specially intended to be detected and they consist of black patterns on top of white background. Regarding object detection, best accuracy is achieved for closet object (81.97%), followed by chair (76.56%, and a true positive rate of 100%) and finally screens (60.13%).

Testing methodology

The following experiments regarding navigation were developed and their results are presented: artificial landmark topological navigation, topological navigation with object detection and combined events topological navigation. Both artificial landmark and combined events navigation experiments were performed using mob-E, while navigation with object detection was performed using Turtlebot platform. These experiments offer a general view of the whole navigation process including perception and path-planning, showing its real application on a robot and its results.

In order to test the different experiments, the odometrical measurements computed by the robot are compared with the actual movement observed and with the commanded trajectory. Results are also provided with the perceptions at each situation.

Artificial landmark topological navigation experiment

In this experiment, events are associated with artificial landmarks and movement is generated using contour following ability until the marker is seen (when the specific locomotion module to reach an object is enabled, go to object). This module uses as goal position, the one corresponding to the detected marker. The scenario developed for this experiment is shown in Figure 9.

Figure 9.

Scenario for the artificial landmark topological experiment.

The robot is commanded to translate between two nodes following a wall, and this path is shown in Figure 10 (right) as the geometrical interpretation of the topological path. The result is shown in Figure 10 (left), a graph obtained from the odometrical position computed during the experiment. In this graph, the position of the marker is shown in red.

Figure 10.

Geometrical interpretation of the path and result.

First, the robot moves until it detects a wall in front of it and follows it until the desired marker is detected. Once the robot perceives the marker, it moves towards a point perpendicular to it separated by a fixed distance. Reaching that position, the execution is finished and the robot waits for new commands.

The obtained path corresponds with the path estimated a priori although some differences can be observed. Against the straight lines of the representation, the execution is curved due to the continuous checking of the contour to follow. When the robot perceives the marker, it moves towards that position, obtaining a more straight trajectory until the desired position is reached. The distance travelled during the execution of this experiment was 1.37 m and it took approximately 40 s.

Topological navigation experiment with object detection

In this experiment, the information registered by the camera is processed and several common objects are detected. An example of the preprocessing, segmentation and identification of objects is shown in Figure 11, and more detailed explanations of this process are found in the study by Hernandez et al. ²⁷ This experiment requires the real-time functioning of navigation and computer vision systems together in the same robot. The scenario for the experiment and the Turtlebot robot are shown in Figure 12 (left).

Figure 11.

Example of object preprocessing and identification.

Figure 12.

Geometrical interpretation of the path.

The navigation system receives generic information of the object detected; in case, the data corresponds to the desired one for the event, the robot will move towards that object. In this case, the robot will perform the path shown in Figure 12 (right) using the ability turn. The first event to reach is a chair; when the chair is detected, the robot will move towards it using the ability go to object. The second event to reach is a closet; when reached, the robot will stop. The result for this experiment is shown as the combination of the position of the robot and the recognition of objects, as shown in Figure 13.

Figure 13.

Result for natural landmark experiment.

In Figure 13(a), the initial position of the robot in order to execute the trajectory 0-1-2 and the disposition of the environment are shown. Figure 13(b) shows how the robot turns facing a chair. As it is the object to reach, the information from the object detection module is sent to the navigator and sets its position as a goal point executing ability go to object. Go to object ability uses the angle and distance from the perceived object. In Figure 13(c), the robot has reached middle goal, chair, which is placed a fixed distance away from it in its perpendicular direction. Once this goal is reached, the target position is refreshed to reach node 2, closet. Figure 13(d) shows how the robot has turned facing a closet and it has been detected setting its position as a goal point, executing ability go to object. Finally, in Figure 13(e), the robot has moved towards the closet executing ability go to object. The robot reaches successfully the desired position and as it is the navigation goal it stops. The distance travelled in this experiment was 2.29 m, executed in 50 s.

Combined events topological navigation experiment

In this experiment, several translations between nodes are implemented with different types of sensorial events and abilities. Moreover, extrasensorial events are placed in the environment showing how the robot reacts only in the case the desired event is detected. The scenario developed for this experiment is shown in Figure 14 (left).

Figure 14.

Scenario for the combined events topological experiment.

The path the robot executes is shown in Figure 14 (right). The robot is commanded to move from node 0 to node 3; in order to accomplish this, it has to execute 0-1-2-3. Node 1 corresponds to an odometrical event, while nodes 2 and 3 correspond to visual events. To move from node 0 to node 1, the robot will execute ability go to point and to move from node 1 to node 2 and node 3, the robot will execute ability turn until it detects the event, when it will execute ability go to object until a precise position related to the marker is obtained.

The result of this experiment is shown in Figure 15, as the odometrical position computed during the execution of the experiment; second, a succession of pictures is shown, in which it is possible to observe how the robot moved through the environment reaching the desired events. Both results are related through the green arrows represented in the odometrical graph, each arrow indicates an instant of the trajectory shown in the pictures bellow.

Figure 15.

Odometry measurements obtained with the experiment.

Regarding the odometry graph, it is noticeable how the trajectory followed corresponds with the schematic path predicted and how the robot reached the position desired in relation to the markers (in red).

In Figure 16, the succession of images illustrating the performance is shown. Comparing the schematic trajectory estimated, the odometrical graph and the succession of images, it is possible to conclude that the experiment was executed satisfactorily. The distance travelled by the robot was 2.02 m, and it took 53 s.

Figure 16.

Global experiment execution result.

Execution time and distances have been taken into account in order to validate the results obtained, giving an average speed of 0.04 m/s. This speed was calculated acknowledging that the paths imply multiple turns which cannot be represented with the distance travelled. In addition, experiments took place in medium-size environments with obstacles and several objects to detect, so travelling velocities must be reduced. Compared to metric navigation works, in the research by Jang et al.,¹⁰ they set a fixed translation velocity 0.1 m/s. Considering that in the experiments developed in our work, part of the time the robot is rotating without translating, no linear velocity increment and the difference between both results is reasonable (0.04 m/s and 0.1 m/s). Compared to other topological works, in the study by Akai and Ozaki, ²⁹ the robot was intended to move long distances in outdoor environments, obtaining in their experiments an approximate speed of 0.032 m/s. The results obtained validate the feasibility of the topological system and demonstrate the functioning of the integration process.

Conclusions

The aim of this article was to provide a mobile robot with the capabilities required in order to navigate autonomously through an indoor environment using mainly topological representations, being able to detect different kinds of perceptions from the environment and associate this information with events to drive its navigation. The main innovation of this article is the integration and management of multiple perceptions and events simultaneously. The advantages of this work are highlighted in the following milestones:

Multiple events from different sources are handled and integrated in the same system successfully managing the data collection and processing.

The system is multidisciplinary regarding the inputs admitted and the outputs offered: it is able to work with different types of perception and it performs different behaviours to reach the goal. In addition, it offers multidisciplinary controllability, thanks to its several user interfaces.

The modular and detached design of the system enhances its versatility, robustness and the implementation of new functionalities.

The developed topological system is able to plan successful trajectories over a given map and satisfactorily navigate through indoor environments following the path planned and reaching the proposed goal without colliding to obstacles. In case the goal is not reachable, the system is able to replan a new trajectory.

The system is robust enough to work with different robotic platforms, independently of their low-level controllers.

The future line of this work is the integration of geometric, topological and semantic levels with multisensorial events allowing each other to complete the information of every level. We would also like to improve the detection algorithms as well as the locomotive abilities and we would like to include an explorer stage previous to navigation. The system proposed establishes a robotic implementation that allows the first implementations regarding robot navigation systems, especially topological, and opens new possibilities to research in the mobile robots navigation field.