Towards temporal verification of swarm robotic systems

A robot swarm is a collection of simple robots designed to work together to carry out some task. Such swarms rely on the simplicity of the individual robots; the fault tolerance inherent in having a large population of identical robots; and the self-organised behaviour of the swarm as a whole. Although robot swarms present an attractive solution to demanding real-world applications, designing individual control algorithms that can guarantee the required global behaviour is a difficult problem. In this paper we assess and apply the use of formal verification techniques for analysing the emergent behaviours of robotic swarms. These techniques, based on the automated analysis of systems using temporal logics, allow us to analyse whether all possible behaviours within the robot swarm conform to some required specification. In particular, we apply model-checking, an automated and exhaustive algorithmic technique, to check whether temporal properties are satisfied on all the possible behaviours of the system. We target a particular swarm control algorithm that has been tested in real robotic swarms, and show how automated temporal analysis can help to refine and analyse such an algorithm.     

A PSO-based algorithm designed for a swarm of mobile robots

This paper presents an algorithm called augmented Lagrangian particle swarm optimization with velocity limits (VL-ALPSO). It uses a particle swarm optimization (PSO) based algorithm to optimize the motion planning for swarm mobile robots. Considering problems with engineering constraints and obstacles in the environment, the algorithm combines the method of augmented Lagrangian multipliers and strategies of velocity limits and virtual detectors so as to ensure enforcement of constraints, obstacle avoidance and mutual avoidance. All the strategies together with basic PSO are corresponding to real situations of swarm mobile robots in coordinated movements. This work also builds a swarm motion model based on Euler forward time integration that involves some mechanical properties such as masses, inertias or external forces to the swarm robotic system. Simulations show that the robots moving in the environment display the desired behavior. Each robot has the ability to do target searching, obstacle avoidance, random wonder, acceleration or deceleration and escape entrapment. So, in summary due to the characteristic features of the VL-ALPSO algorithm, after some engineering adaptation, it can work well for the planning of coordinated movements of swarm robotic systems.     

A geometric approach to deploying robot swarms

We discuss the fundamental problems and practical issues underlying the deployment of a swarm of autonomous mobile robots that can potentially be used to build mobile robotic sensor networks. For the purpose, a geometric approach is proposed that allows robots to configure themselves into a two-dimensional plane with uniform spatial density. Particular emphasis is paid to the hole repair capability for dynamic network reconfiguration. Specifically, each robot interacts selectively with two neighboring robots so that three robots can converge onto each vertex of the equilateral triangle configuration. Based on the local interaction, the self-configuration algorithm is presented to enable a swarm of robots to form a communication network arranged in equilateral triangular lattices by shuffling the neighbors. Convergence of the algorithms is mathematically proved using Lyapunov theory. Moreover, it is verified that the self-reparation algorithm enables robot swarms to reconfigure themselves when holes exist in the network or new robots are added to the network. Through extensive simulations, we validate the feasibility of applying the proposed algorithms to self-configuring a network of mobile robotic sensors. We describe in detail the features of the algorithm, including self-organization, self-stabilization, and robustness, with the results of the simulation.     

基于改进免疫启发群聚集算法的群机器人自恢复方法

群机器人由许多简单的无差别的机器人组成,是多机器人系统的一个重要研究方向。虽然其相比个体机器人有良好的容错性和鲁棒性,但是在机器人发生局部故障--有信息交互能力但无驱动能力时,群机器人系统会受到影响。针 对这一问题,以基于生物免疫系统原理的肉芽肿形成算法为基础,引入离散粒子群算法选取最优的自恢复策略,使群机器人系统实现故障自恢复并更快更有效地完成任务。仿真实验结果表明该算法在群机器人自恢复系统中具有良好的效果。     

Get in touch: cooperative decision making based on robot-to-robot collisions

We demonstrate the ability of a swarm of autonomous micro-robots to perform collective decision making in a dynamic environment. This decision making is an emergent property of decentralized self-organization, which results from executing a very simple bio-inspired algorithm. This algorithm allows the robotic swarm to choose from several distinct light sources in the environment and to aggregate in the area with the highest illuminance. Interestingly, these decisions are formed by the collective, although no information is exchanged by the robots. The only communicative act is the detection of robot-to-robot encounters. We studied the performance of the robotic swarm under four environmental conditions and investigated the dynamics of the aggregation behaviour as well as the flexibility and the robustness of the solutions. In summary, we can report that the tested robotic swarm showed two main characteristic features of swarm systems: it behaved flexible and the achieved solutions were very robust. This was achieved with limited individual sensor abilities and with low computational effort on each single robot in the swarm.     

