Collective Building and Self-Assembly in Natural and Artificial Systems. AM, EE141, Swarm Intelligence, W6-2

1 Collective Building and Self-Assembly in Natural and Artificial Systems AM, EE141, Swarm Intelligence, W6-22 Outline Collective building and self-as...

Author:  Toby O’Connor’
0 downloads 3 Views 9MB Size

Collective Building and Self-Assembly in Natural and Artificial Systems

AM, EE141, Swarm Intelligence, W6-2

Outline • Collective building and self-assembly in natural systems • • • •

Examples Mechanisms Modeling Reverse engineering with GA

• Collective building and self-assembly in artificial systems • Passive bricks • Active mechatronic units

Collective Building and Self-Assembly in Natural Systems

Natural Examples of Collective Building

© Guy Theraulaz

Natural Examples of Collective Building

© Guy Theraulaz

Natural Examples of Collective Building

© Guy Theraulaz

Natural Examples of Collective Building

© Guy Theraulaz

Natural Examples of Collective Building

© Guy Theraulaz

Natural Examples of Collective Building

© Pascal Goetgheluck

Natural Examples of Collective Building

© Pascal Goetgheluck

Natural Examples of Collective Building

© Pascal Goetgheluck

Natural Examples of Collective Building

© Masson

Natural Examples of Collective Building

© Masson

Natural Examples of Collective Digging

Coordination Mechanisms for the Building Activity

Collective Building Mechanisms

1

The plan

2

Environmental template

3

Stigmergy

Collective Building Mechanisms

© Scott Camazine

Collective Building Mechanisms The plan

Collective Building Mechanisms

1

The plan

2

Environmental template

3

Stigmergy

Collective Building Mechanisms Environmental template



The building plan pre-exists in the environment under the form of spatial heterogeneities.



The social insect activity only outlines these pre-existing environmental template. Environmental changes performed by insects play a minimal role in the building activity itself.



There are several forms of environmental template: • gradients naturally existing in the environment (humidity, temperature …) • chemical gradients generated by one or more individuals of the colony

Nest Structure in the Ant Acantholepis Custodiens T Eggs Larvae

Pupae

3.00 a.m.

3.00 p.m.

Convective Air Flows and Complex Chemical Templates

Convective Air Flows and Complex Chemical Templates

© Guy Theraulaz

Collective Building Mechanisms

1

The plan

2

Environmental template

3

Stigmergy

Stigmergy Definition



It defines a class of mechanisms exploited by social insects to coordinate and control their activity via indirect interactions.

Response Stimulus

R1 S1

R2 S2

R3 S3

R4 S4

R5 S5

Stop

time



Stigmergic mechanisms can be classified in two different categories: quantitative (or continuous) stigmergy and qualitative (or discrete) stigmergy

Stigmergy The role of the two different stigmergic mechanisms in collective building

1 Sequence of stimuli and answers quantitatively different Positive feedback and self-organization

2 Sequence of stimuli and answers qualitatively different

Quantitative Stigmergy Features



The successive stimuli quantitatively differentiate in their amplitude and merely modify the answer probability of other individuals



Examples : mass recruitment in ants dead ant aggregation in ant cemetery pillar building in termites

Quantitative Stigmergy Pillar building in termites Spatial distribution of insects and their building activity are locally controlled by the pheromone density.

• • • •

Termites impregnate with pheromones the building material Pheromones diffuse in the environment Individuals carrying ground bullets follow the chemical gradient; they climb towards the highest pheromonal concentration and drop there their bullets Material drop rate is proportional to the number of active insects in the local region (positive feedback)

Stigmergy The role of the two different stigmergic mechamisms in collective building

1 Sequence of stimuli and answers quantitatively different

2 Sequence of stimuli and answers qualitatively different Self-assembly process

Qualitative Stigmergy Features

• •

Successive stimuli are qualitatively different. This process generates a self-assembly dynamics. No pheromone involved? A

S1

B

S2

C

S3

••• time

Nest Building in Polist Wasps

© Guy Theraulaz

Nest Building in Polist Wasps

Organisation of the building activity



It is indirectly carried out via the different, local configurations a wasp can find in the nest



A probability of deposing a new cell is associated to each configuration

Nest Building in Polist Wasps Potential sites for building S1 S2

S2

S1

S1

S1

S2 S1

S3 S2 S1

S1

Nest Building in Polist Wasps Probability of creating a new cell given the configuration of neighboring cells 1 ,0 0 ,8 0 ,6 0 ,4 0 ,2 0 ,0 1 2 3 Number of adjacent cell walls

Nest-Building Modeling

Swarm on a 3D Lattice

A swarm of nest builders … agent features

