Thinning-Based Topological Exploration Using Position Possibility of Topological Nodes

A grid map can be efficiently used in navigation, but this type of map requires a large amount of memory in proportion to the size of the environment. As an alternative, a topological map can be used to represent the environment in terms of discrete nodes with edges connecting them. It is usually constructed by Voronoi-like graphs, but in this paper the topological map is built based on the local grid map by using a thinning algorithm. This new approach can easily extract the topological information in real-time and be robustly applicable to the real environment, and this map can be autonomously built by exploration. The position possibility is defined to evaluate the quantitative reliability of the topological map and then a new exploration scheme based on the position possibility is proposed. From the position possibility information, the robot can determine whether or not it needs to visit a specific end node, which node will be the next target and how much of the environment has yet been explored. Various experiments showed that the proposed map-building and exploration methods can accurately build a local topological map in real-time and can guide a robot safely even in a dynamic environment.     

Environment model adaptation for mobile robot exploration

In this work, we propose a methodology to adapt a mobile robot’s environment model during exploration as a means of decreasing the computational complexity associated with information metric evaluation and consequently increasing the speed at which the system is able to plan actions and travel through an unknown region given finite computational resources. Recent advances in exploration compute control actions by optimizing information-theoretic metrics on the robot’s map. These metrics are generally computationally expensive to evaluate, limiting the speed at which a robot is able to explore. To reduce computational cost, we propose keeping two representations of the environment: one full resolution representation for planning and collision checking, and another with a coarse resolution for rapidly evaluating the informativeness of planned actions. To generate the coarse representation, we employ the Principal of Relevant Information from rate distortion theory to compress a robot’s occupancy grid map. We then propose a method for selecting a coarse representation that sacrifices a minimal amount of information about expected future sensor measurements using the Information Bottleneck Method. We outline an adaptive strategy that changes the robot’s environment representation in response to its surroundings to maximize the computational efficiency of exploration. On computationally constrained systems, this reduction in complexity enables planning over longer predictive horizons, leading to faster navigation. We simulate and experimentally evaluate mutual information based exploration through cluttered indoor environments with exploration rates that adapt based on environment complexity leading to an order-of-magnitude increase in the maximum rate of exploration in contrast to non-adaptive techniques given the same finite computational resources.     

Real-time map building and navigation for autonomous robots inunknown environments

An algorithmic solution method is presented for the problem of autonomous robot motion in completely unknown environments. Our approach is based on the alternate execution of two fundamental processes: map building and navigation. In the former, range measures are collected through the robot exteroceptive sensors and processed in order to build a local representation of the surrounding area. This representation is then integrated in the global map so far reconstructed by filtering out insufficient or conflicting information. In the navigation phase, an A*-based planner generates a local path from the current robot position to the goal. Such a path is safe inside the explored area and provides a direction for further exploration. The robot follows the path up to the boundary of the explored area, terminating its motion if unexpected obstacles are encountered. The most peculiar aspects of our method are the use of fuzzy logic for the efficient building and modification of the environment map, and the iterative application of A*, a complete planning algorithm which takes full advantage of local information. Experimental results for a NOMAD 200 mobile robot show the real-time performance of the proposed method, both in static and moderately dynamic environments.     

Making 2D Map of Environments Based upon Routes Scenes

This paper proposes a method for making a map of large scale environment based upon route scenes, assuming that the topological relation of routes at intersections is known. A panoramic representation is used for describing route scenes, and the number of routes connecting at an intersection is assumed to be known. The idea is to decompose a 2D graph into a number of closed loops. By detecting the closed loops and storing the relation among them, we can describe the 2D map based upon route scenes. A robot can obtain a closed loop by taking the same turn (leftmost for example) at every intersection when it moves along routes. According to the information on routes at intersections, the robot can select unmoved routes for finding new closed loops. By fusing new closed loops with found ones, the robot can, further, build the map of environments. The effectiveness of our method are shown by experiment in a real-world environment.     

