Fault-tolerant flocking for a group of autonomous mobile robots

Consider a system composed of mobile robots that move on the plane, each of which independently executing its own instance of an algorithm. Given a desired geometric pattern, the flocking problem consists in ensuring that the robots form this pattern and maintain it while moving together on the plane. In this paper, we explore flocking in the presence of faulty robots, where the desired pattern is a regular polygon. We propose a distributed fault tolerant flocking algorithm assuming a semi-synchronous model with a k-bounded scheduler, in the sense that no robot is activated no more than k times between any two consecutive activations of any other robot.The algorithm is composed of three parts: failure detector, ranking assignment, and flocking algorithm. The role of the rank assignment is to provide a persistent and unique ranking for the robots. The failure detector identifies the set of currently correct robots in the system. Finally, the flocking algorithm handles the movement and reconfiguration of the flock, while maintaining the desired shape. The difficulty of the problem comes from the combination of the three parts, together with the necessity to prevent collisions and allow the rotation of the flock. We formally prove the correctness of our proposed solution.     

Crab walking of quadruped robots with a locked joint failure

Fault tolerance is an important aspect in the development of control systems for multi-legged robots since a failure in a leg may lead to a severe loss of static stability of a gait. In this paper, an algorithm for tolerating a locked joint failure is described in gait planning for a quadruped robot with crab walking. A locked joint failure is one for which a joint cannot move and is locked in place. If a failed joint is locked, the workspace of the resulting leg is constrained, but legged robots have fault tolerance capability to continue walking maintaining static stability. A strategy for fault-tolerant gaits is described and, especially, a periodic gait is presented for crab walking of a quadruped. The leg sequence and the formula of the stride length are analytically driven based on gait study and robot kinematics. The adjustment procedure from a normal gait to the proposed fault-tolerant crab gait is shown to demonstrate the applicability of the proposed scheme.     

Characterizing geometric patterns formable by oblivious anonymous mobile robots

In a system in which anonymous mobile robots repeatedly execute a “Look–Compute–Move” cycle, a robot is said to be oblivious if it has no memory to store its observations in the past, and hence its move depends only on the current observation. This paper considers the pattern formation problem in such a system, and shows that oblivious robots can form any pattern that non-oblivious robots can form, except that two oblivious robots cannot form a point while two non-oblivious robots can. Therefore, memory does not help in forming a pattern, except for the case in which two robots attempt to form a point. Related results on the pattern convergence problem are also presented.     

Fault-tolerance and self-stabilization: impossibility results and solutions using self-stabilizing failure detectors

This paper focuses on protocols that are simultaneously resilient to permanent failures (crash faults) and transient failures (memory and message corruption). First, we show that asynchronous round-based and fault-tolerant protocols cannot be transformed into protocols that are simultaneously fault-tolerant and self-stabilizing (ftss), as is otherwise possible in the synchronous mode of computation. Secondly, we show that it is impossible to find the number of processes (i.e. the size) on a family of networks, as it has been proven for the ring network. Finally, we present a ftss protocol for solving ring size by assuming that each process accesses a failure detector. We also propose two self-stabilizing implementations for the failure detector that differ in their degree of tolerance to transient failures.     

Fuzzy Policy Reinforcement Learning in Cooperative Multi-robot Systems

A multi-agent reinforcement learning algorithm with fuzzy policy is addressed in this paper. This algorithm is used to deal with some control problems in cooperative multi-robot systems. Specifically, a leader-follower robotic system and a flocking system are investigated. In the leader-follower robotic system, the leader robot tries to track a desired trajectory, while the follower robot tries to follow the reader to keep a formation. Two different fuzzy policies are developed for the leader and follower, respectively. In the flocking system, multiple robots adopt the same fuzzy policy to flock. Initial fuzzy policies are manually crafted for these cooperative behaviors. The proposed learning algorithm finely tunes the parameters of the fuzzy policies through the policy gradient approach to improve control performance. Our simulation results demonstrate that the control performance can be improved after the learning.     

A simple and communication-efficient Omega algorithm in the crash-recovery model

This paper presents a new algorithm implementing the Omega failure detector in the crash-recovery model. Contrary to previously proposed algorithms, this algorithm does not rely on the use of stable storage and is communication-efficient, i.e., eventually only one process (the elected leader) keeps sending messages. The algorithm relies on a nondecreasing local clock associated with each process. Since stable storage is not used to keep the identity of the leader in order to read it upon recovery, unstable processes, i.e., those that crash and recover infinitely often, output a special ⊥ value upon recovery, and then agree with correct processes on the leader after receiving a first message from it.     

A framework for the collective movement of mobile robots based on distributed decisions

A novel framework for the control of the collective movement of mobile robots is presented and analyzed in this article. It allows a group of robots to move as a unique entity performing the following functions: obstacle avoidance at group level, speed control and modification of the inter-robot distance. Its flocking controller is distributed among the robots, allowing them to move in the desired common direction and maintain a desired inter-robot distance. The framework is made up of different modules that modify the behavior of the group thus allowing different functions. They are based on consensus algorithms that allow the robots to agree on different parameters, taking into account which robot has more relevant information. New modules can be easily designed and incorporated into the framework in order to augment its capabilities. It can be easily implemented on any mobile robot capable of measuring the relative positions of neighboring robots and communicating with them. It has been successfully tested using 8 real robots and in simulation with up to 40 robots, demonstrating experimentally its scalability with an increasing number of robots.     

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.     