• • • •

• • •

Reactive actions Random movements on a 3D lattice, no trajectories No embodiment (1agent = 1 single cell), no interference (however 2 agents cannot occupy the same cell) n agents working together means n actions (not necessarily n dropped bricks) before next iteration starts; all n agents see the same configuration at a given iteration Agents’ team is homogeneous No global plan of the whole building Local perception of the environment

Swarm on a 3D Lattice Definition of agent ’s neighborhood for hexagonal cells The neighborhood of each agent is defined as the 20 cells around it (7 above, 6 around, and 7 below). z+1

z+1

z

z

0 2 2

z-1

0 2

Neighborhood

z-1

0 1 1

2 X

A

2 2

0 1

2 X

1

Cell contents

2

2 2

1 1

Swarm on a 3D Lattice Distributed nest building: several sites are active simultaneously

Swarm on a 3D Lattice Examples of building rules

Z+1

z

Z-1



Building process is irreversible (no cell can be removed)



Deposit rules can be strictly deterministic or probabilistic

Swarm on a 3D Lattice Example of a rule set (Polist wasps, 7 rules)

Swarm Intelligence: Bonabeau et al

Figure 6.9

Nest-building Modeling

Obtained structures (Polists wasps, 7 rules)

With deterministic rules

With probabilistic rules

Looking for Stable Nest Architectures What kind of nest architectures can we build with the same method?



What are the rules to implement in order to obtain stable architectures?



An architecture is considered stable when several runs of a simulation with the same rule set generate architectures with the same global structure.



Mechanisms of stigmergic coordination reduce the number of stable architectures.

Examples of Stable Architectures

Agelaia (13 rules)

Examples of Stable Architectures Parachatergus (21 rules)

Vespa (13 rules)

Stelopolybia (12 rules)

Examples of Stable Architectures

Chatergus (39 rules)

Artificial Nest Structure (35 rules)

Looking for Stable Nest Architectures How to build a stable architecture?



The building process is carried out in successive steps. The current local configuration generate a stimulus different from that of the previous and of the successive configuration (qualitative stigmergy).



Only this type of building algorithms generate coherent architectures.



The whole set of these algorithms generates a limited number of nest shapes.

Reverse-Engineering: From the Building to the Individual Rules using GA

Similarities to Controller Evolution Prey-Predator (GA, Floreano 98)

Obstacle avoidance (RL, Kelly 97)

Area Integration (RL,Versino 97) Exploration (RL, Hayes 01) Nest-building (Bonabeau, GA 00)

Exploration (RL, Millan 97)

Foraging (GA, Jefferson 93)

Evolutionary Encoding of the Distributed Nest Building Problem • Phenotype: agent endowed with set of microrules • Genotype: set of microrules (one-to-one mapping with phenotype); chromosome of variable length; 1 gene = 1 microrule. • Life span: number of iteration (e.g. 30,000 iterations, 1 iteration = all 10 agents have applied their microrule) or exhausting of max amount of bricks available (e.g. 500 bricks). • Population: 80 individuals • Generations: 50 • Fitness function: weighted sum of space filling and pattern replication (arbitrary criteria based on 17 human observers who were asked to evaluate the amount of structure in a set of 29 different patterns, [Bonabeau 2000]); • Selection: roulette wheel • Crossover: two-points, pcrossover = 0.2 • Mutation: pmutation1 = 0.9 (during life span inactive microrule); pmutation2 = 0.01 (during life span active microrule).

Figure 6.12

Swarm Intelligence: Bonabeau et al

Evolutionary Encoding of the Distributed Nest Building Problem

• Biased evolution: • Probabilistic templates (reduction of stimulating configurations containing a large number of bricks). • Start microrule. • No diagonal deposits (space not filled).

• Problems: • Fitness function: Functional? Esthetical? Biological plausible? Mathematical definition? • Episthatic interactions (sequence of microrules needed for coordinated algorithms).

Collective Building and Self-Assembly in Artificial Systems

Applications • Obstacle avoidance in highly constrained and unstructured environments • Formation of bridges, buttresses, stairs and other structures for emergencies • Envelopment of objects – Recovering satellites from space

• Inspections in constrained environments – Nuclear reactors

• Self-organizing unfolding structures – Space stations – Satellites – Scaffolds

Passive Bricks

Passive Bricks • In-line 2D structures using Kheperas [Martinoli 99] -> [Easton ??] • Lionel Penrose (1898 – 1972) • Self-assembly mechanisms of genetic relevant molecules reproduced with passive wood bricks • External energy source (shaking, human action) • Evolution and self-assembly tightly coupled • Video-tape!