Multi-Robot Graph Exploration and Map Building with Collision Avoidance: A Decentralized Approach

This paper proposes a decentralized multi-robot graph exploration approach in which each robot takes independent decision for efficient exploration avoiding inter-robot collision without direct communication between them. The information exchange between the robots is possible through the beacons available at visited vertices of the graph. The proposed decentralized technique guarantees completion of exploration of an unknown environment in finite number of edge traversals where graph structure of the environment is incrementally constructed. New condition for declaring completion of exploration is obtained. The paper also proposes a modification in incidence matrix so that it can be used as a data structure for information exchange. The modified incidence matrix after completion represents map of the environment. The proposed technique requires either lesser or equal number of edge traversals compared to the existing strategy for a tree exploration. A predefined constant speed change approach is proposed to address the inter-robot collision avoidance using local sensor on a robot. Simulation results verify the performance of the algorithm on various trees and graphs. Experiments with multiple robots show multi-robot exploration avoiding inter-robot collision.     

Multi-robot olfactory search in structured environments

This paper presents a cooperative distributed approach for searching odor sources in unknown structured environments with multiple mobile robots. While searching and exploring the environment, the robots independently generate on-line local topological maps and by sharing them with each other they construct a global map. The proposed method is a decentralized frontier based algorithm enhanced by a cost/utility evaluation function that considers the odor concentration and airflow at each frontier. Therefore, frontiers with higher probability of containing an odor source will be searched and explored first. The method also improves path planning of the robots for the exploration process by presenting a priority policy. Since there is no global positioning system and each robot has its own coordinate reference system for its localization, this paper uses topological graph matching techniques for map merging. The proposed method was tested in both simulation and real world environments with different number of robots and different scenarios. The search time, exploration time, complexity of the environment and number of double-visited map nodes were investigated in the tests. The experimental results validate the functionality of the method in different configurations.     

THE SPATIAL SEMANTIC HIERARCHY IMPLEMENTED WITH AN OMNIDIRECTIONAL VISION SYSTEM

In this article, we propose a new approach to the map building task: the implementation of the Spatial Semantic Hierarchy (SSH), proposed by B. Kuipers, on a real robot fitted with an omnidirectional camera. The original Kuiper's formulation of the SSH was slightly modified, in order to manage in a more efficient way the knowledge the real robot collects while moving in the environment. The sensory data experienced by the robot are transformed by the different levels of the SSH in order to obtain a compact representation of the environment. This knowledge is stored in the form of a topological map and, eventually, of a metrical map. The aim of this article is to show that a catadioptric omnidirectional camera is a good sensor for the SSH and nicely couples with several elements of the SSH. The panoramic view and rotational invariance of our omnidirectional camera makes the identification and labelling of places a simple matter. A deeper insight is that the tracking and identification of events on an omnidirectional image such as occlusions and alignments can be used for the segmentation of continuous sensory image data into the discrete topological and metric elements of a map. The proposed combination of the SSH and omnidirectional vision provides a powerful general framework for robot maping and offers new insights into the concept of “place.” Some preliminary experiments performed with a real robot in an unmodified office environment are presented.     

基于动态精简式混合地图的移动机器人自主探索

针对未知环境下移动机器人自主探索和地图创建问题,在机器人操作系统的框架下,提出一种基于动态精简式混合地图的移动机器人自主探索方法.首先,提出一种基于几何规则的候选目标点生成方法,用于快速提取当前的前沿目标点;然后,从信息收益和路径成本的角度,引入一种改进的效用函数来评价候选目标点;最后,利用缓存增量式的原理优化拓扑节点,进而构建精简式混合地图.实验结果表明,通过拓扑图构建策略的改进,所提出方法具有良好的导航性能.     

Map evaluation using matched topology graphs