From Fireflies to Fault-Tolerant Swarms of Robots

One of the essential benefits of swarm robotic systems is redundancy. In case one robot breaks down, another robot can take steps to repair the failed robot or take over the failed robot's task. Although fault tolerance and robustness to individual failures have often been central arguments in favor of swarm robotic systems, few studies have been dedicated to the subject. In this paper, we take inspiration from the synchronized flashing behavior observed in some species of fireflies. We derive a completely decentralized algorithm to detect non-operational robots in a swarm robotic system. Each robot flashes by lighting up its on-board light-emitting diodes (LEDs), and neighboring robots are driven to flash in synchrony. Since robots that are suffering catastrophic failures do not flash periodically, they can be detected by operational robots. We explore the performance of the proposed algorithm both on a real-world swarm robotic system and in simulation. We show that failed robots are detected correctly and in a timely manner, and we show that a system composed of robots with simulated self-repair capabilities can survive relatively high failure rates.      

Fault-Tolerant Gait Planning for a Hexapod Robot Walking over Rough Terrain

Multi-legged robots need fault-tolerant gaits if one of attached legs suffers from a failure and cannot have normal operation. Moreover, when the robots with a failed leg are walking over rough terrain, fault-tolerance should be combined with adaptive gait planning for successful locomotion. In this paper, a strategy of fault-tolerant gaits is proposed which enables a hexapod robot with a locked joint failure to traverse two-dimensional rough terrain. This strategy applies a Follow-The-Leader (FTL) gait in post-failure walking, having the advantages of both fault-tolerance and terrain adaptability. The proposed FTL gait can produce the maximum stride length for a given foot position of a failed leg and better ditch-crossing ability than the previous fault-tolerant gaits. The applicability of the proposed FTL gait is verified using computer graphics simulations.     

Distributed leader‐follower flocking control

This paper presents a fuzzy based leader‐follower flocking system. To maintain the distance between robots, we use a fuzzy logic controller to design a “force function” which is related to the relative distance between neighbours. The “force function” is used to control velocity of robots. To prove stability of the flocking system, we build a Hamilton function which is kinetic energy of the flocking system. Utilizing the LaSalle's invariance principle, we prove that the system is stable. Specially, we develop a flocking controller in local form. By using the local controller, the robots in the flocking system only need to know local information (relative distances and relative angles between neighbours). To evaluate performance of the flocking system, we simulate the flocking system tracking trajectories with different shapes. The local flocking algorithm is tested with three Pioneer robots. We use the SICK laser scanner to measure the relative distances and relative angles between neighbours. Copyright © 2009 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Implementing the Omega failure detector in the crash-recovery failure model

Unreliable failure detectors are mechanisms providing information about process failures, that allow to solve several problems in asynchronous systems, e.g., Consensus. A particular failure detector, Omega, provides an eventual leader election functionality. This paper addresses the implementation of Omega in the crash-recovery failure model. We first propose an algorithm assuming that processes are reachable from the correct process that crashes and recovers a minimum number of times. Then, we propose two algorithms which assume only that processes are reachable from some correct process. Besides this, one of the algorithms requires the membership to be known a priori, while the other two do not.     

Data transferring model determination in robotic group

This paper describes the basic idea of data transferring in the group of robots while they move in an area with a high density of obstacles with the goal of increasing their movement speed by creating and synchronizing an area map that is made by each robot separately. This paper provides a brief review of existing robotic swarm projects and definition of the problems in robot teamwork, shows pathfinding methods and their analysis, justifies our technical vision system choice and describes its method of obstacle detecting that is based on dynamic triangulation. According to some behavioristic models, using fuzzy logic, the method of leader changing was used. This knowledge helps with the choice of appropriate models of data transferring, makes their simulation and creates a proper network between the robots to avoid data loss.     

一类有序化多移动机器人群集运动控制系统

群集运动控制(flocking control)是一种新型的多移动机器人运动协调控制, 目前的研究多集中于无leader模式下群集运动控制器的设计. 为此, 本文阐述了一类多移动机器人有序化群集运动系统控制方案及其性能评价方法. 首先, 在前人的研究基础上, 本文介绍了基于Agent的有序化编队控制机制; 然后, 运用非完整约束下移动机器人的动力学原理, 设计了由Agent到移动机器人的控制转化方法; 并进一步提出了基于“最小稳定时间”的群集运动分析法, 可对有序化群集运动系统进行分析; 最后, 运用仿真实例, 描述了多移动机器人有序化群集运动的控制及分析过程. 实验结果验证了此控制方案的有效性.     

Flocking of Multi-Agents With a Virtual Leader

