こんにちは．デイビッドです．今回は，私が最近関心があって色々と遊んでいるマルチエージェントシステムの制御を楽しんでみたという記事です．面白さが伝わると嬉しいです・・・！
Contents
マルチエージェントシステムって何？
二つ以上の相互作用するエージェント（構成員・要素）からなるシステムのことを言っています．最近はかなりイメージしやすい対象として，オリンピックなどで行われていたドローンショーのようにたくさんのドローン・ロボットなどがあります．ああいった多数の個体からなるシステムの総称です．（このドローンショー残念ながら現状はまだ相互作用して協調的動作を行うところまでには至っていないようで，集中的に管理されています．）
単一機では解くことのできない問題を複数機が協調的に動作することによって解決することが期待されていて，これから紹介するマルチエージェントシステムの「制御」のお話の応用先は，本当に様々です．私自身は群衛星システムの制御などに関心があります．
グラフ理論
マルチエージェントシステムの制御を議論する上で，グラフ理論が便利です．情報交換のネットワーク構造を表すのに用います．隣接行列$A$が各エージェントの接続関係を表し，次数行列$D$が，各エージェントがいくつ接続関係を有しているかを表す対角行列です．これら二つで$L$が定義され，グラフラプラシアンと呼びます．グラフラプラシアンについてはこちらの記事がとんでもなくわかりやすいのでおすすめです．ラプラシアンというのは勾配の発散のことで，そこから名前がついています．すなわち，あるエージェントについて，他のエージェント間との通信量（勾配）すべての収支＝いくつ出ていくつ入るか（発散）という量を意味しています．このグラフラプラシアンが，特に線形の綺麗な理論では，重要な役割を担います．
グラフ構造に関して，Spanning Tree（全域木）という構造が，後述の合意制御の理論では重要です．これは，Loopはなく，あるエージェントからすべてのエージェントに到達するような構造を持っているもののことを指します．
合意問題
さて次は，合意問題についてです．これは，マルチエージェントシステムの制御のもっとも基本的な制御問題です．
数学的には，ネットワーク間の通信と適切な制御入力$u_i(t)$によって，すべての$x_i(t)$が，任意の初期値$x_{0i}$から，漸近的にある値（合意値$\alpha$）に一致する
$$\lim_{t\rightarrow \infty}(x_i(t) – x_j(t))=0,\ \ \lim_{t\rightarrow \infty}x_i(t) = \alpha$$
という条件を満たす制御入力$u_i(t)$を求める．
という問題になります．
このとき，マルチエージェントシステムの制御では，基本的に，各エージェントがそれぞれ独自に得た情報だけを用いて制御を行うため，「分散制御器（Distributed Controller）」を用います．その定義が，
$$\begin{matrix}&u_i=c_i(x_i(t), x_{j_1}(t), x_{j_2}(t),\cdots, x_{j_{n_{i}}}(t)),\\&\ \{j_1,j_2,\cdots,j_{n_i}\}=\nu_i:=\{j\in\nu:(j,i)\in\epsilon\ and\ i \neq j \}: adjacency \ set\end{matrix}$$
となります．
合意問題に対する基本的な結果
例えば，以下のようなシンプルなシステムの線形ダイナミクスがあったとします．
$$\dot{x_i}(t) = u_i(t),\ x_i(0)=x_{i0}$$
その際に，先ほど述べた分散制御器を以下のように線形分散制御器として定めてやれば，
$$\begin{matrix}&u_i=c_i(x_i(t), x_{j_1}(t),\cdots)= – \sum^{n}_{j=1}a_{ij}(x_i(t)- x_j(t)),\\ &A = [a_{ij}]: Adjacency\ matrix \end{matrix}$$
各エージェントの状態量をまとめたベクトルに対して，次の式のようにかけます．
$$\begin{matrix}\dot{{\bf x}}(t) = -L{\bf x}(t), \\{\bf x}=\begin{bmatrix}x_1(t)&x_2(t)&\cdots&x_n(t)\end{bmatrix}^T, L: Graph\ Laplacian\end{matrix}$$
ここで，$L$は先述のようにグラフラプラシアンです．したがって，グラフラプラシアンが，システムの挙動を特徴づけることになります．
この線形システムに対するシミュレーションをしてみましょう．ネットワーク構造は以下のようになっています．
線形分散制御器によって，バラバラな初期値を有していた各エージェントの状態量が時間が経つにつれて合意がとれていることがわかります．
合意値は，
$$\alpha = \frac{\sum_{i=0}^nv_ix_{0i}}{\sum_{i=0}^n{v_i}}$$
と記述できて，$v_i$は$L$の固有値０のときの左固有ベクトルになることが解析的に求められます．ここではそこまで踏み込むのはやめておきます．
さて，もうひとつ．ネットワーク構造が，Spanning Treeである場合と単なるTreeである場合についても数値シミュレーションをしてみましょう．
Spanning Treeの場合には，合意が達成されますが，そうでない場合には，合意が達成できないことがわかります．これは，定性的にも理解しやすいことで，Spanning Tree，すなわちあるエージェントから全エージェントにつながる道が存在しなければ，ネットワーク上で分断がおきてしまうということです．適切なネットワーク構造を有していることが条件ではありますが，漸近安定となる制御入力$u_i(t)$の存在が確認できました．
数値シミュレーション（ビークルの編隊協調制御）
さて，次にこれまで知ったことを生かして，ビークルの編隊制御について考えます．編隊の形状を制御するということはすなわち相対位置を所望の値にするということになります．
$$\begin{matrix}\lim_{t\rightarrow\infty}{(p_{xi}(t)-p_{xj}(t))}=r_{xij}=p^*_{xi}-p^*_{xj}\\\lim_{t\rightarrow\infty}(p_{yi}(t)-p_{yj}(t))=r_{yij}=p^*_{yi}-p^*_{yj}\end{matrix}$$
$p_{xi},p_{xj},p_{yi},p_{yj}$は絶対位置を表しています．適切な座標変換を施せば，
$$\begin{matrix}\lim_{t\rightarrow\infty}{(\bar{p_{xi}}(t)-\bar{p_{xj}}(t))}=0, &\bar{p_{xi}}(t) = p_{xi}(t)- p^*_{xi}, &\bar{p_{xj}}(t) = p_{xj}(t)- p^*_{xj}\\\lim_{t\rightarrow\infty}(\bar{p_{yi}}(t)-\bar{p_{yj}}(t))=0, &\bar{p_{yi}}(t) = p_{yi}(t)- p^*_{yi}, &\bar{p_{yj}}(t) = p_{yj}(t)- p^*_{yj}\end{matrix}$$
状態量の差がゼロに漸近するような問題と考えることができます．ビークルの運動がもっともシンプルなダイナミクスに従う場合には，典型的な線形の分散制御器を以下のように定義してやることで，漸近的に収束させることができます．
$$\begin{matrix}u_i&=&- \sum^{n}_{j=1}a_{ij}(\bar{p_{xi}}(t)- \bar{p_{xj}}(t)) \\&=&- \sum^{n}_{j=1}a_{ij}(p_{xi}(t)- p_{xj}(t) – r_{xij})\end{matrix}$$
実際の数値シミュレーション結果がこちらです．
いい具合に配置制御がなされていることが確認できますね！
被覆問題
被覆というのは，ある領域を複数のエージェントでカバーするということで，例えば，小学校の運動会で体操の隊形に開け！とかあったと思うんですけど，両手を広げて周りの人とぶつからないようにいい具合に広まっていくようなそういうイメージでまずは大丈夫です．
被覆の度合いを評価関数$J(x)$によって表現しておきます．
このとき，
おのおののエージェントに対して，その制御入力$u_i(t)$が自身の情報$x_i(t)$と近傍のエージェントの位置情報$x_j(t)$で構成されていて，かつ$x(t)$を状態とするシステム全体が関数$J(x)$の勾配系になるのであれば，
このマルチエージェントシステムの状態$x(t)$は$J(x)$の停留点に収束することになります．そこが大局的あるいは局所的最小点とすると，評価関数を最小にする状態を達成できるということです．
したがって，上記のお話をうまく用いて，各エージェントの制御入力を$J(x)$の勾配系になるように定めれば，ええ具合の被覆制御が実現できる，というのが基本的な考えのようです．
これまでと同様にシステムは以下のダイナミクスに基づいて運動するとすると，
$$\dot{x_i}(t) = u_i(t),\ x_i(0)=x_{i0}$$
です．このとき
$$\dot{x_i}(t) = -G(x)\frac{\partial J}{\partial x}(x)$$
としてやれば，収束するぜ！というのが上で述べていることです．
さて，この評価関数をどう設定してやればうまく収束してくれるのかですが，
$$J(x,W)=\sum^n_{i=1}\int_{W_i}h(||q-x_i||)\phi(q)dq$$
こうすると，位置最適化問題に対して適切な評価関数になります．
これは，複数のお店をどこに配置しますかみたいな問題に近いイメージで，店の位置からある中心点（たとえば駅）までの距離の関数でアクセスのしやすさを表現しますが，駅に近すぎると当然設置コストが高くなるのでそういったことのトレードオフを表現した評価関数になっています．
この位置最適問題の解は「ボロノイ図」で特徴づけられます．エージェント間を結ぶ線からなる境界線たちによって作られる右のような図をボロノイ図と呼びます．
ここで，関数$h$を
$$h(||q-x_i||)=||q-x_i||^2$$
と定義してやると，
勾配が具体的に計算でき，その停留点が，中心ボロノイ配置となることがわかります．したがって，この評価関数でもって制御入力を構成してあげれば，収束結果としてボロノイ図のような配置が得られるということになります．
数値シミュレーション（最適配置制御）
さて，上記を踏まえてシミュレーションをしてみました．各エージェントがいい具合（評価関数を最小にする）の位置に配置する制御を行います．はじめは左下の方に固まっているエージェントたちが，次第にひろがっていき，1 x 1で定義された領域内で最適な位置に収束していく様子が確認できました．
ドローンなどが，ある領域をカバーする際に協調的な制御入力で自律的にちょうどいい配置へと移動するような応用が考えられますね．
まとめ
さて今回は，私が最近関心があって色々と遊んでいるマルチエージェントシステムの制御を楽しんでみたという記事でした．このお話はほんとに応用の幅が広く，いろんなエージェントが分散協調的に活動する世界を考える上で非常に重要だと思っています．ワクワクしますね．
筆者はもう少し詳しく知りたくて最近以下の文献で学習中です！
それではまた！機会があれば，シミュレーションのMATLABコードなんか紹介できれば，と思います．
Reference
- 東，永原，石井，林，桜間，マルチエージェントシステムの制御，システム制御工学シリーズ，コロナ社, 2015．
- 永原，岡野，小蔵，若生，ネットワーク化制御，コロナ社，2019．
今回の内容はほとんど上記の教科書をもとにしています．興味を持たれた方がいたらぜひ参考にしてみてください！
他の記事も読んじゃいます？
コメント