A Winfield

Information about A Winfield

Published on January 7, 2008

Author: Elodie

Source: authorstream.com

Content

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 Emergent radial 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 Stable Behaviour-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 Logic to 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

Related presentations


Other presentations created by Elodie

microwave ovens
06. 11. 2007
0 views

microwave ovens

shrek friendship
25. 12. 2007
0 views

shrek friendship

Collections Strategic Planning
01. 10. 2007
0 views

Collections Strategic Planning

CIMMYT 02
04. 10. 2007
0 views

CIMMYT 02

Oceania PowerPoint Presentation
09. 10. 2007
0 views

Oceania PowerPoint Presentation

20010412Merit
02. 11. 2007
0 views

20010412Merit

Large Datasets in Flex
28. 11. 2007
0 views

Large Datasets in Flex

Belk
05. 11. 2007
0 views

Belk

VTKOverview
05. 11. 2007
0 views

VTKOverview

hazmat
07. 11. 2007
0 views

hazmat

BlastomycosisinDogs
16. 11. 2007
0 views

BlastomycosisinDogs

romanticismo
21. 11. 2007
0 views

romanticismo

section 4 eating out of home
30. 12. 2007
0 views

section 4 eating out of home

label flower parts
31. 12. 2007
0 views

label flower parts

Identifying Variables
01. 01. 2008
0 views

Identifying Variables

fullyear03
04. 12. 2007
0 views

fullyear03

regionsofvagrade4par tA
03. 10. 2007
0 views

regionsofvagrade4par tA

borghys
15. 11. 2007
0 views

borghys

TEQdesign
26. 11. 2007
0 views

TEQdesign

ONR Workshop 6 4 02
24. 12. 2007
0 views

ONR Workshop 6 4 02

CH12 R
24. 02. 2008
0 views

CH12 R

fomac intro
26. 02. 2008
0 views

fomac intro

buy used fire trucks
28. 02. 2008
0 views

buy used fire trucks

LangeNFAIS07
19. 02. 2008
0 views

LangeNFAIS07

ma
11. 03. 2008
0 views

ma

Geographic Mapping of SARS
12. 03. 2008
0 views

Geographic Mapping of SARS

goodwin
14. 03. 2008
0 views

goodwin

Strat Hu Res Manag in Eu
18. 03. 2008
0 views

Strat Hu Res Manag in Eu

ImportTeleSeminarPP
27. 03. 2008
0 views

ImportTeleSeminarPP

LM EIP presentation
17. 12. 2007
0 views

LM EIP presentation

Module3
30. 03. 2008
0 views

Module3

CCGS
13. 04. 2008
0 views

CCGS

d01 005i
01. 12. 2007
0 views

d01 005i

fo
27. 09. 2007
0 views

fo

earl miller
19. 11. 2007
0 views

earl miller

Lect01
12. 12. 2007
0 views

Lect01

carol peters
18. 12. 2007
0 views

carol peters

cit
28. 12. 2007
0 views

cit

YLACL62
20. 11. 2007
0 views

YLACL62

GTC Products Presentation
03. 01. 2008
0 views

GTC Products Presentation

Perth summary
01. 01. 2008
0 views

Perth summary

chapter 12 powerpoint i
12. 11. 2007
0 views

chapter 12 powerpoint i

You found a WHAT
08. 11. 2007
0 views

You found a WHAT

Hughes
05. 11. 2007
0 views

Hughes

Luncheon Keynote Address Kenyon
03. 01. 2008
0 views

Luncheon Keynote Address Kenyon