Transcript Consensus+innovations - Institute for Systems Research

Carnegie Mellon
Kalman and Kalman Bucy @ 50:
Distributed and Intermittency
José M. F. Moura
Joint Work with Soummya Kar
Advanced Network Colloquium
University of Maryland
College Park, MD
November 04, 2011
Acknowledgements: NSF under grants CCF-1011903 and CCF-1018509,
and AFOSR grant FA95501010291
Carnegie Mellon
Outline




Brief Historical Comments: From Kolmogorov to Kalman-Bucy
Filtering Then … Filtering Today
Consensus: Distributed Averaging in Random Environments
Distributed Filtering: Consensus + innovations
 Random field (parameter) estimation: Large scale
 Intermittency: Infrastructure failures, Sensor failures
 Random protocols: Gossip
 Limited Resources: Quantization
 Linear Parameter Estimator: Mixed time scale
 Linear filtering: Intermittency – Random Riccati Eqn.
 Stochastic boundedness
 Invariant distribution
 Moderate deviation
 Conclusion
Carnegie Mellon
Outline




Brief Historical Comments: From Kolmogorov to Kalman-Bucy
Filtering Then … Filtering Today
Consensus: Distributed Averaging in Random Environments
Distributed Filtering: Consensus + innovations
 Random field (parameter) estimation: Large scale
 Intermittency: Infrastructure failures, Sensor failures
 Random protocols: Gossip
 Limited Resources: Quantization
 Linear Parameter Estimator: Mixed time scale
 Linear filtering: Intermittency – Random Riccati Eqn.
 Stochastic boundedness
 Invariant distribution
 Moderate deviation
 Conclusion
Carnegie Mellon
In the 40’s
 1939-41: A. N. Kolmogorov, "Interpolation und
Extrapolation
von Stationaren Zufalligen Folgen,“ Bull. Acad. Sci. USSR, 1941
 Dec 1940: anti-aircraft control pr.–extract signal from
noise: N. Wiener "Extrap., Interp., and Smoothing of Stat. time Series
with Eng. Applications," 1942; declassified, published Wiley, NY, 1949.
 Wiener Model
 Wiener filter
 Wiener-Hopf equation (1931; 1942)
Carnegie Mellon
Norbert WIENER. The extrapolation, interpolation and smoothing of stationary time
series with engineering applications. [Washington, D.C.: National Defense Research
Council,] 1942.
Carnegie Mellon
Kalman Filter @ 51
Trans. of the ASME-J. of Basic Eng., 82 (Series D): 35-45, March 1960
Carnegie Mellon
Kalman-Bucy Filter @ 50
Transactions of the ASME-Journal of Basic Eng.,
83 (Series D): 95-108, March 1961
Carnegie Mellon
Outline




Brief Historical Comments: From Kolmogorov to Kalman-Bucy
Filtering Then … Filtering Today
Consensus: Distributed Averaging in Random Environments
Distributed Filtering: Consensus + innovations
 Random field (parameter) estimation: Large scale
 Intermittency: Infrastructure failures, Sensor failures
 Random protocols: Gossip
 Limited Resources: Quantization
 Linear Parameter Estimator: Mixed time scale
 Linear filtering: Intermittency – Random Riccati Eqn.
 Stochastic boundedness
 Invariant distribution
 Moderate deviation
 Conclusion
Carnegie Mellon
Filtering Then …
 Centralized
“Kalman Gain”
“Prediction”
“Innovations”
 Measurements always available (not lost)
 Optimality: structural conditions – observability/controllability
 Applications: Guidance, chemical plants, noisy images, …
Carnegie Mellon
Filtering Today: Distributed Solution
 Local communications
 Agents communicate with neighbors
 No central collection of data
 Cooperative solution
 In isolation: myopic view and knowledge
 Cooperation: better understanding/global knowledge
 Iterative solution
 Realistic Problem: Intermittency
 Sensors fail
 Local communication channels fail
 Limited resources:
