代写代考 Introduction Routing Clustering and Sorting Architecture Social Robotics – cscodehelp代写
Introduction Routing Clustering and Sorting Architecture Social Robotics
Swarm Intelligence BIC
Marc de Group University of Leeds
Lecture 2 – Collective Behaviour and Swarm Intelligence
Copyright By cscodehelp代写 加微信 cscodehelp
Marc de Kamps
BIC-Lecture 2
Introduction Routing Clustering and Sorting Architecture Social Robotics
1 Introduction
Applications
Clustering and Sorting
4 Architecture
Social Robotics
Marc de Kamps
BIC-Lecture 2
Introduction
Routing Clustering and Sorting Architecture Social Robotics
Command & Control vs. self-organisation The sophisticated abilities of insect colonies
Algorithms inspired by insect intelligence
Clustering &
Swarming & Flocking
Insect-like social robots sorting & clustering
cooperative transport
Marc de Kamps
BIC-Lecture 2
Introduction
Routing Clustering and Sorting Architecture Social Robotics
These slides are based on: Original slides:
Lectures based to a large extent on the book ’Swarm Intelligence’ by Bonabeau, Dorigo & Theraulaz (Santa Fe Institute Studies in the Sciences of Complexity)
BIC-Lecture 2
Marc de Kamps
Introduction
Routing Clustering and Sorting Architecture Social Robotics
Amazonian Categorisation
Imagine you are faced with the task of organising a huge number of Amazonian species. There are hundreds of ways in which these species might be divided up: colour, size, etc.
Your boss tells you that your categorisation will have to match that of his customers over a very long time scale, so it must be flexible, because not only will customers change, but species may also change (colour, size, prevalence, etc.).
One approach to this knowledge management problem is to interview customers, devise a general-purpose, explicit categorisation scheme, pay someone to keep it up to date, and hope customers and species change little and slowly.
amazon.com solve an analogous problem like this: “Customers who bought this book, also bought …”
BIC-Lecture 2
Marc de Kamps
Introduction
Routing Clustering and Sorting Architecture Social Robotics
Amazonian Self-Organisation
Why is this automatic categorisation approach successful? no need to interview customers
no need to discover explicit categories before using them adapts to changing trends automatically as they happen
In contrast, “command and control” approaches suffer from the problem that explicit, hand-designed categorisations …
may be hard to discover through customer interrogation will require constant updating and may still be out of date may sometimes require a radical overhaul
adapts to changing trends automatically as they happen
In the next few lectures, we will learn that simple, self-organising systems such as amazon.com’s often enjoy advantages over their command and control cousins …
BIC-Lecture 2
Marc de Kamps
Introduction
Routing Clustering and Sorting Architecture Social Robotics
Advantages
These systems tend to involve many partially independent entities working together to solve a problem without a central executive. Each entity may be unaware of many or all of its colleagues, attending to only its local environment. Such systems are:
parallel systems
robust to noise & damage
dynamic flexible self-organising
possibly complex
hard to build?
hard to understand?
fast, cheap,out of control?
BIC-Lecture 2
Marc de Kamps
Introduction
Routing Clustering and Sorting Architecture Social Robotics
Foraging for the shortest route
A particularly striking result from ant experimentation concerns the ability of a colony to discover the shortest routes to the resources it requires:
As ants forage they deposit a trail of slowly evaporating pheromone.
Those that reach the food first return before the others.
One pheromone trail is now stronger than the other than the other, directing the ants to the food via the
shorter route.
BIC-Lecture 2
Marc de Kamps
Introduction
Clustering and Sorting Architecture Social Robotics
Applications
Foraging for the shortest route
A particularly striking result from ant experimentation concerns the ability of a colony to discover the shortest routes to the resources it requires:
It is not just ants that need to find optimal pathways. Traf- fic on telecommunications sys- tems, the Internet, roads, rail, and sea would all benefit from the reduction in congestion that efficient routing algorithms could provide.
Marc de Kamps
BIC-Lecture 2
Introduction
Clustering and Sorting Architecture Social Robotics
Applications
Can we understand the principle?
The details of pheromone secretion and perception are not well understood. Can we test our understanding in indirect ways? Consider the following observation of route choices:
After initial fluctuations the ants settle on a path.
Marc de Kamps
BIC-Lecture 2
Introduction
Clustering and Sorting Architecture Social Robotics
Applications
A simple model
Let Ai and Bi be the number of ants that have taken branch A and B, respectively: Now assign a probability:
PA = (k + Ai )n
(k +Ai)n +(k +Bi)n
Generate a random number 0 ≤ δ ≤ 1.
Ai+1 ,δ≤PA Ai+1 = Ai ,δ>PA
Marc de Kamps
BIC-Lecture 2
Introduction
Clustering and Sorting Architecture Social Robotics
Applications
Comparison
Values for k and n are chosen to match the experimental data:
Togivek ≈20andn≈2
Marc de Kamps
BIC-Lecture 2
Introduction
Clustering and Sorting Applications Architecture
Social Robotics
Do we understand foraging?
Consider the three foraging patterns below:
Three species of ants
Common ancestor
Can the difference in foraging patterns be explained by difference in food preference and the associated differences in distribution of food?
BIC-Lecture 2
Marc de Kamps
Introduction
Clustering and Sorting Applications Architecture
Social Robotics
Method: Simulation
Create a grid, update in discrete time steps
On their way out ants deposit 1 unit of pheromone (if
uph ≤ 1000)
On their way back they deposit 10 units of pheromone (if uph ≤ 300)
Ants returning to the nest are loaded with one prey item
BIC-Lecture 2
Marc de Kamps
Introduction
Clustering and Sorting Applications Architecture
Social Robotics
Method: Simulation
Move: pm = 1 1+tanh(ρl+ρr −1)
Left or Right: p =
both full, don’t move
Different distributions of food, large sites or small sites. An ant always returns with 1 item
100 (5+ρl )2
(5+ρl )2 +(5+ρr )2
No more than 20 ants per site. If left site is full go right and vv. If
BIC-Lecture 2
Marc de Kamps
Introduction
Clustering and Sorting Architecture Social Robotics
Applications
The main factor influencing this distribution patterns is the food distribution. The predictions from these sim- ulations have led to the ex- perimental manipulation of the food distribution of E. burchelli swarms. this has turned the forage pattern into that of other swarms. (Franks et al. 1991).
Marc de Kamps
BIC-Lecture 2
Introduction
Clustering and Sorting Architecture Social Robotics
Applications
Is this Intelligent?
A series of interesting experimental manipulations:
Marc de Kamps
BIC-Lecture 2
Introduction
Clustering and Sorting Architecture Social Robotics
Applications
A Minimal Spanning Tree?
Marc de Kamps
BIC-Lecture 2
Introduction
Clustering and Sorting Applications
Architecture Social Robotics
1 Introduction
Applications
Clustering and Sorting
4 Architecture
Social Robotics
Marc de Kamps
BIC-Lecture 2
Introduction
Clustering and Sorting Architecture Social Robotics
Applications
Ant-inspired routing
Consider an in-car system that suggests the best route to take for any
journey from A to B across a road network.
An “ant” traverses the net-
work following the strongest pheromone trails from A to B. At the end of the journey the ant lays down pheromone along the path taken, leaving less pheromone at nodes that were congested. In this way, routes via congested nodes are grad- ually weakened, prompting ants to take alternative paths.
Since many ants traverse the network constantly and their pheromone evaporates gradually, the system
automatically adapts to the current load on the road network.
Marc de Kamps BIC-Lecture 2
Introduction
Clustering and Sorting Applications
Architecture Social Robotics
Ant-inspired Routing
Consider a simple network and a routing table:
There is a row for every neighbour There is a column for every destination
rij is the probability for choosing neighbour i as the next in the chain to destination node j
BIC-Lecture 2
Marc de Kamps
Introduction
Clustering and Sorting Applications
Architecture Social Robotics
Ant-inspired Routing
Each node i has a capacity Ci , spare capacity Si
Calls are deterministic, use the entry with the highest value No spare capacity: call rejected
Ants move probabilistic
BIC-Lecture 2
Marc de Kamps
Introduction
Clustering and Sorting Applications
Architecture Social Robotics
Ant-inspired Routing
Ants launched: any moment, any node
Ants select their route probabilistically, weighted according to routing table entry.
When an ant reaches destination, it is removed.
BIC-Lecture 2
Marc de Kamps
Introduction
Clustering and Sorting Architecture Social Robotics
Applications
Ant-inspired Routing
Ants drop ’pheromone’ in the routing table entry of the node it just came from Let i − 1 be the node it just came from and i be the current
node at time t.
rii−1,s(t + 1) = rii−1,s(t) + δr 1+δr
Other rows are diminished to conserve probability:
ri (t+1)= k,s ,k̸=i−1 k,s 1+δr
Marc de Kamps
BIC-Lecture 2
Introduction
Clustering and Sorting Architecture Social Robotics
Applications
Ant-inspired Routing
A delay D = ce−dS can be imposed, so a lack of spare capacity delays ants.
The amount of pheromone can be diminished with age:
δ r = Ta + b
Congestion leads to lack of spare capacity, leas to dying ants. Noise can be added to the system: ants have a certain probability of violating routing entries.
Marc de Kamps
BIC-Lecture 2
Introduction
Clustering and Sorting Applications
Architecture Social Robotics
Travelling Salesman Problem – Ant System
Find a closed tour of minimal length. Each city must be visited once and only once.
dij =(xi −xj)2 +(yi −yj)221
For each ant k, Jik is the list of cities it still has to visit
Again: ants: Visibility ηij ≡ d1
ij Pheromone τij(t)
l ε that when α = 0, visibility determines the probabilities: ’greedy, locally optimal’
pk (t) = [τij (t)]α[ηij ]β
ij k[τil(t)]α[ηil]β
BIC-Lecture 2
Marc de Kamps
Introduction
Clustering and Sorting Architecture Social Robotics
Applications
Travelling Salesman Problem – Ant System
After completion of a tour an ant k deposits ∆τk = Q
on any of the edges it visited. Pheromone decays:
τij ← (1 − ρ)τij + ∆τij
ρ is the decay rate. This is necessary to prevent stagnation, congestion in non-optimal routes
Marc de Kamps
BIC-Lecture 2
Introduction
Clustering and Sorting Applications
Architecture Social Robotics
How good is it?
Practical experimentation is necessary: too many ants congestion, too few, no good solution
’Elitist’ ants help: extra pheromone on the best known solution; promotes experimentation around
Good on small problems (few 100), not competitive with best known solutions for larger networks
However a relatively minor modification turns the system into a very competitive method: let sometimes a city be chosen at random, otherwise take the maximum transition probability. If the probability with which this happens is slowly reduced (’simulated annealing’) the system performs against other benchmark solutions.
BIC-Lecture 2
Marc de Kamps
Introduction Routing Clustering and Sorting Architecture Social Robotics
Sorting, Clustering & Building
Many species of ant cluster corpses into cemeteries, gradually piling them up together. Brood sorting is also observed, with larger larvae lying further from the brood centre. In addition, some species are able to construct walls, arches and other architectural structures. These behaviours are yet to be fully understood, but have all been modelled as the result of simple probabilistic rules:
Clustering relies on two rules concerning the ant’s local environment:
1 items are more likely to be picked up when they differ from those around them, and
2 items are more likely to be put down amongst similar items.
Wall building, etc., is slightly more complex, relying on
chemical templates to direct what are essentially the same
basic processes
BIC-Lecture 2
Marc de Kamps
Introduction Routing Clustering and Sorting Architecture Social Robotics
Sorting Experiment
Even in a lab setting, ants will quickly start to sort their environment out.
Marc de Kamps
BIC-Lecture 2
Introduction Routing Clustering and Sorting Architecture Social Robotics
Clustering
Agent-based clustering (Deneubourg, 1998) “Pick up” probability
pp=( k1 )2 k1 + f
“Drop down” probability:
f is the perceived fraction of items in the neighbourhood of
k1, k2 are threshold constants Question: how to estimate f ?
BIC-Lecture 2
Marc de Kamps
Introduction Routing Clustering and Sorting Architecture Social Robotics
Define an attribute space, e.g. RGB colour coding. Define a distance between that attribute space:
Define a local density which is dependent on the attribute:
1 [1−d(oi,oj)] iff>0
f(oi) = s2 ojε α 0
Marc de Kamps
BIC-Lecture 2
Introduction Routing Clustering and Sorting Architecture Social Robotics
Clustering starting from a Homogeneous Distribution
BEAST demo
Marc de Kamps
BIC-Lecture 2
Introduction Routing Clustering and Sorting Architecture Social Robotics
Ants for Catering
Imagine you want to seat many guests. It’s best if you group guests that know each other together. But how?
First draw a graph that represents which of your guests know each other.
Then apply an algorithm inspired by ant clustering:
1 scatter the nodes of the graph and a load of ants on a page;
2 let an ant pick up a node, i, if it is surrounded by nodes to
which i is not connected;
3 let an ant drop i if it is surrounded by graph neighbours of i;
4 let the ants wander about at random picking up and
dropping nodes.
Slowly, clusters of acquainted guests will form on the page. This graph-partitioning technique has applications in chip design (where connected components must be placed close together
on a chip) and load balancing on parallel processor machines.
BIC-Lecture 2
Marc de Kamps
Introduction Routing Clustering and Sorting Architecture Social Robotics
Partitioning a Graph
Here we see a random graph being partitioned by ants… After the ant algorithm of
Kuntz, Layzell & Snyers (1997) has been at work, a few clear clusters have emerged.
Cluster members are more connected to each other than to members of other clusters.
This technique can be used to efficiently load the processors of a parallel machine – minimising the amount of communication required.
BIC-Lecture 2
Marc de Kamps
Introduction Routing Clustering and Sorting Architecture Social Robotics
KLS Algorithm
The KLS algorithm is a good example of an ant-inspired sorting algorithm:
pick up and1drop down probability modified by attribute distance
attribute: ’local connectedness’
Let G be a graph, vi a node of G. Let ρ(vi) be the set of vertices
adjacent to vi including vi .
d(vi,vj) = | D(ρ(vi),ρ(vj)) |
| ρ(vi ) | + | ρ(vj ) |
D(A, B) = (A ∪ B) − (A ∩ B) BIC-Lecture 2
Marc de Kamps
Introduction Routing Clustering and Sorting Architecture Social Robotics
Ants for Architecture
How can insects in a colony coordinate their behaviour in order to build highly complex architectures? Ants and termites don’t appear to have blueprints in their heads: they seem to follow simple rules in an almost random manner.
If the blueprint isn’t in the insects’ heads, it may be in their environment: ants appear to use their own previous work to stimulate their behaviour-the building of arches, towers, etc., appears to be governed by the structures themselves. “The worker does not direct his work, but is guided by it”
Marc de Kamps
BIC-Lecture 2
Introduction Routing Clustering and Sorting Architecture Social Robotics
is a slippery concept. At its root is the ability of agents to influence each other and their future selves by altering their environment-often seemingly unknowingly. Some examples:
pedestrians crossing a park make paths in the grass-the most popular will guide future walkers and be reinforced
amazon.com customers buy books-their purchases change the descriptions of the books, guiding future customers
cells divide & differentiate during morphogenesis according to chemical gradients that they themselves influence
BIC-Lecture 2
Marc de Kamps
Introduction Routing Clustering and Sorting Architecture Social Robotics
Artificial Architects
Bonabeau and Théraulaz have demonstrated these ideas in action through simple artificial paper wasp architects.
Wasps wander at random over a 3-d grid of cells and follow a simple set of microrules that govern building behaviour. Depending on the contents of the 26 cells that surround the wasp, it can deposit one of two types of brick, or leave the cell alone – thus wasps are reactive agents with no memory.
B&T show that starting from a single brick, swarms of these wasps following simple sets of microrules can construct complex structures that resemble natural paper wasp nests – layered, cellular combs with internal cavities and a surrounding envelope.
Could sets of these microrules be evolved to build human habitation or useful artefacts?
– cf work on urban planning by , ETH Zurich
Marc de Kamps
BIC-Lecture 2
Introduction Routing Clustering and Sorting Architecture Social Robotics
Termite Construction Simulation (D Ladley,
3 kinds of termite: – trail-laying
– Follow/lay pheromone – Nursing
– Move towards/away queen up to fixed
distance – Building
To place block:
Pheromone level must lie within a
certain bound and one of:
1. Material above or below
(allows vertical stacks)
2. Site shares face with horizontal
loc containing material and satisfying (1)
(allows stack horiz extension)
1. 1 face of the site must neighbour 3 horizontal locations that each contain material (allows gradual construction of
elevated horiz surfaces)
LeBueildisn)g the queen chamber
Queen: green, ground red, yellow: deposited building material.
1. formation of “pillar-like” structures: simulates reality
2. construction of walls between the pillars www.comp.leeds.ac.uk/danl/cconstruct.html
Marc de Kamps
BIC-Lecture 2
Introduction Routing Clustering and Sorting Architecture Social Robotics
Insect-like Social Robots
So far, we have considered software algorithms inspired by the various behaviours of social insects
Researchers are also implementing insect-like robot control systems for a range of tasks. These include single robots inspired by crickets & cockroaches, and multi-robot systems.
Before reviewing some of the collective behaviours that have been achieved with multiple robot systems, we will consider the question:
Why take a multi-robot approach?
single complex robot working alone versus many simple robots working together
BIC-Lecture 2
Marc de Kamps
Introduction Routing Clustering and Sorting Architecture
程序代写 CS代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com
