程序代写代做代考 graph algorithm C Complex Dynamical Networks: Lecture 8: Network Control

Complex Dynamical Networks: Lecture 8: Network Control
EE 6605
Instructor: G Ron Chen
Most pictures on this ppt were taken from un-copyrighted websites on the web with thanks

Motivational Examples

Motivation: Example C. elegans
In its Neural Network:
Neurons: ~ 300 Synapses: ~ 3000

Excerpt
The worm Caenorhabditis elegans has 297 nerve cells. The neurons switch one another on or off, and, making 2345 connections among themselves. They form a network that stretches through the nematode’s millimeter-long body.
How many neurons would you have to commandeer in order to control the network with complete precision?
The answer is: 49
— Adrian Cho, Science, 13 May 2011, vol. 332, p 777 Here, control = stimuli

Another Example
“ … very few individuals (approximately 5%) within honeybee swarms can guide the group to a new nest site.”
I.D. Couzin et al., Nature, 3 Feb 2005, vol. 433, p 513
These 5% of bees can be considered as “controlling” or “controlled” agents
Leader-Follower networks

Now …
o Given a network of dynamical systems (e.g., ODEs)
o Given a specific control objective
(e.g., synchronization)
o Assume: a certain class of controllers (e.g., local state- feedback controllers) are chosen to use

Control Problem:
Pining Control:
 How many controllers to use?
 Where to put them (where to “pin”)?

State Feedback Control

Attempts to Answer
First, consider undirected and unweighted networks
Each node is a higher- dimensional nonlinear dynamical system:
dxi f(x), xRn, i1,2,…,N
o Regular networks
o Random-graph networks o Small-world networks
o Scale-free networks
o …….
dt
i

Network Model
Linearly coupled network:
a general assumption is that f (x) is Lipschitz (e.g., linear: Ax)
dx N
i f(xi)caijHxj xRn
i1,2,…,N
dt j1 i
coupling strength c > 0 and coupling matrices (undirected):
A[a ] ijNN
A: If node
Laplacianmatrix: LDA
r 0 11 
r 
i connects to node
0r
 nn
j (j ≠ i), then aij = aji = 1; else, aij = aji = 0; aii  0 Ddiag{d1,…,dN} di -degreeofnode i
H 
22

What kind of controllers? How many? Where?
i1,2,…,N i1,2,…,N
dx
dt j1
N if(xi)c aHx

ij j
+ ui
(u Hx) ii
dx N
i f(xi)caHxHx dt ij j i i
j1
1 if tocontrol
i 0 if notcontrol 
Q:Howmanyi 1?Which i?

How Many? – One, or a few, if … c is large enough
dx
1 f(x)c
N
dt 1 if(xi)c aHx
dx
dt j1
N

ij j
i  2,3,…, N
 j1
a Hx u u Hx 1jj111
X.F. Wang, G.R. Chen, Physica A (2002): Let l =1 and s = 0 therein

Still yet,
where to apply controllers makes a difference Pinning Control: (How many and which nodes to pin?)
Only a small fraction of nodes are selected for control:
1. Selective pinning scheme 2. Random pinning scheme
X.F. Wang, G.R. Chen, Physica A (2002)

Example
Consider a scale-free CNN, which has a zero equilibrium (s = 0): N

dxi1  j1 
xi3xi4c ax 
dt 2xi2xi3cN ax 

dxi2  j1 
ij j1
dxi dt14xi114xi2cN ax 
ij j2

dt dxi3  j1 
 dt  100xi1 100xi4
dxi4   100(xi4 1 xi4 1)
 dt  
ij j3
 cNax  ij j4
j1  i  1,2,…, N  60

1 Selective Pinning Control
Here, network size N = 60, coupling strength c = 8 and
number of controlled nodes is
Pin the first 15 largest nodes:
The controlled state x1
m =15, by ui  hxi
Control gain: Settling time = 10
h30

2 Random Pinning Control Randomly pin 15 nodes.
Comparison:
The controlled state x1
1. Control gain is much larger: h  513
Recall the last one:
h30
2. It takes twice longer time
to synchronize the network:
Settling time = 20 Recall the last one: 10

Network Controllability Theory

In retrospect, …
(1930-2016)
18

System Controllability
Linear Time-Invariant (LTI) system
x(t)  Ax(t)  Bu(t)
xRn : statevector uRp : controlinput
ARnn : systemmatrix BRnp : controlmatrix
x1(t) x(t)
x2(t) x(t0)
x3(t)
Controllable: The system orbit can be driven by an input from any initial state to any target state in finite time.

