Learning Multiagent Communication with Backpropagation

果たしてこのシリーズが続くのか、はたまた3日坊主になるのか。
（まあ流石に毎日やるつもりはないのだけど）

3行で

マルチエージェントシステムに関して
相互に通信するようなニューラルネット(CommNNと呼ばれている)を用いて制御
交通渋滞回避などに応用できそう

概要

マルチエージェントシステムは元々生体の形態形成に触発されて提唱された計算パラダイムで、個々の個体(computational particleとか、または普通にエージェントとか呼ばれるみたい)はすべて同様のプログラムで動いていて、システム全体として見ると計算が行われるようなシステムのことを指す。
エージェントは自分のglobalな位置を知ることはできず、半径r内近傍のエージェントとの距離や、自身の状態を知ることのみ許されている。

具体的な例としては、ハーバード大学で開発された群ロボットであるKilobotが有名だろう。

www.youtube.com

マルチエージェントシステムは、分散計算やロボティクス等の分野での応用が期待されている。
今回は、マルチエージェントの制御にニューラルネットを用いるという研究である。
エージェントにどのように動くべきか予めプログラムを与えずに、環境からの報酬を元に最適な挙動を学習する、所謂強化学習を行う。

提案手法

ニューラルネットとしてのマルチエージェントシステム

まず、各エージェントの挙動について、

個々のエージェントが自身のプログラムに従って動作する
マルチエージェントシステム全体をモデルとして見做し、モデルがエージェントを同時に制御する

という2つの見方ができる。今回は後者の見方を採用する。
するとこのモデルとして、全エージェントの報酬・位置・状態を入力として受け取り、各エージェントの行動を出力するニューラルネットを考えることができる。

通信モデル

エージェント $j$ の状態 $h_j^i$ は次の関係で決まるとする。

${\displaystyle h_j^{i+1}=f^i(h_j^i,c_j^i) }$
${\displaystyle c_j^{i+1}=\frac{1}{J-1}\sum_{j'\ne j}h_{j'}^{i+1} }$

ここで、上付き文字 $i$ は $i$ 回目の通信ステップ、 $f^i$ はニューラルネット、 $J$ はエージェント数を表す。
各イテレーションでは各エージェントが他のエージェントからメッセージを受信し、それ( $c_j^{i}$ )を用いて自身の状態 $h_j^i$ を計算する。

f:id:levelfour:20160601143033p:plain
(図は論文より引用)

Figure 1は $f^i$ が隠れ層なし1層のニューラルネット、すなわち活性化関数 $\tanh$ のみのニューラルネットの場合を図示化したものだ。

強化学習ではエージェント $j$ は状態 $s_j$ から次に取るべき行動 $a_j$ を選択する。
これは、ニューラルネットの入力 $h_j^0$ を

$\displaystyle h_j^0=r(s_j)$

のようにして得る。 $r$ はエンコーダ関数であり、問題に依存する。同様に出力は

$\displaystyle a_j=q(h_j^K)$

のようにして得る。

モデルの拡張

上記で定式化した通信モデル(ConnNN)にいくつかの拡張を加える。

まず、Local Connectivityを導入する。冒頭でマルチエージェントシステムは「各エージェントが近傍の他のエージェントの状態しか知り得ない」と触れていたが、上記の定式化ではglobalにエージェントの情報を知ることができる。
勿論モデルとしては近傍半径 $r=\infty$ とすれば妥当ではあるのだが、応用問題を考えたときに不適当である。
そこで、エージェント $j$ は集合 $N(j)\subset\{1,\cdots,J\}$ に含まれるエージェントとしか通信できないものと制限する。
このような制限を加えると、 $c_j^i$ の更新式は

$\displaystyle c_j^{i+1}=\frac{1}{|N(j)|}\sum_{j'\in N(j)}h_{j'}^{i+1}$

と変更される。 $N(j)$ はシステムの遷移とともに変化する。

次に、先程提示した $h$ と $c$ に関する漸化式の添字 $i$ は各通信ステップに関する添字だったが、時間遷移として見做すことができる。
すると、モデル全体が時間再帰型のNN、つまりRecurrent Neural Networkとしてみなせる。論文中の実験ではLSTMを用いて実装も実験の一例として行っている。

最後に、入力 $h_j^0$ を常にニューラルネットの入力として与えると便利らしい。

$\displaystyle h_j^{i+1}=f^i(h_j^i, c_j^i, h_j^0)$

Skip Connectionsと呼ばれている。

応用例

応用例としていくつか上げられているが、個人的に渋滞緩和の例(5.2.1)が最も面白かったので、それを取り上げる。

f:id:levelfour:20160601145412p:plain
(図は論文からの引用である)

Figure 2の左図のように、このシミュレーションでは交差点の各方向から一定の確率で車がランダムに出現する。
出現した車は交差点でいずれかの方向に進み、その過程で

(gas) 自分の進行ルート上を1マス進む
(brake) その場で止まる

のいずれかの動作を行う。

車の衝突とは、不幸にも同タイミングで同セルに2つ以上の車が存在してしまうことである。このシミュレーションでは、衝突しても報酬の変化以外には何も影響を与えない（衝突しても無視して進み続ける）。
交差点に現れてから出て行くまでに各車は

$\displaystyle r(t)=C^tr_{coll}+\sum_{i=1}^{N^t}\tau_ir_{time}$

だけの報酬を得ることになる。ただし $C^t$ は衝突回数、 $N^t$ は交差点上に存在した時間ステップ数、 $r_{coll}$ 、 $r_{time}$ はそれぞれ衝突と時間経過における報酬である。報酬とはいえども、どちらも負の値なのでどちらかと言えばペナルティである。
つまり、この強化学習では「できるだけ衝突せずに速く交差点を通過する」ことを目的とする。

詳細なニューラルネットの構成については論文を参照してただきたい。結論としては、エージェント間の通信を行うことによって大幅に衝突率を下げることができるということだ。
これは単なるシミュレーションなので実際に活用できるかどうかについては疑問が残るが、自動運転技術の実用化が視野に入りつつある中、興味を惹かれる内容だった。

シミュレーションの様子は動画もあり、論文中にYouTubeへのリンクがある。
（一応URLを知っている人のみのアクセス制限がかかっているようなので、ここからの直接リンクは遠慮しておく）

参考

[1605.07736] Learning Multiagent Communication with Backpropagation