RVOによる衝突回避アルゴリズム

衝突回避のアルゴリズムの一つである RVO (Reciprocal Velocity Obstacles) について、日本語の資料が見当たらないので書いておく。

元論文：http://gamma.cs.unc.edu/RVO/icra2008.pdf

背景

先行のアルゴリズムとして VO (Velocity Obstacles) があったが、VOではエージェントの速度が振動する挙動があった。RVOはその問題を解消するものとなっている。

エージェントA,Bが速度 で位置 にいるとして、それぞれの位置を基準としたA,B上の点（位置ベクトル）の集合を とする。 で現在のA上の点の集合を表すことができる。 時間が だけ経過した後は となるので、A,Bが衝突することは

が成り立つことと言える。これは

となる がそれぞれ存在することと同値で、

と整理できる。つまり から相対速度 の方向に延びる半直線（時間は巻き戻らないので ）と、 （Aの形の情報をBの方に押しつけたもの）が交わるとき、AとBは衝突する。 そのような の集合を で表し、各々このVOの外側の速度を選ぶことによる衝突回避がVOによるアルゴリズムである。

振動というのは、例えばA,Bが互いに逆方向に直進したくて向かい合っていると、そのままでは衝突するので互いにVOの外の速度を選び直すが、すると今度は衝突しないので直進に戻し、すると衝突するので……といった形でループが発生するケースが起こる。

アルゴリズム

基本的なアイデアは「互いに同じアルゴリズムを使うのだから、半分だけ避ければよい」というものである。（Game AI Pro 3 p.238）

具体的には、現在の速度 とVO外の速度 の平均を選ぶようにする。

これは となるので、 が成り立つ が の要素となる。逆にRVOの外側から速度を選べば、「半分だけ避ける」ことができる。

エージェントが多数の場合は常にRVOの外側を選ぶことはできるとは限らないので、衝突までの時間 と、期待する速度 （衝突がない場合に出したい速度）により

を最小化する を選択する（ はどのくらい頑張って衝突回避するかのパラメータ）。

デモ

JavaScriptでの実装：https://jsfiddle.net/86jh1Lva/

黒い点で を、実線で実際に選ばれた を示している。