諸事情によりマルチエージェントシミュレーションの基本原理と実装に関し勉強する必要が出たので論文を読みました。読んだ論文は
C. Mavrogiannis, J. DeCastro, and S. S. Srinivasa. “Implicit Multiagent Coordination at Uncontrolled Intersections via Topological Braids”. In: Proceedings of the International Workshop on the Algorithmic Foundations of Robotics (WAFR). 2022.
になります。以下に論文の内容をもとに理解したことを再構成してみます。
概要
この論文は車の運転手に当たる複数のエージェントが二次元空間中の信号のない交差点で、衝突をうまく回避しつつ目的地に行けるような、それぞれの意思決定方法に関して述べています。エージェントは他人の座標や向きは見えていますがどこに行こうとしているかは予め知らないものとします。また、直接的な意思疎通は不可能とされており、ウィンカー等で行きたい方向を知らせることもできないとしています。そのため、エージェントたちは他人の動きからどうしたいのか推測することで衝突回避できるような車の運転を試みなければなりません。
ところで、筆者らは先行研究で、交通の動きは「ブレイド群」に分類することができることを示しています。車両の動きを元の座標系で考える代わりに、どのブレイドになるかだけを考えれば予測問題の定式化が容易になったり、計算量が削減できることが期待できます。
本問題では、可能な系の振る舞いが多く、意思疎通が不可能で他人の予測は困難です。そのためブレイド群を使った定式化が有用となります。本論文では各エージェントが系全体のブレイドを予測する確率が、Intention・Behavior・Topology（Braid）・Collisionの4タームの積から構成されることを汎用的な形で示しています。次に、各エージェントの意思決定は、どのブレイドが実現されるかの確率分布のエントロピーを最小化するように行うと良いと主張します。この意思決定方法の良さは引き続く実験で確認されます。
実験では、4タームに関して確率モデルを仮定し、シミュレーションの各ステップで実際に各エージェントが計算可能な形にしています。各ステップでエージェントの意思決定を前述の方法で行い、事故が起きたかどうかを集計します。これを様々な問題設定で複数回行い、事故が起きた割合を計算します。比較対象として、エージェントが全く他人を考慮せず、好きなスピードで動くパターン、他人の意図を知っているパターン（事故率の理論限界となる）、ブレイドを使わないデカルト座標上の行動予測に基づいた動きをするパターンを選びました。結果として、予想通り好きなスピードで動くパターンやブレイドを使わずに予測するパターンよりブレイドを使った予測のほうが低い事故率となりました。更に、理論限界事故率と提案手法事故率は複数のセットアップで有意差なしとなりました。この手法のトレードオフとしてはデカルト座標の予測と比べて収束が遅いことが挙げられます。しかし、エージェント数が増えると無視可能になる傾向が得られました。
実験から、それぞれのエージェントがブレイドに分類するときにつかう座標系はそれぞれ違っていても良いということが言えます。また、他のエージェントがどんなスピードを出してくるか正確に予測がつかなくてもいいということもいえます。
ブレイドを使えば計算量も削減できるのではないかと筆者らは先行研究で述べましたが、本論文では計算量削減が実現されていないことは注意が必要です。特に、行動予測のためにエージェントごとにサブルーチン的にシミュレーションを回しており、計算量は大きいです。また、エージェントが使う確率モデルが単純だったり、交差点が対称で簡単だったりしています。今後は計算量と複雑な系に適用した場合の調査が望まれます。
ブレイド群
n個のスタート地点とゴール地点が並んでいるものを考えます。説明の単純化のため、上にn点、下にn点並んでいるものとします。スタート地点とゴール地点をn個の糸でつなぎます。その際、糸が常に上から下に向かうように、また重複したスタートやゴールを持たないようにします。糸のつなぎ方のことをブレイドといいます。糸を引っ張って同じ形になるつなぎ方は同じブレイドに分類されます。スタートとゴールを結ぶためには糸が交差する必要が出ますが、あるつなぎ方と別のつなぎ方でその上下が違った場合、それらのつなぎ方は別のブレイドに分類されます。
ブレイドは合成することができます。あるn個のスタート地点とゴール地点が糸で結ばれている時、更に別のゴール地点に向けて糸を繋ぐことを考えます。最初のスタート地点と最後のゴール地点がどうつながっているかを見れば全体として一個のブレイドとみなせます。
n個のスタート地点とゴール地点がある中で、考えうるブレイドの集合をBnと表記します。Bnはn-1個の基本的なブレイドの合成で表すことができます。
交通の流れをブレイドで表す方法
ある道路の様子を上空から切り取り、スタート地点とゴール地点を決めます。各時刻における道路の様子をt軸に並べると、エージェントの動きはxyt空間上の軌跡として表現できます。次にxt平面もしくはyt平面に軌跡を射影します。射影された軌跡はブレイドに分類できます。1分類アルゴリズムは多分既存手法があると思います。
エージェントによるブレイドの予測
各エージェントがある時刻において、交通の結果がどのブレイドになりそうかを予測する式が上記になります。各タームは以下の意味を持ちます。
- i エージェント番号
- bel 時刻tにおいて交通の結果がエージェントiから見てどのブレイドになりそうかの確率
- βi ブレイドを表す記号
- βi（チルダ） ブレイドと事故が起きたかどうかの結果の組
- T エージェントたちの軌道（t=0からt=t∞まで）の集合（要素数はエージェント数に一致）
- T（花文字） 存在しうるTの集合
- U 時刻tにおいて各エージェントがどんなスピードと角度を取るかの集合
- Ξ 時刻tまでにエージェントたちが取った軌道
- c 事故が起きたかどうか（0か1）
これらの式から、これまでのエージェントたちの動きΞから、βiチルダの分布、Uの分布、Tの分布、cの分布からどのブレイドが実現されそうかが計算できることがわかります。この式の導出には後述する問題設定を使っていないので、汎用的に使える式です。これら分布はTopology・Behavior・Intention・Collisionの分布と呼ばれます。
ブレイドの予測分布から意思決定する方法
意思決定は自身がどんなスピードと角度を取るか決めることに等しいです。本論文の提案手法は、ブレイドの予測分布のエントロピーを最小化するアクションuを最適化で出すというものです。これは、自分がどういう動きをすれば「丸く収まる」か考えることになります。すなわち、「みんなこういうブレイドにしたいってことでしょ？」あるいは「こういうブレイドにしたらどう？」と空気を読んで行動するようなアルゴリズムになっています。
なお、この表記法だと、H(βiチルダ)はuiを変数として含まないので、argminが計算できません。おそらくエントロピーはP(βiチルダ|Ξ)ではなく、P(βiチルダ|Ξ,ui)に関して計算しないとダメです。
実験
四叉路に複数エージェントがいて、それぞれ右折・左折・直進のどれかをしたいと思っています。交差点直前の直進部分をnegotiation phase、曲がりだしてから以降をexecution phaseと呼びます。エージェントは道路の中心から一切ズレずに動きます。スピードはhighとlow2種類を持っています。エージェントたちはhighを好み、また他人もhighを好むだろうと考えます。P(uj|Ξ,T)の分布形状はベルヌーイ分布ですが、highの確率が高くなるようにすることで表現されています。エージェントごとにベルヌーイ分布のpはバラけさせています（他人がどれくらいハイスピードを好むかわからない）。
確率モデルですが、Intentionのタームはエージェントがnegotiation phaseにいるときは一様分布です。execution phaseにいる時そのエージェントが向いている方向が1となる分布を採用します。Behaviorのタームは自分の速度嗜好を他人にも当てはめます。つまり、ベルヌーイ分布です。Topologyのタームは複雑です。まず、各エージェントが条件付き分布の条件に入っているUのスピードで動いた場合をシミュレートします。次にシミュレーション結果がどのブレイドになったかを分類します。この結果をβ*とします。P(βi|Ξ,U,T)はβi=β*で1、それ以外0となるように取ります。最後に、CollisionはTopologyのタームの計算時にエージェント間距離の最小値が出ますが、それを使ったシグモイド関数で表現します。
実験は2から4エージェントで行われました。各実験では、次の4条件が比較されました。
- C1 エージェントが好き勝手なスピードで動く
- C2 提案手法を使う
- C3 エージェントが他人が取ろうとしている軌道を知っている
- C4 ブレイドではなくデカルト座標の軌道を予想して動く
- C5 C4で他人が取ろうとしている軌道を知っている
実験の結果、C2とC3で事故率の減少が見られました。一方で目標到達までの時間が伸びる傾向にありました。
議論
ブレイドを使うほうがいい結果が出たのは、領域の構造を加味できたからと思われます。
エージェントは他人のことを完全に把握していなくても事故回避できました。また、ブレイドに射影する座標系はそれぞれ違っていていいこともわかりました。
本手法はサブルーチン的にシミュレーションを回しており、計算量が大きいです。データドリブンな方法などで削減することが可能と見られます。
また、問題設定やモデルの形式が単純なのでよりリアリスティックなシミュレーションのために複雑なモデルを使うなども今後の方向性として考えられます。
所感
Ξ’を直接予想する手法（C4とC5）の詳細が書かれていませんでしたが、それ次第で実験結果がまるっきり変わりそうだと思いました。デカルト座標上で計算すると予測が大変だぞ、ブレイドでやると楽になるぞ、という主張だと思うのですが、実験ではエージェントが特定軌道を完全になぞるようにしていたため、本当に楽になっているのかわかりませんでした。元の座標系でやる場合の詳細を知りたいところです。
マルチエージェントシミュレーションの雰囲気は掴めました。エージェントが複数いて、環境を知覚し、内部ロジックにもとづいて行動し、それが環境に影響を与え、創発が起こる。エージェントの内部ロジックとしてはメモリを持たず反射的に動くパターンやメモリを持っていて状態遷移を行うパターンが存在する。メモリを持つエージェントには、他者の動きの予測を行うものがあり、ベイズ的な確率モデルを使う事がある。などが特徴みたいですね。特に他者の動きの予測で使われる確率モデルの理解などは統計検定やKaggleで確率論を学んできたので役立ちそうです。
コメント