ORCA: Optimal Reciprocal Collision Avoidance

一言でいうと

周辺情報を使った低次元の線形問題を解くだけで、エージェント間通信無しで複数エージェントの無衝突軌道を各エージェントが計算する。

論文リンク

Reciprocal n-body collision avoidance: http://gamma.cs.unc.edu/ORCA/publications/ORCA-1.pdf
http://gamma.cs.unc.edu/ORCA/

著者/所属機関

Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, and Dinesh Manocha Department of Computer Science, University of North Carolina at Chapel Hill

投稿日付(yyyy/MM/dd)

2010/10

掲載誌・学会等

Proceedings of the 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), October 2010

先行研究と比べてどこがすごい？

あんまりちゃんと文章にされてこなかった。
線形計画問題に帰着されているので計算が早い。
技術や手法のキモはどこ？
1. 2つのエージェントAB間の相対速度を使って、速度平面上でVelocity Obstacleを計算する。(速度ベクトルがvelocity obstacle内にあるということは、定めた時間τ後に相手のエージェントに衝突するということである)
2. 衝突しない範囲でそれぞれV_A、V_Bを最大化するような最適なV_A^opt、V_B^optに近いV_A、V_Bのペアの集合を、VAに関してはORCA{A|B}^tau、VBに関してはORCA{B|A}^tauとする。
3. もしV_A+V_BがVO内にある場合、A・Bは時間τ内に衝突するということであり、これを回避するための速度ベクトル上の変異uはV_A、VBに半分ずつ適用されなければならない。つまり、ORCA{A|B}^tauはV_A+uに直行する直線を端面とする半平面内に存在することになる。
4. n-エージェント間のペアに上記を適用することでペア数ぶんの境界条件が得られ、衝突回避可能なV_Aのとりうる凸範囲がO(n)で計算できる。さらにV_Aの許容できるV_Aの範囲との積集合から次なるV_Aを決定する。
5. もしエージェント密度が高く、許容できるv範囲が存在しない場合は、エージェントAから見たORCA{A|B}^tauの境界までのsigned distance d{A|B}(v) (v∈ORCA_{A|B}^tauなら負)の最大値ができるだけ小さくなるようにvを選ぶことで、できうる限り衝突の可能性を避けたvにすることができる。

どうやって有効だと検証した？

シミュレーション。1000エージェント、5000エージェントをIntel Xeon 2.66GHz (Clovertown)上で。(OpenMP使用)
8コアで5000エージェントの計算をしたとき、1フレーム・1エージェントあたりの計算に8msかかる。

議論や検証がまだ必要なところはある？

各エージェントは周辺エージェントの現在位置と速度を正確に計算する必要があるので、実践では高度なセンシング環境か高速な中央演算処理が必要。中央処理をする場合、各エージェントにおける処理オーダーはO(n)でも、全体でみるとO(n^2)になってしまう。
次に読むべき論文は？
完全分散swarmingの定式化: J. McLurkin, E. Demaine. A Distributed Boundary Detection Algorithm for Multi-Robot Sys-tems.(under review), 2009.
Reciprocal Velocity Obstaclesの定式化: . van den Berg, M. Lin, D. Manocha. Reciprocal Velocity Obstacles for real-time multi-agent navigation.IEEE Int. Conf. on Robotics and Automation, pp. 1928–1935, 2008.
コメント

Drunkar / papers

ORCA: Optimal Reciprocal Collision Avoidance #11