Computation-free swarming

We present a solution to the problem of self-organised aggregation of embodied robots that requires no arithmetic computation.

The robots have no memory and are equipped with one binary sensor, which informs them whether or not there is another robot in their line of sight. It is proven that the sensor needs to have a sufficiently long range; otherwise, aggregation cannot be guaranteed, irrespective of the controller used.

The optimal controller is found by performing a grid search over the space of all possible controllers. With this controller, robots rotate on the spot when they perceive another robot, and move backwards along a circular trajectory otherwise. This controller is proven to always aggregate two simultaneously moving robots in finite time, an upper bound for which is provided.

Simulations show that the controller also aggregates at least 1,000 robots into a single cluster consistently. Moreover, in thirty experiments with forty physical e-puck robots, 98.6% of the robots aggregated into one cluster.

The results obtained have profound implications for the implementation of multi-robot systems at scales where conventional approaches to sensing and information processing are no longer applicable.

  1. Spatial Coverage Without Computation ICRA 2019, in Press
  2. Finding Consensus Without Computation IEEE Robotics and Automation Letters, 3(3):1346-1353, 2018 (PDF, 640KB)
  3. Shepherding with Robots That Do Not Compute ECAL 2017 (PDF, 772KB)
  4. Clustering Objects with Robots That Do Not Compute AAMAS 2014 (PDF, 3.1MB)
  5. Self-Organised Aggregation without Computation. The International Journal of Robotics Research, 33(8):1145-1161, 2014 (PDF, 2.5MB)

Return to menu

Modular hydraulic propulsion

This paper introduces the concept of Modular Hydraulic Propulsion, in which a modular robot that operates in a fluid environment moves by routing the fluid through itself.

The robot's modules represent sections of a hydraulics network. Each module can move fluid between any of its faces. The modules (network sections) can be rearranged into arbitrary topologies. We propose a decentralised motion controller, which does not require modules to communicate, compute, nor store information during run-time.

We use 3-D simulations to compare the performance of this controller to that of a centralised controller with full knowledge of the task. We also detail the design and fabrication of six 2-D prototype modules, which float in a water tank. Results of systematic experiments show that the decentralised controller, despite its simplicity, reliably steers modular robots towards a light source.

Modular Hydraulic Propulsion could offer new solutions to problems requiring reconfigurable systems to move precisely in 3-D, such as inspection of pipes, vascular systems or other confined spaces.

  1. Modular hydraulic propulsion: a robot that moves by routing fluid through itself ICRA 2016, IEEE (2016) 5189-5196 (PDF, 5.96MB)

Return to menu 

Turing Learning (metric-free machine learning)

We propose Turing Learning, a novel system identification method for inferring the behaviour of natural or artificial systems. Turing Learning simultaneously optimises two populations of computer programs, one representing models of the behaviour of the system under investigation, and the other representing classifiers.

By observing the behaviour of the system as well as the behaviours produced by the models, two sets of data samples are obtained. The classifiers are rewarded for discriminating between these two sets, that is, for correctly categorising data samples as either genuine or counterfeit. Conversely, the models are rewarded for 'tricking' the classifiers into categorising their data samples as genuine.

Unlike other methods for system identification, Turing Learning does not require predefined metrics to quantify the difference between the system and its models. We present two case studies with swarms of simulated robots and prove that the underlying behaviours cannot be inferred by a metric-based system identification method. By contrast, Turing Learning infers the behaviours with high accuracy. It also produces a useful by-product - the classifiers - that can be used to detect abnormal behaviour in the swarm.

Moreover, we show that Turing Learning also successfully infers the behaviour of physical robot swarms. The results show that collective behaviours can be directly inferred from motion trajectories of individuals in the swarm, which may have significant implications for the study of animal collectives.

Furthermore, Turing Learning could prove useful whenever a behaviour is not easily characterisable using metrics, making it suitable for a wide range of applications.

Return to menu 

OpenSwarm operating system

