A Winfield

From Swarm Intelligence to Swarm Engineering: 

From Swarm Intelligence to Swarm Engineering Alan FT Winfield Intelligent Autonomous Systems Lab www.ias.uwe.ac.uk out of the lab and into the real world

This talk: 

This talk Questions: How can we design swarm intelligence in a methodologically rigorous way? How can we formally prove or validate swarm engineered systems? This talk The IAS lab Case study: a wireless connected swarm Swarm Engineering

The IAS Laboratory: 

The IAS Laboratory

Swarm Robotics: 

Swarm Robotics [Melhuish] [Wessnitzer, Melhuish] Collective sorting Emergent formation

A Lighter Than Air Web Server: 

A Lighter Than Air Web Server [Welsby]

The Flying Flock: 

The Flying Flock [Welsby, Melhuish, Winfield]

Energy Autonomy: SlugBot: 

Energy Autonomy: SlugBot [Kelly, Holland ]

Energy Autonomy: EcoBot: 

Energy Autonomy: EcoBot [Greenman, Melhuish, Ieropoulos]

The Whiskerbot: 

The Whiskerbot www.whiskerbot.org [Melhuish, Pipe, Pearson, Gilhespy et al]

A case study in Swarm Robotics: hypothesis… : 

A case study in Swarm Robotics: hypothesis… “That it is possible to maintain swarm integrity using wireless networking alone” In other words: Is it possible to use wireless networking as a structural component in building multi-robot systems..? We seek simple rules linking locomotion with communications To create emergent swarm coherence and Scalable control of swarm morphology [Nembrini, PhD Thesis 2004]

A Minimalist Approach: 

A Minimalist Approach Robots have Range limited, omni-directional wireless communications Situated communications Robots can transmit their identity But signal strength not available No global positional information No range or bearing sensors Only local knowledge of network topology

Primitive behaviour: i: 

Primitive behaviour: i 1. Connected 2. Connection Lost Continuous PING: send Are You There, respond with Yes I’m Here

Primitive behaviour: ii: 

Primitive behaviour: ii 3. Turn Back 4. Reconnected, choose New Heading Continuous PING: send Are You There, respond with Yes I’m Here

Basic Algorithm: 

Basic Algorithm Extend the basic primitive to multiple robots… React to the number of neighbours in range, i.e. the number of connections K

Swarm division: 

Swarm division But the basic algorithm cannot prevent swarm division…

Shared Neighbour Algorithm: 

Shared Neighbour Algorithm If you lose a connection to robot N, find how many of your still connected neighbours have N in their neighbour lists: nShared If nShared drops below β, turn back If K is rising, choose new random heading

Area Control: 

Area Control The single parameter β controls determines the swarm coverage

Area control examples: 

Area control examples Swarm disposition for β = 1, β = 4

Directed Swarming: 

Directed Swarming Consider now the problem of directing the swarm (taxis) toward a beacon We could introduce differential sensing into one individual But this is highly dependent on signal-to-noise ratio …and completely fails to exploit the spatial distribution of the swarm Instead give each robot a simple binary sensor (illuminated or not illuminated)

Emergent swarm taxis: 

Emergent swarm taxis For the illuminated (red) robots set the value of β to infinity The red robots then shrink together to form a complete graph Reds become blues, which become more mobile, resulting in… slow translation toward the beacon beacon Red: illuminated Blue: occluded

Swarm taxis with obstacles: 

Swarm taxis with obstacles Introduce occluding obstacles The swarm finds it way between the narrow obstacles beacon

Encapsulation of the beacon: 

Encapsulation of the beacon An unexpected emergent phenomenon…

Swarm morphology control: 

Swarm morphology control By introducing a differential velocity between illuminated and occluded robots we have emergent morphology control

Emergent concentric symmetry: 

Emergent concentric symmetry 2 cell types 3 cell types

Emergentradial symmetry: 

Emergent radial symmetry

Physical Implementation: 

Physical Implementation Experimental platform: the LinuxBot Play: n2th2 n7th2c50

What is a Dependable Swarm?: 

What is a Dependable Swarm? It is a complex distributed system, designed using the Swarm Intelligence paradigm, which meets standards of analysis, design and test that would give sufficient confidence that the system could be employed in critical applications Q: What are these standards? A: They don't exist The purpose of our current work is to develop a framework for the analysis, design and test of dependable swarms I propose to call this framework Swarm Engineering [Winfield et al, LNCS 3342, 2005]

Assurance of Dependability: 

Analysis Design Test Assurance of Dependability What makes swarm engineered systems different? System functionality achieved through emergence Swarms are dynamical, stochastic, non-linear systems Task completion becomes very hard to define.

Designing the Swarm: 

Designing the Swarm Structured Design Methodology Use Waterfall (v-shaped) model? Robot design Swarm design Problematical because there are (as yet) no principled approaches to the design of emergence Ideally we need a formal, provable approach to the design of individuals within the swarm Swarm design and robot design are tightly coupled

(Structured) Swarm Engineering: 

(Structured) Swarm Engineering Swarm Design Robot Implementation Swarm Test Swarm Analysis Swarm Test Specification Requirements Specification Dependable Swarm Top down Functional Decomposition Bottom up Integration and Test Robot Design / Analysis Robot Test Robot Design Specification RTS Single Agent Engineering Morphology/Behaviours Working Robots Code Simulation

(Dynamic) Data Flow Diagram: 

