Routing-based navigation of dense mobile robots

In the future, many teams of robots will navigate in home or office environments, similar to dense crowds operating currently in different scenarios. The paper aims to route a large number of robots so as to avoid build-up of congestions, similar to the problem of route planning of traffic systems. In this paper, first probabilistic roadmap approach is used to get a roadmap for online motion planning of robots. A graph search-based technique is used for motion planning. In the literature, typically the search algorithms consider only the static obstacles during this stage, which results in too many robots being scheduled on popular/shorter routes. The algorithm used here therefore penalizes roadmap edges that lie in regions with large robot densities so as to judiciously route the robots. This planning is done continuously to adapt the path to changing robotic densities. The search returns a deliberative trajectory to act as a guide for the navigation of the robot. A point at a distant of the deliberative path becomes the immediate goal of the reactive system. A ‘centre of area’-based reactive navigation technique is used to reactively avoid robots and other dynamic obstacles. In order to avoid two robots blocking each other and causing a deadlock, a deadlock avoidance scheme is designed that detects deadlocks, makes the robots wait for a random time and then allows them to make a few random steps. Experimental results show efficient navigation of a large number of robots. Further, routing results in effectively managing the robot densities so as to enable an efficient navigation.     

基于初等运动的多机器人避碰及死锁预防

该文以一实际应用为背景提出了多移动机器人避碰及死锁预防算法,该算法将机器人的运行环境形式化地描述为初等运动集、冲突图、总任务集及机器人作业集,利用集合论、图论的有关方法及技术实现了多机器人间的避碰与死锁预防。当机器人的运行环境改变时,只需要对相应的集合描述文件进行修改,而不用对程序做任何屐改动。算法的另一个特点是利用避碰算法巧妙地完成了死锁预防。仿真和实际运行证明了该算法高效可靠。     

Initial configuration dependence in a self-organizing robot

In this paper, we describe the dependence of an initial state in a self-organizing robot on an optimal structure configuration, where a “fractum” is used as a basic unit. Each robot operates on a genetic algorithm (GA) by itself, and all of them will produce a desired configuration. However, problems such as a deadlock state can happen depending on the initial configuration. A deadlock state means a state in which no robots can move because each robot moves autonomously. It is proved from simulations that a difference in the initial configuration can affect both the deadlock rate and the number of movements of fracta needed to obtain an optimal structure configuration. This work was presented, in part, at the Third International Symposium on Artificial Life and Robotics, Oita, Japan, January 19–21, 1998     

基于行为优先与模糊控制的移动机器人导航

由于动态未知环境下自主移动机器人的导航具有较大困难,为实现自主机器人在动态未知环境下的无碰撞运行,文中将行为优先级控制与模糊逻辑控制相结合,提出4种基本行为控制策略:目标寻找、避障、跟踪和解锁.针对'U'型和'V'型障碍物运行解锁问题,提出了行走路径记忆方法,并通过构建虚拟墙来避免机器人再次走入此类区域.仿真实验表明,所提出的控制策略可有效地运用于复杂和未知环境下自主移动机器人的导航,且具有较好的鲁棒性和适应性.     

基于双向搜索的改进蚁群路径规划算法

针对移动机器人在复杂地图环境中移动耗时长、易陷入局部最优等问题,设计了一种基于双向搜索的改进蚁群路径规划算法。基于K-means算法对地图预处理,量化地图的局部复杂度程度,并将局部环境信息融合到状态转移概率函数,使机器人优先选择在复杂程度小的区域进行寻优,减少路径拐点。设定双向搜索规则,改进启发函数,提高算法的局部方向搜索精度和全局搜索效率。针对蚁群算法中蚂蚁遇到U障碍物陷入死锁的问题,提出死锁判断系数,增加了有效蚂蚁的数量,进一步提高了算法性能。仿真结果表明所设计的算法在复杂地图环境中相较于传统蚁群算法移动机器人的路径搜索效率更高。     

An algorithm for multi-robot collision-free navigation based on shortest distance

This paper presents a new approach for multi-robot navigation in dynamic environments, called the shortest distance algorithm. This approach uses both the current position and orientation of other robots to compute the collision free trajectory. The algorithm suggested in this paper is based on the concept of reciprocal orientation that guarantees smooth trajectories and collision free paths. All the robots move either in a straight line or in a circular arc using the Bresenham algorithms. The current approach is tested on three simulation scenarios.     

Deadlock-free dynamic resource assignment in multi-robot systems with multiple missions： application in wireless sensor networks

In unstructured environments, dynamic resource assignment is required for effective cooperation of robot teams. In some scenarios, robots are in charge of executing multiple missions simultaneously. This creates risks of deadlock due to the presence of shared resources among various missions. The main contribution of this paper is the development of a novel approach that combines the one-step look-ahead deadlock avoidance policy with dynamic resource assignment. The dynamic resource assignment is achieved using greedy resource assignment for multi-mission robot teams in the framework of a matrix-based discrete event controller. Simulation results are presented in MATLAB°R to discuss in detail the proposed control strategy. The paper also discusses the toolkit developed in LabVIEW°R which is used to implement this control framework using a suitable example.     