OpenSwarm is an easy-to-use event-driven preemptive operating system for miniature robots. It offers abstract hardware-independent functions to make user code more extendible, maintainable, and portable.

More to follow!

1. OpenSwarm: an event-driven embedded operating system for miniature robots IROS 2016, IEEE (2016) 4483-4490

Return to menu 

Supervisory control theory applied to swarm robotics

Currently, the control software of swarm robotics systems is created by ad hoc development. This makes it hard to deploy these systems in real-world scenarios. In particular, it is difficult to maintain, analyse, or verify the systems.

Formal methods can contribute to overcome these problems. However, they usually do not guarantee that the implementation matches the specification, because the system's control code is typically generated manually. Also, there is cultural resistance to apply formal methods; they may be perceived as an additional step that does not add value to the final product.

To address these problems, we propose supervisory control theory for the domain of swarm robotics. The advantages of supervisory control theory, and its associated tools, are a reduction in the amount of ad hoc development, the automatic generation of control code from modelled specifications, proofs of properties over generated control code, and the reusability of formally designed controllers between different robotic platforms.

These advantages are demonstrated in four case studies using the e-puck and Kilobot robot platforms. Experiments with up to six hundred physical robots are reported, which show that supervisory control theory can be used to formally develop state-of-the-art solutions to a range of problems in swarm robotics.

Supervisory Control Theory Applied to Swarm Robotics Swarm Intelligence, 10(1):65-97, 2016 (PDF, 2.17MB)

Return to menu 

Cooperative transport of tall objects (plus feasibility study in a domestic environment)

This paper proposes a strategy for transporting a large object to a goal using a large number of mobile robots that are significantly smaller than the object.

The robots only push the object at positions where the direct line of sight to the goal is occluded by the object. This strategy is fully decentralised and requires neither explicit communication nor specific manipulation mechanisms. We prove that it can transport any convex object in a planar environment.

We implement this strategy on the e-puck robotic platform and present systematic experiments with a group of twenty e-pucks transporting three objects of different shapes. The objects were successfully transported to the goal in forty-three out of forty-five trials.

When using a mobile goal, teleoperated by a human, the object could be navigated through an environment with obstacles. We also tested the strategy in a 3-D environment using physics-based computer simulation. Due to its simplicity, the transport strategy is particularly suited for implementation on microscale robotic systems.

  1. Occlusion-based cooperative transport with a swarm of miniature mobile robots IEEE Transactions on Robotics, 31(2):307-321, 2015 
  2. A Strategy for Transporting Tall Objects with a Swarm of Miniature Mobile Robots Proc. of the 2013 IEEE Int. Conf. on Robotics and Automation, ICRA 2013 (2013), 863-869

Return to menu 

Human-robot swarm interaction with limited situational awareness

This paper studies how an operator with limited situational awareness can collaborate with a swarm of simulated robots.

The robots are distributed in an environment with wall obstructions. They aggregate autonomously but are unable to form a single cluster due to the obstructions. The operator lacks the bird's-eye perspective, but can interact with one robot at a time, and influence the behaviour of other nearby robots.

We conducted a series of experiments. They show that untrained participants had marginal influence on the performance of the swarm. Expert participants succeeded in aggregating 85% of the robots while untrained participants, with a bird's-eye view, succeeded in aggregating 90%. This demonstrates that the controls are sufficient for operators to aid the autonomous robots in the completion of the task and that lack of situational awareness is the main difficulty.

An analysis of behavioural differences reveals that trained operators learned to gain superior situational awareness.

  1. Human-robot swarm interaction with limited situational awareness ANTS 2016, volume 9882 of LNCS, Springer (2016) 125-136 doi>
  2. Using Google Glass in human-robot swarm interaction TAROS 2016, volume 9716 of LNAI, Springer (2016) 282-287
  3. Human management of a robotic swarm TAROS 2016, volume 9716 of LNAI, Springer (2016) 196-201 

Return to menu 

Modular reconfigurable robots with high-speed genderless connectors

