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.     

可移动机器人的马尔可夫自定位算法研究

马尔可夫定位算法是利用机器人运动环境中的概率密度分布进行定位的方法.使用该 方法机器人可在完全不知道自己位置的情况下通过传感器数据和运动模型来估计自己的位置. 但是,在研究中发现它还存在一些问题,如概率减小到零后就无法恢复.对只有距离传感器的机 器人在对称的环境中仅仅采用该算法就无法确定位置.为了解决这些问题,文中给出了修正算 法,并建议在机器人上装上方向仪(如指南针或陀螺仪等),然后利用定义的一个角度高斯分布 函数来构造新的机器人感知模型.在此基础上详细地阐述了一种新的自定位技术.最后,采用仿 真程序验证了机器人在对称环境中运动时这一新算法的可行性.     

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.     

ADAPTIVE SLIDING-MODE CONTROL OF SPHERICAL ROBOT WITH ESTIMATED ROLLING RESISTANCE

A spherical robot will inevitably be affected by rolling resistance from the ground when it is used in an unstructured exploration environment. Because of the complex contact condition between the robot and the ground, it is very difficult to obtain the information about the rolling resistance correctly. This fact decreases the movement performances of spherical robots greatly. In this study, dynamic models of the sphere subsystem and the inner suspension subsystem are derived. By Lyapunov theorem, the sliding surface with integral element is applied to construct a new sliding-mode control scheme to track the desired velocity of the spherical robot. In the proposed controller, the sgn(x) function is replaced by the tanh(x) function, in order to reduce the inherent chattering phenomena of the sliding-mode algorithm. Because the rolling resistance is uncertain, an adaptive control scheme is applied to estimate the uncertain rolling resistance dynamically, which makes the robot more sensitive and adaptive in unstructured exploration. The simulation results demonstrate the validity of the proposed schemes.     

Sonar Sensor-Based Efficient Exploration Method Using Sonar Salient Features and Several Gains

This paper describes a sonar sensor-based exploration method. To build an accurate map in an unknown environment during exploration, a simultaneous localization and mapping problem must be solved. Therefore, a new type of sonar feature called a ??sonar salient feature?? (SS-feature), is proposed for robust data association. The key concept of an SS-feature is to extract circle feature clouds on salient convex objects from environments by associating sets of sonar data. The SS-feature is used as an observation in the extended Kalman filter (EKF)-based SLAM framework. A suitable strategy is needed to efficiently explore the environment. We used utilities of driving cost, expected information about an unknown area, and localization quality. Through this strategy, the exploration method can greatly reduce behavior that leads a robot to explore a previously visited place, and thus shorten the exploration distance. A robot can select a favorable path for localization by localization gain during exploration. Thus, the robot can estimate its pose more robustly than other methods that do not consider localizability during exploration. This proposed exploration method was verified by various experiments, and it ensures that a robot can build an accurate map fully autonomously with sonar sensors in various home environments.     

Discovering and restoring changes in object positions using an autonomous robot with laser rangefinders

This paper describes an object rearrangement system for an autonomous mobile robot. The objective of the robot is to autonomously explore and learn about an environment, to detect changes in the environment on a later visit after object disturbances and finally, to move objects back to their original positions. In the implementation, it is assumed that the robot does not have any prior knowledge of the environment and the positions of the objects. The system exploits Simultaneous Localisation and Mapping (SLAM) and autonomous exploration techniques to achieve the task. These techniques allow the robot to perform localisation and mapping which is required to perform the object rearrangement task autonomously. The system includes an arrangement change detector, object tracking and map update that work with a Polar Scan Match (PSM) Extended Kalman Filter (EKF) SLAM system. In addition, a path planning technique for dragging and pushing an object is also presented in this paper. Experimental results of the integrated approach are shown to demonstrate that the proposed approach provides real-time autonomous object rearrangements by a mobile robot in an initially unknown real environment. Experiments also show the limits of the system by investigating failure modes.     

Reinforcement based mobile robot navigation in dynamic environment

