"Swarm robotics deals with the design, construction and deployment of large groups of robots that coordinate and cooperatively solve a problem or perform a task. It takes inspiration from natural self-organising systems such as social insects, fish schools or bird flocks, characterised by emergent collective behaviour based on simple local interaction rules. Typically, swarm robotics extracts engineering principles from the study of those natural systems, in order to provide multi-robot systems with similar abilities. This way, it aims to build systems that are more robust, fault-tolerant and flexible than single robots, and that can better adapt their behaviour to changes in the environment."
Five bullets frame the field:
These are the criteria to apply when asked "is this a swarm robotics system?". All five must hold.
Characteristics 3 and 4 are what make swarm robotics hard rather than merely multiple. A fleet of warehouse robots coordinated by a central server has many robots and is not a swarm. The constraint is not on the number of robots but on the absence of a global view — which is exactly why the collective behaviour has to emerge rather than be commanded.
The platform gallery in the lectures shows homogeneous swarms — jasmine, alice, kilobots, e-pucks, swarm-bots — and one heterogeneous swarm, the swarmanoid.
Six reasons, each with the one-line justification given in the slides:
| Property | Why |
|---|---|
| Parallelism | Different robots can perform different tasks at the same time |
| Fault tolerance | Simple agents are less prone to failure. When a robot breaks down another one can take over. No single point of failure |
| Cost | Simple robots are cheaper to build than complex robots |
| Scalability | Add more robots, get more work done |
| Robustness | Ability to cope with the loss of individuals |
| Flexibility | Capability of tackling a broad spectrum of different environments and tasks |
Notice that robustness and flexibility are two of the three properties the definition promised, and that they are the pair Chapter 1 listed as "still difficult to bring together". Swarm robotics is one of the course's two structural answers to that problem — the other being automatic design, Chapter 11. The two meet in the DEMIURGE project of section 8.
Swarm intelligence is collective intelligence emerging in groups of (simple) agents. Its roots are in models of social insect behaviour:
Properties of collective intelligence systems: distributed computation; direct and indirect interactions; agents equipped with simple computational capabilities; robustness; adaptiveness.
Self-organisation: dynamical mechanisms whereby structures appear at the global level from interactions among lower-level components.
Its signatures: creation of spatio-temporal structures; possible coexistence of several stable states (multistability); existence of bifurcations when some parameters are varied.
The example given is Bénard cells; further examples are synchronisation in fireflies, ant foraging and flocking. The lectures also introduce the vocabulary of upward and downward causation across levels of organization — the structure at the global level is caused by the components, and in turn constrains them.
Feedback returns here in the same words as Chapter 4: a feedback loop is a circular arrangement of causally connected elements; positive feedback is self-reinforcing (amplification of random fluctuations and structure formation, reinforcement of the most common behaviour patterns), negative feedback is self-regulating (saturation, competition, resource exhaustion), and complex systems are usually characterised by the presence of both.
These two words are worth understanding rather than reciting, because lab activity 6 makes you observe both. Multistability: with two identical black spots in the arena, the swarm aggregates on one of them — two stable states exist and the symmetry is broken by a fluctuation that positive feedback amplifies. Bifurcation: vary a parameter (say α) and the qualitative outcome changes — below a value no aggregate forms at all, above it aggregation is inevitable. That is a bifurcation, observed on a robot swarm.
Stigmergy is a kind of indirect communication used by social insects. One agent modifies the environment and the other agent reacts to the changed environment.
Stigmergy is the mechanism that makes characteristic 3 of section 1 — purely local communication — survivable. Two robots that never meet can still coordinate, provided one of them leaves a trace the other can read. The environment becomes a shared memory that no one owns and nobody has to maintain.
The notable ant behaviours listed in the deck are foraging, division of labour, collective transport and cluster formation — the first, second and fourth of which get a model in the next three sections.
The natural behaviour, in three lines:
The canonical experiment is the double bridge. The formal model views the trajectory of an ant as a sequence of discrete steps along a graph, one step being the traversal of one edge between two nodes. It has two main mechanisms:
The lectures add: these two mechanisms characterise many collective behaviour models. Once you have seen probabilistic choice plus two-signed feedback in foraging, you will recognise the same skeleton in the response-threshold model of section 6, in corpse clustering in section 7, and in the aggregation rule of lab activity 6.
The simple case, choosing among three nodes with pheromone levels τ1, τ2, τ3:
P(j) = tau_j / (tau_1 + tau_2 + tau_3)The typical case in applications, moving from node i to node j:
[tau_ij]^alpha [eta_ij]^beta
P(i -> j) = ------------------------------------ if j is feasible
SUM over feasible k of
[tau_ik]^alpha [eta_ik]^beta
P(i -> j) = 0 otherwisewhere τij is the amount of pheromone on edge (i, j), ηij is a heuristic value estimating the desirability of the edge, and α and β weight the relative influence of pheromone and heuristic.
Ant foraging models have been successfully used in optimization in a family of metaheuristics named Ant Colony Optimization. The state of the art named in the deck: MAX-MIN Ant System, Hyper-cube Framework, Multi-level ACO, Beam ACO (see M. Dorigo and T. Stützle, Ant Colony Optimization, The MIT Press, 2004).
Run the colony. Then turn evaporation off and watch the swarm lock onto whichever branch happened to be lucky first — the failure mode the lectures call premature convergence to low-quality solutions.
| Term | Definition |
|---|---|
| Division of labour | Different activities are performed simultaneously by specialised individuals |
| Task allocation | The process that leads to the assignment of one task to each individual of the colony |
Advantages in terms of efficiency:
There are several kinds of division of labour — reproductive, castes, tasks accomplished in the colony — and the ratios of workers performing the different tasks can also vary in time.
A simple model of task allocation:
Formally, for one task: let Si be the state of individual i (inactive: 0, active: 1), s the amount of stimulus corresponding to the task, and θi the response threshold of individual i — the higher θi, the lower the tendency to perform the task. An inactive individual starts performing the task with probability p per unit time:
p(S_i = 0 -> S_i = 1) = s^alpha / (s^alpha + theta_i^alpha)where α is a parameter. An active individual becomes inactive with probability p = p0 per unit time.
Nobody assigns anything. Each individual makes a private probabilistic decision from a private threshold, and the ratio of workers across tasks emerges — and self-corrects, because as workers engage, the stimulus falls, and fewer new workers engage. That is negative feedback doing task allocation without a scheduler.
Vary the stimulus, the threshold and α. Watch how α turns a soft preference into a near-switch — and how a population with different thresholds spontaneously splits into specialists and reserves.
Ants collect dead bodies and objects and aggregate them in clusters. The basic mechanism: clusters of items grow by attracting workers to deposit more items — positive feedback.
The model. Let f be the fraction of perceived items in the neighbourhood of the ant. Ants move randomly, and:
probability of pick-up: p_p = ( k_1 / (k_1 + f) )^2
probability of delivery: p_d = ( f / (k_2 + f) )^2where k1 and k2 are threshold constants.
Read the two formulas against each other. When f is small — the ant is in an empty region — pp is near 1 and pd is near 0: isolated items get picked up and are not dropped in the void. When f is large, the probabilities swap: items are dropped where items already are. The cluster grows itself.
Compare with the Swiss robot of Chapter 3, which also produced heaps. There, clustering came from a behavioural error exploiting sensor geometry, with no rule about items at all. Here it comes from two explicit probabilistic rules. Same observed structure, radically different mechanism — a clean illustration of the frame-of-reference warning that observed behaviour does not determine the underlying mechanism.
swarm-bots.org. Goal: study a novel approach to the design and implementation of self-organising and self-assembling artefacts. Institutes involved: IRIDIA (Université Libre de Bruxelles, Belgium), EPFL (Lausanne, Switzerland), IDSIA (Lugano, Switzerland), CNR-IP (Rome, Italy).
Further achievements of the project listed in the deck: hole/obstacle avoidance, finding object/goal, cooperative transport.
A group of robots involved in an object retrieval task, with a control system inspired by a model of ant foraging. Individuals adapt to the environment using only locally available information; this adaptation is an effective way to improve the efficiency of the group and brings forth division of labour between the members of the group. (T. H. Labella, M. Dorigo and J.-L. Deneubourg, Division of Labor in a Group of Robots Inspired by Ants' Foraging, ACM TAAS, Vol. 1, No. 1, September 2006, pp. 4–25.)
A model for real-world applications such as toxic-waste cleanup, search and rescue, demining or collection of terrain samples in unknown environments. The main scientific question is sharp and worth remembering:
Is there an actual performance gain in using more than one robot, since the task can be accomplished by a single one?
The setup uses simple robots with simple sensors and no communication, and the controller is designed as a probabilistic finite state automaton — the mechanism introduced in Chapter 6, now doing real work.
| State | Behaviour |
|---|---|
| Search | The robot looks for a prey, randomly exploring the environment and changing direction when it encounters an obstacle. If a prey is found, the robot grasps it. If a timeout occurs before the robot has grasped a prey, the robot gives up searching |
| Retrieve | The robot looks for the nest and pulls the prey toward it |
| Deposit | The robot leaves the prey in the nest and turns to the point from which it came (to mimic ants' behaviour) |
| Return | The robot looks for the nest and returns to it |
| Rest | The robot rests in the nest |
The adaptation. The robots change from Rest to Search with probability P1 each second. P1 is updated during the transitions from Search to Return (failure), and from Deposit to Rest (success). P1 is constrained to assume values in [Pmin, Pmax].
Experimental set-up: circular arena with a diameter of 2.40 metres; a light bulb to signal the position of the nest centre; search timeout 228 seconds; Pmin = 0.0015, Pmax = 0.05, Pinit = 0.033 — i.e. a mean time spent in the nest of approximately 11 minutes, 20 seconds and 30 seconds respectively; Δ = 0.005. Preys appear randomly in the environment during the experiments, with a density expressed as the probability of prey appearance per second. The results are reported as the distribution of P1 — the frequencies of P1 after 2400 s, i.e. the distribution of the probability to leave the nest.
| Project | What it is |
|---|---|
Swarmanoid (swarmanoid.org) | A swarm composed of heterogeneous robots, each equipped with a specific capability |
Symbrion (symbrion.eu) | A swarm of real robots undergoing online evolution by exchanging information in a decentralized evolutionary robotics scheme. The diffusion of each individual's genotype depends both on its ability to survive in an unknown environment and on its ability to maximize mating opportunities during its lifetime. An open-ended evolutionary approach |
Flora robotica (florarobotica.eu) | Named among the prominent works |
| Aerial swarms | See the work by Dario Floreano at EPFL |
DEMIURGE (demiurge.be) | Automatic design of robot swarms. An intelligent system able to design and realize robot swarms in a totally integrated and automatic way: starting from requirements expressed in an appropriate specification language, the DEMIURGE will design all aspects of a robot swarm — hardware and control software |
Symbrion is the exception that proves the rule of Chapter 3, section 4: evolutionary adaptation normally requires populations and generations, which is why it is done off-line. Symbrion gets around it by making the swarm itself the population — genotypes diffuse between robots during operation. Keep it in mind for Chapter 10, where on-board evolution is flagged as the hard case.
Models of division of labour in social insects are a useful way of designing controllers to solve task allocation problems. A related problem is task partitioning, in which the goal is to optimally partition the task into sub-tasks that can be tackled separately.
G. Pini, A. Brutschy, M. Frison, A. Roli, M. Dorigo and M. Birattari, Task partitioning in swarms of robots: an adaptive method for strategy selection, Swarm Intelligence (2011) 5:283–304.
The relevant quantities are Pp, the probability of choosing task partitioning, and Pgφstore, Pgφharvest, the probabilities of giving up the store and harvest sub-tasks.
L. Garattoni and M. Birattari, Autonomous task sequencing in a robot swarm, Science Robotics 3, 2018. A robot swarm able to collectively sequence tasks whose order of execution is not known a priori.
"The ability to plan emerges at the collective level from the interaction of reactive individuals."
This is a genuinely striking claim and a favourite discussion point. Chapter 13 will define planning as looking ahead at the outcomes of possible actions and searching for a sequence that reaches the goal — an activity that seems to demand a world model and deliberation. Here, individuals that are purely reactive nonetheless produce, collectively, an ordered sequence of task executions. Planning, like intelligence in Chapter 3, turns out to be describable at a level where no component is doing it.
Real-world applications of SR are still not many. The main current ones: underwater exploration and monitoring; lawn mowing. Future scenarios: heterogeneous robots, nanorobots, self-assembly.
Every one of these is a mechanism you already know: PFSA from Chapter 6, rules from Chapter 5, potential fields from Chapter 7, neural networks from Chapter 10. Swarm robotics does not introduce a new controller — it introduces a new design problem:
"The main difficulty in programming swarms of robots is that individual behaviours have to be programmed such that the desired collective behaviour emerges from the interactions among robots. A promising and viable alternative to manual programming consists in automatic or semi-automatic design."
That last sentence is the bridge to Chapter 11. Requirements are naturally expressed at the collective level, but the designer must eventually decide what each individual robot does; no general approach exists to derive the individual behaviour from the desired collective one. Automatic design attacks the problem by optimising the individual controller directly against a collective performance measure.
A typical task in SR is aggregation: the swarm behaviour consisting in gathering in one place. The informal model comes from the observation of social insects:
Let S ∈ [0,1] be the spontaneous stopping probability, W ∈ [0,1] the spontaneous walking probability, and N the number of nearby stopped robots:
Ps = min{ Psmax , S + alpha*N }
Pw = max{ Pwmin , W - beta*N }Ps = math.min(PSmax, S + alpha*N)
Pw = math.max(PWmin, W - beta*N)
-- Bernoulli decision with probability p
t = robot.random.uniform()
if t <= p then
...
else
...
endS, W, α, β, Psmax and Pwmin are parameters of the control software, and in general they depend upon the number of robots, the size of the arena and the maximal range used for the range-and-bearing. For a rectangular arena of 5 × 5 metres, at least 30 robots and a maximal range of 30 cm, the handout suggests starting with:
W = 0.1 S = 0.01 Psmax = 0.99 Pwmin = 0.005 alpha = 0.1 beta = 0.05Robots perceive their nearby companions by means of a range-and-bearing communication system, which allows localized communication: a robot receiving data from another also detects the position of the sender relative to its own local point of view. The handout is emphatic that this is not like WiFi:
Each received message is stored in a table composed of data (the 10-byte payload), horizontal_bearing (the angle between the robot's local x axis and the position of the message source, on the robot's xy plane, in radians), vertical_bearing, and range (the distance of the source in cm).
-- signal "I am stopped" on byte 1
robot.range_and_bearing.set_data(1, 1)
-- signal "I am moving"
robot.range_and_bearing.set_data(1, 0)
-- count the stopped robots sensed close by
function CountRAB()
number_robot_sensed = 0
for i = 1, #robot.range_and_bearing do
if robot.range_and_bearing[i].range < MAXRANGE and
robot.range_and_bearing[i].data[1] == 1 then
number_robot_sensed = number_robot_sensed + 1
end
end
return number_robot_sensed
endMAXRANGE can be initially set to 30 (cm). In ARGoS the sensor is declared with <range_and_bearing implementation="medium" medium="rab" />; by default a message sent by a foot-bot can be received up to 3 m, and the rab_range attribute changes it, e.g. <foot-bot id="fb" rab_range="1">.
Ps = min{Psmax, S + alpha*N + Ds} and Pw = max{Pwmin, W - beta*N - Dw}, where Ds and Dw are the probabilities of stopping (or remaining) on the black spot.Is the behaviour robust with respect to parameter values? What are the advantages and disadvantages of a collective choice? How would you bias the aggregation on a specific area of the arena? What are the pros and cons of distributed solutions with respect to centralised ones? Exercise 3 is the multistability of section 3 made experimental — two equivalent stable states, and a symmetry broken by amplified fluctuation.
Thirty robots, the two update rules, nothing else. Try α = 0 to remove the positive feedback, and watch aggregation fail to happen at all.
Swarm robotics deals with the design, construction and deployment of large groups of robots that coordinate and cooperatively solve a problem or perform a task, taking inspiration from natural self-organising systems characterised by emergent collective behaviour based on simple local interaction rules. Characteristics: robots are autonomous; they are situated and can act to modify the environment; their sensing and communication capabilities are local; they have no access to centralized control or global knowledge; they cooperate to carry on a given task.
Parallelism (different robots perform different tasks at the same time); fault tolerance (simple agents are less prone to failure, another can take over, no single point of failure); cost (simple robots are cheaper); scalability (add more robots, get more work done); robustness (cope with the loss of individuals); flexibility (tackle a broad spectrum of environments and tasks).
Self-organisation consists of dynamical mechanisms whereby structures appear at the global level from interactions among lower-level components. Signatures: creation of spatio-temporal structures; possible coexistence of several stable states (multistability); existence of bifurcations when some parameters are varied. Examples: Bénard cells, synchronisation in fireflies, ant foraging, flocking.
A kind of indirect communication used by social insects: one agent modifies the environment and the other agent reacts to the changed environment. It is what makes coordination possible under the constraint that sensing and communication are purely local — the environment acts as a shared memory that nobody owns.
The trajectory of an ant is viewed as a sequence of discrete steps along a graph. (1) Probabilistic choice rule: the choice of the next node favours edges with a higher amount of artificial pheromone. (2) Feedbacks: positive — the quantity of pheromone laid down depends on the quality of the path, so in a shortest-path task lower-cost paths are reinforced and attract more ants; negative — pheromone evaporates in time, which dampens the effect of random fluctuations that might lead to premature convergence to low-quality solutions.
P(i->j) = [tau_ij]^alpha [eta_ij]^beta / SUM_k [tau_ik]^alpha [eta_ik]^beta for feasible j, and 0 otherwise. τij is the amount of pheromone on edge (i,j); ηij is a heuristic value estimating the desirability of the edge; α and β weight the relative influence of pheromone and heuristic. In the simple three-node case this reduces to P(j) = tau_j / (tau_1 + tau_2 + tau_3).
Division of labour: different activities are performed simultaneously by specialised individuals. Task allocation: the process that leads to the assignment of one task to each individual of the colony. Task partitioning: optimally partitioning the task into sub-tasks that can be tackled separately. Division of labour is efficient because parallelism avoids task switching (which costs energy and time) and specialization enables high performance.
A stimulus is associated with a task; individuals start to be engaged when the stimulus exceeds a threshold. With Si the state of individual i (0 inactive, 1 active), s the stimulus and θi the response threshold (the higher θi, the lower the tendency to perform the task), an inactive individual becomes active with probability per unit time p = s^alpha / (s^alpha + theta_i^alpha), while an active individual becomes inactive with probability p0 per unit time.
With f the fraction of perceived items in the neighbourhood, and ants moving randomly: probability of pick-up p_p = (k1/(k1+f))^2, probability of delivery p_d = (f/(k2+f))^2, with k1 and k2 threshold constants. When few items are around, pick-up is likely and delivery unlikely, so isolated items are removed; where many items are around, the reverse, so items are deposited. Clusters grow by attracting workers to deposit more items — positive feedback.
Controller: a probabilistic finite state automaton with states Search, Retrieve, Deposit, Return, Rest. Robots move from Rest to Search with probability P1 each second; P1 is updated on the transitions Search→Return (failure) and Deposit→Rest (success), and constrained to [Pmin, Pmax]. Simple robots, simple sensors, no communication. The main scientific question: is there an actual performance gain in using more than one robot, since the task can be accomplished by a single one?
DEMIURGE is a project on the automatic design of robot swarms: an intelligent system able to design and realize robot swarms in a totally integrated and automatic way, designing all aspects of a swarm — hardware and control software — starting from requirements expressed in an appropriate specification language. It appears here because the main difficulty in programming swarms is that individual behaviours must be programmed so that the desired collective behaviour emerges, and automatic or semi-automatic design is the promising alternative to manual programming.
A robot swarm able to collectively sequence tasks whose order of execution is not known a priori. The key claim: the ability to plan emerges at the collective level from the interaction of reactive individuals — planning without any individual planner.
Ps = min{Psmax, S + alpha*N} and Pw = max{Pwmin, W - beta*N}, where N is the number of nearby stopped robots. The first is positive feedback: the more stopped neighbours, the more likely a robot is to stop. The second is negative feedback: robots at the boundary of a group perceive fewer neighbours, so their probability of leaving is higher than that of robots inside. Suggested starting values for a 5×5 m arena, at least 30 robots and 30 cm range: W = 0.1, S = 0.01, Psmax = 0.99, Pwmin = 0.005, α = 0.1, β = 0.05.
It provides localized communication: a receiving robot also detects the position of the sender relative to its own point of view. Unlike WiFi: robots exchange data only in direct line of sight (an object in between blocks it); senders can only broadcast in a limited area, so you cannot choose an addressee as with an IP address; and the payload is only 10 bytes. Each message carries data, horizontal_bearing, vertical_bearing and range.