ゲームへのRRTsの実装とか載ってる http://aigamedev.com/open/highlights/rapidly-exploring-random-trees/ 神尾、伊庭「マルチエージェント協調作業のためのランダムサンプリングを用いた経路プラニングアルゴリズム」 http://ci.nii.ac.jp/naid/110004669…

アルゴリズムは以下。 1.初期状態x_initだけの探索木τを生成する 2.探索すべき状態空間からランダムサンプリングにより状態を選び、x_randとする 3.探索木τの中でx_randに最も近い状態x_nearからx_randに向けて一定距離進めた状態をx_newとする 4.状態x_new…

探索手法のひとつ 前処理いらず、高次元空間でも高速な探索ができる ロボットの経路探索とか 状態空間内で探索木を成長させる手法 解(目的地)が存在しても、必ず見つけるわけではない 解が存在しないと、ループが止まらない

概略図。

OpenCVにCondensationという「ParticleFilterによる物体追跡」のアルゴリズムが実装されている。 OpenCVを使わなくても、簡単なのですぐ実装はできると思う。 実装の時に参考にしたサイト http://mist.suenaga.cse.nagoya-u.ac.jp/trac/wiki/Tutorial/Practi…

扱う状態空間・観測モデルなどにほとんど制約がない。 パーティクルを用意する(構造体{位置、重み}とかで、1000個とか) 基本的な流れは、以下。 1.パーティクルの位置・重みを初期化。(画像内から最大尤度を計算してそこに配置したり、ランダムに配置するだ…

非線形・非ガウス型の状態空間モデルに対して、効率よく状態を推定することができる。 それ以前での時系列フィルタ(カルマンフィルタ)は制限が多かったが、ParticleFilterはほとんど制限がない。 ロボットの姿勢推定やコンピュータビジョンなど広く利用され…