A macroscopic model for high intensity radiofrequency signal detection in swarm robotics systems

In recent years, there has been a growing interest in resource location in unknown environments for robotic systems, which are composed of multiple simple robots rather than one highly capable robot [M. Sempere, F. Aznar, M. Pujol, and R. Rizo, On cooperative swarm foraging for simple, non explicitly connected, agents, 2010]. This tradeoff reduces the design and hardware complexity of the robots and removes single point failures, but adds complexity in algorithm design. The challenge is to programme a swarm of simple robots, with minimal intercommunication and individual capability, to perform a useful task as a group. This paper is focused on finding the highest intensity area of a radiofrequency (RF) signal in urban environments. These signals are usually more intense near the city centre and its proximity, since in these zones the risk of signal saturation is high. RF radiation (RFR) is boosted or blocked mainly depending on orography or building structures. RF providers need to supply enough coverage, setting up different antennas to be able to provide a minimum quality of service. We will define a micro/macroscopic mathematical model to efficiently study a swarm robotic system, predict their long-term behaviour and gain insight into the system design. The macroscopic model will be obtained from Rate Equations, describing the dynamics of the swarm collective behaviour. In our experimental section, the Campus of the University of Alicante will be used to simulate our model. Three RFR antennas will be taken into account, one inside our Campus and the other two in its perimeter. Several tests, that show the convergence of the swarm towards the RFR, will be presented. In addition, the obtained RFR maps and the macroscopic behaviour of the swarm will be discussed.     

Perpetual Robot Swarm: Long-Term Autonomy of Mobile Robots Using On-the-fly Inductive Charging

Swarm robotics studies the intelligent collective behaviour emerging from long-term interactions of large number of simple robots. However, maintaining a large number of robots operational for long time periods requires significant battery capacity, which is an issue for small robots. Therefore, re-charging systems such as automated battery-swapping stations have been implemented. These systems require that the robots interrupt, albeit shortly, their activity, which influences the swarm behaviour. In this paper, a low-cost on-the-fly wireless charging system, composed of several charging cells, is proposed for use in swarm robotic research studies. To determine the system’s ability to support perpetual swarm operation, a probabilistic model that takes into account the swarm size, robot behaviour and charging area configuration, is outlined. Based on the model, a prototype system with 12 charging cells and a small mobile robot, Mona, was developed. A series of long-term experiments with different arenas and behavioural configurations indicated the model’s accuracy and demonstrated the system’s ability to support perpetual operation of multi-robotic system.     

Gradual spatial pattern formation of homogeneous robot group

This paper proposes a gradual formation of a spatial pattern for a homogeneous robot group. The autonomous formation of spatial pattern is one of key technologies for the advancement of cooperative robotic systems because a pattern formation can be regarded as function differentiation of a multi-agent system. When multiple autonomous robots without a given local task cooperatively work for a global objective, the function differentiation is the first and indispensable step. For example, each member of cooperative insects or animals can autonomously recognize own local tasks through mutual communication with local members. There were a lot of papers that reported a spatial pattern formation of multiple robots, but the global information was supposed to be available in their approaches. It is however almost impractical assumption for a small robot to be equipped with an advanced sensing system for global localization due to robot’s scale and sensor size. The local information-based algorithm for the pattern formation is desired even if each robot is not equipped with a global localization sensor.We therefore propose a gradual pattern formation algorithm, i.e., a group of robots improves complexity of their pattern from to a simple pattern to a goal pattern like a polygon. In the algorithm, the Turing diffusion-driven instability theory is used so that it could differentiate roles of each robot in a group based only on local information. In experiment, we demonstrate that robots can make a few polygon patterns from a circle pattern by periodically differentiating robot’s roles into a vertex or a side. We show utilities of the proposed gradual pattern formation algorithm for multiple autonomous robots based on local information through some experiments.     

Self-organized task allocation to sequentially interdependent tasks in swarm robotics