The practical effectiveness of modular robotic systems depends heavily on the connection mechanisms used to join their separate entities, particularly for those systems capable of self-reconfiguration.

This work presents HiGen, a high-speed genderless mechanical connection mechanism for the docking of robotic modules. HiGen connectors can join with one another in a manner that allows either side to disconnect in the event of failure.

During connection electrical contacts are mated, supporting the concurrent use of local and global communication protocols, as well as power-sharing techniques. Rapid actuation of the mechanism allows connections to be made and broken at a speed that is, to our knowledge, an order of magnitude faster than existing mechanical genderless approaches that feature single-sided disconnect, benefiting the reconfiguration time of modular robots.

The HiGen connector is intended for future work in modular robotics, but could also see use in other areas of robotics for tool and payload attachment.

  1. HyMod: A 3-DOF hybrid mobile and self-reconfigurable modular robot and its extensions DARS 2016, in press
  2. HiGen: A High-Speed Genderless Mechanical Connection Mechanism with Single-Sided Disconnect for Self-Reconfigurable Modular Robots IROS 2014, IEEE (2014) 3926-3932 (PDF, 3.6MB)

Return to menu 

Artificial life

We propose an experimental study where simplistic organisms rise from inanimate matter and evolve solely through physical interactions.

These organisms are composed of three types of macroscopic building blocks floating in an agitated medium. The dynamism of the medium allows the blocks to physically bind with and disband from each other. This results in the emergence of organisms and their reproduction. The process is governed solely by the building blocks' local interactions in the absence of any blueprint or central command.

