Julia

Juliaでグラフラプラシアンを用いた合意形成を計算する

内容

例題状況のグラフ

  • 隣接行列 $A$ を図示すると以下の系が得られる

graph1.png

概要

  • ノード数が5つなので、状態変数5つをベクトル化し $x = (x_1, x_2, x_3, x_4, x_5)$ と表す
  • 状態変数 $x_i$ の時間変化は、自身の値と制御器(コントローラ)の入力を関数 $f$ によって処理した結果決定されると仮定する
    • $\frac{dx_i(t)}{dt} = f_i(x_i(t), u_i(t))$
  • 制御器 $u_i$ は、自分自身の状態変数値 $x_i$ と、自分の近傍の状態変数値によって決定される関数とする
    • 例えば $u_1(t) = c(x_1(t), x_4(t))$
    • 時刻 $t$ におけるノード1への制御信号は、自分の状態値 $x_1$ と $A$ で規定される近傍からの状態値 $x_4$ によって決定する
  • 合意形成
    • 制御器により$\lim_{t\to\infty} x_i(t) = \alpha$となる合意値$\alpha$を達成すること
    • 例えば $\alpha=\frac{1}{N} \sum_{i} x_{0i}$ であるとき、平均値合意である

グラフラプラシアンで表現される系

  • 具体的なシステム $f, c$ について、以下の積分系を仮定する

    • $x_i(0) = x_{0i}$
    • $\frac{dx_i(t)}{dt} = u_i(t)$
    • $u_i(t) = -\sum_{j\in\mathcal{N}i} x_i(t) - x_j(t) $
      • i番目のノードの近傍$N_j$中のノードjに対する状態変数値の差分が制御信号として入力される
  • 行列 $A$ とグラフラプラシアンを思い出す

  • 上の積分系は $\frac{dx(t)}{dt} = -Lx(t)$ という行列形式で表される。

計算例

  • 初期値として $x(t) = (1, 3, 5, 7, 9)$ を与える
  • この系が合意を達成することを確認する
  • 実行結果
    • 4.712程度の値に収束する(合意が形成される)

ex3.png

コード

using PyPlot

# 初期値
x = [1, 3, 5, 7, 9]

# グラフラプラシアンL
A = [0 0 0 1 0;
     1 0 1 0 0;
     0 0 0 0 1;
     0 1 0 0 0;
     1 0 0 0 0]
D = diagm(squeeze(sum(A, 2), 2))
Δ = maximum(D)
L = D - A

# シミュレーション
Δt = 0.05
tf = 10
xx = []
for t in 0:Δt:tf
    push!(xx, x)
    Δx = -L*x
    x += Δx * Δt
    print(x)
end

# plot
t = 0:Δt:tf
figure(figsize=(6, 3))
plot(t, xx)
grid(true)
savefig("ex3.png", format="png", dpi=300)