(Dynamic) Data Flow Diagram Robot 4 Data (Message) Flows Between neighbours Wireless Range Robot 3 Robot 5 Robot 2 Robot 1

Single Robot Processes: 

Single Robot Processes Behaviour- based Control Process UDP Message Server Neighbourhood Connectivity Messages from Neighbours Messages to Neighbours Level 1 process Level 2 process

Provably StableBehaviour-based Control: 

We extend Lyapunov stability theory to second-order stability theorems then use the partial subsumption relationship between the 1st and 2nd order Lyapunov stability theorems as the basis for a formal model of the subsumption architecture Provably Stable Behaviour-based Control Avoidance Behaviour Network Behaviour S Actuators Colony-style control architecture

Direct Lyapunov Design: 

Direct Lyapunov Design We use the 2nd order Lyapunov stability theorems as the basis for a design procedure for the motor schema of a behaviour module Model the Open- Loop Dynamics Define goal state S and its neighbourhood For each point in the grid select a control action Define a piecewise map function and define a grid of points over the neighbourhood select control actions that yield the most stabilising behaviour according to 2nd order stability theorems in which grid points are the central states of each i/o pair and their associated selected actions are the function outputs [Harper and Winfield, accepted for RAS]

Swarm modelling and analysis: 

Swarm modelling and analysis Liveness the property of exhibiting desirable behaviours Safety the property of not exhibiting undesirable behaviours Simulation Mathematical Modelling Single Robot Multiple Robots + Hazard Analysis Random errors Systematic (design) errors Single Robot Multiple Robots

State Transition Diagram: 

State Transition Diagram Turn back Reverse Random turn All paths blocked Fwd blocked rear path clear Obstacle left or right front Swarm Lost Swarm Found b a c Spin Network Behaviour Avoidance Behaviour

Modelling: 

Modelling Current work is attempting to model the wireless connected swarm, by extending the probabilistic approach of Martinoli et al. Take the Finite State Machine then express as an ensemble of probabilistic FSMs: Coherence Forward Avoid The basic FSM

Probabilistic FSM: 

Probabilistic FSM Each box represents the number of robots in the swarm: in a given state, and with a given number of connections The PFSM thus describes the state/ connection structure of the swarm Using the modelling approach of Martinoli et al [IJR, 2004]

Hazards: 

Hazards Failure Modes and Effects Analysis (FMEA)

FSM with hazards: 

FSM with hazards Coherence Forward Avoid H1: motor failure Pl Pa PH1 PH1 PH1 H2: Pa=0 H3: Pl=1, Pr=0 Pr H4: all systems failure PH4

Using Temporal Logicto Specify Emergent Behaviours: 

Using Temporal Logic to Specify Emergent Behaviours We are investigating the use of a Linear Time Temporal Logic to specify (and possibly prove) emergent properties NASA have explored formal methods within the Autonomous Nano-Technology (ANTS) project (Rouff et al, 2004) however that work did not investigate a temporal logic

Swarm specification: 

Swarm specification Specify the safety and liveness properties of each robot (in terms of lower level behaviours) Then specify the Swarm as the logical ‘and’ of all the robots

Specification of Emergent Properties: 

Specification of Emergent Properties First specify the emergent properties Now attempt to prove (or disprove) that the swarm of robots satisfies the emergent behaviours [Winfield, Sa et al, accepted for Taros 05]

Testing the Swarm: 

Testing the Swarm System Test (swarm) Component Test (single robot) Witness tests against a System Test Specification (STS) Tests for Liveness Tests for (partial) Safety Tolerance and robustness to random errors (and threats) Dynamic/Static Analysis + Problematical because of the need to create test harnesses

Testing the swarm: 

Testing the swarm We need to establish robust measures for achievement of desired (emergent) behaviours, then define (statistical) test for these measures Qe – Mean quality of encapsulation Re – Mean radius of encapsulation Vs – Mean swarm velocity toward target Frequency that Qe>Qthreshold in a given time period for given starting conditions

Swarm Tests in progress: 

Swarm Tests in progress

Swarm tests can provide an environment for single robot test: 

Swarm tests can provide an environment for single robot test State;position;heading; sensor readings;connectivity Actual behaviour Expected behaviour Pass/Fail Controlled Swarm Tests Swarm test results Single robot simulation Single Robot Tests

A roadmap towards swarm engineering: 

A roadmap towards swarm engineering Substantial work is needed before dependable swarms can become reality We need to extend and strengthen analytical approaches to modelling of swarm systems We need to extend and strengthen formal approach to provably stable intelligent control To include safety as well as liveness We need a more principled approach to the design of emergence We need to start work on 'safety' analysis at the swarm level We need to develop metrics, methodologies and practices for the testing of swarm engineered systems

Discussion: 

Discussion But... can or should we really think about classical approaches to system validation in the context of swarm engineering? some in classical safety systems believe the standard approach is already breaking down for very complex (conventional) systems perhaps a new engineering paradigm calls for new approaches to dependability?

IAS lab acknowledgements: 

IAS lab acknowledgements Prof Owen Holland Prof Andrew Adamatzky Prof Chris Melhuish Prof John Greenman Dr Tony Pipe Dr Ben de Lacy Costello Dr Ian Kelly Dr Julien Nembrini Dr Jan Wessnitzer Dr Chris Harper Ioannis Ieropoulos Jason Welsby Ian Horsfield Ian Gilhespy

And finally, back to the future…: 

And finally, back to the future… Bristol Pioneer, Dr W Grey Walter Machina Speculatrix