基于预测窗的轮式移动机器人最优避障避碰算法

针对非线性轮式移动机器人的避障以及多机器人间的相互避碰问题,提出了一种基于预测窗的避障避碰算法.首先为了便于预测碰撞的发生,通过反馈线性化将非线性的机器人运动学模型转化成线性模型;然后根据线性模型预测会导致机器人发生碰撞的所有相对虚拟加速度变化量集合,称之为加速度变化障碍.基于此,为每个机器人构造既能躲避障碍物又能相互避碰的可行加速度变化集合.然后通过优化指标函数求得最优虚拟加速度变化量,最后将其转换成机器人的实际控制量.这种算法与现有的相比,可使机器人在避障或避碰过程中的行驶方向角、线速度的变化幅值更小,角速度和线加速度的变化更为平顺,而且运行所用的平均时间更短.仿真结果演示了所提出算法的有效性和相对于已有方法的优势.     

青少年机器人足球比赛死锁解除的模糊数学法

青少年机器人足球比赛中,常常会出现死锁。目前,一般采用手工方法解除死锁,这影响了比赛的智能性与观赏性。论文对模糊系统做了概述,分析了足球机器人运动死锁的特征,定义了模糊系统的输入输出变量,以及变量在论域上的模糊集合;建立了双层模糊系统,获取了足球机器人比赛中运动死锁发生时的数据,并将模糊系统对这些数据的处理结果与机器人足球专家对相应死锁的处理结果进行了比较和分析。     

Path planning strategy for autonomous mobile robot navigation using Petri-GA optimisation

In this paper, a novel knowledge based genetic algorithm (GA) for path planning of multiple robots for multiple targets seeking behaviour in presence of obstacles is proposed. GA technique has been incorporated in Petri-Net model to make an integrated navigational controller. The proposed algorithm is based upon an iterative non-linear search, which utilises matches between observed geometry of the environment and a priori map of position locations, to estimate a suitable heading angle, there by correcting the position and orientation of the robots to find targets. This knowledge based GA is capable of finding an optimal or near optimal robot path in complex environments. The Petri-GA model can handle inter robot collision avoidance more effectively than the stand alone GA. The resulting navigation algorithm has been implemented on real mobile robots and tested in various environments to validate the developed control scheme.     

基于强化学习算法的多机器人系统的冲突消解策略

多机器人系统中，随着机器人数目的增加．系统中的冲突呈指数级增加．甚至出现死锁．本文提出了基于过程奖赏和优先扫除的强化学习算法作为多机器人系统的冲突消解策略．针对典型的多机器人可识别群体觅食任务．以计算机仿真为手段，以收集的目标物数量为系统性能指标，以算法收敛时学习次数为学习速度指标，进行仿真研究，并与基于全局奖赏和Q学习算法等其他9种算法进行比较．结果表明所提出的基于过程奖赏和优先扫除的强化学习算法能显著减少冲突．避免死锁．提高系统整体性能．     

Analyzing the Multiple-target-multiple-agent Scenario Using Optimal Assignment Algorithms

This work considers the problem of maximum utilization of a set of mobile robots with limited sensor-range capabilities and limited travel distances. The robots are initially in random positions. A set of robots properly guards or covers a region if every point within the region is within the effective sensor range of at least one vehicle. We wish to move the vehicles into surveillance positions so as to guard or cover a region, while minimizing the maximum distance traveled by any vehicle. This problem can be formulated as an assignment problem, in which we must optimally decide which robot to assign to which slot of a desired matrix of grid points. The cost function is the maximum distance traveled by any robot. Assignment problems can be solved very efficiently. Solution times for one hundred robots took only seconds on a Silicon Graphics Crimson workstation. The initial positions of all the robots can be sampled by a central base station and their newly assigned positions communicated back to the robots. Alternatively, the robots can establish their own coordinate system with the origin fixed at one of the robots and orientation determined by the compass bearing of another robot relative to this robot. This paper presents example solutions to the multiple-target-multiple-agent scenario using a matching algorithm. Two separate cases with one hundred agents in each were analyzed using this method. We have found these mobile robot problems to be a very interesting application of optimal assignment algorithms, and we expect this to be a fruitful area for future research.     

一种多移动机器人避障的改进算法

为了使多机器人在有障碍物的环境中可靠地运行,针对多机器人的避障问题,融合沿墙行为的避障模式,构造出一类具有自适应特性l-ψ闭环控制律下的多机器人避障算法,以作为基于行为的控制策略的有益补充。仿真结果表明,该算法可以成功地解决机器人因融合参数不当而形成的避障"死锁"问题,使多机器人在有障碍物的环境下,在障碍物区能够顺利地通过障碍物,在离开障碍物后,快速恢复至稳定。     

Improving traversability of quadruped walking robots using body movement in 3D rough terrains

