"移動体の自己位置を推定する自己位置推定装置であって、前記移動体の周辺空間に存在する各物体の位置情報を時系列に取得する位置情報取得部と、前記位置情報取得部により第1時刻で取得された第1位置情報を、前記第1時刻と時系列的に前又は後の時刻である第2時刻で取得された第2位置情報に対して平行移動及び回転移動させたときの前記第1位置情報と前記第2位置情報との一致度を算出する一致度算出部と、前記第1位置情報の平行移動量及び回転移動量を変更させて、前記一致度を最大にする前記平行移動量及び前記回転移動量を探索し、前記自己位置を推定する推定部とを備え、前記一致度算出部は、前記第1位置情報を構成するある計測点に対し、一定距離内に前記第2位置情報を構成するある計測点が存在すれば、前記一致度に所定のポイントを付与し、付与したポイントの合計値を前記一致度として算出する自己位置推定装置。前記一致度算出部は、前記周辺空間を前記一定距離に基づいて格子状に区切ることで格子空間を生成し、前記第2位置情報の各計測点を所定のハッシュ関数を用いて前記格子空間に投影し、前記格子空間の各位置における前記計測点の存在の有無を示すハッシュテーブルを生成し、前記第1位置情報の各計測点を前記ハッシュ関数を用いて前記格子空間に投影し、ある計測点の前記格子空間における位置が前記ハッシュテーブルに存在した場合、前記一致度に前記ポイントを付与する請求項1記載の自己位置推定装置。前記一致度算出部は、種類の異なる複数のハッシュ関数を用いて前記ハッシュテーブルを複数生成し、前記第1位置情報のある計測点を各ハッシュ関数を用いて前記格子空間に投影し、いずれかの位置が対応するハッシュテーブルに存在した場合、前記一致度に前記ポイントを付与する請求項2記載の自己位置推定装置。前記推定部は、前記平行移動量及び前記回転移動量をランダムに変化させて前記第1位置情報からn1n1は正の整数個の探索候補を生成する第1処理と、各探索候補の前記一致度に基づき、各探索候補の重み値を算出し、算出した重み値に基づいて、n2n2<n1個の探索候補を抽出する第2処理と、抽出したn2個の探索候補のそれぞれについて、所定の確率分布に基づいて前記平行移動量及び前記回転移動量を変化させてn3n3は正の整数個の探索候補を生成する第3処理と、前記n3個の探索候補のそれぞれに対し、前記重み値を算出し、算出した重み値が最大となる探索候補を探索解として求める第4処理とを備える請求項1~3のいずれかに記載の自己位置推定装置。前記第4処理は、前記第2、第3処理を所定回数繰り返し、前記重み値が最大となる探索候補を前記探索解として求める請求項4記載の自己位置推定装置。前記移動体のオドメトリを算出するオドメトリ算出部を更に備え、前記第1処理は、前記オドメトリから得られる前記移動体の位置の事前確率に基づき、前記平行移動量及び前記回転移動量をランダムに変化させてn1個の探索候補を生成する請求項4又は5記載の自己位置推定装置。請求項1~6のいずれかに記載の自己位置推定装置と、前記位置情報を取得する位置センサとを備える移動体。移動体の自己位置を推定する自己位置推定方法であって、コンピュータが、前記移動体の周辺空間に存在する各物体の位置情報を時系列に取得する位置情報取得ステップと、コンピュータが、前記位置情報取得ステップにより第1時刻で取得された第1位置情報を、前記第1時刻と時系列的に前又は後の時刻である第2時刻で取得された第2位置情報に対して平行移動及び回転移動させたときの前記第1位置情報と前記第2位置情報との一致度を算出する一致度算出ステップと、コンピュータが、前記第1位置情報の前記平行移動量及び前記回転移動量を変更させて、前記一致度を最大にする前記平行移動量及び前記回転移動量を探索し、前記自己位置を推定する推定ステップとを備え、前記一致度算出ステップは、前記第1位置情報のある計測点から一定距離内に前記第2位置情報のある計測点が存在すれば、前記一致度に所定のポイントを付与し、前記ポイントの加算値を前記一致度として算出する自己位置推定方法。移動体の自己位置を推定する自己位置推定プログラムであって、前記移動体の周辺空間に存在する各物体の位置情報を時系列に取得する位置情報取得部と、前記位置情報取得部により第1時刻で取得された第1位置情報を、前記第1時刻と時系列的に前又は後の時刻である第2時刻で取得された第2位置情報に対して平行移動及び回転移動させたときの前記第1位置情報と前記第2位置情報との一致度を算出する一致度算出部と、前記第1位置情報の前記平行移動量及び前記回転移動量を変更させて、前記一致度を最大にする前記平行移動量及び前記回転移動量を探索し、前記自己位置を推定する推定部としてコンピュータを機能させ、前記一致度算出部は、前記第1位置情報のある計測点から一定距離内に前記第2位置情報のある計測点が存在すれば、前記一致度に所定のポイントを付与し、前記ポイントの加算値を前記一致度として算出する自己位置推定プログラム。以下、本発明の実施の形態による自己位置推定装置について説明する。図1は、本発明の実施の形態による自己位置推定装置が適用された移動体のブロック図である。自己位置推定装置は、位置情報取得部11、一致度算出部12、推定部13、マップ生成部14、及びオドメトリ算出部15を備えている。そして、自己位置推定装置は、位置センサ16により取得された位置情報に基づき、移動体の自己位置を推定する。移動体は、自己位置推定装置、位置センサ16、及び回転量センサ17を備えている。本実施の形態では、自己位置推定装置は例えばCPU、ROM、RAM、及びハードディスク等を備えるコンピュータにより構成されている。そして、位置情報取得部11、一致度算出部12、推定部13、マップ生成部14、及びオドメトリ算出部15は、ハードディスクに格納された自己位置推定プログラムを例えばCPUが実行することで実現される。なお、自己位置推定プログラムは、DVD-ROM等のコンピュータ読み取り可能な記録媒体に記録されてユーザに提供される。ユーザはこの記録媒体をコンピュータにインストールすることで、コンピュータを自己位置推定装置として機能させる。位置情報取得部11は、位置センサ16により計測された移動体の周辺空間に存在する各物体の位置情報を一定の周期で時系列に取得する。ここで、位置情報は、物体が存在する箇所を示す計測点から構成されている。本実施の形態では、位置センサ16として、レーザレンジファインダが採用されている。そのため、計測点は、位置センサ16の位置を原点とし、位置センサ16の正面方向を基準方向とする2次元のローカル座標空間において、その基準方向からの角度と、原点からの距離とを含む2次元の極座標データにより表される。以下の説明では、ローカル座標空間は、基準方向にy軸が設定され、原点を通り、かつ、基準方向に直交する方向にx軸が設定されているものとする。一致度算出部12は、位置情報取得部11により第1時刻で取得された第1位置情報を、第1時刻と時系列的に前又は後の時刻である第2時刻で取得された第2位置情報に対して平行移動及び回転移動させたときの第1位置情報と第2位置情報との一致度を算出する。本実施の形態では、第1時刻を時刻tとし、第2時刻を時刻t-1として説明するが、これに限定されず、第1時刻を時刻t-1とし、第2時刻を時刻tとしてもよい。また、時刻tとは、位置センサが時系列に取得する位置情報の取得タイミングを示す。また、必要に応じて、位置情報の取得タイミングをフレームと記述する。また、本実施の形態では、時刻tの位置情報と時刻t-1の位置情報との一致の度合いを評価する評価値を用いて一致度を表す。具体的には、評価値Eは、式1により表される。ER,T=Σi=1nfRaiT,{bj}1fai,{bj}=0∋j,|ai-bj|≦εor1但し、aiは時刻tの位置情報の各計測点を表し、bjは時刻t-1の位置情報の各計測点を表している。また、Rは時刻t-1を基準としたときの時刻tの各計測点の回転移動量を示し、Tは時刻t-1を基準としたときの時刻tの各計測点の平行移動量を示す。iは時刻tの位置情報の計測点を特定するためのインデックスであり、jは時刻t-1の位置情報の計測点を特定するためのインデックスでる。εはレーザレンジファインダの精度を考慮した距離である。nは計測点の個数を示している。式1は、計測点aiをR回転移動させ、かつ、T平行移動させたときにおいて、計測点aiが計測点bjを中心として距離ε以内に存在しなかった場合、評価値Eに1のペナルティが課されると解釈することができる。したがって、式1では評価値Eが小さいほど時刻t-1の位置情報と時刻tの位置情報との一致度が高いことを示す。なお、式1において、fai,{bj}=1∋j,|ai-bj|≦εor0otherwiseとしてもよい。この場合、計測点aiが計測点bjを中心として距離ε以内に存在する場合、評価値Eに1ポイントが付与され、一致度が高いほど評価値Eが大きくなる。式1の計算では、明示的に対応点を決定する必要はなく、単に、計測点bjを中心として、距離ε内に計測点aiが存在するか否かを判定すればよい。つまり、式1ではL0ノルムを用いて評価値Eが定義されている。このようにして、計測点bjに対して距離ε内に計測点aiが存在するか否かを探索する手法はr近傍探索と呼ばれている。なお、ノルムとは距離を意味し、L0ノルムの他、L2ノルム等が存在する。L2ノルムは距離の2乗和であり、従来より広く用いられている。図5Aは、評価値Eの算出手法を説明する概念図である。図5Aに示すように、時刻t-1の位置情報を構成するある計測点bに対し、時刻tの位置情報を構成するある計測点a2は距離ε内に位置している。よって、式1はfx=0となり、評価値Eにはペナルティが課されない。一方、時刻tの位置情報を構成する別の計測点a1は計測点bに対し、距離ε内に位置していない。よって、式1はfx=1となり、評価値Eには1のペナルティが課される。図5Bは、時刻tの位置情報を構成する計測点a1~a3が回転移動される様子を示している。図5Cは、回転移動された計測点a1~a3と計測点b1~b3とにおいて評価値Eが算出される様子を示した図である。図5Cでは計測点b1,b2から距離ε内に計測点a1,a2が位置しているが、計測点b3から距離ε内に計測点a3が存在していない。そのため、評価値Eは1となる。図1に戻り、推定部13は、時刻tの位置情報の平行移動量T及び回転移動量Rを変更させて、一致度を最大にする平行移動量T及び回転移動量Rを探索し、自己位置を推定する。つまり、推定部13は、式1に示す評価値Eを最小にする回転移動量R及び平行移動量Tを探索する。このような探索を行い、その探索結果に基づいてマップを作成し、自己位置を推定する手法はSLAMと呼ばれている。具体的には、推定部13は、時刻t-1における位置情報において、時刻tにおける位置情報のローカル座標空間を平行移動量Tで平行移動し、かつ、回転移動量Rで回転させ、時刻t-1の位置情報と時刻tの位置情報との評価値Eを算出する処理を繰り返し、評価値Eを最小にする平行移動量T及び回転移動量Rを探索する。そして、推定部13は、評価値Eを最小にする平行移動量Tを時刻t-1から時刻tまでの移動体の移動量として求め、時刻t-1における移動体の位置に移動量を加えた値を時刻tにおける移動体の位置として求める。また、推定部13は、評価値Eを最小にする回転移動量Rを時刻t-1から時刻tまでの移動体の向きの変化量として求め、時刻t-1における移動体の向きに変化量を加えた値を時刻tにおける移動体の向きとして求める。ここで、時刻tにおける移動体の向きとしては、例えば、移動体の周辺空間を示す2次元のグローバル座標空間において、所定の基準方向に対する、時刻tにおける移動体の基準方向の角度を採用することができる。また、時刻tにおける移動体の位置としては、例えばグローバル座標空間における移動体の位置を採用することができる。また、回転移動量Rとしては、例えば、時刻t-1における移動体の向きに対する時刻tにおける移動体の向きの回転を示す2×2の行列を採用することができる。また、平行移動量Tとしては、例えば、時刻t-1から時刻tまでの移動体の移動量を示すx成分とy成分との値を示す採用することができる。図6は、評価値EとしてL2ノルムを採用した場合において、動的環境下で時刻t-1の位置情報と時刻tの位置情報とにおいてマッチング誤差が生じる理由を示した図である。時刻tにおいて、移動物体41は例えば人間のような移動する物体である。静止物体42は例えば壁のような静止している物体である。時刻t及び時刻t-1の位置情報において、静止物体42のみが存在していれば、評価値Eの最小値を求めると、時刻t-1における静止物体42を時刻tにおける静止物体42に一致させることができ、誤差は生じない。しかしながら、移動物体41が存在すると、移動物体41は時々刻々移動するため、時刻tにおける移動物体41及び静止物体42の位置関係と、時刻t-1における移動物体41及び静止物体42の位置関係とは異なってしまう。よって、評価値Eの最小値を求めたとしても、評価値EとしてL2ノルムを用いた場合は、移動物体41の影響により、時刻tにおける静止物体42に対して、時刻t-1における静止物体42を一致させることができない。その結果、静止物体42においてマッチング誤差が生じてしまうのである。このように動的環境下ではマッチング誤差が発生するが、本発明者らはL0ノルムを用いて評価値Eを算出すると、マッチング誤差を低減させることができることを見出した。そこで、本実施の形態では、評価値EをL0ノルムを用いて算出している。ノルムとは距離を示し、一般的によく用いられるのは、距離の2乗和であるL2ノルムである。L2ノルムを用いて最小の評価値Eを探索する場合、最適解を求める際に非線形最小二乗法を用いることができる。一方、L0ノルムを用いて最小の評価値Eを求める処理は、離散最適化問題に分類されるため、NP困難である。そのため、L0ノルムを採用した場合、時刻tに計測した位置情報の平行移動量T及び回転移動量Rを総当たり的に変化させて最小の評価値Eを探索する必要がある。図1に戻り、マップ生成部14は、推定部13により推定された時刻tでの移動体の位置及び向きをグローバル座標空間にプロットし、かつ、プロットした位置及び向きを基準とし、時刻tでの位置情報をプロットすることで、周辺空間の2次元マップを生成する。位置センサ16は、レーザレンジファインダにより構成され、一定周期で時系列に位置情報を取得し、位置情報取得部11に供給する。レーザレンジファインダとしては、SICKのLMS100を採用することができる。図7AはSICKのLSM100の外観図である。図7Bは本発明の実施の形態による移動体の外観図である。図7Bに示すように、位置センサ16は移動体の前側に取り付けられている。図8は、位置センサ16の仕様を示した表である。図8に示すように位置センサ16は、画角が270度であり、解像度が0.5度であり、測定可能な範囲が20mであり、周波数が30Hzであり、取得できる計測点の個数が540個である。図1に戻り、オドメトリ算出部15は、移動体の車輪に取り付けられた回転量センサ17から供給さされる計測データにしたがって移動体のオドメトリを算出し、推定部13に供給する。ここで、オドメトリは回転量センサ17からの計測データに従って推定される時刻t-1を基準としたときの時刻tでの移動体の自己位置である。本実施の形態では、オドメトリ算出部15は、位置センサ16と同じ周期で時系列にオドメトリを算出する。回転量センサ17は、移動体の左右一対の車輪のそれぞれに取り付けられ、移動体の車輪の回転量を示す計測データをオドメトリ算出部15に供給する。ここで、回転量センサ17は、位置センサ16と同じ周期で計測データを取得する。図7Bに示すように移動体は、前方に設けられた左右一対の車輪91,91、後方に設けられた左右一対の車輪92,92を備えている。そして、一対の回転量センサ17は、それぞれ、車輪92,92に取り付けられ、車輪92,92の回転量を計測する。その他、移動体は図7Bに示すように、車輪91,92の上部に設けられたフレーム93、フレーム93の底面931の表側に載置されたコンピュータ94、底面931の裏側に取り付けられたモータ95等を備えている。位置センサ16は、フレーム93の上部に設けられたバー932に取り付けられている。コンピュータ94は、上記の位置情報取得部11~オドメトリ算出部15の機能を実現する。また、コンピュータ94は、移動体の駆動制御プログラムが実装され、移動体の駆動制御を司る。例えば、コンピュータ94は、マップ生成部14により生成された2次元マップを参照し、物体との衝突を回避しながら、所定のゴールに向けて移動するようにモータ95を駆動させる。モータ95は例えば、車輪92,92に取り付けられた一対のモータにより構成され、コンピュータ94からの信号に基づいて駆動する。左右一対のモータ95は、コンピュータ94からの信号にしたがって、車輪92,92の回転量を変えることで移動体を旋回させる。次に、図1に示す自己位置推定装置の動作について説明する。図2は、本発明の実施の形態による自己位置推定装置の動作を示すフローチャートである。まず、位置情報取得部11は時刻tにおける位置情報を取得するS1。次に、推定部13は、時刻tにおける位置情報の平行移動量Tと回転移動量Rとを変化させて複数の探索候補を生成し、各探索候補の評価値Eを一致度算出部12に算出させ、評価値Eを最小にする探索候補を探索するS2。次に、推定部13は、S2で探索した探索候補の回転移動量Rと平行移動量Tとから移動体の自己位置を推定するS3。次に、マップ生成部14は、推定部13により推定された自己位置を2次元の座標空間にプロットし、移動体の周辺空間の2次元マップを生成するS4。S4の処理が終了すると、処理がS1に戻され、S1~S4の処理が繰り返される。図3は、図2のS2に示す探索処理の詳細を示すフローチャートである。まず、推定部13は、変数kに0を代入し、変数kを初期化するS21。次に、推定部13は、n1n1は2以上の整数個の探索候補を生成する。具体的には、推定部13は、オドメトリ算出部15により推定された移動体の自己位置から移動体の位置の事前確率を求め、この事前確率にしたがって、ランダムにn1パターンの回転移動量R及び平行移動量Tを決定し、決定したn1パターンの回転移動量Rと平行移動量Tとを用いて時刻tの位置情報を時刻t-1の位置情報に対してずらし、n1個の探索候補を生成するS22。ここで、事前確率としては、オドメトリ算出部15が推定した自己位置に近い位置ほど探索候補が多くなるような確率を採用することができる。そして、この事前確率にしたがった抽選処理によってn1個の探索候補が生成される。図9は探索候補が生成される処理を説明する図である。図9では、A~Dに向けて処理が進む。図9の各点は時刻tの位置情報の回転移動量Rと平行移動量Tとの要素をまとめたものを点の位置として現してある。図9Aでは、S22の処理によってn1個の探索候補が生成されている。次に、一致度算出部12は、n1個の探索候補のそれぞれにつき、式1を用いて時刻tの位置情報との評価値Eを算出するS23。次に、推定部13は、変数kが定数K未満の場合S24でNO、n1個の探索候補の評価値Eからn1個の探索候補のそれぞれの重み値wjを算出するS25。ここで、重み値wjは式2によって規定される。wj=expm-ER,T/k2ここで、m、kは定数である。mとしては例えば想定される評価値Eの最大値を採用することができる。jは探索候補を特定するインデックスである。式2に示すように評価値Eが小さくなるほど、重み値wjは大きくなる。次に、推定部13は、重み値wjに基づき、n1個の探索候補の中からn2n2<n1個の探索候補を抽出するS26。この場合、推定部13は、重み値wjの値が大きいほど抽選確率が高くなるような抽選処理を行い、n2個の探索候補を抽出してもよいし、重み値wjが大きい順にn2個の探索候補を抽出してもよい。S26の処理により、図9Aに示すn1個の探索候補から図9Bに示すようにn2個の探索候補が抽出される。図9Bの例では、n2=3と設定されているため、3個の探索候補が抽出されていることが分かる。図3に戻り、S27において、推定部13は、n2個の探索候補のそれぞれにつき、n3個の探索候補を生成する。この場合、推定部13は、n2個の探索候補の原点を基準とし、σx,σy,σθの正規分布にしたがって、n3パターンの回転移動量R及び平行移動量Tを決定し、n3個の探索候補を生成すればよい。例えば、n2=3の場合、3個の探索候補の原点を基準としてn3個の探索候補が生成される。この場合、n2個の探索候補の重み値wjの値に応じてn3個の個数を変えても良い。例えば、n2=3の場合の探索候補をZ1~Z3とし、探索候補Z1~Z3の重み値がw1~w3であったとする。但し、w1>w2>w3である。この場合、探索候補Z1~Z3から生成される探索候補の個数をそれぞれn31~n33とすると、重み値w1に応じて、n31~n33の値を決定し、探索候補を生成すればよい。なお、n31>n32>n33である。図9Cに示すように、S27の処理により、n2個の探索候補を基準としてn3個の探索候補が生成され、合計、n2×n3個の探索候補が生成されていることが分かる。次に、推定部13は変数kを1インクリメントしS28、処理をS23に戻す。S24において、変数kが定数K以上になった場合S23でNO、推定部13は、評価値Eが最小の探索候補を特定するS29。なお、2ループ目以降のS23において、S27で算出された全探索候補に対して評価値Eが算出される。このように、推定部13は、S23~28の処理をK回繰り返し、評価値Eが最小の探索候補を特定する。そして、探索候補を生成するにあたり、解となる可能性が高い回転移動量R及び平行移動量Tを持つ探索候補を重点的に生成する重点的サンプリングを行う。そのため、解となる探索候補を効率良く求めることが可能となる。評価値Eを最小化する解を求める手法として、ベイズ推定を用いる手法が知られている。この手法は、L2ノルムを用いて評価値Eを算出する手法において、位置推定の信頼性が移動物体の影響によって一時的に乏しくなることを防止し、位置推定の頑強性を高めるために用いられる。本実施の形態では、S26に示すように、n1個からn2個に探索候補を絞り、以降の処理が行われている。このように、本実施形態ではベイズ推定ではなく、maximumaposterioriMAP推定のように、解を絞り込んで次のステップに処理を進める手法を採用している。そのため、解の正確性に懸念が残るが、L0ノルムは移動する物体に対して頑健であるため、MAP推定を適用しても問題はない。その結果、探索候補の個数の増大を抑制し、最小の評価値Eを探索する処理を高速化することができる。なお、図3において、S22が第1処理に相当し、S25,S26が第2処理に相当し、S27が第3処理に相当し、S24,S29が第4処理に相当する。次に、図3のS23に示す評価値の算出処理の詳細について説明する。ベクトルデータをハッシュ値に変換するアルゴリズムとして、LSHLocalitySensitiveHashingが知られているAlexandrAndoniMayurDatarNicoleImmorlicaPiotrIndykandVahabMirrokniLocalitySensitiveHashingSchemeBasedonpStableDistributionsNearestNeighborMethodsinLearningandVisionMITPress2006。上記のようにL0ノルムを用いた評価値Eにおいて、最小の評価値Eを探索する処理は最適化が困難であり、総当り法で計算されることが多い。したがって、探索範囲及び解像度によっては計算量が爆発的に増大してしまう。そのため、評価値Eの算出手法としては、可能な限り高速な手法を採用することが好ましい。L0ノルムを用いた評価値Eにおいて最小の評価値Eを探索する場合、r近傍を求める際の計算の負荷が大きい。r近傍を求める単純なアルゴリズム例えば、Bruteforceの計算量はOnであるが、kd-treeやボロノイ図を用いれば、計算量をOlognまで減らすことができる。しかしながら、LSHは、近似的ではあるがこれらの手法よりも更に高速であることが知られている。そこで、本実施の形態では、LSHを採用している。LSHは、データの距離が近いほど、高い確率で同じハッシュ値をとる性質を有する。同じハッシュ値に分類されたデータのみが近傍点の候補であるとみなすことで、計算量を大幅に削減することができる。図4は、評価値Eの算出処理の詳細を示すフローチャートである。まず、一致度算出部12は、時刻t-1の位置情報から複数のハッシュテーブルを生成するS41。ここで、ハッシュテーブルは、時刻t-1の位置情報の各計測点を所定のハッシュ関数を用いて格子空間に投影し、格子空間の各位置における計測点の存在の有無を示すテーブルである。格子空間は、時刻t-1における位置情報のローカル座標空間を距離εに基づき、格子状に区切ることで生成される空間である。ここで、ハッシュ関数hは式3により表される。hb=<pbq/ε>3但し、<>はpbq/ε以下の最大の整数を示す。pは1を平均とする正規分布により決定される。qは一様分布により0からεの範囲でランダムに決定される。bは計測点を示している。本実施の形態では、以下に示す2つのハッシュ関数hx,hyを採用する。hxb=<pbxqx/ε>3-1hyb=<pbyqy/ε>3-2なお、qx,qyは、qのx,y成分であり、一様分布により0からεの範囲でランダムに決定される。bx,byは計測点bのx,y成分である。計測点bはx軸及びy軸で規定されるローカル座標空間に位置している。したがって、一致度算出部12は、式3-1に示すように、hxbを用いて計測点bの格子空間におけるx座標の値を求め、式3-2に示すように、hybを用いて計測点bの格子空間におけるy座標の値を求める。図10はハッシュテーブルを示した概念図である。図10Aは時刻t-1の位置情報のローカル座標空間に設定された格子空間を示している。図10Bは、図10Aに示す格子空間に基づいて生成されたハッシュテーブルT1~T3を示している。図10Aにおいて、計測点bは式3-1,3-2の<>の演算が施される前の位置にプロットされている。図10Aにおいて、例えば1行1列目の格子には計測点bが存在している。よって、この計測点bに<>の演算を施してハッシュ値hxb,hybを求めると、図10Bに示すように、計測点bはハッシュテーブルT1の1行1列目のビンに位置することになる。よって、ハッシュテーブルT1の1行1列目のビンには計測点bの存在を示す、例えば1のラベルが設定される。一方、図10Aにおいて、例えば1行3列目の格子には計測点bが存在していない。よって、図10Bに示すように、ハッシュテーブルT1の1行3列目のビンには計測点bの非存在を示す例えば0のラベルが設定される。このようにして、計測点bが式3-1、3-2を用いて格子空間に投影され、ハッシュテーブルT1が生成される。ここで、一致度算出部12は、式3-1、3-2に示すハッシュ関数を複数種類用意して、複数のハッシュテーブルを生成する。図10Bの例では、3種のハッシュ関数h1=h1xb,h1yb~h3=h3xb,h3ybを用いて3個のハッシュテーブルT1~T3が生成されている。この場合、一致度算出部12は、式3-1、3-2に示す、p,qx,qyの値を異なる値に設定することで複数種類のハッシュ関数を生成すればよい。このように、複数のハッシュテーブルT1~T3を採用することで、計測点aが計測点bの距離εの範囲内にあるにも関わらず、たまたまハッシュテーブルにはハッシュ値が存在しなかったというような、探索ミスを防止することができる。なお、上記では、3-1、3-2で示すハッシュ関数を用いたが、3-1’、3-2’で示すハッシュ関数を採用してもよい。hxb=<bxqx/pε>3-1’hyb=<byqy/pε>3-2’3-1、3-2との違いは、pが分母に移され、εに乗じられている点である。これにより、ローカル座標空間に設定される格子の長さが変わり、ハッシュテーブルにより多くの多様性を持たせることができる。図4に戻り、S42において、一致度算出部12は、時刻tの位置情報の各計測点aをハッシュ関数h1~h3を用いて投影空間に投影し、計測点aのハッシュ値h1a~h3aを求める。次に、一致度算出部12は、求めたハッシュ値h1a~h3aのいずれかが対応するハッシュテーブルT1~T3に存在すれば、評価値Eにペナルティを課さずに評価値Eを算出するS43。例えば、ハッシュ値h1aで示されるハッシュテーブルT1のビンに1のラベルが設定されていれば、ハッシュ値h2a,h3aで示されるハッシュテーブルT2,T3のビンに0のラベルが設定されていても、計測点aから距離ε内に計測点bが位置するとみなされ、評価値Eにペナルティが課されない。一致度算出部12は、このような処理を各計測点aに対して行い、付与したペナルティの合計値を評価値Eとして算出する。このように時刻t-1の計測点bに基づいて予めハッシュテーブルを生成しておくことで、ハッシュテーブルの参照にかかる計算量をO1にすることができる。なお、上記実施の形態では、位置情報は2次元としたが、これに限定されず3次元であってもよい。この場合、位置センサ16として、例えば深度センサを採用すればよい。そして、周辺空間を3次元のグローバル座標空間で表し、推定した移動体の自己位置プロットしていき、3次元マップを採用してもよい。<実験例>次に、本発明の実施の形態による自己位置推定装置が適用された移動体の実験について説明する。<実験環境>本実験では、移動体として、車椅子型移動ロボットEMC230を採用し、これに図8に示す仕様のレーザレンジファインダLRFを取りつけ、センシングを行った。LRFがセンシングした情報は極座標で表現され、角度方向に等間隔である。センサからの距離が増大すると点の密度が疎になるため、セグメンテーションを行い、セグメント内の点の間隔がε以下になるよう補間した。実験場所として、奈良先端科学技術大学院大学情報棟1階を用いた。動的環境をLRFで計測し、時刻t,時刻t-1の位置情報のマッチングを行った。この実験において、移動体は静止した状態で動的環境の計測を行った。動的環境は幅10m程の廊下で奥行き20mの範囲で、25人前後の歩行者が移動していた。図11Aは実験場所を示した図であり、図11Bはこの実験場所に人物が行き来する動的環境を示した図である。図12は、実験場所に人物が行き来していない静的環境下で生成した周辺空間の2次元マップを示している。この2次元マップはRBPF-SLAMを用いて生成されたものであり真値とみなせる。<実験結果>この実験では最小の評価値Eを探索する際の探索範囲を、x軸方向、y軸方向にそれぞれプラスマイナス20[cm]とし、角度をプラスマイナス0.3[rad]と設定した。そして、この探索範囲において、1.0[cm]、0.01[rad]=約0.57[deg]刻みで総当たり法で、回転移動量R、平行移動量Tを変化させて、評価値Eの最小値を探索した。そして、評価値EとしてL0ノルムを採用した場合、L2ノルムを採用した場合、M-estimatorを採用した場合のマッチングの位置推定精度の比較を行った。この際、M-estimatorにはBiweight法に基づき、距離dに対し、以下の評価関数ρdを用いた。ρd=B2/2d≧BorB2/21-1-d/B23d<Bここで、Bは任意の残差値であり、0.01[m]とした。図13は、評価値Eとして、L2ノルム、M-estimator、及びL0ノルムを用いた場合の実験結果を示した表である。L2ノルムでは最大14[cm]のマッチング誤差が発生しており、平均二乗誤差RMSEも10[cm]ほどあった。一方、L0ノルムではマッチング誤差は最大1[cm]であり、LRFの計測誤差内に収まっていることがわかる。次に、LRFにより200フレーム分の位置情報を測定し、L2ノルム、M-estimator、及びL0ノルムをそれぞれ用いて隣接するフレーム同士の位置情報のマッチングを行い、2次元マップを生成した。図14は、L2ノルムを採用した場合に作成した2次元マップである。図15は、M-estimatorを採用した場合に作成した2次元マップである。図16は、L0ノルムを採用した場合に作成した2次元マップである。図14に示すようにL2ノルムを採用した場合、マッチング誤差により、移動体が移動していると誤認識され、2次元マップの生成に失敗していることが分かる。図15に示すように、M-estimatorを採用した場合、大きなマッチング誤差はなかったが、累積したマッチング誤差により、移動体が移動していると誤認識され、2次元マップの生成に失敗している。一方、図16に示すように、L0ノルムを採用した場合、フレーム間のマッチング誤差がほとんど発生せず、自己位置推定装置は移動体が静止している状態を計測できている。この実験結果から分かるようにL0ノルムを採用した場合、他の手法を採用した場合に比べ、動的環境下において、高い頑健性を有していることが分かる。次に、本実施の形態による自己位置推定装置の優位性を検証するため、LSHを採用した場合、Brute-forceを採用した場合、及びkd-treeを採用した場合の計算時間の比較を行った。なお、評価値EとしてはL0ノルムを採用した。探索範囲は、上記の値と同じである。合計24000通りの評価値Eを計算し、総計算時間Averagecalculationtime、1秒あたりに計算できるL0ノルムの数Frequencyofcalculationaec、及びr近傍点が発見できた計測点の平均個数Averagematchpointsを求めた。図17は、Brute-force、kd-tree、LSHを用いて計算時間を比較する実験を行った場合の実験結果をまとめた表である。図17に示すように、Brute-force、kd-treeに比べ、LSHを用いた場合、総計算時間が短いことがわかる。しかしながら、Brute-force及びkd-treeに比べ、LSHはr近傍点が発見できた計測点の平均個数Averagematchpointsが15個ほど少ない。これは、LSHによる近傍点探索が近似であることが原因である。この一致点数の差の影響を、複数フレームのマッチングにより2次元マップを生成することで調べる。図18は静的環境下でRBPF-SLAMを用いて生成した2次元マップである。この2次元マップを真値と見なす。図19は、動的環境下で移動体を移動させながら計測した位置情報を利用し、L0ノルムを用いた評価値Eで位置情報同士のマッチングを行って生成した2次元マップである。この2次元マップ内に存在する点は移動する人の軌跡を示している。図20は、L2ノルムを用いた評価値Eで位置情報同士のマッチングを行って生成した2次元マップである。両2次元マップのエッジの形状を比較すると、L0ノルムの方が動的環境下でも比較的正確に2次元マップが生成されていることが分かる。更に、図21に示すような大規模な2次元マップを生成した。図21は、RBPF-SLAMを用いて生成した2次元マップである。この2次元マップを真値と見なす。L0ノルムでは、フレーム間のマッチングしか行っていないため、微少なマッチング誤差が累積し、図22に示すように地図が歪んでしまう。図22は、L0ノルムを用いて生成された2次元マップである。この2次元マップは、図21と同じ環境下で生成されたものである。図22に現れた歪みは、例えばループクロージング等の手法を適用すれば改善することができる。上記の自己位置推定装置及び移動体の技術的特徴は以下のようにまとめられる。1上記の自己位置推定装置は、移動体の自己位置を推定する自己位置推定装置であって、前記移動体の周辺空間に存在する各物体の位置情報を時系列に取得する位置情報取得部と、前記位置情報取得部により第1時刻で取得された第1位置情報を、前記第1時刻と時系列的に前又は後の時刻である第2時刻で取得された第2位置情報に対して平行移動及び回転移動させたときの前記第1位置情報と前記第2位置情報との一致度を算出する一致度算出部と、前記第1位置情報の平行移動量及び回転移動量を変更させて、前記一致度を最大にする前記平行移動量及び前記回転移動量を探索し、前記自己位置を推定する推定部とを備え、前記一致度算出部は、前記第1位置情報を構成するある計測点に対し、一定距離内に前記第2位置情報を構成するある計測点が存在すれば、前記一致度に所定のポイントを付与し、付与したポイントの合計値を前記一致度として算出する。この構成によれば、第2位置情報に対して第1位置情報がずらされて一致度を最大とする平行移動量及び回転移動量が探索される。そして、一致度は、第1位置情報を構成するある計測点に対し、一定距離内に第2位置情報のある計測点が位置すれば所定のポイントが付与される。つまり、本構成では、静止物体のみならず移動物体を含む動的環境下においても頑強なL0ノルムを用いて一致度が算出されている。そのため、移動物体を含む未知環境下において、移動体の自己位置を正確に推定することができる。2前記一致度算出部は、前記周辺空間を前記一定距離に基づいて格子状に区切ることで格子空間を生成し、前記第2位置情報の各計測点を所定のハッシュ関数を用いて前記格子空間に投影し、前記格子空間の各位置における前記計測点の存在の有無を示すハッシュテーブルを生成し、前記第1位置情報の各計測点を前記ハッシュ関数を用いて前記格子空間に投影し、ある計測点の前記格子空間における位置が前記ハッシュテーブルに存在した場合、前記一致度に前記ポイントを付与することが好ましい。この構成によれば、第2位置情報の各計測点が所定のハッシュ関数を用いて格子空間に投影され、各計測点の存在の有無を示すハッシュテーブルが生成される。そして、第1位置情報の各計測点もハッシュ関数を用いて格子空間に投影され、投影された計測点の位置がハッシュテーブルに存在すれば、第1位置情報を構成するある計測点の近傍に第2位置情報を構成するある計測点が存在するとみなされ、一致度に所定のポイントが付与される。このように、本構成では、第1、第2位置情報の計測点のハッシュ値同士を比較することで一致度が算出されているため、一致度を最大とする平行移動量及び回転移動量を高速に求めることができる。3前記一致度算出部は、種類の異なる複数のハッシュ関数を用いて前記ハッシュテーブルを複数生成し、前記第1位置情報のある計測点を各ハッシュ関数を用いて前記格子空間に投影し、いずれかの位置が対応するハッシュテーブルに存在した場合、前記一致度に前記ポイントを付与することが好ましい。この構成によれば、複数のハッシュテーブルが採用されているため、第1位置情報のある計測点が第2位置情報のある計測点に対し、距離εの範囲内にあるにも関わらず、たまたまハッシュテーブルにはハッシュ値が存在しなかったというような、探索ミスを防止することができる。4前記推定部は、前記平行移動量及び前記回転移動量をランダムに変化させて前記第1位置情報からn1n1は正の整数個の探索候補を生成する第1処理と、各探索候補の前記一致度に基づき、各探索候補の重み値を算出し、算出した重み値に基づいて、n2n2<n1個の探索候補を抽出する第2処理と、抽出したn2個の探索候補のそれぞれについて、所定の確率分布に基づいて前記平行移動量及び前記回転移動量を変化させてn3n3は正の整数個の探索候補を生成する第3処理と、前記n3個の探索候補のそれぞれに対し、前記重み値を算出し、算出した重み値が最大となる探索候補を探索解として求める第4処理とを備えることが好ましい。この構成によれば、解となる可能性の高い位置に重点的に第1位置情報がずらされて、複数の探索候補が生成されて第2位置情報との一致度が求められている。そのため、一致度を最大にする探索候補を効率良く算出することができる。5前記第4処理は、前記第2、第3処理を所定回数繰り返し、前記重み値が最大となる探索候補を前記探索解として求めることが好ましい。この構成によれば、第2、第3処理が繰り返されるため、一致度を最大にする探索候補をより正確に算出することができる。6前記移動体のオドメトリを算出するオドメトリ算出部を更に備え、前記第1処理は、前記オドメトリから得られる前記移動体の位置の事前確率に基づき、前記平行移動量及び前記回転移動量をランダムに変化させてn1個の探索候補を生成することが好ましい。この構成によれば、第1処理において、解となる可能性の高い位置に重点的に第1位置情報をずらして探索候補を生成することができ、探索精度をより高めることができる。7上記の移動体は、1~6のいずれかの移動体と、前記位置情報を取得する位置センサとを備える。この構成によれば、未知環境下において自己位置を精度良く推定しながら、移動することができる移動体を提供することができる。"