A Winfield

62 %
38 %
Information about A Winfield

Published on January 7, 2008

Author: Elodie

Source: authorstream.com

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

Add a comment

Related presentations

Related pages

WinField - Home

WinField has the technical know-how, proprietary tools and research-based solutions you can trust for success today, tomorrow and beyond. Look to WinField ...
Read more

Winfield – Wikipedia

Winfield bezeichnet. Orte in den Vereinigten Staaten: Winfield (Alabama) Winfield (Arkansas) Winfield (Colorado) Winfield (Florida) Winfield (Georgia ...
Read more

Winfield (cigarette) - Wikipedia, the free encyclopedia

Winfield is a brand of cigarette that is popular in Australia and New Zealand. They are also sold in other markets in Europe, Canada, South Africa and Asia.
Read more

Town of Winfield

Town of Winfield 9th Annual Community Garage Sale! June 23rd, 24th, & 25th - click here for details and Garage Sale Application!
Read more

Winfield Scott - Wikipedia, the free encyclopedia

Winfield Scott (June 13, 1786 – May 29, 1866) was a United States Army general, and unsuccessful presidential candidate of the Whig Party in 1852.
Read more

WinField - FGEU

Power Transmission Lines and Stations. WinField computes electric and magnetic field distribution for high-voltage power lines, transformer substations and ...
Read more

WinField - Find A Retailer

WinField has the technical know-how, proprietary tools and research-based solutions you can trust for success today, tomorrow and beyond. Look to WinField ...
Read more

Winfield Scott – Wikipedia

Winfield Scott (* 13. Juni 1786 in Laurel Branch bei Petersburg, Dinwiddie County, Virginia; † 29. Mai 1866 in West Point, Orange County, New York) war ...
Read more

Winfield - Facebook

Get updates from Winfield on Facebook. Log in or sign up for Facebook today. Sign Up Log In
Read more

Online Buchhaltung | Start

Die ideale Online Buchhaltung für Unternehmer, Start-Ups und Freelancer...
Read more