In this paper, a new approach is developed for solving the problem of mobile robot path planning in an unknown dynamic environment based on Q-learning. Q-learning algorithms have been used widely for solving real world problems, especially in robotics since it has been proved to give reliable and efficient solutions due to its simple and well developed theory. However, most of the researchers who tried to use Q-learning for solving the mobile robot navigation problem dealt with static environments; they avoided using it for dynamic environments because it is a more complex problem that has infinite number of states. This great number of states makes the training for the intelligent agent very difficult. In this paper, the Q-learning algorithm was applied for solving the mobile robot navigation in dynamic environment problem by limiting the number of states based on a new definition for the states space. This has the effect of reducing the size of the Q-table and hence, increasing the speed of the navigation algorithm. The conducted experimental simulation scenarios indicate the strength of the new proposed approach for mobile robot navigation in dynamic environment. The results show that the new approach has a high Hit rate and that the robot succeeded to reach its target in a collision free path in most cases which is the most desirable feature in any navigation algorithm.     

Image-based memory for robot navigation using properties of omnidirectional images

This paper proposes a new technique for vision-based robot navigation. The basic framework is to localise the robot by comparing images taken at its current location with reference images stored in its memory. In this work, the only sensor mounted on the robot is an omnidirectional camera. The Fourier components of the omnidirectional image provide a signature for the views acquired by the robot and can be used to simplify the solution to the robot navigation problem. The proposed system can calculate the robot position with variable accuracy (‘hierarchical localisation’) saving computational time when the robot does not need a precise localisation (e.g. when it is travelling through a clear space). In addition, the system is able to self-organise its visual memory of the environment. The self-organisation of visual memory is essential to realise a fully autonomous robot that is able to navigate in an unexplored environment. Experimental evidence of the robustness of this system is given in unmodified office environments.     

Modeling curiosity in a mobile robot for long-term autonomous exploration and monitoring

This paper presents a novel approach to modeling curiosity in a mobile robot, which is useful for monitoring and adaptive data collection tasks, especially in the context of long term autonomous missions where pre-programmed missions are likely to have limited utility. We use a realtime topic modeling technique to build a semantic perception model of the environment, using which, we plan a path through the locations in the world with high semantic information content. The life-long learning behavior of the proposed perception model makes it suitable for long-term exploration missions. We validate the approach using simulated exploration experiments using aerial and underwater data, and demonstrate an implementation on the Aqua underwater robot in a variety of scenarios. We find that the proposed exploration paths that are biased towards locations with high topic perplexity, produce better terrain models with high discriminative power. Moreover, we show that the proposed algorithm implemented on Aqua robot is able to do tasks such as coral reef inspection, diver following, and sea floor exploration, without any prior training or preparation.     

Autonomous robotic exploration using a utility function based on Rényi’s general theory of entropy

In this paper we present a novel information-theoretic utility function for selecting actions in a robot-based autonomous exploration task. The robot’s goal in an autonomous exploration task is to create a complete, high-quality map of an unknown environment as quickly as possible. This implicitly requires the robot to maintain an accurate estimate of its pose as it explores both unknown and previously observed terrain in order to correctly incorporate new information into the map. Our utility function simultaneously considers uncertainty in both the robot pose and the map in a novel way and is computed as the difference between the Shannon and the Rényi entropy of the current distribution over maps. Rényi’s entropy is a family of functions parameterized by a scalar, with Shannon’s entropy being the limit as this scalar approaches unity. We link the value of this scalar parameter to the predicted future uncertainty in the robot’s pose after taking an exploratory action. This effectively decreases the expected information gain of the action, with higher uncertainty in the robot’s pose leading to a smaller expected information gain. Our objective function allows the robot to automatically trade off between exploration and exploitation in a way that does not require manually tuning parameter values, a significant advantage over many competing methods that only use Shannon’s definition of entropy. We use simulated experiments to compare the performance of our proposed utility function to these state-of-the-art utility functions. We show that robots that use our proposed utility function generate maps with less uncertainty and fewer visible artifacts and that the robots have less uncertainty in their pose during exploration. Finally, we demonstrate that a real-world robot using our proposed utility function is able to successfully create a high-quality map of an indoor office environment.     

Information based indoor environment robotic exploration and modeling using 2-D images and graphs

