Transcript Swarm Intelligence on Graphs

Swarm Intelligence on
Graphs
Advanced Computer Networks: Part 2
1
Agenda

Graph Theory (Brief)

Swarm Intelligence

Multi-agent Systems

Consensus Protocol

Example of Work
2
Graph Theory
3
Graph Theory

Graph connection: nodes and links
(undirected graph: balanced digraph)

Identity matrix

or unit matrix of size n is the n×n square matrix
with ones on the main diagonal and zeros
elsewhere

AIn = A
Identity Matrix
4
Graph Theory

Adjacency matrix

a means of representing which or nodes of a
graph are adjacent to which other nodes
n1 n2 n3 n4 n5 n6
Node 1-6
Graph
n1
n2
n3
n4
n5
n6
Adjacency Matrix
5
Graph Theory

Degree matrix
n1 n2 n3 n4 n5 n6
Node 1-6
Graph
n1
n2
n3
n4
n5
n6
Degree Matrix
6
Graph Theory

Laplacian matrix
L=
Graph
7
Swarm Behavior in Nature
Collective Behavior
Self-organized System
8
Swarm Intelligence

Ant Colony Optimization Algorithms
http://www.funpecrp.com.br/gmr/year2005/vol3-4/wob09_full_text.htm
9
Swarm Intelligence

Ant Colony Optimization Algorithms

The Traveling Salesman Problem
• A set of cities is given and the
distance between each of them
is known.
• The goal is to find the shortest
tour that allows each city to be
visited once and only once.
10
Swarm Intelligence

Ant Colony Optimization Algorithms

the Traveling Salesman Problem: An iterative algorithm

At each iteration, a number of artificial ants are considered.

Each of them builds a solution by walking from node to node on the graph with the
constraint of not visiting any vertex that she has already visited in her walk.

An ant selects the following node to be visited according to a stochastic
mechanism that is biased by the pheromone: when in node i, the following node is
selected stochastically among the previously unvisited ones

if j has not been previously visited, it can be selected with a probability that is
proportional to the pheromone associated with edge (i, j).

the pheromone values are modified in order to bias ants in future iterations to
construct solutions similar to the best ones previously constructed.
11
Swarm Intelligence

Ant Colony Optimization Algorithms
12
Swarm Intelligence

Ant Colony Optimization Algorithms

ConstructAntSolutions:


ApplyLocalSearch:


A set of m artificial ants constructs solutions from elements of a finite set of
available solution components.
Once solutions have been constructed, and before updating the pheromone, it is
common to improve the solutions obtained by the ants through a local search.
UpdatePheromones:


The aim of the pheromone update is to increase the pheromone values associated
with good or promising solutions, and to decrease those that are associated with
bad ones.
Usually, this is achieved


by decreasing all the pheromone values through pheromone evaporation
by increasing the pheromone levels associated with a chosen set of good solutions.
13
Swarm Intelligence

Particle Swarm Optimization Algorithms (PSO)

PSO emulates the swarm behavior of insects,
animals herding, birds flocking, and fish
schooling where these swarms search for food in
a collaborative manner.

Each member in the swarm adapts its search
patterns by learning from its own experience and
other members’ experiences.

A member in the swarm, called a particle,
represents a potential solution which is a point in
the search space.

The global optimum is regarded as the location
of food.

Each particle has a fitness value and a velocity to
adjust its flying direction according to the
bestexperiences of the swarm to search for the
global optimum in the solution space.
http://science.howstuffworks.com/environmental/life/zoology/
insects-arachnids/termite3.htm
14
Swarm Intelligence

Particle Swarm
Optimization Algorithms
(PSO)
http://www.sciencedirect.com/science/article/pii/S09
60148109001232
15
Swarm Intelligence

Application of Swarm Principles: Swarm of
Robotics
http://www.domesro.com/2008/08/swarm-robotics-for-domestic-use.html

http://www.youtube.com/watch?feature=playe
r_embedded&v=rYIkgG1nX4E#!
16
Multi-Agent Systems

Multi-agent system

Many agents:



Interaction topology



homogeneous
heterogeneous
complex network
How to control the global
behavior of the multi-agent
system?
How to apply the proposed
model to solve the realistic
problem?
17
Consensus Protocols

Consensus problem
 A group of agents




To make a decision
To reach an agreement
Depend on their shared state information
Information exchange among the agents

To design a suitable protocol for the group
to reach a consensus

Shared information among agents is
converged to the group decision value
 but do not allow to reach a particular
