前回は第３章、マルチエージェントシステム制御の基本として、合意制御について一通り触れました。
今回は第４章として、被覆制御に触れていきます。
被覆制御がなんなのかという話ですが、空間上にある指定の分布でエージェントを配置する制御のことのようです。
第３章で、空間上のエージェントを一箇所に集めることを以ってしか「合意に至った」と言えないのか？ という疑問を抱いていましたが、これに対する答えの一つが被覆制御なのだと思います。
本質的には合意制御と同じで「ある指定の分布に至った時点を以って合意とみなす」というだけなのかもしれませんが、合意制御と同じ問題として扱うと状態変数の設計が難しそうな気がしますので、便宜的に別の問題としているということでしょうか。
被覆問題
m次元空間上におけるn個のエージェントから成るMASを考えます。
エージェントiの位置について、速度dxi/dt = fi(xi(t), ui(t)) と、エージェントの速度が現在位置と制御入力の関数で表せるという点は、合意制御と同じです。
なお、ｎ個のエージェントの位置は、各エージェントの位置をm行×１列のベクトルとし、それらを全て連結したm行×n列の行列で表すものとします。
この際、各エージェントは自己に隣接するエージェントの位置情報を取得し、それに基づいて自己の運動を制御するものとします。
このようなMASにおいて、空間上にエージェントを指定された分布で配置することを被覆といい、それを任意の初期条件から達成する制御入力を求める問題を被覆問題または展開問題といいます。
この問題の解き方ですが、各エージェントの位置（先ほど定義したm×nの行列から表される）を入力とし、各エージェントのバラつき度合いを得られる評価関数を導入し、その値を最適化（ばらつきが大きいほど小さくなる値とし、最小化する）する問題に帰着できます。
評価関数としては、ある地点から最も近いエージェントまでの距離の２乗の総和（制御対象エリアに沿って合算）等が挙げられます。
この値は、エージェントが対象エリアで空間的に均一に配置された時に最も小さくなる。
ボロノイ図と勾配系
ある空間上に配置される複数の点を考える。この際、空間を、どの点に一番近いかで分割する。言い換えれば、それぞれの点に最も近い点からなる領域に分割する。
この分割した図をボロノイ図という。
点xiに対する領域を、xiに対するボロノイ領域という。
ボロノイ領域を全て合わせれば領域全体になるし、ボロノイ領域は境界を除いて互いに重ならない。また、領域が凸集合、または凸多面体であれば、各ボロノイ領域も同じように凸集合or凸多面体となる。
・・・おそらくだが（後で出てくる？）ボロノイ領域は、各点から２点選んで結ぶ線分の垂直２等分線をひき続ければ得られる。
互いに隣接するボロノイ領域に所属する点のみを辺として結んで得られる無向グラフをドロネーグラフという。
（順番が逆なのか？）ドロネーグラフは、各点に対するボロノイ領域を計算するために必要な情報を含んでいる。
各ボロノイ領域の境界は、各辺の垂直二等分面（２次元空間なら垂直２等分線）の部分集合となっているからである（上述と同じ）
従って、あるボロノイ領域は、それが属する点と、ドロネーグラフ上におけるその隣接点の位置から計算できる。
ボロノイ領域が先に出てきたのだから、ドロネーグラフを作ってボロノイ領域を計算できると言われても嬉しくもなんともないが、どういうことだろうか。
定義上はボロノイ領域が先に出てくるが、領域と各点だけを与えられてボロノイ図をいきなり解析的に描くことは無理で、先にドロネーグラフを描く必要があるということ？
ボロノイ図は最適配置問題において重要。
そもそも最適配置問題とは、ある集合に対して、境界のみが重なるｎ個の部分集合に分割する際、評価関数J（ある点へ、その点が属する領域の各地点からの「重み付き行きにくさの総量」の、全点の総和）を最小にする問題のこと。
この解がボロノイ図と関係がある。らしい。
というか、Jが最小値となるような領域分割のやりかたが、ボロノイ領域による分割となる。
勾配系：
状態変数x(t)（n次元、n×1ベクトル）の時間微分であるu = dx/dtが、-G(x)と、J(x)のx偏微分の積で表せる時、そのシステムを勾配系と呼ぶ。
ただしn×n行列であるGは、任意のxに対して正定値となる行列。
この概念の導入が何の意味を持つのかは、情けないが全くわからず・・・
被覆制御
実際に被覆制御の方法を考えます。
前々項で導入した、被覆の度合いを表す評価関数Jを考えます。
- 各々のエージェントの制御入力が、自身の位置情報と隣接するエージェントの位置情報から構成される
- x(t)を状態するシステム全体が関数Jの勾配系である
と仮定します。１つ目は今までのMASの前提と同じです。
この時、このMASの配置x(t)は、Jの停留点に収束します。停留点がJの大域的最小点や局所的最小点であれば、その範囲で被覆が実現されるということです。
・・・なるほどわからん。
とにかく、システム全体がJの勾配系になるようにxへの制御入力u = dx/dtを決めるということらしい。
たとえば、二次元空間上でエージェントiの位置を制御することを考える。ただし、隣接エージェントはドロネーグラフにより定義されるとする。
全エージェントの位置を
x :=
| x1, y1 |
| x2, y2 |
| x3, y3 |
| ・・・ |
とn×2行列で表す。
この時、ある2つのエージェントが全く同じ位置に存在する集合をO、その補集合\Oは全てのエージェントが違う位置にある場合を表す。
この時、それぞれのエージェントが形成するボロノイ領域中の点から当該エージェントの位置までの距離で表せる関数と当該点の重みのをボロノイ領域に渡って積分し、それを1〜nまで和を取ったものが、評価関数Jとなる。
まとめ
被覆制御について学びました（？）
カッコハテナがついているのは、理解が追いつかなくなってきているからです。
今読んでいるのは２周目ですが、３周目を読んで、直感的理解（この記事のように、言葉で説明できる範囲の理解）に留まらず式を書き下す作業もしようかと思っています。
次回は最終章、分散最適化です。
正直、ついていけなくなっています。
ktd-prototype.hatenablog.com