As the autonomy of personal service robotic systems increases so has their need to interact with their environment. The most basic interaction a robotic agent may have with its environment is to sense and navigate through it. For many applications it is not usually practical to provide robots in advance with valid geometric models of their environment. The robot will need to create these models by moving around and sensing the environment, while minimizing the complexity of the required sensing hardware. Here, an information-based iterative algorithm is proposed to plan the robot's visual exploration strategy, enabling it to most efficiently build a graph model of its environment. The algorithm is based on determining the information present in sub-regions of a 2-D panoramic image of the environment from the robot's current location using a single camera fixed on the mobile robot. Using a metric based on Shannon's information theory, the algorithm determines potential locations of nodes from which to further image the environment. Using a feature tracking process, the algorithm helps navigate the robot to each new node, where the imaging process is repeated. A Mellin transform and tracking process is used to guide the robot back to a previous node. This imaging, evaluation, branching and retracing its steps continues until the robot has mapped the environment to a pre-specified level of detail. The set of nodes and the images taken at each node are combined into a graph to model the environment. By tracing its path from node to node, a service robot can navigate around its environment. This method is particularly well suited for flat-floored environments. Experimental results show the effectiveness of this algorithm.     

Cooperative exploration based on supervisory control of multi-robot systems

When multiple mobile robots cooperatively explore an unknown environment, the advantages of robustness and redundancy are guaranteed. However, available traditional economy approaches for coordination of multi-robot systems (MRS) exploration lack efficient target selection strategy under a few of situations and rely on a perfect communication. In order to overcome the shortages and endow each robot autonomy, a novel coordinated algorithm based on supervisory control of discrete event systems and a variation of the market approach is proposed in this paper. Two kinds of utility and the corresponding calculation schemes which take into account of cooperation between robots and covering the environment in a minimal time, are defined. Different moving target of each robot is determined by maximizing the corresponding utility at the lower level of the proposed hierarchical coordinated architecture. Selection of a moving target assignment strategy, dealing with communication failure, and collision avoidance are modeled as behaviors of each robot at the upper level. The proposed approach distinctly speeds up exploration process and reduces the communication requirement. The validity of our algorithm is verified by computer simulations.     

Sensor fusion-based exploration in home environments using information,driving and localization gains

Exploration is one of the most important functions for a mobile service robot because a map is required to carry out various tasks. A suitable strategy is needed to efficiently explore an environment and to build an accurate map. This study proposed the use of several gains (information, driving, localization) that, if considered during exploration, can simultaneously improve the efficiency of the exploration process and quality of the resulting map. Considering the information and driving gains reduces behavior that leads a robot to explore a previously visited place, and thus the exploration distance is reduced. In addition, the robot can select a favorable path for localization by considering the localization gain during exploration, and the robot can estimate its pose more robustly than other methods that do not consider localizability during exploration. This proposed exploration method was verified by various experiments, which verified that a robot can build an accurate map fully autonomously and efficiently in various home environments using the proposed method.     

机器人信息增益RRT环境探索算法

由于传统RRT(rapidly-exploring random trees)路径规划算法固有的盲目探索的问题,机器人到达目标点时除起始点扩展到目标点的路径之外还会生成其他与结果无关的分支路径与节点,为使这些分支路径得到利用并且减少探索的盲目性,提出基于信息增益与RRT思想相结合的机器人环境探索策略.该方法对未知环境中的节点进行信息估计,选取具有最大信息增益的节点作为采样节点,且每次都会生成最大信息增益的新节点进行扩展.该策略使机器人能完成对未知环境的探索,还可以降低传统RRT算法固有的盲目性.仿真实验结果表明,所提出方法能够有效快速地帮助机器人探索未知环境,实现环境探索.     

Adaptation technique for integrating genetic programming and reinforcement learning for real robots

We propose an integrated technique of genetic programming (GP) and reinforcement learning (RL) to enable a real robot to adapt its actions to a real environment. Our technique does not require a precise simulator because learning is achieved through the real robot. In addition, our technique makes it possible for real robots to learn effective actions. Based on this proposed technique, we acquire common programs, using GP, which are applicable to various types of robots. Through this acquired program, we execute RL in a real robot. With our method, the robot can adapt to its own operational characteristics and learn effective actions. In this paper, we show experimental results from two different robots: a four-legged robot "AIBO" and a humanoid robot "HOAP-1." We present results showing that both effectively solved the box-moving task; the end result demonstrates that our proposed technique performs better than the traditional Q-learning method.     

Exploration of 2D and 3D Environments using Voronoi Transform and Fast Marching Method