value
18
Consensus Protocols
19
Consensus Protocols
20
Calculation Examination
 1 1 0 0 0 0 
 1 3  1  1 0 0 


 0  1 4  1  1  1
L

 0 1 1 3 1 0 
 0 0 1 1 2 0 


 0 0  1 0 0 1 
21
Leader-Following Discrete-time Consensus
Protocol

Effective leadership
and decision making in
animal groups on the
move
22
Leader-Following Discrete-time Consensus
Protocol

Leader-following consensus models


Leader





agreement of a group based on specific quantities
of interest
an external input to control the global behavior of
the system
determine the final state of the system
unaffected by the followers
send the information to the followers only
Followers



reach consensus following the leader's state
influenced by the leader directly
no feedback information from the followers to the
leader
23
W. Ren, 2007

Multi-vehicle consensus with a
time-varying reference state
1
24
W. Ren, 2007
2
3
c
25
Y. Cao, 2009

Distributed discrete-time
coordinated tracking with a
time-varying reference state
and limited communication
4
26
Y. Cao, 2009
5
ζ1(0)=3, ζ2(0)=1, ζ3(0)=-1, ζ4(0)=-2
ζ1(-1)=0, ζ2(-1)=0, ζ3(-1)=0, ζ4(-1)=0
27
Example of Work:
Leader-Following Behavior
28
28
Proposed work: Leader-Following
Behavior
1.5
node 1
node 2
node 3
node 4
LEADER
Information State
1
0.5
0
-0.5
0
5
10
15
20
25
Times
30
35
40
45
6
29
50
Leader-Following Behavior
30
Leader-Following Behavior
leader connects to node 1, 2, 3, 4 respectively
Compared with 1
31
Leader-Following Behavior
5
6
32
Leader-Following Behavior
45
node 1
node 2
node 3
node 4
LEADER
40
35
Information State
30
25
20
15
10
5
0
-5
0
5
10
15
20
Times
25
30
35
40
33
Further Work

Large scale multi-agent networks
with dynamical topologies

Partial information exchange
between followers and leader



How to identify the leader?
How the leader control the group
behavior?
Consensus on large scale multiagent networks
34
References














www.wikipedia.com
Marco Dorigo, Mauro Birattari, and Thomas St¨utzle, “Ant Colony Optimization”, IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE,
NOVEMBER, 2006.
J. J. Liang, A. K. Qin, “Comprehensive Learning Particle Swarm Optimizer for Global Optimization of Multimodal Functions”, IEEE
TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 10, NO. 3, JUNE 2006.
J. A. Fax and R. M. Murray, "Information flow and cooperative control of vehicle formations," IEEE Trans. Autom. Control,
vol. 49, pp.1465-1476, 2004.
D. B. Kingston, R. W. Beard, "Discrete-time average-consensus under switching network topologies," in Proc. American
Control Conf.,14-16 June 2006.
W. Ren, "Multi-vehicle consensus with a time -varying reference state, “Systems & Control Letters, vol. 56, pp. 474-483,
2007.
Y. Cao, W. Ren, Y. Li, "Distributed discrete-time coordinated tracking with a time-varying reference state and limited
communication," Automatica, vol. 45, pp. 1299-1305, 2009.
J. Hu, Y. Hong, "Leader-follower coordination of multi-agent systems with coupling time delays," Physica A: Statistical
Mechanics and its Applications., vol. 374, iss. 2, pp.853-863, 2007.
D. Bauso, L. Giarr'e, R. Pesenti, "Distributed consensus protocols for coordinating buyers," Proc. IEEE Decision and Control
Conf., December, 2003.
R. E. Kranton, D. F. Minehart, "A theory of buyer-seller networks," The American Economic Review, vol. 91, no. 3, pp. 485508, 2001.
I.D. Couzin, J. Krause, N.R. Franks, S. A. Levin, “Effective leadership and decision making in animal groups on the move,”
Nature, iss. 433, pp. 513-516, 2005.
R.O. Saber, R.M. Murray, “Flocking with obstacle avoidance: cooperation with limited communication in mobile networks,” in
Proc. IEEE Decision and Control Conf., vol.2, pp. 2022-2028, 2003.
E. Semsar-Kazerooni, K. Khorasani, “Optimal consensus algorithms for cooperative team of agents subject to partial
information,” Automatica, 2008.
J. Zhou, W. Yu, X. Wu, M. Small, J. Lu, “Flocking of multi-agent dynamical systems based on pseudo-leader mechanism,”
Chaotic Dynamics, 2009.
35