All agents being informed and the virtual leader traveling at a constant velocity are the two critical assumptions seen in the recent literature on flocking in multi-agent systems. Under these assumptions, Olfati-Saber in a recent IEEE Transactions on Automatic Control paper proposed a flocking algorithm which by incorporating a navigational feedback enables a group of agents to track a virtual leader. This paper revisits the problem of multi-agent flocking in the absence of the above two assumptions. We first show that, even when only a fraction of agents are informed, the Olfati-Saber flocking algorithm still enables all the informed agents to move with the desired constant velocity, and an uninformed agent to also move with the same desired velocity if it can be influenced by the informed agents from time to time during the evolution. Numerical simulation demonstrates that a very small group of the informed agents can cause most of the agents to move with the desired velocity and the larger the informed group is the bigger portion of agents will move with the desired velocity. In the situation where the virtual leader travels with a varying velocity, we propose modification to the Olfati-Saber algorithm and show that the resulting algorithm enables the asymptotic tracking of the virtual leader. That is, the position and velocity of the center of mass of all agents will converge exponentially to those of the virtual leader. The convergent rate is also given.      

Gathering on rings under the Look–Compute–Move model

A set of robots arbitrarily placed on different nodes of an anonymous ring have to meet at one common node and there remain. This problem is known in the literature as the gathering. Anonymous and oblivious robots operate in Look–Compute–Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), decides whether to stay idle or to move to one of its neighbors (Compute), and in the latter case makes the computed move instantaneously (Move). Cycles are asynchronous among robots. Moreover, each robot is empowered by the so called multiplicity detection capability, that is, it is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one. The described problem has been extensively studied during the last years. However, the known solutions work only for specific initial configurations and leave some open cases. In this paper, we provide an algorithm which solves the general problem but for few marginal and specific cases, and is able to detect all the ungatherable configurations. It is worth noting that our new algorithm makes use of some previous techniques and unifies them with new strategies in order to deal with any initial configuration, even those left open by previous works.     

Adaptive role assignment for self-organized flocking of a real robotic swarm

Self-organized flocking of robotic swarms has been investigated for approximately 20 years. Most studies are based on a computer animation model named Boid. This model reproduces flocking motion by three simple behavioral rules: collision avoidance, velocity matching, and flock centering. However, flocking performance depends on how these rules are configured and no guideline for the configuration exists. This paper investigates real robot flocking where individuals can switch their roles depending on the situations. Robots can move as leaders or followers, and the roles are dynamically allocated using stochastic learning automata. The flocking performance is evaluated, and swarming behavior is analyzed in a scenario where robots consecutively travel between two landmarks.     

Fault-Tolerant Dynamic Rescheduling for Heterogeneous Computing Systems

As the scale and complexity of heterogeneous computing systems grow, failures occur frequently and have an adverse effect on solving large-scale applications. Hence, fault-tolerant scheduling is an imperative step for large-scale computing systems. The existing fault-tolerant scheduling algorithms belong to static scheduling, and they allocate multiple copies of each task to several processors no matter whether processor failures affect the execution of tasks. Such active replication strategies not only waste resource but also sacrifice the makespan. What is more, they cannot guarantee the successful execution of applications. In this paper, we propose a fault-tolerant dynamic rescheduling algorithm named FTDR, which can overcome above drawbacks. FTDR keeps listening to the processor failure, and reschedules the suspended tasks once failures occur. Because FTDR reschedules the tasks that are suspended because of failures, it can tolerate an arbitrary number of failures. Randomly generated DAGs are tested in our experiments. Experimental results show that the proposed algorithm achieves good performance in terms of makespan and resource consumption compared with its direct competitors.     

Symmetry position/force hybrid control for cooperative object transportation using multiple humanoid robots

A symmetry position/force hybrid control framework for cooperative object transportation tasks with multiple humanoid robots is proposed in this paper. In a leader-follower type cooperation, follower robots plan their biped gaits based on the forces generated at their hands after a leader robot moves. Therefore, if the leader robot moves fast (rapidly pulls or pushes the carried object), some of the follower humanoid robots may lose their balance and fall down. The symmetry type cooperation discussed in this paper solves this problem because it enables all humanoid robots to move synchronously. The proposed framework is verified by dynamic simulations.     

Operator Performance in Exploration Robotics

Mobile robots can accomplish high-risk tasks without exposing humans to danger: robots go where humans fear to tread. Until the time in which completely autonomous robots are fully deployed, remote operators will be required in order to fulfill desired missions. Remotely controlling a robot requires that the operator receives the information about the robot??s surroundings, as well as its location in the scenario. Based on a set of experiments conducted with users, we evaluate the performance of operators when they are provided with a hand-held-based interface or a desktop-based interface. Results show how performance depends on the task asked of the operator and the scenario in which the robot is moving. The conclusions prove that the operator??s intra-scenario mobility when carrying a hand-held device can counterbalance the limitations of the device. By contrast, the experiments show that if the operator cannot move inside of the scenario, his performance is significantly better when using a desktop-based interface. These results set the basis for a transfer of control policy in missions involving a team of operators, some equipped with hand-held devices and others working remotely with desktop-based computers.