Example
x(t)  Ax(t)  Bu(t) xax
1 111
x a x a x bu, 2 211 222
x3  a32x2 a33x3
a 0 0 0
11  Aa21 a22 0 , Bb
0aa 0  32 33 

Classical Controllability Theorem
x(t)  Ax(t)  Bu(t) Rank Criterion:
The linear system is controllable if and only if the controllability matrix C has full row rank:
Previous
Example
uncontrollable

What About Directed Networks?

In retrospect: large-scale systems theory Structural Analysis of Dynamical Systems
Q:
Is this kind of structures controllable?

Structural Controllability
Corresponding linearized system has the following general form:
xax 1 111
xaxax bu, 2 211 222
a 0 0 0 11  
Aa21 a22 0, Bb 0aa 0
x3  a32x2 a33x3
rankB,AB,A2Bb a b a2 b 2
 32 33   00 0

22 22
0 a b a (a a )b  32 32 22 33 
Uncontrollable

1 0 0  b0a 0
1 0 0 b0a0
1 0 0  1 0 0  b0a 0b0aaa
1 21  0 0 a a 
1 21  0 a 0
1 21  1 21 2331 0 a a a  0 a a a 
 3221, rank C  3  N
 31 , rank C  2  Nn  3
 31 3331, rank C  3  Nn
 31 3221 rank C  ? controllable ?
Examples: Structure matters
C=[B,AB,A2 B]
controllable
uncontrollable
controllable
See also: Y.Y. Liu, J.J. Slotine, A.L. Barabási, Nature (2011)

Building Blocks
Cactus is the minimum structure which contains no inaccessible nodes and no dilations

Structural Controllability Theorem
The following statements are equivalent:
Algebra:
1. An LTI control system (A,B) is controllable Geometry:
2. The digraph G (A,B) contains neither inaccessible nodes nor dilations, but is spanned by a cactus
C.T. Lin, IEEE Trans. Auto. Contr., 1977

Undirected network
Matching:
a set of edges without common nodes
Matched Unmatched node node
Maximum matching
(Perfect matching):
matching of largest size
Matching in Undirected Networks
L. Lovász, M.D. Plummer, Matching Theory (2009)
Matchings may not be unique

Matching in Directed Networks
 Matching: a set of directed edges without common heads and common tails
 Matched node: the head node of a matching edge

Minimum Inputs Theorem
Q: How many?
A: The minimum number of inputs ND needed is:
Case 1: If there is a perfect matching, then ND = 1
Case 2: If there is no perfect matching, then ND = number of unmatched nodes
Q: Where to put them? A: Case 1: Anywhere
Case 2: At unmatched nodes
Y. Y. Liu, J. J. Slotine, A. L. Barabási, Nature (2011)

Examples
Perfect Matching
 1 input; anywhere

A Network of MIMO LTI Systems

xi
xi Rn
xi
Axi
Bui
yi Rm
ui Rp

yi Cxi
N ijHyj, yi Cxi, i1,2, ,N
Node system Networked system
Networked system with external control

j1
Axi
Some notations
xi i 1:

j1
i 0:
without external control
N ijHCxj iBui, i1,2, ,N with external control
Axi
Node system (A,B,C) Network structure
L  [ij ] RNN
  diag(1, ,
Coupling matrix H
External control inputs
N
)

Some counter-intuitive examples
Network structure
0 1 L111
Node system
Networked MIMO system
H  1  0



10

 A1 0 B0

structurally controllable
C01 
(A,B) is uncontrollable (A,C) is observable
state controllable

Network structure
Node system
Networked MIMO system
Some counter-intuitive examples
H  0 
01 
10  A B1
L
structurally controllable
11 0
10



C01 
(A,B) is controllable (A,C) is observable
state uncontrollable
1


Now, in general …
A Network of MIMO LTI Systems
xi

j1
N
 HyBu, yCx, i1,2, ,N

Axi
i 1:withexternalcontrol i 0:withoutexternalcontrol
ij j i i i i
Question:
Given the MIMO node system (A, B, C), network structure L, and coupling matrix H, how to determine external inputs Δ to guarantee the controllability?

A Network of MIMO LTI Systems
Ns
xi Axi ijHCxj ikBuk,
xiRn, i1, N ukRp,k1, s
ylRq, l1, r Necessary and Sufficient Condition
j1 k1 yl mDx
N
 j1
lj j
L [ij ]RNN
 [ij ]RNs