In this article we present a self-organized method for allocating the individuals of a robot swarm to tasks that are sequentially interdependent. Tasks that are sequentially interdependent are common in natural and artificial systems. The proposed method does neither rely on global knowledge nor centralized components. Moreover, it does not require the robots to communicate. The method is based on the delay experienced by the robots working on one subtask when waiting for input from another subtask. We explore the capabilities of the method in different simulated environments. Additionally, we evaluate the method in a proof-of-concept experiment using real robots. We show that the method allows a swarm to reach a near-optimal allocation in the studied environments, can easily be transferred to a real robot setting, and is adaptive to changes in the properties of the tasks such as their duration. Finally, we show that the ideal setting of the parameters of the method does not depend on the properties of the environment.     

A Framework for Augmented Reality using Non-Central Catadioptric Cameras

This paper proposes a strategy for a group of swarm robots to self-assemble into a single articulated(legged) structure in response to terrain difficulties during autonomous exploration. These articulated structures will have several articulated legs or backbones, so they are well suited to walk on difficult terrains like animals. There are three tasks in this strategy: exploration, self-assembly and locomotion. We propose a formation self-assembly method to improve self-assembly efficiency. At the beginning, a swarm of robots explore the environment using their sensors and decide whether to self-assemble and select a target configuration from a library to form some robotic structures to finish a task. Then, the swarm of robots will execute a self-assembling task to construct the corresponding configuration of an articulated robot. For the locomotion, with joint actuation from the connected robots, the articulated robot generates locomotive motions. Based on Sambot that are designed to unite swarm mobile and self-reconfigurable robots, we demonstrate the feasibility for a varying number of swarm robots to self-assemble into snake-like and multi-legged robotic structures. Then, the effectiveness and scalability of the strategy are discussed with two groups of experiments and it proves the formation self-assembly is more efficient in the end.     

Navigation strategy of multiple mobile robot systems based on the null-space projection method

This paper deals with a navigation algorithm for swarm robot systems in which multiple mobile robots work together. The motion of each mobile robot is modeled in such a way to have more inputs than the number of outputs. The null-space projection method of this model is employed to resolve the motion of the swarm robot system while avoiding obstacles. The feasibility of the proposed navigation algorithm is verified through a simulation study using several swarm robot models.     

目标围捕任务中搜索与预包围阶段的群机器人行为学习

为了进行群机器人协同作业,提出目标搜索中导航类集体行为学习策略.在使用具有闭环调节功能的动态任务分工方法进行任务分配、自组织地生成多个子群后,在子群中引入基于社会学习微粒群算法的机器人行为学习策略.在子群框架内,机器人各自独立地以感知的共同意向目标信号强度为标准对所有成员排序,将感知优于自己的机器人作为行为示范者.然后在搜索空间各维度上分别随机选择一个行为示范者,学习其在相应维度上的位置坐标,经构造得到搜索空间中自己的学习行为向量,由此决策自身的运动行为.仿真结果表明,在不需要学习全局社会经验的前提下,机器人能针对所属子群的共同意向目标进行协同作业,提高搜索效率.     

基于确定型有穷自动机的机器人行为控制单元

基于机器人基本行为的控制方法是机器人能够执行许多高级算法的基本条件,且能有效的减少重编程时的代码量,适用于大规模机器人群体中的无线程序烧录,减少通信量。针对课题研发的需求,提出一种基于确定型有穷自动机的机器人行为控制的数学模型,并使用Picoblaze处理器在FPGA上实现了该数学模型,实验表明本文的方法能大幅度的减少代码更新时的通信量。     

Efficient metaheuristics for pick and place robotic systems optimization

This paper deals with a pick and place robotic system design problem. The objective is to present an efficient method which is able to optimize the performances of the robotic system. By defining the suitable combination of scheduling rules, our method allows each robot to perform the assigned pick and place operations in real time in order to maximize the throughput rate. For that, we have developed different resolution methods which define the scheduling rule for each robot in order to seize the products from the first side of the system and to place them on the second side. We suggest three metaheuristics which are the ant colony optimization, the particle swarm optimization and the genetic algorithm. Then, we try to select the best algorithm which is able to get the best solutions with the lowest execution times. This is the main advantage of our methods compared to exact methods. This fact represents a great interest taking in consideration that our methods must respect a strong industrial constraint regarding the functioning of a real industrial robotic system. This constraint states that the answer time to manage the seizing strategies of the robots must be less than 1 second. Numerical results show that the different algorithms perform optimally for the tested instances in a reasonable computational time.     

Kilobot: A low cost robot with scalable operations designed for collective behaviors