Mapping is an important task for mobile robots. The assessment of the quality of maps in a simple, efficient and automated way is not trivial and an ongoing research topic. Here, a new approach for the evaluation of 2D grid maps is presented. This structure-based method makes use of a topology graph, i.e., a topological representation that includes abstracted local metric information. It is shown how the topology graph is constructed from a Voronoi diagram that is pruned and simplified such that only high level topological information remains to concentrate on larger, topologically distinctive places. Several methods for computing the similarity of vertices in two topology graphs, i.e., for performing a place-recognition, are presented. Based on the similarities, it is shown how subgraph-isomorphisms can be efficiently computed and two topology graphs can be matched. The match between the graphs is then used to calculate a number of standard map evaluation attributes like coverage, global accuracy, relative accuracy, consistency, and brokenness. Experiments with robot generated maps are used to highlight the capabilities of the proposed approach and to evaluate the performance of the underlying algorithms.     

Self-Motion Representation and Global Path Planning Optimization for Redundant Manipulators through Topology-Based Discretization

This paper addresses manipulator redundancy from a global perspective, aiming at kinematic control through the exploration of self-motion topology. The methodology is based on collecting information about the structure of the kinematic map with the use of topological tools, providing an overall view of the configuration space and its relationship to the work space – a suitable framework for the efficient implementation of global approaches. A space discretization method has been developed to benefit from the topological structure, embedding kinematics in its representation. This method enables an efficient exploration of global redundancy resolution and path planning, offering the means to avoid local minima and deadlocks with minimum effort. The discretization was implemented for a planar manipulator, demonstrating significant improvement in the search for globally optimum solutions of path planning when compared to traditional approaches.     

基于目标导向行为和空间拓扑记忆的视觉导航方法

针对在具有动态因素且视觉丰富环境中的导航问题,受路标机制空间记忆方式启发,提出一种可同步学习目标导向行为和记忆空间结构的视觉导航方法.首先,为直接从原始输入中学习控制策略,以深度强化学习为基本导航框架,同时添加碰撞预测作为模型辅助任务;然后,在智能体学习导航过程中,利用时间相关性网络祛除冗余观测及寻找导航节点,实现通过情景记忆递增描述环境结构;最后,将空间拓扑地图作为路径规划模块集成到模型中,并结合动作网络用于获取更加通用的导航方法.实验在3D仿真环境DMlab中进行,实验结果表明,本文方法可从视觉输入中学习目标导向行为,在所有测试环境中均展现出更高效的学习方法和导航策略,同时减少构建地图所需数据量;而在包含动态堵塞的环境中,该模型可使用拓扑地图动态规划路径,从而引导绕路行为完成导航任务,展现出良好的环境适应性.     

Integrating fuzzy topological maps and fuzzy geometric maps for behavior‐based robots

In behavior‐based robots, planning is necessary to elaborate abstract plans that resolve complex navigational tasks. Usually maps of the environment are used to plan the robot motion and to resolve the navigational tasks. Two types of maps have been mainly used: metric and topological maps. Both types present advantages and weakness so that several integration approaches have been proposed in literature. However, in many approaches the integration is conducted to build a global representation model, and the planning and navigational techniques have not been fitted to profit from both kinds of information. We propose the integration of topological and metric models into a hybrid deliberative‐reactive architecture through a path planning algorithm based on A^* and a hierarchical map with two levels of abstraction. The hierarchical map contains the required information to take advantage of both kinds of modeling. On one hand, the topological model is based on a fuzzy perceptual model that allows the robot to classify the environment in distinguished places, and on the other hand, the metric map is built using regions of possibility with the shape of fuzzy segments, which are used later to build fuzzy grid‐based maps. The approach allows the robot to decide on the use of the most appropriate model to navigate the world depending on minimum‐cost and safety criteria. Experiments in simulation and in a real office‐like environment are shown for validating the proposed approach integrated into the navigational architecture. © 2002 Wiley Periodicals, Inc.     

一种移动机器人环境模型——灰色定性地图