Nn SMoalutrtiixoenqXuatioRn of
Controllability
TT
 XB  0, L XHC  X ( I A)
If and only if
Has a unique solution X = 0 is X  0.
L. Wang, X.F. Wang, G.R. Chen and W.K.S. Tang, Automatica, 2016

Pinning Control of MIMO Networks

BREAK
10 minutes

Consensus and Control over Complex Networks
 Swarm Dynamics / Modeling Consensus Protocols/Analysis Flocking Algorithms / Control  DEMO

Fish Schooling
DEMO

Birds Flocking
Flocking: to congregate or travel in flock DEMO

Consensus
A position reached by a group as a whole
Battle space management scenario

Fireflies Synchronization
Attitude Alignment
The attitude of each spacecraft is synchronized with its two adjacent neighbors via a bi-directional communication channel

 Swarming
 Flocking
 Rendezvous  Consensus  Synchrony  Cooperation  ……
Distributed coordination of
a network of agents:
 Agents
 Network
 Distributed local control  Global consensus
What are in common ?

Flocking

Flocking (Some Real Photos)
DEMO

Position:
xi (t 1)  xi (t)  vt Heading:
(t1) (t) R  Vicsek, et al, Phys. Rev. Lett. (1995)
Vicsek Model

(t1) (t) R 

Vicsek Model
DEMO

Stability Analysis
 A group of M globally nonlinearly coupled individuals:
dx M
i g(xi xj), i1,2,…,M
dt j1
Attraction/Repulsion function:
  ||y||2 g(y)yabexp c 
  
 All the agents will converge to a spherical region: Bx:||xx|| x1M x b c/2exp(1/2)
Mi
i1 a
Gazi, Passino, IEEE Trans. Auto. Control, 2003, 48: 692–697

A/R function:
g(y)  y[ga (|| y ||)  gr (|| y ||)]
Linear attraction
Bounded repulsion
gr(||xi xj ||)||xi xj ||b,b0 xi(t)B (x(t))
ga(||xi xj ||)a,a0 ||y(y)||
Stability Analysis
xi  (xi) M g(xi xj),i1,…,M
j1,ji
xi

M 
Gazi, Passino, IEEE Trans. Sys. Man Cybern., B: 2004, 34(1): 539-557
 b/a
  M 1b 2  aM M

(t 1)  F(t) lim(t) ss1
Convergence Analysis
t
F  random matrix
ss  steady state T
1  [1,1,…,1]
Contraction Mapping Principle
Jadbabaie, Lin, Morse, IEEE Trans. Auto. Control, 2003, 48(6): 988-1001 Moreau, IEEE Trans. Auto. Control, 2005, 50(2): 169-182

Consensus
Design a network connection topology, or design local control law, so that || xi  x j || 0 (here, consensus = synchronization)
Consensus is achieved asymptotically if there exists an infinite sequence of bounded intervals such that the union of the graphs over such intervals is totally connected.
union
Olfati-Saber, Murray, IEEE Trans. Auto. Control, 2004, 49(9): 1520-1533

Small-World Networks
are better for Consensus
N / 2 Condition number — the smaller, the better Regular networks Small-world networks
1000 times average
Olfati-Saber, Amer. Control Conf. (2005)

Flocking
DEMO

Boids Flocking Model
Three Rules:
Separation: Steer to avoid crowding local flockmates
Alignment: Steer to move toward the average heading of local flockmates Cohesion: Steer to move toward the average position of local flockmates
Reynolds, “Flocks, herd, and schools: A distributed behavioral model,” Computer Graphics, 1987, 21(4): 15-24
http://www.red3d.com/cwr/boids/

Flocking: Small-World Organization Small-world communication generates “pseudo-leaders”
who control their neighbors
H.T. Zhang, G.R. Chen, PhysCon, Germany (2007)

Flocking: Small-World Organization
2 11 00
2
Leader
Pseudo leader
Follower
-1
-2
-0.5 0 0.5 1 1.5 2
Initial position of the flock
-1
-2
-0.5 0 0.5 1 1.5 2
Flock position after 40 iterations

Flocking: DEMO
H.T. Zhang, G.R. Chen, PhysCon, Germany (2007)

Another Flocking Algorithm: DEMO
J. Lu and G. Chen (simulation)

Movies: Robot Fish
Acknowledgement: College of Engineering, Peking University

Movie 1: Coordination
Acknowledgement: College of Engineering, Peking University

Movie 2: Cooperation
Acknowledgement: College of Engineering, Peking University

End