Structural Random
Failures
 Noisy sensors
 Noisy communications
 Limited bandwidth (quantized communications)
 Optimality:
 Asymptotically
 Convergence rate
Carnegie Mellon
Outline
 Brief Historical Comments: From Kolmogorov to Kalman-Bucy
 Filtering Then … Filtering Today
 Consensus: Distributed Averaging
 Standard consensus
 Consensus in random environments
 Distributed Filtering: Consensus + innovations
 Random field (parameter) estimation
 Realistic large scale problem:
 Intermittency: Infrastructure failures, Sensor failures
 Random protocols: Gossip
 Limited Resources: Quantization
 Two Linear Estimators:
 LU: Stochastic Approximation
 GLU: Mixed time scale estimator
 Performance Analysis: Asymptotics
 Conclusion
Carnegie Mellon
Consensus: Distributed Averaging
 Network of (cooperating) agents updating their beliefs:
 (Distributed) Consensus:
 Asymptotic agreement: λ2 (L) > 0
2
limi !
1
3
1
6
7
x (i ) = r 4 ... 5 ;
1
r =
1
N
P
N
n= 1
x n (0)
DeGroot, JASA 74; Tsitsiklis, 74, Tsitsiklis, Bertsekas, Athans, IEEE T-AC 1986
Jadbabaie, Lin, Morse, IEEE T-AC 2003
Carnegie Mellon
Consensus in Random Environments
 Consensus: random links, comm. or quant. noise
 Consensus (reinterpreted): a.s. convergence to unbiased rv θ:
Var µ ·
2M ¾2 (1¡ p)
N2
P
i¸
2
®(i
)
0
Xiao, Boyd, Sys Ct L., 04, Olfati-Saber, ACC 05, Kar, Moura, Allerton 06, T-SP 10,
Jakovetic, Xavier, Moura, T-SP, 10, Boyd, Ghosh, Prabhakar, Shah, T-IT, 06
Carnegie Mellon
Outline




Brief Historical Comments: From Kolmogorov to Kalman-Bucy
Filtering Then … Filtering Today
Consensus: Distributed Averaging in Random Environments
Distributed Filtering: Consensus + innovations
 Random field (parameter) estimation: Large scale
 Intermittency: Infrastructure failures, Sensor failures
 Random protocols: Gossip
 Limited Resources: Quantization
 Linear Parameter Estimator: Mixed time scale
 Linear filtering: Intermittency – Random Riccati Eqn.
 Stochastic boundedness
 Invariant distribution
 Moderate deviation
 Conclusion
Carnegie Mellon
In/Out Network Time Scale Interactions
 Consensus : In network dominated interactions
 fast comm. (cooperation) vs slow sensing (exogenous, local)
time scale
ζcomm
ζcomm
« ζsensing
ζsensing
 Consensus + innovations: In and Out balanced interactions
 communications and sensing at every time step
time scale
ζcomm
~ ζsensing
 Distributed filtering: Consensus +Innovations
Carnegie Mellon
Filtering: Random Field
 Random field:
 Network of agents: each agent observes:
spatially correlated, temporally iid,
 Intermittency: sensors fail at random times
 Structural failures (random links)/ random protocol (gossip):
 Quantization/communication noise
Carnegie Mellon
Consensus+Innovations: Generalized Lin. Unbiased
 Distributed inference: Generalized linear unbiased (GLU)
“Prediction”
Consensus: local avg
Consensus
Weights
¯(i ) > 0;
P
i ¸ 0 ¯(i )
“Kalman Gain”
Innovations
Weights
= 1;
P
i¸ 0 ¯
2
(i ) < 1
Gain
“Innovations”
Carnegie Mellon
Consensus+Innovations: Asymptotic Properties
 Properties
 Asymptotic unbiasedness, consistency, MS convergence, As. Normality
 Compare distributed to centralized performance
 Structural conditions
 Distributed observability condition: Matrix G is full rank
 Distributed connectivity: Network connected in the mean