Robot navigation in unknown environments requires an efficient exploration method. Exploration involves not only to determine towards the robot must to move but also motion planning, and simultaneous localization and mapping processes. The final goal of the exploration task is to build a map of the environment that previously the robot didn’t know. This work proposes the Voronoi Fast Marching method, that uses a Fast Marching technique on the Logarithm of the Extended Voronoi Transform of the environment’s image provided by sensors, to determine a motion plan. The Logarithm of the Extended Voronoi Transform imitates the repulsive electric potential from walls and obstacles, and the Fast Marching Method propagates a wave over that potential map. The trajectory is calculated by the gradient method. The robot is directed towards the most unexplored and free zones of the environment so as to be able to explore all the workspace. Finally, to build the environment map while the robot is carrying out the exploration task, a SLAM (Simultaneous Localization and Modelling)algorithm is implemented, the Evolutive Localization Filter (ELF) based on a differential evolution technique. The combination of these methods provide a new autonomous exploration strategy to construct consistent maps of 2D and 3D indoor environments.     

Intelligent and Efficient Strategy for Unstructured Environment Sensing Using Mobile Robot Agents

In field environments it is not usually possible to provide robots in advance with valid geometric models of its task and environment. The robot or robot teams need to create these models by scanning the environment with its sensors. Here, an information-based iterative algorithm to plan the robot's visual exploration strategy is proposed to enable it to most efficiently build 3D models of its environment and task. The method assumes mobile robot (or vehicle) with vision sensors mounted at a manipulator end-effector (eye-in-hand system). This algorithm efficiently repositions the systems' sensing agents using an information theoretic approach and fuses sensory information using physical models to yield a geometrically consistent environment map. This is achieved by utilizing a metric derived from Shannon's information theory to determine optimal sensing poses for the agent(s) mapping a highly unstructured environment. This map is then distributed among the agents using an information-based relevant data reduction scheme. This method is particularly well suited to unstructured environments, where sensor uncertainty is significant. Issues addressed include model-based multiple sensor data fusion, and uncertainty and vehicle suspension motion compensation. Simulation results show the effectiveness of this algorithm.     

移动机器人环境视觉小波稀疏压缩传感和识别

视觉环境认知,尤其处理实时性,是自主移动机器人研究的重要内容之一,而减少视觉信息数据处理量是提高视觉感知处理性能的重要举措之一。基于小波稀疏和灰度共生矩阵,对两种典型环境图像的压缩传感信息进行了纹理特征提取与直接识别研究。结果表明:进行小波稀疏的两种压缩传感环境图像信息保留了原始图像特征,能够直接进行环境特征认知,在一定程度上说明了压缩传感信息直接特征识别的可行性。     

A global localization approach based on Line-segment Relation Matching technique

This paper presents a novel global localization approach for mobile robots by exploring line-segment features in any structured environment. The main contribution of this paper is an effective data association approach, the Line-segment Relation Matching (LRM) technique, which is based on a generation and exploration of an Interpretation Tree (IT). A new representation of geometric patterns of line-segments is proposed for the first time, which is called as Relation Table. It contains relative geometric positions of every line-segment respect to the others (or itself) in a coordinate-frame independent sense. Based on that, a Relation-Table-constraint is applied to minimize the searching space of IT therefore greatly reducing the processing time of LRM. The Least Square algorithm is further applied to estimate the robot pose using matched line-segment pairs. Then a global localization system can be realized based on our LRM technique integrated with a hypothesis tracking framework which is able to handle pose ambiguity. Sufficient simulations were specially designed and carried out indicating both pluses and minuses of our system compared with former methods. We also presented the practical experiments illustrating that our approach has a high robustness against uncertainties from sensor occlusions and extraneous observation in a highly dynamic environment. Additionally our system was demonstrated to easily deal with initialization and have the ability of quick recovery from a localization failure.     

遥操作机器人的新型力反馈算法*

在采用液压挖掘机改造的遥操作机器人双向伺服控制系统中,针对大臂和前臂两个自由度构建力反馈控制算法。以准确地获取从端机器人与环境的作用力,使反馈力能够更好地反映从端工作状况为目的,采用构建干扰力补偿项的方法消除干扰力对反馈力的影响;以机器人转角为输入,以空载时检测到的液压缸作用力为输出,通过径向基函数构建干扰力补偿项,此补偿项可对多种因机器人的机械本体动力学特性产生的干扰力之合力进行补偿。实验证明,在以液压机构为从手的双向力反馈系统中,通过构建干扰力补偿项的方法提高力反馈效果的方法是可行的,采用的带有干扰力