We demonstrate the feasibility of our approach by realistic computer simulations and a hardware prototype. Our results suggest that an autonomous evolution of non-biological organisms can be realised in human-designed environments and, potentially, in natural environments as well.

  1. Evo-bots: A simple, stochastic approach to self-assembling artificial organisms DARS 2016, in press
  2. Towards an Autonomous Evolution of Non-Biological Physical Organisms Lecture Notes in Computer Science, 5777:173-180, 2011 (PDF, 0.99MB

Return to menu 

Self-folding modular robots

We are currently developing a self-folding modular robotic system. The system can transform from 2-D configurations to 3-D configurations. This is work in progress, jointly undertaken by Ahmed and Chris.

Return to menu

Spatial segregation based on the Brazil nut effect

We study a simple algorithm inspired by the Brazil nut effect for achieving segregation in a swarm of mobile robots.

The algorithm lets each robot mimic a particle of a certain size and broadcast this information locally. The segregation task requires the swarm to self-organise into a spatial arrangement in which the robots are ranked by particle size (eg annular structures or stripes).

Using a physics-based computer simulation, we study the segregation performance of swarms of fifty mobile robots. We show that the system is very robust to noise on inter-robot perception and communication. Moreover, we investigate a simplified version of the control algorithm, which does not rely on communication.

Finally, we show that the mean percentage of errors in rank decreases exponentially as the particles' size ratio increases.

  1. Segregation in Swarms of e-puck Robots Based On the Brazil Nut Effect Proc. of the 11th Int. Conf. on Autonomous Agents and Multiagent Systems, AAMAS 2012 (2012) 163-170 (PDF, 2.3MB)
  2. Segregation in swarms of mobile robots based on the Brazil nut effect Proc. of the 2009 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, IROS 2009 (2009) 4349-4356 (PDF, 568KB)

Return to menu 

Self-assembly at the macroscopic scale

We have reviewed half a century of research on the design of systems displaying (physical) self-assembly of macroscopic components.

We report on the experience gained in the design of twenty-one such systems, exhibiting components ranging from passive mechanical parts to mobile robots. We present a taxonomy of the systems and discuss design principles and functions.

Finally, we summarise the main achievements and indicate potential directions for future research.

  1. Self-Assembly at the Macroscopic Scale Proceedings of the IEEE, 96(9):1490-1508, 2008 (PDF, 3.7MB)

Return to menu 

Simple learning rules to cope with changing environments

We consider an agent that must choose repeatedly among several actions. Each action has a certain probability of giving the agent an energy reward, and costs may be associated with switching between actions. The agent does not know which action has the highest reward probability, and the probabilities change randomly over time.

We study two learning rules that have been widely used to model decision-making processes in animals - one deterministic and the other stochastic. Over relatively short periods of time, both rules are successful in enabling agents to exploit their environment.

Moreover, under a range of effective learning rates, both rules are equivalent, and can be expressed by a third rule that requires the agent to select the action for which the current run of unsuccessful trials is shortest. However, the performance of both rules is relatively poor over longer periods of time, and under most circumstances no better than the performance an agent could achieve without knowledge of the environment.

We propose a simple extension to the original rules that enables agents to learn about and effectively exploit a changing environment for an unlimited period of time.

  1. Simple learning rules to cope with changing environments Journal of the Royal Society Interface, 5(27):1193-1202, 2008 (PDF, 424KB)

Return to menu 

Cooperation in groups of solitary or social individuals (evolution of self-assembly)

We simulate a system of simple, insect-like robots that can move autonomously and grasp objects as well as each other. We use artificial evolution to produce solitary transport and group transport behaviours.

We show that robots, even though not aware of each other, can be effective in group transport. Group transport can even be performed by robots that behave as in solitary transport. Still, robots engaged in group transport can benefit from behaving differently from robots engaged in solitary transport.

Moreover, we provide evidence that self-assembly can provide adaptive value to individuals that compete in an artificial evolution based on task performance.

Return to menu 

Self-assembly with swarm-bot

We report on experiments in which we study the process that leads a group of robots to self-assemble. In particular, we present the results of experiments in which we vary the number of robots (up to 16 physical robots, and up to 100 in simulation), their starting configurations, and the properties of the terrain on which self-assembly takes place.

In view of the very successful experimental results, swarm-bot qualifies as the current state of the art in autonomous self-assembly.

  1. Autonomous Self-Assembly in Swarm-Bots IEEE Transactions on Robotics, 22(6):1115-1130, 2006 (PDF, 1.45MB)
  2. Autonomous Self-assembly in a Swarm-bot Proc. of the 3rd Int. Symp. on Autonomous Minirobots for Research and Edutainment, Springer (2006) 314-322 (PDF, 708KB)

Return to menu 

Collective choices in house-hunting ants

Many decisions involve a trade-off between commitment and flexibility.We show here that the collective decisions ants make over new nest sites are sometimes sufficiently flexible that the ants can change targets even after an emigration has begun.

Our findings suggest that, in this context, the ants' procedures are such that they can sometimes avoid 'negative information cascades' which might lock them into a poor choice. The ants are more responsive to belated good news of a higher quality nest than they are when the nest they had initially chosen degraded to become worse than an alternative.

Our study confirms, in a new way, that ant colonies can be very powerful 'search engines'.

Return to menu 

Division of labour in self-organised groups

In social insect colonies, many tasks are performed by higher-order group or team entities, whose task solving capacities transcend those of the individual participants. In this paper, we investigate the emergence of such higher-order entities.

We report on an experimental study in which a team of physical robots performs a foraging task. The robots are ``identical'' in hardware and control. They make little use of memory and take actions purely on the basis of local information. Our study advances the current state of the art in swarm robotics with regard to the number of real-world robots engaging in teamwork (up to 12 robots in the most challenging experiment).

To the best of our knowledge, in this paper we present the first self-organised system of robots that displays a dynamical hierarchy of teamwork (with cooperation also occurring among higher-order entities).

Our study shows that teamwork requires neither individual recognition nor differences between individuals. This result might also contribute to the ongoing debate on the role of these characteristics in the division of labour in social insects.

  1. Teamwork in Self-Organized Robot Colonies IEEE Transactions on Evolutionary Computation, 13(4):695-711, 2009 (PDF, 2MB)
  2. Division of Labour in Self-Organised Groups Lecture Notes in Artificial Intelligence, 5040:426-436, 2008 (PDF, 748KB)
  3. Group Transport Along a Robot Chain in a Self-Organised Robot Colony Proc. of the 9th Int. Conf. on Intelligent Autonomous Systems, IOS Press (2006) 433-442 (PDF, 1028KB)

Return to menu 

Cooperative transport of objects of different shapes and sizes

We examine the ability of a swarm robotic system to transport cooperatively objects of different shapes and sizes.

We simulate a group of autonomous mobile robots that can physically connect to each other and to the transported object. Controllers - artificial neural networks - are synthesised by an evolutionary algorithm. They are trained to let the robots self-assemble, that is, organise into collective physical structures, and transport the object towards a target location.

We quantify the performance and the behaviour of the group. We show that the group can cope fairly well with objects of different geometries as well as with sudden changes in the target location. Moreover, we show that larger groups, which are made of up to 16 robots, make possible the transport of heavier objects.

Finally, we discuss the limitations of the system in terms of task complexity, scalability, and fault tolerance, and point out potential directions for future research.

  1. Towards group transport by swarms of robots Int. J. Bio-Inspired Computation, , 1(1-2):1-13, 2009 (PDF, 477KB)
  2. Cooperative Transport of Objects of Different Shapes and Sizes Lecture Notes in Computer Science, 3172:106-117, 2004 (PDF, 165KB)

Return to menu 

Object transport by modular robots that self-assemble

We present a first attempt to accomplish a simple object manipulation task using the self-reconfigurable robotic system swarm-bot.

The number of modular entities involved, their global shape or size and their internal structure are not pre-determined but result from a self-organised process in which the modules autonomously grasp each other and/or an object. The modules are autonomous in perception, control, action, and power.

We present quantitative results, obtained with six physical modules, that confirm the utility of self-assembling robots in a concrete task.

  1. Object Transport by Modular Robots that Self-assemble Proc. of the 2006 IEEE Int. Conf. on Robotics and Automation, IEEE (2006) 2558-2564 (PDF, 626KB)
  2. Cooperation through self-assembly in multi-robot systems ACM Transactions on Autonomous and Adaptive Systems, 1(2):115-150, 2006 (PDF, 2.6MB)

Return to menu 

Self-assembly with a super-mechano Colony

We show that a control algorithm for autonomous self-assembly can be ported from a source multi-robot platform (ie the swarm-bot system) to a different target multi-robot platform (ie a super-mechano colony system).

Although there are substantial differences between the two robotic platforms, it is possible to qualitatively reproduce the functionality of the source platform on the target platform. Therefore, the transfer does neither require modifications in the hardware nor an extensive redesign of the control.

The results of a set of experiments demonstrate that a controller that was developed for the source platform lets robots of the target platform self-assemble with high reliability.

  1. Self-assembly of Mobile Robots - From Swarm-bot to Super-mechano Colony Proc. of the 9th Int. Conf. on Intelligent Autonomous Systems, IOS Press (2006) 487-496 (PDF, 664KB)

Return to menu 

Evolving self-organising behaviours

In this paper, we introduce a self-assembling and self-organising artifact, called a swarm-bot, composed of a swarm of s-bots, mobile robots with the ability to connect to and to disconnect from each other.

We discuss the challenges involved in controlling a swarm-bot and address the problem of synthesizing controllers for the swarm-bot using artificial evolution. Specifically, we study aggregation and coordinated motion of the swarm-bot using a physics-based simulation of the system.

Experiments, using a simplified simulation model of the s-bots, show that evolution can discover simple but effective controllers for both the aggregation and the coordinated motion of the swarm-bot. Analysis of the evolved controllers shows that they have properties of scalability, that is, they continue to be effective for larger group sizes, and of generality, that is, they produce similar behaviours for configurations different from those they were originally evolved for.

  1. Evolving Self-Organizing Behaviors for a Swarm-bot Autonomous Robots, 17(2-3):223-245, 2004 
  2. Evolving Aggregation Behaviors in a Swarm of Robots Lecture Notes in Artificial Intelligence, 2801:865-874, 2003 (PDF, 220KB)

Return to menu 

Fault tolerance in groups of physically assembled robots

We address the problem of how a group of mobile robots can self-assemble into physical structures that cooperatively transport a heavy object towards a target location. We examine the situation that some robots of the transport structure exhibit partial failure, that is, they are unable to perceive the target location.

We compare the performance of this system with the performance of systems in which the robots that are unable to perceive the target location (i) exhibit complete failure (they are switched off); (ii) get manually removed from the experiment; and (iii) get replaced by fully functional robots.

Robots unable to perceive the target location can, by interacting with other members of the group, contribute to task performance, that is, achieve a performance superior to that of a passive caster.

  1. Group Transport of an Object to a Target that Only Some Group Members May Sense Lecture Notes in Computer Science, 3242:852-861, 2004 (PDF, 228KB)
  2. Transport of an Object by Six Pre-attached Robots Interacting via Physical Links Proc. of the 2006 IEEE Int. Conf. on Robotics and Automation, IEEE (2006) 1317-1323 (PDF, 638KB)

Return to menu 

Adaptive all-terrain navigation

We study the problem of functional self-assembling. The task we consider requires a group of robots to navigate over an area of unknown terrain towards a target light source.

If possible, the robots should navigate to the target independently. If, however, the terrain proves too difficult for a single robot, the group should self-assemble into a larger entity and collectively navigate to the target.

  1. Self-Assembly Strategies in a Group of Autonomous Mobile Robots Autonomous Robots, 28(4):439-455, 2010 (PDF, 1.56MB)
  2. Self-assembly on demand in a group of physical autonomous mobile robots navigating rough terrain Lecture Notes in Artificial Intelligence, 3630:272-281, 2005 (PDF, 4.2MB)
  3. Performance Benefits of Self-Assembly in a Swarm-Bot Proc. of the 2007 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, IEEE (2007) 2381-2387

Return to menu 

Pattern formation

This study is about pattern generation in robotic swarm.

Using self-organised principles we can let robots form patterns such as chains, clusters and center-periphery. The study is carried out in a simple grid-based simulation environment. Additionally, a mathematical model is proposed.

  1. Modeling Pattern Formation in a Swarm of Self-Assembling Robots. Technical Report TR/IRIDIA/2002-12, IRIDIA, Université Libre de Bruxelles, Brussels, Belgium (2002) (PDF, 452KB)

Return to menu 

Negotiation of goal direction for cooperative transport

In this paper, we study the cooperative transport of a heavy object by a group of robots towards a goal.

We investigate the case in which robots have partial and noisy knowledge of the goal direction and can not perceive the goal itself. The robots have to coordinate their motion to apply enough force on the object to move it. Furthermore, the robots should share knowledge in order to collectively improve their estimate of the goal direction and transport the object as fast and as accurately as possible towards the goal.

We propose a bio-inspired mechanism of negotiation of direction that is fully distributed. Four different strategies are implemented and their performances are compared on a group of four real robots, varying the goal direction and the level of noise.

  1. Negotiation of goal direction for cooperative transport Lecture Notes in Computer Science, 4150:191-202, 2006 (PDF, 1067KB)

Return to menu 

Evolving chess playing programs

EvoChess is a scientific experiment that uses Internet-connected computers for the evolution of chess playing programs.

You can participate by running qoopy, an environment for distributed computing as done by EvoChess. The users can start their own evolution to develop a variety of chess programs. The better ones will survive and produce offspring, who inherit their successful behavior encoded in their genotype.

  1. Evolving chess playing programs Proc. of the Genetic and Evolutionary Computation Conf., Morgan Kaufmann (2002) 740-747 (PDF, 364KB)

Return to menu

Project updates

Natural Robotics Lab: investigating robotic systems inspired by nature, and robotic models of natural systems.

A global reputation

Sheffield is a research university with a global reputation for excellence. We're a member of the Russell Group: one of the 24 leading UK universities for research and teaching.