Carnegie Mellon
Consensus+Innovations: GLU
 Observation:
zn (i ) = H n (i )µ¤ + ° (i )»n (i ); ° (i ) = (1 + i ) ° 0
 Assumptions:
 f »n (i )g iid, spatially correlated, E µjj»(i )jj 2+ ² 1 < 1
 L(i) iid, independent
 Distributed observable + connected on average
 Estimator:
 A6. assumption: Weight sequences
Soummya Kar, José M. F. Moura, IEEE J. Selected Topics in Sig. Pr., Aug2011.
Carnegie Mellon
Consensus+Innovations: GLU Properties
 A1-A6 hold, 0 · ° 0 < :5, generic noise distribution (finite 2nd moment)
 Consistency: sensor n is consistent
Pµ¤ (limi !
1
x n (i ) = µ¤ ) = 1; 8n
 Asymptotic variance matches that of centralized estimator
 Asymptotically normality:
p
(i + 1) (x n (i ) ¡ µ¤ ) =) N (0; Sc (K ))
 Efficiency: Further, if noise is Gauss, GLU estimator is asymptotically
efficient
Carnegie Mellon
Consensus+Innovations: Remarks on Proofs




Define
Let
Find dynamic equation for
Show
is nonnegative supermartingale, converges a.s.,
hence pathwise bounded (this would show consistency)
 Strong convergence rates: study sample paths more critically
 Characterize information flow (consensus): study convergence to
averaged estimate
 Study limiting properties of averaged estimate:
 Rate at which convergence of averaged estimate to centralized estimate
 Properties of centralized estimator used to show convergence to
Carnegie Mellon
Outline




Intermittency: networked systems, packet loss
Random Riccati Equation: stochastic Boundedness
Random Riccati Equation: Invariant distribution
Random Riccati Equation: Moderate deviation principle
 Rate of decay of probability of rare events
 Scalar numerical example
 Conclusions
Carnegie Mellon
Kalman Filtering with Intermittent Observations
 Model:
xt+ 1
=
Ax t + w t
yt
=
Cx t + v t
 Intermittent observations:
