同書の読書メモ、第１章からの続きです。
第２章は省略しました。
第２章は数学的基礎として、線形代数の基礎、代数的グラフ基礎を学びます。
この部分も今まで全く理解していなかった部分ですので、一通り読み込んでは居ますが、読書メモにはしづらいため省略しました。
定理の証明を全て追っているわけでもないのと、線形代数も大学の授業でしか受けていない（その授業も出席したかどうかさえ怪しい）ので、読書メモはともかくとして精読する機会は別で必要とは思っています・・・
さて、第３章は合意制御の話です。
合意とは、全エージェントが情報交換を通じてある共通する状態変数を一致させることを意味するとのこと。
状態変数が各エージェントの位置と問題設定すれば、全てのエージェントが合意制御により一箇所に集合することになります。
何らかのフォーメーションで整列した状態を合意状態としたい場合は・・・その状態を表す何らかの変数を作って、それに一致させるんですかね。状態変数設計が結局難しくなるような気がします。
もっと高度な動作、例えば何らかの動作を順番に実施していくような「任務」をMASに与える場合は・・・ 制御対象の状態変数とその合意目標値を逐次切り替えていくのかもしれませんが、結局その切り替えを誰がやるのかという問題が生じるような。。。？
合意問題
前提：
- 各エージェントに１〜ｎのインデックスを割り当てる。
- 各エージェントを持つ状態変数の時間微分は、当該エージェントの状態変数と当該エージェントへの制御入力の関数で表される。
- 各エージェント間に情報伝達経路がある場合、その方向に辺を持ち、各エージェントが頂点となるグラフとして、MASを表現することができる。
- エージェントjからエージェントiに情報伝達が可能である場合、エージェントiはjに隣接すると言う。
- あるエージェントについて、隣接するエージェントの集合を隣接集合または近接と呼ぶ。
- 各エージェントは、自己の隣接集合からのみ情報を得ることができる。よって、2で触れた各エージェントの動的状態（状態変数の時間微分）を決定する関数は、自己の状態変数と、隣接集合が有する状態変数の関数で表せる。制御入力がこの形をした制御器を分散制御器と呼ぶ。
MASが合意を達成するとは、任意の初期状態に対して各エージェントに適当な制御入力を加えた時、全エージェントの状態変数が漸近的に一致する、という状態のこと。この一致した値のことを合意値と呼ぶ。
この問題は、各エージェントが持つｎ個の初期値から、ある意味のある値（これが合意値に相当）を求める作業と表現することも可能で、各初期値の平均値を求める平均合意、同じく幾何平均を求める幾何平均合意、最大（小）値を求める最大（最小）値合意、あるエージェント（リーダー）の初期値に他のエージェントの状態変数を一致させるリーダー・フォロワー合意等が代表例として挙げられる。
更に、各エージェントの状態変数を各成分に持つベクトルとして表現することで、MASの全エージェントの状態を１つの状態ｎ次元ベクトルで表すことができる。この時、合意状態は、当該ｎ次元ベクトルの各成分が全て一致すること（３つのエージェントから成るMASであれば、３次元空間上の原点を通る直線に状態３次元ベクトルが重なること）
状態ｎ次元ベクトルは、合意前であっても合意方向のベクトルと、その直行ベクトルの和で表すことができると考えられる。その直行ベクトルは各エージェントの状態の不一致度を表す成分と考えられ、相違ベクトルと表現する。
相違ベクトルが指数的に０に収束する場合、このMASは指数合意を達成すると言い、指数関数の時間の係数であるλの最大値を合意速度と呼ぶ。
連続時間システムの合意制御
各エージェントに対する制御入力として、当該エージェントの状態変数と隣接エージェントの状態変数の偏差の総和（のマイナス１倍）であるとする。
この制御入力により、任意のエージェント間の状態の偏差が０に収束するため、合意に達することが期待される。
この偏差を計算する項には、隣接行列の該当項を乗じても同じ結果が得られる。（隣接行列の該当項が、隣接する場合は１、しない場合は０のため、隣接する場合は通常通りのフィードバックあり、隣接しない場合はそもそもフィードバックしないという結果になるため）
この式を利用して、全エージェントの状態変数の時間微分を各項に持つベクトルを、全エージェントの状態変数を各項に持つベクトルと、隣接行列の各項（またはその和等）からなる行列の積として表すことができる。この行列をこのMASを表すグラフのグラフラプラシアンと呼ぶ。
このように、隣接エージェントとの偏差の総和を制御入力として持つ系に対して、
この系がある無向グラフで表されるMASであれば、それが合意に達する必要十分条件は、グラフが連結である（グラフのうち、他と繋がりを持たない頂点（群）が存在しない）こと。これは直感とも合致する。他と情報共有ができない頂点（群）が居ては、合意に達することは不可能であろう。
更にこの時、合意が達成されるときそれは平均合意であり、指数合意である。その合意速度は、グラフラプラシアンの２番めに小さい固有値で与えられる。
グラフの規模が大きい（頂点の数が多い）ほど、合意速度は遅くなる。同じ頂点数の無向グラフであれば、辺の数が多い方が合意速度は速くなる。これも直感と合致する。
無向グラフでない場合は？
無向グラフとは限らない場合、外向きにしか矢印を持たない頂点は、合意に達することができない。
全域木を持つグラフの場合は、その根が情報発信をすることで合意に達することができると考えられる。
実際、グラフが全域木を持つことが、MASが合意に達する必要条件であるという定理が存在する。
直感的には、単一の全域木のみから構成されるグラフの場合、情報を発信することしかできない根は「自己の状態変数を他のエージェントの状態変数に寄せることができない」から、合意値は根の状態変数の初期値に大きな影響を受けそうである・・・？
もっと言えば、上記のフィードバック系の場合は、最初の１ステップで、根は制御入力として自身の状態変数のフィードバック（＝０）を入力するのみ、すなわち状態変数が不変であり、その値にしか合意できない？
MASが平均合意に達する必要十分条件は、上記に加え、平衡グラフ（任意の頂点について入次数と出次数が同一）であること。
リーダー・フォロワー合意を達成する必要十分条件は、Gが全域木を持ち、全ての全域木の根となる頂点が唯一であること。
この２個目が、上で懸念した、MASが単一の全域木のみから構成されるグラフの場合に相当すると思われる。この場合、リーダー／フォロワー制御は可能であり、リーダーの状態変数の初期値に全頂点が合意する。
MASを表すグラフが全域木を持たない場合は、必ず情報伝達が不可能となる経路があるということであり、合意に達することはできない。
離散時間システムの合意制御
基本的には連続時間系と変わらない。
ただ、離散時間系なので、状態変数の時間微分 dx/dt＝u(t)はなく、x（t+1）-x(t)=u(t)となる。
合意に達する条件、その時の合意値等は連続時間計と基本的に共通。
制御入力である隣接ノードとの差分のフィードバックには、MASを表すグラフの最大次数の逆数よりも小さいゲインが乗じられる。最大次数は１以上の自然数と考えられるので、ゲインは１未満なのは間違いない。
単純差分のフィードバックでゲインが１以上の値を取ると発散するというのは直感的にも理解できる。
実際、最大次数が２のグラフで、ゲインは0.5未満であるべきところ0.77とした場合、発散して合意に至らない事例が示されている。
むしろ連続時間系の時はなぜ要らなかったのか？
平均合意とリーダ・フォロワ合意に関する定理についても、同様に連続時間系と同じく成り立つ。
スイッチングネットワークにおける合意制御
エージェント間の情報伝達経路が時刻ごとに切り替わるネットワークをスイッチングネットワークと呼ぶ。
これはある基準となるグラフがあるとして、そのグラフと頂点のみが完全に共通で辺の構造が異なる、複数種類（本書中ではｍ種類）の全域部分グラフのいずれかと考え、モデル化することができる。
ネットワーク構造、それに伴って上記離散時間系で導入したゲインの最大値が変化する点を除けば、システム全体を表す差分方程式は概ね離散時間系のそれと似たような記載が可能。
ｍ種類の全てのグラフが全域木を持つ場合は、切り替わりに関係なく全てのエージェントが情報共有可能な状態が維持されるため、MASが合意に達することができる。
そうでない場合についても、ｍ種類のグラフの総和が全域木を持っていれば、ネットワークの切り替えに従って全エージェントがいずれは情報を共有できるため、合意に達することができる。
連続時間系についても基本は同様。
まとめ
マルチエージェントシステム制御の基本として、合意制御について一通り触れました。
基本的に単一の変数を同じ値にすることを以って「合意」と呼んでいますので、多次元の値の場合はどうなるのか、同じ値にする場合以外を以って合意としたい場合はどうすれば良いのか等、まだ具体的なイメージがつかめていない部分もありますが・・・
二次元状態変数（二次元空間上のビークルの位置x、y）を制御する例は第３章にありましたね。独立変数なので、何次元であろうと１個ずつ独立に計算するというだけなのかも知れません。
この時もビークルが一箇所に集合することを以って「合意」としていましたが、群制御において群を一箇所に集合させるメリットってそれほど大きくないような気がして、実世界で役に立つ群制御アルゴリズムにするにはどのような発展のさせ方があるのかは、少し気になっています。
次回は第４章、被覆制御について触れていきます。