In current robotics research there is a vast body of work on algorithms and control methods for groups of decentralized cooperating robots, called a swarm or collective. These algorithms are generally meant to control collectives of hundreds or even thousands of robots; however, for reasons of cost, time, or complexity, they are generally validated in simulation only, or on a group of a few tens of robots. To address this issue, this paper presents Kilobot, an open-source, low cost robot designed to make testing collective algorithms on hundreds or thousands of robots accessible to robotics researchers. To enable the possibility of large Kilobot collectives where the number of robots is an order of magnitude larger than the largest that exist today, each robot is made with only $14 worth of parts and takes 5 min to assemble. Furthermore, the robot design allows a single user to easily operate a large Kilobot collective, such as programming, powering on, and charging all robots, which would be difficult or impossible to do with many existing robotic systems. We demonstrate the capabilities of the Kilobot as a collective robot, by using a small robot test collective to implement four popular swarm behaviors: foraging, formation control, phototaxis, and synchronization.     

An algorithm for cooperative task allocation in scalable,constrained multiple robot systems

The current trends in the robotics field have led to the development of large-scale multiple robot systems, and they are deployed for complex missions. The robots in the system can communicate and interact with each other for resource sharing and task processing. Many of such systems fail despite the availability of necessary resources. The major reason for this is their poor coordination mechanism. Task planning, which involves task decomposition and task allocation, is paramount in the design of coordination and cooperation strategies of multiple robot systems. Task allocation mechanism allocates the task in a mission to the robots by maximizing the overall expected performance, and thereby reducing the total allocation cost for the team. In this paper, we formulate a heuristic search-based task allocation algorithm for the task processing in heterogeneous multiple robot system, by maximizing the efficiency in terms of both communication and processing cost. We assume a set of decomposed tasks of a mission, which needs to be allocated to the robots. The near-optimal allocation schemes are found using the proposed peer structure algorithm for the given problem, where the number of the tasks is more than the robots present in the system. The cost function is the summation of static overhead cost of robots, assignment cost, and the communication cost between the dependent tasks, if they are assigned to different robots. Experiments are performed to verify the effectiveness of the algorithm by comparing it with the existing methods in terms of computational time and quality of solution. The experimental results show that the proposed algorithm performs the best under different problem scales. This proves that the algorithm can be scaled for larger system and it can work for dynamic multiple robot system.     

Collective robotic search using hybrid techniques: Fuzzy logic and swarm intelligence inspired by nature

This paper presents two new strategies for navigation of a swarm of robots for target/mission focused applications including landmine detection and firefighting. The first method presents an embedded fuzzy logic approach in the particle swarm optimization (PSO) algorithm robots and the second method presents a swarm of fuzzy logic controllers, one on each robot. The framework of both strategies has been inspired by natural swarms such as the school of fish or the flock of birds. In addition to the target search using the above methods, a hierarchy for the coordination of a swarm of robots has been proposed. The robustness of both strategies is evaluated for failures or loss in swarm members. Results are presented with both strategies and comparisons of their performance are carried out against a greedy search algorithm.     

Telemanipulation of cooperative robots: a case of study

This article addresses the problem of dexterous robotic grasping by means of a telemanipulation system composed of a single master and two slave robot manipulators. The slave robots are analysed as a cooperative system where it is assumed that the robots can push but not pull the object. In order to achieve a stable rigid grasp, a centralised adaptive position-force control algorithm for the slave robots is proposed. On the other hand, a linear velocity observer for the master robot is developed to avoid numerical differentiation. A set of experiments with different human operators were carried out to show the good performance and capabilities of the proposed control-observer algorithm. In addition, the dynamic model and closed-loop dynamics of the telemanipulation is presented.     

绝对定位机制下目标位置估计辅助的群机器人搜索

基于扩展微粒群算法模型控制群机器人协同搜索目标时,成员机器人在社会经验和自身认知,主要是社会经验引导下逐步向目标趋近.由于社会经验仅从成员机器人的认知中“选举”产生,未形式化地融合多个机器人的经验,因此文中从群机器人通信子系统在本质上属于无线传感器网络的事实出发,引入集体决策机制,改进社会经验的生成模式.用无线传感器网络中的测距定位方法来估计目标位置,并将估计值作为社会经验引入现有模型.仿真结果表明,当群体规模够大时,采用文中社会经验生成模式可使协同搜索速度得到提高.