f ° t gt 2 T+ i.i.d. Bernoulli random variables with mean °
° t = 1 { arrival of t he observat ion packet y t at t
° t = 0 { packet dropout
¡
¢
yet = y t I (° t = 1) ; ° t
 Optimal Linear Filter (conditioned on path of observations) –
Kalman filter with Random Riccati Equation
Pt
=
Pt + 1
=
h¡
¢T
i
x t ¡ xbt j t ¡ 1 j f ye(s)g0· s< t
¡
¢¡ 1
T
T
T
APt A + Q ¡ ° t APt C CPt C + R
CPt A T
E
x t ¡ xbt j t ¡
¢¡
1
Carnegie Mellon
Outline




Intermittency: networked systems, packet loss
Random Riccati Equation: stochastic Boundedness
Random Riccati Equation: Invariant distribution
Random Riccati Equation: Moderate deviation principle
 Rate of decay of probability of rare events
 Scalar numerical example
 Conclusions
Carnegie Mellon
Random Riccati Equation (RRE)
 Sequence f Pt gt 2 T+ is random
 Define operators f0(X), f1(X) and reexpress Pt:
f 0 (X ) = AX A T + Q;
8X 2 SN
+
T
T
¡
T
f 1 (X ) = AX A + Q ¡ ° t AX C CX C + R
Pt = f ° t ¡ 1 ± f ° t ¡ 2 ± ¢¢¢± f ° 0 (P0 )
¢¡
1
CX A T ;
8X 2 SN
+
St ochast ic b oundedness: Fix ° , P0 2 SN
+ . T hen f Pt gt 2 Z + s.b. i®
lim sup P° ;P 0 (kPt k > N ) = 0
N ! 1 t 2 Z+
n
Sequence of measures ¹
° ;P 0
t
o
t 2 Z+
is tight
[2] S. Kar, Bruno Sinopoli and J.M.F. Moura, “Kalman filtering with intermittent
observations: weak convergence to a stationary distribution,” IEEE Tr. Aut Cr, Jan 2012.
Carnegie Mellon
Outline




Intermittency: networked systems, packet loss
Random Riccati Equation: stochastic Boundedness
Random Riccati Equation: Invariant distribution
Random Riccati Equation: Moderate deviation principle
 Rate of decay of probability of rare events
 Scalar numerical example
 Conclusions
Carnegie Mellon
Random Riccati Equation: Invariant Distribution
 Stochastic Boundedness:
°
sb
n
SN
+
o
= inf ° 2 [0; 1] : f Pt gt 2 Z+ is s.b.; 8P0 2
¡
¢
1=2
st abilizable; (A; C) det ect able; Q > 0;
 T heor em : A; Q
P ¤ ¯xed point of (det erminist ic) Riccat i equat ion; ¯x ° , P0 2 SN
+ ;
¤
S ½ SN
+ : S = f f i 1 ± f i 2 ± ¢¢¢± f i s (P ) j i r 2 f 0; 1g; 1 · r · sg
T hen:
(i) If ° > 0, f Pt gt 2 Z + s.b.
(ii) 8P0 , ¹ °t ;P 0 ) ¹ ° , ¹ ° unique
¡ °¢
= cl(S)
(iii) supp ¹
¡©
ª¢
°
N
¤
¹
Y 2 S+ j Y º P
= 1
Carnegie Mellon
Moderate Deviation Principle (MDP)
 Interested in probability of rare events:
 As ϒ
1: rare event: steady state cov. stays away from P* (det. Riccati)
 RRE satisfies an MDP at a given scale:
 Pr(rare event) decays exponentially fast with good rate function
 String:
Let
³ R be a st ring of lengt h n of t he form:
´
R = f i 11 ; ¢¢¢; f i 1t ; ¢¢¢; f i 21 ; ¢¢¢; f i 2t ; ¢¢¢; f i l1 ; ¢¢¢; f i lt ; P0
1
2
l
 Counting numbers of
String (f 0 ; f 1 ; f 1 ; f 1 ; f 0 ; f 0 ; P0 ) written concisely
¡
f 0 ; f 13 ; f 02 ; P0
¢
f 0 s in R
½Pt
j = 1 I f 0g (i j ) if t ¸ 1
¼(R ) =
0
ot herwise
Soummya Kar and José M. F. Moura, “Kalman Filtering with Intermittent Observations:
Weak Convergence and Moderate Deviations,” IEEE Tr. Automatic Control;
Carnegie Mellon
MDP for Random Riccati
Equation
© ª
 T heor em Invariant dist ribut ions ¹ ° sat isfy an MDP at ¡ ln(1 ¡ ° )
as ° " 1 wit h good rat e funct ion I (¢):
1
lim inf ¡
ln ¹ ° (O)
°"1
ln(1 ¡ ° )
1
lim sup ¡
ln ¹ ° (F )
ln(1 ¡ ° )
°"1
I (X )
¸
¡ inf I (X );
for every open set O
·
¡ inf I (X );
for every closed set F
=
X 2O
X 2F
inf¤
R 2 S P (X )
¼(R );
8X 2 SN
+
P*
C
BM
(P ¤ )
¡ C ¤ ¢
inf X 2 B C
°
M
¹ B M (P ) » (1 ¡ ° )
(P ¤ )
I (X )
Soummya Kar and José M. F. Moura, “Kalman Filtering with Intermittent Observations:
Weak Convergence and Moderate Deviations,” IEEE Tr. Automatic Control
Carnegie Mellon
Outline




Intermittency: networked systems, packet loss
Random Riccati Equation: stochastic Boundedness
Random Riccati Equation: Invariant distribution
Random Riccati Equation: Moderate deviation principle
 Rate of decay of probability of rare events
 Scalar numerical example
 Conclusions
Carnegie Mellon
Support of the Measure
 Example: scalar
xk + 1 =
p
2x k + uk
yk = x k + wk
p
A = 2; C = Q = R = 1
 Lyapunov/Riccati operators:
f 0 (X ) = 2X + 1
and
¤
P = 1+
¡
 Support supp ¹
°
¢
2
f 1 (X ) = 3 ¡
X +1
p
2
is independent of 0 < ° < 1
p
p ¢
¢ £
¤
£n¡
¤
n
Let S0 = supp ¹ \ 1 + 2; 3 ; Sn = 2 1 + 2 ; 3 £ 2 n ¸ 1.
Then
¡ °¢
supp ¹ = [ n ¸ 0 Sn
¡
°
Carnegie Mellon
Self-Similarity of Support of Invariant Measure

¡
supp ¹
°
¢
‘Fractal like’: A =
p
2; C = Q = R = 1
¢ £ p
¤
S0 = supp ¹ \ 1 + 2; 3
¡
°
p
¡ ¢ £
¤
S1 = supp ¹ ° \ 3 + 2 2; 7
S0 [ S1 [ S2
Carnegie Mellon
Class A Systems: MDP
 D e¯nit ion[Class A systems] (Bucy, 6t h Berkeley Symposium, 1972)
(A; C) observable, Q; R > 0. Let S¡ = f X ¸ 0jf 1 (X ) · X g
Syst em is class A i®
f X ¸ 0jX ¸ f 0 (P ¤ )g ½ S¡
 Define
©
ª
k
¤
¶(M ) = inf k 2 T+ jkf 0 ¡ P k ¸ M
©
ª
k
¤
¶+ (M ) = inf k 2 T+ jkf 0 ¡ P k > M
 T heor em (A; Q; C; R) class A syst em. T hen, 8M > 0
¡ C ¤ ¢
1
°
lim sup ¡
ln ¹ B M (P )
· ¡ ¶(M )
ln(1 ¡ ° )
°"1
³ C
´
1
°
¤
lim inf ¡
ln ¹
B M (P )
¸ ¡ ¶+ (M )
°"1
ln(1 ¡ ° )
p
¡
¢
 Scalar system A = 2; C = 1; Q > 0; R > 0 is class A
Carnegie Mellon
MDP: Scalar Example
 Scalar system:
Soummya Kar and José M. F. Moura, “Kalman Filtering with Intermittent Observations:
Weak Convergence and Moderate Deviations,” accepted EEE Tr. Automatic Control
Carnegie Mellon
Outline




Intermittency: networked systems, packet loss
Random Riccati Equation: stochastic Boundedness
Random Riccati Equation: Invariant distribution
Random Riccati Equation: Moderate deviation principle
 Rate of decay of probability of rare events
 Scalar numerical example
 Conclusions
Carnegie Mellon
Conclusion
 Filtering 50 years after Kalman and Kalman-Bucy:
 Consensus+innovations: Large scale distributed networked agents




Intermittency: sensors fail; comm links fail
Gossip: random protocol
Limited power: quantization
Observ. Noise
 Linear estimators:
 Interleave consensus and innovations
 Single scale: stochastic approximation
 Mixed scale: can optimize rate of convergence and limiting covariance
 Structural conditions: distributed observability+ mean connectivitiy
 Asymptotic properties: Distributed as Good as Centralized
 unbiased, consistent, normal, mixed scale converges to optimal centralized
Carnegie Mellon
Conclusion
 Intermittency: packet loss
 Stochastically bounded as long as rate of measurements strictly
positive
 Random Riccati Equation: Probability measure of random
covariance is invariant to initial condition
 Support of invariant measure is ‘fractal like’
 Moderate Deviation Principle: rate of decay of probability of
‘bad’ (rare) events as rate of measurements grows to 1
P*
¡ C
¹ ° BM
 All is computable
C
BM
(P ¤ )
¢
(P ¤ )
»
(1 ¡ ° )
i nf X
2 B C (P ¤ )
M
I (X )
Carnegie Mellon
Thanks
Questions?