Passive Bricks Evolutionary architecture: Nicolas Reeves (UQAM Montreal, Canada) • Cellular automata approach. • No genetic operator: population manager replaced by direct intervention of the human being.

3D CAD simulations

Stereolytographic sculptures

Passive Bricks Evolutionary architecture: Pablo Funes (Brandeis University, US) • GA approach, geometry- and force-based fintness functions • Off-board evolution and reproduction of results with Lego® bricks • 2D (bridge, crane) and 3D structures (table)

Set-up and objective

Diagram of forces

Passive Bricks Evolutionary architecture: Pablo Funes (Brandeis University, US) 2D Ex.: Bridge

Simulated bridge

Real Lego bridge

Passive Bricks Evolutionary architecture: Pablo Funes (Brandeis University, US)

2D Ex.: Crane

3D Ex.: Table

Active Mechatronic Units

MEL

Mechanical Engineering Laboratory

Research on Self-Reconfigurable Mechatronic Systems in MEL Eiichi Yoshida Satoshi Murata Haruhisa Kurokawa Kohji Tomita Shigeru Kokaji http://www.mel.go.jp/

MEL

Mechanical Engineering Laboratory

Self-Reconfigurable Mechatronic Systems

• Distributed mechanical system • composed of many identical units • using local communication only • dynamically reconfigurable • Self-assembly / Self-repair

arbitrary initial state

trouble

self-assembly

cut off

self-repair using spare units

MEL

Mechanical Engineering Laboratory

Self-Reconfigurable Mechatronic Systems

difference / diffusion var. per units

• Self-assembly and Self-repair

6.0 5.0 4.0 3.0 2.0 1.0 0.0

remove difference diffusion var.

0

100

200

300 Step

MEL

Mechanical Engineering Laboratory

2D Self-Reconfigurable Systems

SMA Torsion Coil Springs

SMA Coil Spring

Vertical Direction

Pin holes pin

Female: Auto-locking (releasing by SMA)

Male: Rotating Drum

Weight: 50[g] (approx. ) Span: 50[mm] Basic Motion

MEL

Mechanical Engineering Laboratory

2D Self-Reconfigurable Systems

• Experiment using 6 units

Initial

Moving Unit

Final

MEL

Mechanical Engineering Laboratory

2D Self-Reconfigurable Systems

MEL

Mechanical Engineering Laboratory

3D Self-Reconfigurable Systems

• Basic Motion

A

MEL

Mechanical Engineering Laboratory

3D Self-Reconfigurable Systems

Grey: distance from target different from zeo -> to be moved Green: distance from target = 0 -> ok! Red: current moved unit (once at the time)

MEL

Mechanical Engineering Laboratory

3D Self-Reconfigurable Systems

• 3D Mechanical Unit

connecting hand

rotating arm

span: 27.5cm weight: 6.8kg DC motor: 7W

Modular Robotics (PolyPod) Mark Yim (Stanford University, Xerox Park Research Center, 1994- …)

Parallel structure, 10 links

Two types of modules: segment and nodes • Nodes: power modules • Segments: HC11 microcontroller, angle position (potentiometer), IR local communication

Modular Robotics (PolyPod) Mark Yim (Stanford University, Xerox Park Research Center, 1994- …)

Modular Robotics (PolyBot) Mark Yim (Stanford University, Xerox Park Research Center, 1994- …) The future … PolyBot

This generation of PolyBot included onboard computing (Power PC 555) as well as the ability to reconfigure automatically via shape memory alloy (SMA) actuated latches.

Self-Configurable and Modular Robotics

Other researchers: • Hajime Asama, RIKEN Center, Saitama, Japan • http://www.riken.go.jp/eng/index.html • Distributed assembling and disassembling of stair-like structures

• Peter Will and Wei-Min Shen, ISI-USC, L.A.,US • http://www.isi.edu/conro • Modular robotics

Crystalline Atomic Modular Selfreconfigurable Robot • http://www.ai.mit.edu/~vona/xtal • Autonomous self-reconfiguring robots • Simulator (Xtalsim) created – 2D and 3D

• Automated planning algorithm developed – Melt-Grow planner: O(n2) for n atoms

Conclusion

Self-Assembly, Distributed Building, Modular Robotics Very promising domain but • System design and hardware development are crucial • Energetic problem still unsolved • Scalability and distributed control still unsolved problems: how to control individual units for obtaining a given team performance?

Evolution and bio-inspiration can help: incremental/modular evolution, reverse engineering

Life Enjoy

" Life is not a problem to be solved but a reality to be experienced! "

Get in touch

Social

© Copyright 2013 - 2019 DOKUMENTIS.COM - All rights reserved.