This paper presents a study on improving the traversability of a quadruped walking robot in 3D rough terrains. The key idea is to exploit body movement of the robot. The position and orientation of the robot are systematically adjusted and the possibility of finding a valid foothold for the next swing is maximized, which makes the robot have more chances to overcome the rough terrains. In addition, a foothold search algorithm that provides the valid foothold while maintaining a high traversability of the robot, is investigated and a gait selection algorithm is developed to help the robot avoid deadlock situations. To explain the algorithms, new concepts such as reachable area, stable area, potential search direction, and complementary kinematic margin are introduced, and the effectiveness of the algorithms is validated via simulations and experiments.     

Decentralized behavior-based formation control of multiple robots considering obstacle avoidance

This paper proposes a decentralized behavior-based formation control algorithm for multiple robots considering obstacle avoidance. Using only the information of the relative position of a robot between neighboring robots and obstacles, the proposed algorithm achieves formation control based on a behavior-based algorithm. In addition, the robust formation is achieved by maintaining the distance and angle of each robot toward the leader robot without using information of the leader robot. To avoid the collisions with obstacles, the heading angles of all robots are determined by introducing the concept of an escape angle, which is related with three boundary layers between an obstacle and the robot. The layer on which the robot is located determines the start time of avoidance and escape angle; this, in turn, generates the escape path along which a robot can move toward the safe layer. In this way, the proposed method can significantly simplify the step of the information process. Finally, simulation results are provided to demonstrate the efficiency of the proposed algorithm.     

基于运动图式的多机器人合作追捕

为实现多个机器人合作追捕目标机器人,以基于运动图式的反应式控制结构为基础,设计追捕机器人的4种基本行为：奔向目标,避开障碍物,避让队友以及收缩包围,为避免机器人陷入死锁状态,引入随机漫游行为。通过基本行为的矢量合成和机器人之间的局部交互作用,实现多机器人的协作行为。仿真试验验证了该方法的有效性。     

危险气体泄漏源搜寻多机器人系统的设计与实现

危险气体泄漏源搜寻是仿生嗅觉技术的重要应用领域之一.为了提高气体泄露源定位的效率和准确性,设计并实现了一种基于无线传感器网络的气源目标搜寻多机器人系统.该系统由多个嗅觉机器人组成,每个机器人作为无线传感器网络节点实现信息交换,协同工作,实现危险气体泄漏源的定位.嗅觉机器人以DSP处理器(TMS320F28335)为控制核心,对MOS气体传感器和风速传感器的输出信号进行融合,设计了浓度梯度与风速信息相结合的单一气体泄漏源搜寻算法.当嗅觉机器人完成气源定位时将发出警报,其他机器人利用装配的麦克风阵列和声源定位算法实现对泄漏源的间接定位.最后,为了说明所设计的多机器人系统对气体泄露源定位的有效性和准确性,本文设计了针对单一泄露源的气源搜寻实验进行验证.     

A novel efficient algorithm for mobile robot localization

Being autonomous is one of the most important goals in mobile robots. One of the fundamental works to achieve this goal is giving the ability to a robot for finding its own correct position and orientation. Different methods have been introduced to solve this problem. In this paper, a novel method based on the harmony search (HS) algorithm for robot localization through scan matching is proposed. Simulation results show that the proposed method in comparison with a genetic algorithm-based approach has better accuracy and higher performance. Furthermore a new hybrid algorithm based on harmony search and differential evolution (DE) algorithms is proposed and evaluated on different benchmark functions. Finally the hybrid algorithm has been applied for mobile robot localization and it outperformed the HS-based approach.     

Locomotion with articulated legs in pipes or ducts

Different implementations of remote controlled robots exist that can inspect and repair the interior of a pipe or duct. For this purpose they have video cameras and tools like a welding set or a grinder on board. This paper describes an approach with articulated legs that are pushed against the walls to obtain a grip. In contrast to wheels, for instance, legs overcome problems of common pipe inspection robots, like branches or obstacles in the pipe. The robot has a hierarchical control architecture with reflexive behaviour in the lower layers. In a two-dimensional simulation environment the robot performed successfully in several shapes of pipes. The results show that simple reflexive behaviour is sufficient to overcome even complex shapes. In the tested environment, reflexive behaviour prevented deadlock and ensured the robot's safe operation.     

Altruistic coordination for multi-robot cooperative pathfinding

When multiple robots perform tasks in a shared workspace, they might be confronted with the risk of blocking each other’s ways, which will lead to conflicts or interference among them. Planning collision-free paths for all the robots is a challenge for a multi-robot system, which is also known as the multi-robot cooperative pathfinding problem in which each robot has to navigate from its starting location to the destination while keeping avoiding stationary obstacles as well as the other robots. In this paper, we present a novel fully decentralized approach to this problem. Our approach allows robots to make real-time responses to dynamic environments and can resolve a set of benchmark deadlock situations subject to complex spatial constraints in a shared workspace by means of altruistic coordination. Specifically, when confronted with congested situations, each robot can employ waiting, moving-forwards, dodging, retreating and turning-head strategies to make local adjustments. Most importantly, each robot only needs to coordinate and communicate with the others that are located within its coordinated network in our approach, which can reduce communication overhead in fully decentralized multi-robot systems. In addition, experimental results also show that our proposed approach provides an efficient and competitive solution to this problem.