针对移动机器人的环境建模问题,提出一种综合拓扑地图和儿何地图特点的混合环境模型——灰色定性地图.用凸剖分算法将环境中的自由空间分解为一组凸多边形.灰色定性地图的定性层由凸多边形及其之间的邻接关系构成,用于模拟人类在路径规划时的高层定性推理.定量层由凸多边形顶点的坐标和势场向量构成,用于决定机器人在连续空间中的运动方向和速度.理论分析和实验均表明:灰色定性地图可以模拟人类对环境认知的知识表达,并且可以仪由凸多边形邻接信息和顶点信息支持机器人完成路径规划且确保路径的平滑性,有效地降低了环境模型的空间复杂度.     

Learning View Graphs for Robot Navigation

We present a purely vision-based scheme for learning a topological representation of an open environment. The system represents selected places by local views of the surrounding scene, and finds traversable paths between them. The set of recorded views and their connections are combined into a graph model of the environment. To navigate between views connected in the graph, we employ a homing strategy inspired by findings of insect ethology. In robot experiments, we demonstrate that complex visual exploration and navigation tasks can thus be performed without using metric information.     

基于场景图谱的室内移动机器人目标搜索

在移动机器人执行日常家庭任务时,首先需要其能够在环境中避开障碍物,自主地寻找到房间中的物体。针对移动机器人如何有效在室内环境下对目标物体进行搜索的问题,提出了一种基于场景图谱的室内移动机器人目标搜索,其框架结合了导航地图、语义地图和语义关系图谱。在导航地图的基础上建立了包含地标物体位置信息的语义地图,机器人可以轻松对地标物体进行寻找。对于动态的物体,机器人根据语义关系图中物体之间的并发关系,优先到关系强度比较高的地标物体旁寻找。通过物理实验展示了机器人在语义地图和语义关系图的帮助下可以实现在室内环境下有效地寻找到目标,并显著地减少了搜索的路径长度,证明了该方法的有效性。     

Modelling Route Instructions for Robust Human-Robot Interaction on Navigation Tasks

In this paper, we demonstrate the use of qualitative spatial modelling as the foundation for the conceptual representation of route instructions, to enable robust humanrobot interaction on navigation tasks. Our conceptual model is motivated by empirical studies on route navigation, and combines Qualitative Orientation Calculi for spatial reasoning using directional orientation information and topological maps for structuring route segments and routes. Moreover, we present a formal de nition of the conceptual model using the algebraic speci cation language CASL for syntactic and semantic checking, consistency checking and veri cation. Finally, we introduce a generic route graph concept and its formalization. The instantiation of the generic route graph at di erent abstraction levels provides a formal foundation for linking the conceptual model to a global environment map used by an intelligent robot, e.g., a semi-autonomous wheelchair, to carry out human navigation tasks.     

基于不确定网格地图的移动机器人导航

研究了在未知环境下的移动机器人导航问题．在分析超声传感器不确定性模型的基础上,根据模糊集理论创建网格地图来描述机器人工作环境,使用模糊隶属度表示网格占用状态．通过网格信息融合来减弱传感器测量误差,提高网格地图的精度．提出基于模糊网格地图的路径规划算法,利用重复局部优化路径搜索来实现全局路径规划．机器人通过交替进行创建地图和路径规划两个基本过程来完成导航任务．仿真结果表明创建的地图能较精确地表示环境信息。规划的路径可以使机器人安全地到达目的地．     

Autonomous Exploring System Based on Ultrasonic Sensory Information

An autonomous exploring system for a mobile robot is presented in this article. The system consists of an ultrasonic range sensor (URS) module and a novel method for building a map from exploration of an environment. Instead of random exploration, the proposed approach provides a systematic and efficient strategy to build the map by means of some preferential points. Taking a multitude of observations or measurements by sonar sensors, a mobile robot derives a virtual polygonal map from a set of regressed segments, partial prior known environmental information, and some inference rules for vertices. Additionally, the concept of safe zones is also introduced in the system to keep the mobile robot safe during exploration. Based on the identified virtual map, a searching method is used to select a next best observation to collect the most sufficient information. Several experiments are given to demonstrate the performance of this proposed approach.