Towards Dependable Swarms

Alan FT Winfield

Intelligent Autonomous Systems Lab

http://www.ias.uwe.ac.uk/

The IAS Laboratory

This talk

Swarm Engineering

What is a dependable swarm?

Processes for assuring dependability

Analysis, design and test

Case study (work in progress)

A minimalist coherent swarm of wireless networked mobile robots

To illustrate (Structured) Swarm Engineering

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 this work is to develop a framework for the analysis, design and test of dependable swarms

I propose to call this framework Swarm Engineering

Analysis

Design

Test

Assurance of Dependability

What makes swarm engineered systems different?

System functionality achieved through emergence

Swarms are highly dynamical, often chaotic, systems

Task completion becomes hard to define.

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

Design

Structured Design Methodology

Use Waterfall (v-shaped) model?

Robot design

Swarm design

Problematical because there are 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

Test

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

Case Study:
Swarm Containment

Consider using a swarm robotics approach to physical containment or encapsulation:

Containment of marine pollution or hazards

In vivo nano-bots, artificial phagocyte

Emergent encapsulation

Coherent Swarming of Wireless Networked Mobile Robots

The 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

Knowledge only of neighbourhood connectivity

Simple uni-sensor for 'beacon' detection

A minimalist swarm intelligence approach gives

Swarm coherence

Emergent taxis towards the beacon; emergent beacon encapsulation

Robustness and scalability

(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

Simulation

For proof-of-concept prototyping of basic algorithms

and to understand the design and parameter space

e.g. Distance to Beacon:

Run movie:

taxisobst15.avi

Back

(Dynamic) Data Flow Diagram

Robot 1

Robot 3

Robot 2

Robot 5

Robot 4

Data (Message) Flows

Between neighbours

Wireless

Range

Single Robot Processes

Behaviour-

based

Control

Process

UDP

Message

Server

Neighbourhood

Connectivity

Messages from

Neighbours

Messages to

Neighbours

Level 1 process

Level 2 process

Back

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

Forward

Halt

b

a

c

Spin

Network Behaviour

Avoidance Behaviour

Back

Provably Stable
Behaviour-based Control

Avoidance Behaviour

Network Behaviour

S

Actuators

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

Colony-style control architecture

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

Back

Physical Implementation

Experimental platform: the LinuxBot

Back

Run movies

n2th2.avi

n7th2c50.avi

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

Back

A roadmap towards dependable swarms

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 methodologies and practices for the testing of swarm engineered systems

Acknowledgements: Chris Harper and Julien Nembrini

Note that typically a swarm doesn't stop when it has finished. When tasks are emergent consequences, task completion becomes something which is only in the eye of the beholder

The framework proposed in this talk is sketchy and full of holes

Towards Dependable Swarms

Alan Winfield

2004-03-05T18:09:53