(57)【要約】【課題】メモリ使用量を低減すること。【解決手段】（Ｃ）は、時刻ｔ＝１でのカップリングツリーＴの枝刈り後の状態を示す。枝刈りとは、不要となったパーティクルノードを削除する処理である。パーティクルノードの削除にしたがって、削除されたパーティクルノード内のランドマークノードも枝刈りにより削除される。（Ｃ）では、（Ｂ）の状態において、子ノードを持たない親ノードが削除される。たとえば、パーティクルノードＰ０３，Ｐ０４，Ｐ０６は、子ノードを持たないため削除される。（Ｃ）では、パーティクルノードＰ０１，Ｐ０２，Ｐ０７，Ｐ０８は、子ノードが１つだけの親ノードであり、かつ、パーティクルノードＰ０１，Ｐ０２，Ｐ０７，Ｐ０８には、親ノードは存在しない。このため、親ノードであるパーティクルノードＰ０１，Ｐ０２，Ｐ０７，Ｐ０８は削除される。【選択図】図１
2014016831.tif 000002
【特許請求の範囲】
【請求項１】
各々自装置の位置および向きを示すパーティクルノード群を生成して時系列に階層化し、前記パーティクルノード群の各パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを生成元のパーティクルノードに関連付けて生成して時系列に階層化し、階層間で同一ランドマークを示すランドマークノードを関連付けることにより、記憶部内でツリー構造を構築する構築部と、
前記ツリー構造を参照して、最下層のパーティクルノードを除く残余のパーティクルノード群の中から、下位階層に関連付けられていないパーティクルノードを検出する検出部と、
前記検出部によって検出されたパーティクルノードおよび当該パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを、前記ツリー構造から削除することにより、前記ツリー構造を更新する更新部と、
を有することを特徴とする更新装置。
【請求項２】
各々自装置の位置および向きを示すパーティクルノード群を生成して時系列に階層化し、前記パーティクルノード群の各パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを生成元のパーティクルノードに関連付けて生成して時系列に階層化し、階層間で同一ランドマークを示すランドマークノードを関連付けることにより、記憶部内でツリー構造を構築する構築部と、
前記ツリー構造を参照して、前記パーティクルノード群の中から、下位階層に関連付けられたパーティクルノードが１つであり、かつ、上位階層に関連付けられていないパーティクルノードを検出する検出部と、
前記検出部によって検出されたパーティクルノードおよび当該パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを、前記ツリー構造から削除することにより、前記ツリー構造を更新する更新部と、
を有することを特徴とする更新装置。
【請求項３】
各々自装置の位置および向きを示すパーティクルノード群を生成して時系列に階層化し、前記パーティクルノード群の各パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを生成元のパーティクルノードに関連付けて生成して時系列に階層化し、階層間で同一ランドマークを示すランドマークノードを関連付けることにより、記憶部内でツリー構造を構築する構築部と、
前記ツリー構造を参照して、前記パーティクルノード群の中から、上位階層に関連付けられているパーティクルノードが自ノード以外の他の下位階層のパーティクルノードに関連付けられていないパーティクルノードを検出する検出部と、
前記検出部によって検出されたパーティクルノードおよび当該パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを、前記上位階層に関連付けられているパーティクルノードに統合することにより、前記ツリー構造を更新する更新部と、
を有することを特徴とする更新装置。
【請求項４】
前記検出部によって検出されたパーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを選択する選択部と、
前記選択部によって選択されたランドマークノードについて、上位階層および下位階層に関連付けられているランドマークノードを特定する特定部と、を有し、
前記更新部は、
前記特定部によって特定された特定結果に基づいて、前記選択されたランドマークノードの生成元である前記検出されたパーティクルノードを、当該検出されたパーティクルノードの生成元である前記上位階層に関連付けられているパーティクルノードに統合することにより、前記ツリー構造を更新することを特徴とする請求項３に記載の更新装置。
【請求項５】
最上位階層のパーティクルノードを生成元とするランドマークノード群のうち、下位階層のランドマークノードに関連付けられていないランドマークノードを抽出する抽出部と、
最下位階層のパーティクルノードにより特定される自装置の位置および向きに応じた観測範囲に、前記抽出部によって抽出されたランドマークノードが示すランドマークが存在するか否かを判断する判断部と、
前記判断部によって存在しないと判断されたランドマークを示すランドマークノードを前記記憶部から前記記憶部とは異なる他の記憶部に格納する格納部と、
を有することを特徴とする請求項１〜４のいずれか一つに記載の更新装置。
【請求項６】
前記抽出部は、
前記他の記憶部に記憶されているランドマークノード群のうち、前記最下位階層のパーティクルノードにより特定される自装置の位置および向きに応じた観測範囲に存在するランドマークを示すランドマークノードを抽出し、
前記格納部は、
前記抽出部によって抽出されたランドマークノードを、前記記憶部内のツリー構造における前記最上位階層のパーティクルノードに関連付けて格納し、
前記構築部は、
前記格納部によって格納されたランドマークノードと、当該ランドマークノードが示すランドマークと同一ランドマークを示す下位階層のランドマークノードとを関連付けることを特徴とする請求項５に記載の更新装置。
【請求項７】
コンピュータに、
各々自装置の位置および向きを示すパーティクルノード群を生成して時系列に階層化し、前記パーティクルノード群の各パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを生成元のパーティクルノードに関連付けて生成して時系列に階層化し、階層間で同一ランドマークを示すランドマークノードを関連付けることにより、記憶部内でツリー構造を構築し、
前記ツリー構造を参照して、最下層のパーティクルノードを除く残余のパーティクルノード群の中から、下位階層に関連付けられていないパーティクルノードを検出し、
前記検出されたパーティクルノードおよび当該パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを、前記ツリー構造から削除することにより、前記ツリー構造を更新する、
処理を実行させることを特徴とする更新プログラム。
【請求項８】
コンピュータが、
各々自装置の位置および向きを示すパーティクルノード群を生成して時系列に階層化し、前記パーティクルノード群の各パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを生成元のパーティクルノードに関連付けて生成して時系列に階層化し、階層間で同一ランドマークを示すランドマークノードを関連付けることにより、記憶部内でツリー構造を構築し、
前記ツリー構造を参照して、最下層のパーティクルノードを除く残余のパーティクルノード群の中から、下位階層に関連付けられていないパーティクルノードを検出し、
前記検出されたパーティクルノードおよび当該パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを、前記ツリー構造から削除することにより、前記ツリー構造を更新する、
処理を実行することを特徴とする更新方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、更新装置、更新方法、および更新プログラムに関する。
【背景技術】
【０００２】
従来、ランドマーク地図作成には、パーティクルフィルタが採用される場合がある。パーティクルフィルタは移動体に実装され、個々のパーティクルノードに相当する複数の仮説となる移動体の位置情報を生成し、生成した位置情報に基づいてランドマークの位置情報を生成することにより環境地図を構築する技術である。パーティクルフィルタでは、順次生成された仮説となる移動体の位置情報において、整合性の良い位置情報に高い点数が付けられ、より多くの子ノードが生成される。整合性の悪い仮説となる位置情報や点数の低い仮説となる位置情報については、少ない数の子ノードが生成されるか、または消滅させられる。
【０００３】
また、親パーティクルノードから子パーティクルノードが生成されると、生成された子パーティクルノードには、移動体の位置情報のほか移動体から観測されたランドマークの位置情報が生成される。生成された各位置情報は親パーティクルノードから継承される。このように、各位置情報についての整合性の評価に応じた生成、消滅、および親パーティクルノードからの継承を繰り返すことによって、ランドマークの位置情報を有する環境地図が構築される。
【０００４】
また、移動体にロボットを採用した技術として、超音波センサを用いてロボットを壁沿いに移動させることにより、ロボットの位置推定を行う技術が開示されている。当該技術は、新しいランドマークを見つけた場合、推定したロボットの位置に基づいて、ランドマークの位置を算出し登録することにより、地図を作成する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００６−１８４９７６号公報
【非特許文献】
【０００６】
【非特許文献１】Ｍｉｃｈａｅｌ  Ｍｏｎｔｅｍｅｒｌｏ，Ｓｅｂａｓｔｉａｎ  Ｔｈｒｕｎ，Ｄａｐｈｎｅ  Ｋｏｌｌｅｒ  ａｎｄ  Ｂｅｎ  Ｗｅｇｂｒｅｉｔ，「ＦａｓｔＳＬＡＭ：Ａ  Ｆａｃｔｏｒｅｄ  Ｓｏｌｕｔｉｏｎ  ｔｏ  ｔｈｅ  Ｓｉｍｕｌｔａｎｅｏｕｓ  Ｌｏｃａｌｉｚａｔｉｏｎ  ａｎｄ  Ｍａｐｐｉｎｇ  Ｐｒｏｂｌｅｍ」，ｔｈｅ  ＡＡＡＩ  Ｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ（２００２）
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述した従来技術では子パーティクルノードが順次生成されるため、移動体が移動を継続すると、生成された子パーティクルノードの蓄積により移動体のメモリ容量が不足する。メモリ容量不足に陥ると、それ以上子パーティクルノードの蓄積ができなくなるため、移動体の位置やランドマークの位置が観測できなくなる。したがって、地図情報の生成が継続できなくなるという問題がある。一方、パーティクルノードの生成量を制限すると、それに伴い、移動体の移動範囲や移動時間が制限され、地図情報の生成範囲が抑制されるという問題がある。また、パーティクルフィルタは移動体に搭載されるため、搭載できるメモリの容量には限界がある。
【０００８】
本発明は、パーティクルフィルタによるメモリ使用量の増加を抑制することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の一側面によれば、各々自装置の位置および向きを示すパーティクルノード群を生成して時系列に階層化し、前記パーティクルノード群の各パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを生成元のパーティクルノードに関連付けて生成して時系列に階層化し、階層間で同一ランドマークを示すランドマークノードを関連付けることにより、記憶部内でツリー構造を構築し、前記ツリー構造を参照して、最下層のパーティクルノードを除く残余のパーティクルノード群の中から、下位階層に関連付けられていないパーティクルノードを検出し、検出されたパーティクルノードおよび当該パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを、前記ツリー構造から削除することにより、前記ツリー構造を更新する更新装置、更新方法、および更新プログラムが提案される。
【発明の効果】
【００１０】
本発明の一側面によれば、パーティクルフィルタによるメモリ使用量の増加を抑制することができるという効果を奏する。
【図面の簡単な説明】
【００１１】
【図１】図１は、本実施の形態にかかるパーティクルノードの枝刈り例を示す説明図である。
【図２】図２は、更新装置のハードウェア構成例を示すブロック図である。
【図３】図３は、地図情報ＤＢの記憶内容の一例を示す説明図である。
【図４】図４は、時刻ｔ＝２におけるカップリングツリーＴの更新状態を示す説明図である。
【図５】図５は、時刻ｔ＝３におけるカップリングツリーＴの更新状態を示す説明図である。
【図６】図６は、時刻ｔ＝３におけるカップリングツリーＴの統合処理を示す説明図である。
【図７】図７は、時刻ｔ＝３におけるカップリングツリーＴの統合処理後の状態を示す説明図である。
【図８】図８は、時刻ｔ＝４におけるカップリングツリーＴでの新規パーティクルノードの生成状態を示す説明図である。
【図９】図９は、時刻ｔ＝４におけるカップリングツリーＴでのパーティクルノードの削除状態を示す説明図である。
【図１０】図１０は、時刻ｔ＝４におけるカップリングツリーＴの更新状態（その１）を示す説明図である。
【図１１】図１１は、時刻ｔ＝４におけるカップリングツリーＴの更新状態（その２）を示す説明図である。
【図１２】図１２は、時刻ｔ＝４におけるカップリングツリーＴの統合処理を示す説明図である。
【図１３】図１３は、時刻ｔ＝４におけるカップリングツリーＴの統合処理後の状態を示す説明図である。
【図１４】図１４は、時刻ｔ＝ＺにおけるカップリングツリーＴの更新状態を示す説明図である。
【図１５】図１５は、時刻ｔ＝Ｚ＋１におけるカップリングツリーＴの状態を示す説明図である。
【図１６】図１６は、更新装置２００の機能的構成例を示すブロック図である。
【図１７】図１７は、類似ランドマークノードの探索例を示す説明図である。
【図１８】図１８は、更新装置２００による更新処理手順例を示すフローチャート（その１）である。
【図１９】図１９は、更新装置２００による更新処理手順例を示すフローチャート（その２）である。
【図２０】図２０は、図１９に示した枝刈り処理（ステップＳ１９０６）の詳細な処理手順例を示すフローチャートである。
【図２１】図２１は、図２０に示した統合処理（ステップＳ２００８）の詳細な処理手順例を示すフローチャートである。
【発明を実施するための形態】
【００１２】
以下に添付図面を参照して、この発明にかかる更新装置、更新方法、および更新プログラムの実施の形態を詳細に説明する。なお、パーティクルフィルタにより時刻ごとに生成されるパーティクルノードの生成個数は、たとえば、７００個〜１００００個程度であるが、本明細書では、説明を単純化するため、時刻ごとの生成個数を８個として説明する。なお、パーティクルノードの符号を、Ｐｘｙとする。ｘはパーティクルノードが所属する階層番号を示し、ｙは階層番号ｘでの固有な番号を示す。階層番号ｘは時刻に対応する。たとえば、時刻ｔ＝０の第０階層では、８個のパーティクルノードＰ０１〜Ｐ０８が生成される。また、本実施の形態の更新装置は、自律移動型のロボットなどの移動体に搭載される。ロボットには、２個のステレオカメラが搭載され、ランドマークの画像やロボットからランドマークまでの距離が観測可能である。以下、ロボットに更新装置を搭載された場合を例に挙げて説明する。
【００１３】
＜パーティクルノードの枝刈り例＞
図１は、本実施の形態にかかるパーティクルノードの枝刈り例を示す説明図である。（Ａ）は、時刻ｔ＝０のときのカップリングツリーＴを示す。カップリングツリーＴとは、パーティクルノードが階層化されたデータ構造である。時刻ｔ＝０では、第０階層Ｒ０の８個のパーティクルノードが生成される。８個のパーティクルノードは、ロボットの現在位置の仮説群である。すなわち、各パーティクルノードは、時刻ｔ＝０でのロボットの現在の位置および向きを示し、位置および向きは、パーティクルごとに異なる。
【００１４】
（Ａ）において、各パーティクルノード内に示した○図形は、ランドマークノードである。ランドマークノードは、ランドマークの識別情報と位置を有する。パーティクルノード内のランドマークノードは、ロボットが存在する空間内のランドマーク群のうち、ロボットに搭載されたセンサにより検出されたランドマークの位置と属性を示すランドマークノードである。このように、パーティクルノードとランドマークノードには関連性があり、ランドマークノードは、観測の起点となったパーティクルノードへのポインタを有する。以下、観測の起点となったパーティクルノードが示すロボットの位置および向きで観測されたランドマークを示すランドマークノードを、「所属ランドマークノード」と称す。
【００１５】
また、各パーティクルノードについては、尤度が算出される。尤度の計算については、公知のパーティクルフィルタと同様である。尤度は、パーティクルの尤もらしさを示す。親階層である第０階層のパーティクルノード群は、その尤度の高さに応じて、子階層である第１階層Ｒ１で生成される８個のパーティクルノードの親ノードとなる。
【００１６】
（Ｂ）は、次時刻ｔ＝１のときのカップリングツリーＴを示す。時刻ｔ＝１では、第０階層Ｒ０の各パーティクルノードの尤度に従って、第１階層Ｒ１の８個のパーティクルノードが生成される。尤度が高いパーティクルノードほどより多くの子ノードを生成することができる。第１階層Ｒ１のパーティクルノードは、第０階層Ｒ０のパーティクルノード群のいずれかのパーティクルノードの子ノードである。
【００１７】
（Ｂ）では、パーティクルノードＰ０１を継承したパーティクルノードＰ１１、パーティクルノードＰ０２を継承したパーティクルノードＰ１２、パーティクルノードＰ０５を継承したパーティクルノードＰ１３〜Ｐ１６、パーティクルノードＰ０７を継承したパーティクルノードＰ１７、パーティクルノードＰ０８を継承したパーティクルノードＰ１８が生成される。
【００１８】
継承により、親ノードの位置および向きが子ノードに渡される。そして、継承された親ノードの位置および向きと、時刻ｔ＝０からｔ＝１までの移動距離とにより、子ノードの位置および向きが得られる。なお、パーティクルノードＰ０３，Ｐ０４，Ｐ０６については、他のパーティクルノードＰ０１，Ｐ０２，Ｐ０５，Ｐ０７，Ｐ０８よりも尤度が低いため、子ノードが生成されない。図１では、太矢印の始端が親ノードであり、終端が子ノードである。以降の図でも同様である。
【００１９】
（Ｂ）では、時刻ｔ＝１での第１階層Ｒ１の各パーティクルノードＰ１１〜Ｐ１８が示すロボットの位置および向きにおいて、ロボットに搭載されたセンサにより、ランドマークが検出される。この場合、親となるパーティクルノードが示す位置から、検出されたランドマークまでの距離が算出される。
【００２０】
各パーティクルノードＰ１１〜Ｐ１８では、検出されたランドマークノードが親であるパーティクルノード内のランドマークノードと同一ノードであるか否かが判断される。たとえば、識別情報が同一である場合、両ランドマークノードは同一ノードであると判断される。また、両ランドマークの画像パターンなどの特徴により同一性を判断してもよい。同一ノードである場合、親であるランドマークノード（親ノード）が示す位置と、子であるランドマーク（子ノード）までの距離と、により、子ノードであるランドマークの位置が得られる。そして、親子関係のあるランドマークノードはポインタにより関連付けられる。図１では、細矢印の始端が親ノードであり、終端が子ノードである。以降の図でも同様である。
【００２１】
たとえば、（Ｂ）の場合、パーティクルノードＰ１１が示す位置から、あるランドマークノードＬ１が示すランドマークまでの距離が計測されたとする。親であるパーティクルノードＰ０１にはランドマークノードＬ１が存在するため、ランドマークノードＬ１が示すランドマークの地図上の位置と、パーティクルノードＰ１１が示す位置からランドマークノードＬ１が示すランドマークまでの距離と、により、パーティクルノードＰ１１におけるランドマークノードＬ１が示すランドマークの位置が得られる。
【００２２】
（Ｃ）は、時刻ｔ＝１でのカップリングツリーＴの枝刈り後の状態を示す。枝刈りとは、不要となったパーティクルノードを削除する処理である。パーティクルノードの削除にしたがって、削除されたパーティクルノード内のランドマークノードも枝刈りにより削除される。（Ｃ）では、（Ｂ）の状態において、子ノードを持たない親ノードが削除される。たとえば、パーティクルノードＰ０３，Ｐ０４，Ｐ０６は、子ノードを持たないため削除される。また、カップリングツリーＴの冗長性を排除するため、子ノードが１つだけの親ノードが存在する場合、親子ノードの統合処理が実行される。
【００２３】
親子ノードの統合処理は、親子ノードのうち親であるパーティクルノードに親ノードが存在する場合に実行される。親子ノードのうち親であるパーティクルノードに親ノードが存在しない場合、単に親ノードが削除される。（Ｃ）では、パーティクルノードＰ０１，Ｐ０２，Ｐ０７，Ｐ０８は、子ノードが１つだけの親ノードであり、かつ、パーティクルノードＰ０１，Ｐ０２，Ｐ０７，Ｐ０８には、親ノードが存在しない。このため、親ノードであるパーティクルノードＰ０１，Ｐ０２，Ｐ０７，Ｐ０８は削除される。
【００２４】
このように、カップリングツリーＴでは、パーティクルノードが増加するが、不要なパーティクルノードを枝刈りによりカップリングツリーＴから削除することにより、カップリングツリーＴのサイズ拡大を抑制し、省メモリ化を図ることができる。
【００２５】
＜ハードウェア構成＞
図２は、更新装置のハードウェア構成例を示すブロック図である。図２において、更新装置２００は、プロセッサ２０１、内部メモリ２０２、外部メモリ２０３、通信装置２０４、入力装置２０５、出力装置２０６、内部センサ２０７、外部センサ２０８、移動機構２０９、およびバス２１０を有する。プロセッサ２０１、内部メモリ２０２、外部メモリ２０３、通信装置２０４、入力装置２０５、出力装置２０６、内部センサ２０７、外部センサ２０８、および移動機構２０９は、バス２１０に接続される。
【００２６】
プロセッサ２０１は、更新装置２００の全体の制御を司る。また、プロセッサ２０１は、内部メモリ２０２に記憶されている各種プログラム（ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）や本実施の形態の更新プログラム）を実行することで、内部メモリ２０２内のデータを読み出したり、実行結果となるデータを内部メモリ２０２に書き込んだりする。
【００２７】
内部メモリ２０２は、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、フラッシュメモリなどで構成され、プロセッサ２０１のワークエリアとなる。内部メモリ２０２には、たとえば、更新装置２００の移動中に更新されるカップリングツリーＴが格納される。外部メモリ２０３は、フラッシュメモリや磁気ディスクドライブにより構成され、各種プログラム（ＯＳや本実施の形態の更新プログラム）や各種データ（各プログラムの実行により得られたデータを含む）を記憶したりする。
【００２８】
通信装置２０４は、ネットワークを介して外部からデータを受信したり、外部にデータを送信したりするインターフェースである。入力装置２０５は、キーボード、マウス、タッチパネルなどユーザの操作により、各種データの入力をおこなうインターフェースである。出力装置２０６は、プロセッサ２０１の指示により、データを出力するインターフェースである。出力装置２０６には、ディスプレイやプリンタが挙げられる。
【００２９】
内部センサ２０７は、車輪の移動量など更新装置２００内部の状態を検出するデバイスである。内部センサ２０７としては、たとえば、エンコーダやジャイロセンサが採用される。外部センサ２０８は、更新装置２００外部のランドマークを検出するデバイスである。外部センサ２０８としては、たとえば、ステレオカメラが採用される。本実施の形態の場合、ランドマークまでの距離を計測するため、ステレオカメラは２台搭載される。そして、３角測量により、ランドマークまでの距離が計測される。また、移動機構２０９は、更新装置２００を移動させるデバイスである。たとえば、車輪や移動を制御する回路などにより構成される。
【００３０】
＜地図情報ＤＢ＞
図３は、地図情報ＤＢの記憶内容の一例を示す説明図である。地図情報ＤＢ３００は、図２に示した外部メモリ２０３に格納される。地図情報ＤＢ３００は、ランドマークＩＤ項目と、位置項目と、を有する。ランドマークＩＤ項目には、ランドマークＩＤが格納される。ランドマークＩＤとは、ランドマークを一意に特定する識別情報である。位置項目には、ランドマークの空間内での位置が格納される。地図情報ＤＢ３００での位置は、初期状態の位置であり、上述したようにロボットの移動により更新される。
【００３１】
＜カップリングツリーＴの更新例＞
つぎに、図１に示したカップリングツリーＴの（Ｃ）以後の更新について説明する。
【００３２】
図４は、時刻ｔ＝２におけるカップリングツリーＴの更新状態を示す説明図である。図４の（Ａ）は、図１の（Ｃ）の次状態である。図４の（Ａ）では、更新装置２００は、第１階層Ｒ１の各パーティクルノードについて尤度を算出する。ここでは、尤度にしたがって、更新装置２００は、パーティクルノードＰ１４を親ノードとして、子ノードであるパーティクルノードＰ２１〜Ｐ２４を生成する。また、パーティクルノードＰ１５を親ノードとして、更新装置２００は、子ノードであるパーティクルノードＰ２５〜Ｐ２８を生成する。また、各パーティクルノードＰ２１〜Ｐ２８において、更新装置２００は、３個のランドマークノードを検出する。図４においても、パーティクルノードの親子関係は太矢印で示しており、ランドマークノードの親子関係も細矢印で示している。
【００３３】
（Ｂ）は、時刻ｔ＝２でのカップリングツリーＴの枝刈り後の状態を示す。（Ｂ）では、（Ａ）の状態において、更新装置２００は、子ノードを持たない親ノードを削除する。たとえば、パーティクルノードＰ１１〜Ｐ１３，Ｐ１６〜Ｐ１８は、子ノードを持たないため削除される。また、子ノードが１つだけの親ノードは、存在しない。このように、カップリングツリーＴでは、パーティクルノードが増加するが、不要なパーティクルノードを枝刈りによりカップリングツリーＴから削除することにより、カップリングツリーＴのサイズ拡大を抑制し、省メモリ化を図ることができる。
【００３４】
図５は、時刻ｔ＝３におけるカップリングツリーＴの更新状態を示す説明図である。図５の（Ａ）は、図４の（Ｂ）の次状態である。図５の（Ａ）では、尤度にしたがって、更新装置２００は、第２階層Ｒ２の各パーティクルノードについて尤度を算出する。ここでは、パーティクルノードＰ２２を親ノードとして、更新装置２００は、子ノードであるパーティクルノードＰ３１，Ｐ３２を生成する。また、パーティクルノードＰ２４を親ノードとして、更新装置２００は、子ノードであるパーティクルノードＰ３３〜Ｐ３５を生成する。また、パーティクルノードＰ２５を親ノードとして、更新装置２００は、子ノードであるパーティクルノードＰ３６〜Ｐ３８を生成する。また、各パーティクルノードＰ３１〜Ｐ３８において、更新装置２００は、２個のランドマークノードを検出する。図５においても、パーティクルノードの親子関係は太矢印で示しており、ランドマークノードの親子関係も細矢印で示している。
【００３５】
（Ｂ）は、時刻ｔ＝３でのカップリングツリーＴにおける親ノードの削除後の状態を示す。（Ｂ）では、（Ａ）の状態において、更新装置２００は、子ノードを持たない親ノードを削除する。たとえば、パーティクルノードＰ２１，Ｐ２３，Ｐ２６〜Ｐ２８は、子ノードを持たないため削除される。このように、カップリングツリーＴでは、パーティクルノードが増加するが、不要なパーティクルノードを枝刈りによりカップリングツリーＴから削除することにより、カップリングツリーＴのサイズ拡大を抑制し、省メモリ化を図ることができる。
【００３６】
図６は、時刻ｔ＝３におけるカップリングツリーＴの統合処理を示す説明図である。図６において、パーティクルノードＰ１５は、子ノードが１つ（パーティクルノードＰ２５）だけの親ノードであり、かつ、親ノード（パーティクルノードＰ０５）が存在する。したがって、親子関係にあるパーティクルノードＰ１５，Ｐ２５に対し統合処理が実行される。ここで、パーティクルノードＰ２５内のランドマークノードをａ〜ｃとし、パーティクルノードＰ１５内のランドマークノードをｄ〜ｇとする。
【００３７】
統合処理では、子ノードが親ノードに統合される。具体的には、ランドマークノードａ，ｄは、同一ランドマークに関するノードである。したがって、統合の際には、更新装置２００は、ランドマークノードａ，ｄのうち最新であるランドマークノードａでランドマークノードｄを更新する。そして、更新装置２００は、更新されたランドマークノードｄと、ランドマークノードａの子ノードであるパーティクルノードＰ３６内のランドマークノードｈとを関連付ける。
【００３８】
ランドマークノードｃ，ｆについても同様に、統合の際には、更新装置２００は、ランドマークノードｃ，ｆのうち最新であるランドマークノードｃでランドマークノードｆを更新する。そして、更新装置２００は、更新されたランドマークノードｆと、ランドマークノードｃの子ノードであるパーティクルノードＰ３７内のランドマークノードｉとを関連付ける。また、ランドマークノードｂには、親となるランドマークノードが存在しないため、更新装置２００は、ランドマークノードｂをパーティクルノードＰ１５に移行させる。そして、更新装置２００は、移行させたランドマークノードｂと、ランドマークノードｂの子ノードであるパーティクルノードＰ３８内のランドマークノードｊとを関連付ける。ランドマークノードａ〜ｃの更新（移行含む）が完了すると、更新装置２００は、パーティクルノードＰ２５を削除する。
【００３９】
図７は、時刻ｔ＝３におけるカップリングツリーＴの統合処理後の状態を示す説明図である。図７の状態でのカップリングツリーＴには、子ノードがないパーティクルノード（末端のパーティクルノードを除く）や、子ノードが１つだけのパーティクルノードが存在しない。
【００４０】
図８は、時刻ｔ＝４におけるカップリングツリーＴでの新規パーティクルノードの生成状態を示す説明図である。図８は、図７の次状態である。第３階層Ｒ３の各パーティクルノードについて尤度が算出された結果、パーティクルノードＰ３１によりパーティクルノードＰ４１，Ｐ４２が生成されたものとする。また、パーティクルノードＰ３２によりパーティクルノードＰ４３，Ｐ４４が生成されたものとする。また、パーティクルノードＰ３３によりパーティクルノードＰ４５，Ｐ４６が生成されたものとする。また、パーティクルノードＰ３４によりパーティクルノードＰ４７，Ｐ４８が生成されたものとする。また、時刻ｔ＝４では２個のランドマークが観測されたことにより、第４階層Ｒ４の各パーティクルノードには、観測された２個のランドマークに対応する２個のランドマークノードが生成される。
【００４１】
図９は、時刻ｔ＝４におけるカップリングツリーＴでのパーティクルノードの削除状態を示す説明図である。図９は、図８の次状態である。図８の状態のカップリングツリーＴには、子ノードを持たないパーティクルノードＰ３５〜Ｐ３８が存在する。したがって、更新装置２００は、パーティクルノードＰ３５〜Ｐ３８を削除する。当該削除に伴い、更新装置２００は、パーティクルノードＰ３５〜Ｐ３８内のランドマークノードも削除する。また、パーティクルノードＰ３５〜Ｐ３８の削除により、その親ノードであるパーティクルノードＰ１５も、子ノードを持たないパーティクルノードになる。したがって、更新装置２００は、パーティクルノードＰ１５を削除する。当該削除に伴い、更新装置２００は、パーティクルノードＰ１５内のランドマークノードも削除する。
【００４２】
図１０は、時刻ｔ＝４におけるカップリングツリーＴの更新状態（その１）を示す説明図である。図１０の状態でのカップリングツリーＴには、子ノードがないパーティクルノードは存在しない。子ノードが１つだけで、かつ、親ノードが存在するパーティクルノードも存在しない。一方、子ノードが１つだけで、かつ、親ノードが存在しないパーティクルノードは存在する。ルートであるパーティクルノードＰ０５が該当する。この場合、親子関係にあるパーティクルノードＰ０５，Ｐ１４は、統合処理の対象となる。
【００４３】
図１１は、時刻ｔ＝４におけるカップリングツリーＴの更新状態（その２）を示す説明図である。図１１は、図１０の次状態である。内部メモリ２０２に格納されているカップリングツリーＴは、パーティクルノードの生成によりサイズが大きくなる。このため、更新装置２００は、ルートとなるパーティクルノードにおいて、子ノードを持たないランドマークノードを外部メモリ２０３に移行させる。子ノードを持たないランドマークノードは、子ノードにより更新されていないノードであるため、当該ランドマークが持つ情報は古い情報となる。したがって、そのようなランドマークノードについては、外部メモリ２０３に移行させることにより、カップリングツリーＴのサイズを縮小し、内部メモリ２０２の空き容量の増大を図る。
【００４４】
具体的には、ルートである第０階層Ｒ０のパーティクルノードＰ０５において、子ノードを持たないランドマークノードが外部メモリ２０３への吐出し候補となる。パーティクルノードＰ０５には、子ノードを持たないランドマークノードｋ，ｌが存在する。ランドマークノードｋ，ｌは吐出し候補となる。
【００４５】
このうち、最新時刻での更新装置２００を搭載するロボットの位置および向きから見た計測範囲外のランドマークは、時刻ｔ＝４のパーティクルノード内のランドマークに更新される可能性がないため、吐出し対象に決定される。図１１では、最新時刻はｔ＝４である。時刻ｔ＝４では、更新装置２００を搭載するロボットの位置および向きは、パーティクルノードＰ４１〜Ｐ４８により推定される。最新時刻ｔ＝４でのすべてのパーティクルノードＰ４１〜Ｐ４８により推定される更新装置２００を搭載するロボットの位置および向きから見た計測範囲にあるか否かにより、吐出し対象が決定される。
【００４６】
また、最新時刻ｔ＝４でのすべてのパーティクルノードＰ４１〜Ｐ４８ではなく、一部のパーティクルノードにより推定される更新装置２００を搭載するロボットの位置から見た計測範囲にあるか否かにより、吐出し対象が決定されることとしてもよい。更新装置２００は、一部のパーティクルノードをランダムに決定してもよく、しきい値以上の尤度のパーティクルノードや尤度が相対的に高いパーティクルノードを、一部のパーティクルノードとして決定してもよい。
【００４７】
図１１では、吐出し対象として、ランドマークｌが決定されたものとする。吐出し対象に決定されたランドマークｌは外部メモリ２０３に書き込まれ、パーティクルノードＰ０５から削除される。
【００４８】
図１２は、時刻ｔ＝４におけるカップリングツリーＴの統合処理を示す説明図である。図１２は、図１１の次状態である。図１２において、パーティクルノードＰ０５は、子ノードが１つ（パーティクルノードＰ１４）だけの親ノードであり、かつ、親ノードは存在しないがルートノードである。したがって、親子関係にあるパーティクルノードＰ０５，Ｐ１４に対し統合処理が実行される。統合処理は、図６に示した統合処理と同様である。ここで、パーティクルノードＰ１４内のランドマークノードをｍ〜ｐとし、パーティクルノードＰ０５内のランドマークノードをｋ，ｑ〜ｓとする。
【００４９】
統合処理では、子ノードが親ノードに統合される。具体的には、ランドマークノードｍ，ｑは、同一ランドマークに関するノードである。したがって、統合の際には、更新装置２００は、ランドマークノードｍ，ｑのうち最新であるランドマークノードｍでランドマークノードｑを更新する。そして、更新装置２００は、更新されたランドマークノードｑと、ランドマークノードｍの子ノードであるパーティクルノードＰ２２内のランドマークノードｔとを関連付ける。また、更新装置２００は、更新されたランドマークノードｑと、パーティクルノードＰ２４内のランドマークノードｖとを関連付ける。
【００５０】
ランドマークノードｎ，ｒについても同様に、統合の際には、更新装置２００は、ランドマークノードｎ，ｒのうち最新であるランドマークノードｎでランドマークノードｒを更新する。そして、更新装置２００は、更新されたランドマークノードｒと、ランドマークノードｎの子ノードであるパーティクルノードＰ２４内のランドマークノードｗとを関連付ける。
【００５１】
ランドマークノードｐ，ｓについても同様に、統合の際には、更新装置２００は、ランドマークノードｐ，ｓのうち最新であるランドマークノードｐでランドマークノードｓを更新する。そして、更新装置２００は、更新されたランドマークノードｓと、ランドマークノードｐの子ノードであるパーティクルノードＰ３２内のランドマークノードｘとを関連付ける。
【００５２】
また、ランドマークノードｏには、親となるランドマークノードが存在しないため、更新装置２００は、ランドマークノードｏをパーティクルノードＰ０５に移行させる。そして、更新装置２００は、移行させたランドマークノードｏと、ランドマークノードｏの子ノードであるパーティクルノードＰ２２内のランドマークノードｕとを関連付ける。ランドマークノードの更新（移行含む）が完了すると、更新装置２００は、パーティクルノードＰ１４を削除する。
【００５３】
図１３は、時刻ｔ＝４におけるカップリングツリーＴの統合処理後の状態を示す説明図である。図１３の状態でのカップリングツリーＴには、子ノードがないパーティクルノード（末端のパーティクルノードを除く）や、子ノードが１つだけのパーティクルノードが存在しない。
【００５４】
図１４は、時刻ｔ＝ＺにおけるカップリングツリーＴの更新状態を示す説明図である。時刻ｔ＝ＺはＺ＞４とする。時刻ｔ＝Ｚでは、更新装置２００は、ルートであるパーティクルノードＰ０５が示す位置に戻ってきたものとする。時刻ｔ＝Ｚまでに、外部メモリ２０３にはランドマークノードｌのほか、他のランドマークノードも書き込まれているものとする。この場合、時刻ｔ＝ＺにおけるパーティクルノードＰＺ１〜ＰＺ８のうち少なくともいずれかのパーティクルノードが示す位置および向きが、パーティクルノードＰ０５が示す位置および向きに一致したことになる。ここでの一致については、所定量の誤差が許容されるものとする。
【００５５】
このように、位置および向きが一致した場合、これまでにルートであるパーティクルノードＰ０５に存在したことがあるランドマークノードが示すランドマークが、パーティクルノードＰＺ１〜ＰＺ８内のランドマークノードが示すランドマークと一致する可能性がある。したがって、更新装置２００は、これまでにパーティクルノードＰ０５から吐き出されて外部メモリ２０３に書き込まれたランドマークノード群のうち、一致した位置および向きから見た観測範囲内の位置を示すランドマークノードをパーティクルノードＰ０５に書き込む。図１５の例では、外部メモリ２０３のランドマークノードα，β，γが、パーティクルノードＰ０５に書き戻される。
【００５６】
図１５は、時刻ｔ＝Ｚ＋１におけるカップリングツリーＴの状態を示す説明図である。時刻ｔ＝Ｚ＋１は時刻ｔ＝Ｚの次時刻であり、図１５は、図１４の次状態である。時刻ｔ＝Ｚ＋１では、第（Ｚ＋１）階層Ｒ（Ｚ＋１）のパーティクルノード群が生成される。ここでは、パーティクルノードＰ０５に書き戻されたランドマークノードαとランドマークノードδとが同一ランドマークを示すノードであるため、更新装置２００は、両ランドマークノードα，δを関連付ける。また、パーティクルノードＰ０５に書き戻されたランドマークノードβとランドマークノードεとが同一ランドマークを示すノードであるため、更新装置２００は、両ランドマークノードβ，εを関連付ける。また、パーティクルノードＰ０５に書き戻されたランドマークノードγとランドマークノードζとが同一ランドマークを示すノードであるため、更新装置２００は、両ランドマークノードγ，ζを関連付ける。
【００５７】
＜更新装置２００の機能的構成例＞
図１６は、更新装置２００の機能的構成例を示すブロック図である。図１６において、更新装置２００は、第１の記憶部１６０１、第２の記憶部１６０２、構築部１６０３、検出部１６０４、更新部１６０５、選択部１６０６、特定部１６０７、抽出部１６０８、判断部１６０９、および格納部１６１０を有する。第１の記憶部１６０１は、内部メモリ２０２に対応し、第２の記憶部１６０２は、外部メモリ２０３に対応する。また、構築部１６０３、検出部１６０４、更新部１６０５、選択部１６０６、特定部１６０７、抽出部１６０８、判断部１６０９、および格納部１６１０は、具体的には、たとえば、図２に示した内部メモリ２０２、または外部メモリ２０３などの記憶装置に記憶されたプログラムをプロセッサ２０１に実行させることにより、その機能を実現する。
【００５８】
第１の記憶部１６０１は、カップリングツリーＴを記憶する。また、第２の記憶部１６０２は、地図情報ＤＢ３００や、カップリングツリーＴから吐き出されたランドマークノードを格納する。
【００５９】
構築部１６０３は、第１の記憶部１６０１内でカップリングツリーＴを構築する。カップリングツリーＴは、上述したように、各々自装置の位置および向きを示すパーティクルノード群が時系列に階層化されたツリー構造である。また、カップリングツリーＴは、パーティクルノード群の各パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードが生成元のパーティクルノードに関連付けて生成され時系列に階層化されたツリー構造である。また、カップリングツリーＴは、階層間で同一ランドマークを示すランドマークノードが関連付けられたツリー構造である。
【００６０】
構築部１６０３は、時刻ごとにあらかじめ決められた個数のパーティクルノードを生成する。図１〜図１５の例では、構築部１６０３は、８個のパーティクルノードを生成する。構築部１６０３は、生成された各パーティクルノードに対し、尤度を算出する。尤度とは、そのパーティクルノードが示す自装置の位置および向きの確からしさを示す指標値である。ここで、尤度の算出例について具体的に説明する。まず、時刻ｔ＝０のときは、下記式（１）となる。
【００６１】
ωi＝１／Ｎ・・・（１）
【００６２】
Ｎは、パーティクルノードの生成個数である。ωiは、第０階層Ｒ０のｉ番目のパーティクルノードＰ０ｉの尤度である。ｉは、１≦ｉ≦Ｎの自然数である。すなわち、時刻ｔ＝０では、どのパーティクルノードの尤度も同じ値となる。
【００６３】
ここで、ｓiをｉ番目のパーティクルノードの状態とし、ｓiを下記式（２）であらわす。すなわち、ｉ番目のパーティクルノードは状態ｓiを持つ。
【００６４】
【数１】
2014016831.tif 000003
【００６５】
状態ｓiにおいて、ｘiはｉ番目のパーティクルノードが有するロボットの位置および向きを示す情報である。ｌi,jは、ｉ番目のパーティクルノードが持つ地図に含まれているｊ番目のランドマークの位置を示す情報である。ｉ番目のパーティクルノードが持つ地図とは、ｘiで示されるロボットの位置を中心とする地図情報であり、ｘiでのロボットが外部センサ２０８により外部を観測する観測範囲を含む。Ｋiは、ｉ番目のパーティクルノードが持つランドマークノードの総数である。Σi,jは、ｉ番目のパーティクルノードが持つ地図に含まれるｊ番目のランドマークの位置ｌi,jに関する共分散行列である。共分散行列は、ｊ番目のランドマークの位置ｌi,jの不確実さをあらわす。時刻ｔ＞０のときは、尤度ωiは、下記式（３）であらわされる。
【００６６】
【数２】
2014016831.tif 000004
【００６７】
上記式（３）において、Ｄは、時刻ｔにおいて外部センサ２０８で観測したランドマークの個数である。ｋは、観測されたランドマークの種類を区別する番号である。異なるランドマークでも、同種のランドマークであれば、同一の値が割当てられる。ｚkは、観測したｋ番目のランドマークの位置である。ｊ（ｋ）は、ｋ番目に観測されたランドマークの地図内での番号である。これにより、同種のランドマークが複数存在しても、地図上の位置が指定されるため、区別することができる。Σi,j(k)は、ｉ番目のパーティクルの持つ第ｊ（ｋ）番目のランドマークの位置ｌi,j(k)に関しての共分散行列である。
【００６８】
そして、構築部１６０３は、次時刻のパーティクルノードを、現時刻のパーティクルノードの尤度ωiに従って生成する。具体的には、たとえば、構築部１６０３は、尤度の大きさに従って、次時刻のパーティクルノードの生成元となる現時刻のパーティクルノードを決定する。尤度が大きいほど、より多くのパーティクルノードの親ノードとなる。
【００６９】
たとえば、図４の（Ａ）を例に挙げると、パーティクルノードＰ１１〜Ｐ１８の尤度が、
ω1＝０．０２５
ω2＝０．０２５
ω3＝０．０２５
ω4＝０．４
ω5＝０．４
ω6＝０．０５
ω7＝０．０２５
ω8＝０．０５
であったとする。
【００７０】
そして、たとえば、小数点第２位以下を切り捨てて正規化すると、
ω1＝０
ω2＝０
ω3＝０
ω4＝４
ω5＝４
ω6＝０
ω7＝０
ω8＝０
となり、パーティクルノードＰ１４は、４個のパーティクルノードＰ２１〜Ｐ２４の生成元となり、パーティクルノードＰ１５は、４個のパーティクルノードＰ２５〜Ｐ２８の生成元となる。
【００７１】
また、尤度が大きいほど、次時刻のパーティクルノードの生成元となる確率が高くなるように設定し、その確率に応じてランダムに決定してもよい。たとえば、上述した正規化前の尤度ω1〜ω8を出現確率として用い、パーティクルノードの総数が８個になるまで、次時刻のパーティクルノードの生成元を求めるようにしてもよい。
【００７２】
また、構築部１６０３は、新規生成されたパーティクルノードが示す位置および向きから観測されたランドマークの位置を示すランドマークノードと、既観測のランドマークの位置を示すランドマークノードとを関連付ける。具体的には、たとえば、ランドマークに固有の識別情報がある場合には、構築部１６０３は、識別情報が一致することにより、両ランドマークノードを関連付ける。また、識別情報がない場合、構築部１６０３は、下記の探索方法により類似ランドマークノードを探索し、類似するランドマークノード同士の関連付けをおこなう。
【００７３】
図１７は、類似ランドマークノードの探索例を示す説明図である。図１７のカップリングツリーＴにおいて、パーティクルノードＨが新規生成されたパーティクルノードであり、パーティクルノードＦがパーティクルノードＨの生成元となる親ノードであり、パーティクルノードＧがパーティクルノードＦの生成元となる親ノードであり、パーティクルノードＲがパーティクルノードＧの生成元となる親ノードである。
【００７４】
また、ランドマークノードｍは、パーティクルノードＨにおいて観測されたランドマークの位置を示すノードであり、構築部１６０３は、ランドマークノードｍの類似ランドマークノードを探索する。なお、パーティクルノードＦにおいて観測されたランドマークノードａ〜ｃのうち、ランドマークノードａの親ノードは、ランドマークノードｄであり、ランドマークノードｃの親ノードはランドマークノードｆである。また、パーティクルノードＧにおいて観測されたランドマークノードｄ〜ｆのうち、ランドマークノードｄの親ノードは、ランドマークノードｇである。
【００７５】
まず、構築部１６０３は、探索対象であるランドマークノードｍが所属するパーティクルノードＨの先祖ノードを探索する。本例の場合、先祖ノードとしてパーティクルノードＦ，Ｇ，Ｒが探索される。つぎに、構築部１６０３は、探索された先祖ノードの各々について、子ノードへの関連付けがされていないランドマークノードを抽出する。
【００７６】
たとえば、パーティクルノードＦに所属するランドマークノードａ〜ｃには子ノードが存在しない。この時点でランドマークノードａ〜ｃは最新のランドマークを示しているため、構築部１６０３は、ランドマークノードａ〜ｃを集合Ωに入れる。
【００７７】
また、パーティクルノードＧに所属するランドマークノードｄ，ｆは、それぞれランドマークノードａ，ｃに関連付けられている。したがって、構築部１６０３は、ランドマークノードｄ，ｆを集合Ωに入れない。一方、ランドマークノードｅは、ランドマークノードｅが所属するパーティクルノードＧの子ノードであるパーティクルノードＦの所属ランドマークノードとは関連付けられていない。したがって、構築部１６０３は、ランドマークノードｅを集合Ωに入れる。
【００７８】
また、パーティクルノードＲに所属するランドマークノードｇ，ｈは、それぞれランドマークノードｄ，ｅに関連付けられている。したがって、構築部１６０３は、ランドマークノードｇ，ｈを集合Ωに入れない。
【００７９】
このあと、構築部１６０３は、集合Ω内のランドマークノードａ〜ｃ，ｅが示すランドマークと、探索対象であるランドマークノードｍが示すランドマークとの距離を算出する。ランドマークノードａ〜ｃ，ｅ，ｍは各々ランドマークの位置を保持しているため、ランドマーク間の距離は、２点間の距離Ｄを求める下記式（４）により算出可能である。
【００８０】
【数３】
2014016831.tif 000005
【００８１】
（ｘ１，ｘ２，ｘ３）は一方の点の位置を示すベクトルであり、（ｙ１，ｙ２，ｙ３）は他方の点の位置を示すベクトルである。本例の場合、構築部１６０３は、ランドマークノードａ〜ｃ，ｅの各々が示すランドマークと、ランドマークノードｍが示すランドマークとの距離を算出する。そして、構築部１６０３は、ランドマークノードｍが示すランドマークと最短距離となるランドマークを示すランドマークノードと、ランドマークノードｍとを関連付ける。
【００８２】
検出部１６０４は、ツリー構造を参照して、最下層のパーティクルノードを除く残余のパーティクルノード群の中から、下位階層に関連付けられていないパーティクルノードを検出する。最下層のパーティクルノードとは、新規生成されたパーティクルノードであり、下位階層に関連付けられていないパーティクルノードとは、子ノードがないパーティクルノードである。検出部１６０４は、具体的には、たとえば、検出部１６０４は、カップリングツリーＴを参照して、新規生成されたパーティクルノード以外の残余のパーティクルノードの中から、子ノードがないパーティクルノードを検出する。検出されたパーティクルノードは削除対象となる。
【００８３】
たとえば、図１の（Ｂ）では、検出部１６０４は、パーティクルノードＰ０３，Ｐ０４，Ｐ０６を検出し、図４の（Ａ）では、パーティクルノードＰ１１，Ｐ１２，Ｐ１７，Ｐ１８を検出する。また、図９では、検出部１６０４は、パーティクルノードＰ３５〜Ｐ３８を検出する。また、パーティクルノードＰ３５〜Ｐ３８が削除された後、検出部１６０４は、パーティクルノードＰ１５を検出する。
【００８４】
また、検出部１６０４は、ツリー構造を参照して、パーティクルノード群の中から、下位階層に関連付けられたパーティクルノードが１つであり、かつ、上位階層に関連付けられていないパーティクルノードを検出する。下位階層に関連付けられたパーティクルノードとは、子ノードである。上位階層に関連付けられていないパーティクルノードとは、親ノードが存在しないパーティクルノードである。すなわち、検出部１６０４は、子ノードが１つだけで、かつ、親ノードが存在しないパーティクルノードを検出する。検出されたパーティクルノードは削除対象となる。たとえば、図１の（Ｂ）では、検出部１６０４は、パーティクルノードＰ０１，Ｐ０２，Ｐ０７，Ｐ０８を検出する。
【００８５】
また、検出部１６０４は、ツリー構造を参照して、パーティクルノード群の中から、上位階層に関連付けられているパーティクルノードが当該パーティクルノード以外の他の下位階層のパーティクルノードに関連付けられていないパーティクルノードを検出する。具体的には、たとえば、検出部１６０４は、親ノードが自ノードのみを子ノードとするパーティクルノードを検出する。図６の例では、検出部１６０４は、パーティクルノードＰ２５を検出する。パーティクルノードＰ１５は、パーティクルノードＰ２５の親ノードであり、パーティクルノードＰ２５のみを子ノードとする。検出されたパーティクルノードは、親ノードへの統合対象となる。すなわち、パーティクルノードＰ２５は、親ノードであるパーティクルノードＰ１５に統合される。
【００８６】
更新部１６０５は、ツリー構造を更新する。具体的には、たとえば、パーティクルノードの削除とパーティクルノードの統合を実行することにより、カップリングツリーＴを更新する。また、更新部１６０５は、検出部１６０４により、新規生成されたパーティクルノード以外の残余のパーティクルノードの中から、子ノードがないパーティクルノードが検出された場合、検出されたパーティクルノードの削除処理を実行する。同様に、更新部１６０５は、子ノードが１つだけで、かつ、親ノードが存在しないパーティクルノードが検出された場合、検出されたパーティクルノードの削除処理を実行する。
【００８７】
更新部１６０５は、削除処理として、検出されたパーティクルノードおよび当該パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを、カップリングツリーＴから削除する。たとえば、図１の（Ｂ），（Ｃ）では、パーティクルノードＰ０１〜Ｐ０４，Ｐ０６〜Ｐ０８が所属ランドマークノードとともに削除される。
【００８８】
また、更新部１６０５は、検出部１６０４により、親ノードが自ノードのみを子ノードとするパーティクルノードが検出された場合、統合処理を実行する。たとえば、図６に示したように、パーティクルノードＰ２５が検出された場合、更新部１６０５は、パーティクルノードＰ２５をパーティクルノードＰ１５に統合する。
【００８９】
選択部１６０６は、統合対象となるパーティクルノードが検出された場合、検出部１６０４によって検出されたパーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを選択する。具体的には、たとえば、図６において、選択部１６０６は、パーティクルノードＰ２５が統合対象として検出されると、パーティクルノードＰ２５に所属するランドマークノードａ〜ｃを選択する。
【００９０】
特定部１６０７は、選択部１６０６によって選択されたランドマークノードについて、上位階層および下位階層に関連付けられているランドマークノードを特定する。具体的には、特定部１６０７は、選択されたランドマークノードの親ノードや子ノードを特定する。たとえば、図６において、特定部１６０７は、ランドマークノードａが選択された場合、ランドマークノードａの親ノードであるランドマークノードｄを特定する。また、特定部１６０７は、ランドマークノードａが選択された場合、ランドマークノードａの子ノードであるランドマークノードｈを特定する。また、特定部１６０７は、ランドマークノードｂが選択された場合、ランドマークノードｂの子ノードであるランドマークノードｊを特定する。また、図示されていないが、特定部１６０７は、選択されたランドマークノードが親ノードのみ有する場合、当該親ノードを特定する。
【００９１】
上述した更新部１６０５は、特定部１６０７によって特定されたランドマークノードに応じて、選択部１６０６による選択ランドマークノードの生成元であるパーティクルノードを、当該パーティクルノードの生成元である上位階層に関連付けられているパーティクルノードに統合する。
【００９２】
具体的には、更新部１６０５は、特定部１６０７により上位階層のランドマークノードのみ特定された場合、上位階層に関連付けられているパーティクルノードを選択ランドマークノードにより更新し、選択ランドマークノードを削除する。具体的には、更新部１６０５は、特定部１６０７により、選択ランドマークノードの親ノードのみ特定された場合には、その親ノードが所属するパーティクルノードにおいて、当該親ノードを選択ランドマークノードで更新する。これにより、親ノードが持つランドマークの位置が、選択ランドマークノードが持つ位置に更新される。そして、更新部１６０５は、選択ランドマークノードを削除する。
【００９３】
また、更新部１６０５は、特定部１６０７により下位階層のランドマークノードのみ特定された場合、選択ランドマークノードを、上位階層に関連付けられているパーティクルノードに関連付ける。具体的には、更新部１６０５は、特定部１６０７により、選択ランドマークノードの子ノードのみ特定された場合には、選択ランドマークノードを、選択ランドマークノードの所属パーティクルノードの親ノードに関連付ける。たとえば、図６では、更新部１６０５は、選択ランドマークノードｂを、選択ランドマークノードｂが所属するパーティクルノードＰ２５の親ノードであるパーティクルノードＰ１５に関連付ける。すなわち、更新部１６０５は、選択ランドマークノードｂの所属先をパーティクルノードＰ２５からパーティクルノードＰ１５に変更する。また、この場合、選択ランドマークノードｂとその子ノードであるランドマークノードｊとの関係は維持したままである。
【００９４】
また、更新部１６０５は、特定部１６０７により上位階層および下位階層のランドマークノードが特定された場合、上位階層のランドマークノードを選択ランドマークノードにより更新し、かつ、更新後の上位階層のランドマークノードを下位階層のランドマークノードに関連付ける。具体的には、更新部１６０５は、特定部１６０７により、選択ランドマークの親ノードおよび子ノードが特定された場合には、親ノードを選択ランドマークノードで更新する。そして、更新部１６０５は、更新後の親ノードを選択ランドマークノードの子ノードに関連付ける。たとえば、図６では、更新部１６０５は、選択ランドマークノードａで親ノードであるランドマークノードｄを更新する。これにより、ランドマークノードｄが示す位置は、選択ランドマークが示す位置となる。そして、更新部１６０５は、更新後のランドマークノードｄと選択ランドマークノードａの子ノードであるランドマークノードｈとを関連付ける。
【００９５】
また、更新部１６０５は、特定部１６０７によりランドマークノードが特定されなかった場合、選択ランドマークノードを削除する。すなわち、選択ランドマークノードに親ノードも子ノードも存在しない場合は、更新部１６０５は、その選択ランドマークノードを削除する。これにより、カップリングツリーＴの省メモリ化を図ることができる。なお、削除せずに、図６の選択ランドマークノードｂのように、親ノードが所属するパーティクルノードＰ１５に関連付けることで移行させてもよい。これにより、構築部１６０３による類似ノードの探索候補として残存させておくことができ、類似ノード探索の高精度化を図ることができる。
【００９６】
抽出部１６０８は、最上位階層のパーティクルノードを生成元とするランドマークノード群のうち、下位階層のランドマークノードに関連付けられていないランドマークノードを抽出する。具体的には、たとえば、抽出部１６０８は、図１１に示したように、最上位階層である第０階層のパーティクルノードＰ０５の所属ランドマークノード群のうち、子ノードが存在しないランドマークノードｋ，ｌを抽出する。
【００９７】
判断部１６０９は、最下位階層のパーティクルノードにより特定される自装置の位置および向きに応じた観測範囲に、抽出部１６０８によって抽出されたランドマークノードが示すランドマークが存在するか否かを判断する。最下位階層のパーティクルノードとは、新規生成されたパーティクルノードである。すなわち、最下位階層のパーティクルノードが示す最新時刻でのロボットの位置および向きからの観測範囲に、抽出ランドマークノードが示すランドマークが存在するか否かを判断する。なお、観測範囲は、外部センサ２０８のスペックによりあらかじめ設定された範囲である。たとえば、観測範囲は、外部センサ２０８から見通せる範囲である。図１１の場合、判断部１６０９は、ランドマークノードｋについては、観測範囲内と判断し、ランドマークノードｌについては観測範囲外と判断する。なお、位置および向きが採用される新規生成のパーティクルノードは、例えば、尤度が最大のパーティクルノードである。
【００９８】
格納部１６１０は、判断部１６０９によって存在しないと判断されたランドマークを示すランドマークノードを第１の記憶部１６０１から第２の記憶部１６０２に格納する。具体的には、たとえば、観測範囲外と判断されたランドマークノードは、最下位階層のパーティクルノードに所属するランドマークノードの近傍には存在しない。すなわち、構築部１６０３により、最下位階層のパーティクルノードに所属するランドマークノードの類似ノードとして探索されることはない。したがって、探索に影響のないランドマークノードを第２の格納部１６１０に退避させることで、探索対象を絞り込むことができ類似ノード探索の効率化を図ることができる。また、第１の記憶部１６０１でのカップリングツリーＴのサイズが縮小されるため、省メモリ化を図ることができる。
【００９９】
また、抽出部１６０８は、第２の記憶部１６０２に記憶されているランドマークノード群のうち、最下位階層のパーティクルノードにより特定される自装置の位置および向きに応じた観測範囲に存在するランドマークを示すランドマークノードを抽出する。この場合、格納部１６１０は、抽出部１６０８によって抽出されたランドマークノードを、第１の記憶部１６０１内のツリー構造における最上位階層のパーティクルノードに関連付けて格納する。すなわち、第２の記憶部１６０２内に退避させられたランドマークノードであっても、最下位階層のパーティクルノードが示す最新時刻でのロボットの位置および向きからの観測範囲に存在する場合がある。この場合には、類似ノード探索の対象とするために、格納部１６１０は、最上位階層のパーティクルノードに書き戻す。これにより、類似ノード探索の高精度化を図ることができる。
【０１００】
＜更新処理手順＞
図１８は、更新装置２００による更新処理手順例を示すフローチャート（その１）である。まず、更新装置２００は、時刻ｔをｔ＝０とし（ステップＳ１８０１：Ｙｅｓ）、更新装置２００が搭載される移動体の位置と移動体が有する外部センサ２０８の向きについて初期設定をおこなう（ステップＳ１８０２）。そして、更新装置２００は、時刻ｔ＝０である第０階層Ｒ０のパーティクルノードを生成する（ステップＳ１８０３）。つぎに、更新装置２００は、外部センサ２０８からの計測結果を取得して（ステップＳ１８０４）、ランドマークノードを生成する（ステップＳ１８０５）。そして、更新装置２００は、各パーティクルノードに、生成されたランドマークノードを関連付けることにより、各パーティクルノード内にランドマークノードを追加する（ステップＳ１８０６）。
【０１０１】
このあと、更新装置２００は、パーティクル評価、すなわち、パーティクルノードごとに尤度を算出する（ステップＳ１８０７）。そして、時刻ｔを次の時刻に進めて（ステップＳ１８０８）、更新装置２００は、処理が終了したか否かを判断する（ステップＳ１８０９）。終了の場合（ステップＳ１８０９：Ｙｅｓ）、更新処理を終了する。一方、終了でない場合（ステップＳ１８０９：Ｎｏ）、ステップＳ１８０１に戻り、更新装置２００は、ｔ＝０か否かを判断する（ステップＳ１８０１）。ｔ＝０でない場合（ステップＳ１８０１：Ｎｏ）、図１９のステップＳ１９０１に移行する。
【０１０２】
図１９は、更新装置２００による更新処理手順例を示すフローチャート（その２）である。図１９において、更新装置２００は、構築部１６０３により、直前に算出されたパーティクルノードの尤度に基づいて生成元のパーティクルノードを決め、生成元のパーティクルノードの子ノードとなる新規パーティクルノードを生成する（ステップＳ１９０１）。このあと、更新装置２００は、外部センサ２０８からの計測結果を取得して（ステップＳ１９０２）、ランドマークノードを生成する（ステップＳ１９０３）。そして、更新装置２００は、各パーティクルノードに、生成されたランドマークノードを関連付けることにより、各パーティクルノード内にランドマークノードを追加する（ステップＳ１９０４）。
【０１０３】
このあと、更新装置２００は、パーティクル評価、すなわち、ステップＳ１９０１で生成されたパーティクルノードごとに尤度を算出する（ステップＳ１９０５）。このあと、更新装置２００は、枝刈り処理を実行する（ステップＳ１９０６）。枝刈り処理（ステップＳ１９０６）の詳細については後述するが、枝刈り処理（ステップＳ１９０６）では、パーティクルノードの削除や統合が実行される。
【０１０４】
枝刈り処理（ステップＳ１９０６）のあと、更新装置２００は、抽出部１６０８により、第０階層であるルートパーティクルノードに所属する、子ノードがないランドマークノードを抽出する（ステップＳ１９０７）。そして、更新装置２００は、判断部１６０９により、抽出ランドマークノードについて、新規生成されたパーティクルノードが示すロボットの位置および向きにおいて、観測範囲内か否かを判断する（ステップＳ１９０８）。そして、更新装置２００は、格納部１６１０により、観測範囲外のランドマークノードを外部メモリ２０３に移行する（ステップＳ１９０９）。また、更新装置２００は、外部メモリ２０３のランドマークノード群のうち観測範囲内のランドマークノードをルートパーティクルノードに移行する（ステップＳ１９１０）。このあと、更新装置２００は、構築部１６０３により、類似ノード探索を実行して、カップリングツリーＴを更新する（ステップＳ１９１１）。そして、ステップＳ１８０８に移行する。
【０１０５】
図２０は、図１９に示した枝刈り処理（ステップＳ１９０６）の詳細な処理手順例を示すフローチャートである。更新装置２００は、まず、カップリングツリーＴの最下位階層以外の階層のパーティクルノード群をスキャンし（ステップＳ２００１）、子ノードがないパーティクルノードがあるか否かを判断する（ステップＳ２００２）。子ノードがないパーティクルノードがある場合（ステップＳ２００２：Ｙｅｓ）、更新装置２００は、子ノードがないパーティクルノードを削除して（ステップＳ２００３）、ステップＳ２００２に戻る。子ノードがないパーティクルノードがない場合（ステップＳ２００２：Ｎｏ）、更新装置２００は、カップリングツリーＴのパーティクルノード群をスキャンし（ステップＳ２００４）、子ノードが１つのみのパーティクルノードがあるか否かを判断する（ステップＳ２００５）。
【０１０６】
子ノードが１つのみのパーティクルノードがある場合（ステップＳ２００５：Ｙｅｓ）、更新装置２００は、子ノードが１つのみのパーティクルノードを１つ選択する（ステップＳ２００６）。そして、更新装置２００は、選択パーティクルノードに親ノードがあるか否かを判断する（ステップＳ２００７）。親ノードがある場合（ステップＳ２００７：Ｙｅｓ）、更新装置２００は、統合処理を実行して（ステップＳ２００８）、ステップＳ２００５に戻る。一方、親ノードがない場合（ステップＳ２００７：Ｎｏ）、図１の（Ｃ）に示したように、更新装置２００は、選択パーティクルノードを削除して（ステップＳ２００９）、ステップＳ２００５に戻る。ステップＳ２００５において、子ノードが１つのみのパーティクルノードがない場合（ステップＳ２００５：Ｎｏ）、枝刈り処理（ステップＳ１９０６）を終了し、図１９のステップＳ１９０７に移行する。
【０１０７】
図２１は、図２０に示した統合処理（ステップＳ２００８）の詳細な処理手順例を示すフローチャートである。図２１において、更新装置２００は、選択パーティクルノード内に未選択ランドマークノードがあるか否かを判断する（ステップＳ２１０１）。未選択ランドマークノードがある場合（ステップＳ２１０１：Ｙｅｓ）、更新装置２００は、未選択ランドマークノードを１つ選択し（ステップＳ２１０２）、選択ランドマークノードに親ノードがあるか否かを判断する（ステップＳ２１０３）。親ノードがある場合（ステップＳ２１０３：Ｙｅｓ）、更新装置２００は、選択ランドマークノードで親ノードを更新する（ステップＳ２１０４）。
【０１０８】
一方、選択ランドマークノードに親ノードがない場合（ステップＳ２１０３：Ｎｏ）、更新装置２００は、選択ランドマークノードを選択パーティクルノードの親ノードに移行させる（ステップＳ２１０５）。そして、更新装置２００は、ステップＳ２１０４またはＳ２１０５のあと、選択ランドマークノードに子ノードがあるか否かを判断する（ステップＳ２１０６）。
【０１０９】
子ノードがある場合（ステップＳ２１０６：Ｙｅｓ）、ステップＳ２１０４で選択ランドマークノードに更新された更新後の親ノードと子ノードとを関連付け（ステップＳ２１０７）、ステップＳ２１０１に戻る。ステップＳ２１０５で選択パーティクルノードの親ノードに移行した選択ランドマークノードについても、更新装置２００は、子ノードと関連付けをおこなう（ステップＳ２１０７）。一方、選択ランドマークノードに子ノードがない場合（ステップＳ２１０６：Ｎｏ）、更新装置２００は、選択ランドマークノードを選択パーティクルノードから削除する（ステップＳ２１０８）。そして、ステップＳ２１０１に戻る。未選択ランドマークノードがない場合（ステップＳ２１０１：Ｎｏ）、ステップＳ２００５に移行する。
【０１１０】
そして、一連の処理が終了すると、更新装置２００は、図３の地図情報ＤＢ３００に記憶された各ランドマークの位置を、最終的に生成されたカップリングツリーＴ内のランドマークノードが示す位置に更新する。これにより、地図情報ＤＢ３００が最新の状態となる。
【０１１１】
このように、本実施の形態によれば、不要なパーティクルノードを枝刈りによりカップリングツリーＴから削除することにより、カップリングツリーＴのサイズ拡大を抑制し、省メモリ化を図ることができる。また、カップリングツリーＴにおいて冗長な箇所を統合することにより、必要なランドマークの情報を喪失することなく、カップリングツリーＴのサイズ拡大を抑制し、省メモリ化を図ることができる。このように、メモリ使用量を低減することにより地図情報を効率的に生成することができる。
【０１１２】
また、ルートパーティクルノード内のランドマークノードが示すランドマークが現在のロボットの位置および向きからの観測範囲外となるランドマークノードを、カップリングツリーＴを格納する内部メモリ２０２とは異なる外部メモリ２０３に退避させることにより、内部メモリ２０２のメモリ使用量を低減することができ、カップリングツリーＴの使用領域の拡張を図ることができる。また、観測範囲内のランドマークノードを外部メモリ２０３から内部メモリ２０２に戻すことにより、類似ノード探索の高精度化を図ることができる。なお、上述した実施の形態では、更新装置２００をロボットに搭載した例について説明したが、ロボットに限らず、自動車や自転車などの移動体に搭載してもよい。また、人間に携行させることとしてもよい。
【０１１３】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０１１４】
（付記１）各々自装置の位置および向きを示すパーティクルノード群を生成して時系列に階層化し、前記パーティクルノード群の各パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを生成元のパーティクルノードに関連付けて生成して時系列に階層化し、階層間で同一ランドマークを示すランドマークノードを関連付けることにより、記憶部内でツリー構造を構築する構築部と、
前記ツリー構造を参照して、最下層のパーティクルノードを除く残余のパーティクルノード群の中から、下位階層に関連付けられていないパーティクルノードを検出する検出部と、
前記検出部によって検出されたパーティクルノードおよび当該パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを、前記ツリー構造から削除することにより、前記ツリー構造を更新する更新部と、
を有することを特徴とする更新装置。
【０１１５】
（付記２）各々自装置の位置および向きを示すパーティクルノード群を生成して時系列に階層化し、前記パーティクルノード群の各パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを生成元のパーティクルノードに関連付けて生成して時系列に階層化し、階層間で同一ランドマークを示すランドマークノードを関連付けることにより、記憶部内でツリー構造を構築する構築部と、
前記ツリー構造を参照して、前記パーティクルノード群の中から、下位階層に関連付けられたパーティクルノードが１つであり、かつ、上位階層に関連付けられていないパーティクルノードを検出する検出部と、
前記検出部によって検出されたパーティクルノードおよび当該パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを、前記ツリー構造から削除することにより、前記ツリー構造を更新する更新部と、
を有することを特徴とする更新装置。
【０１１６】
（付記３）各々自装置の位置および向きを示すパーティクルノード群を生成して時系列に階層化し、前記パーティクルノード群の各パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを生成元のパーティクルノードに関連付けて生成して時系列に階層化し、階層間で同一ランドマークを示すランドマークノードを関連付けることにより、記憶部内でツリー構造を構築する構築部と、
前記ツリー構造を参照して、前記パーティクルノード群の中から、上位階層に関連付けられているパーティクルノードが自ノード以外の他の下位階層のパーティクルノードに関連付けられていないパーティクルノードを検出する検出部と、
前記検出部によって検出されたパーティクルノードおよび当該パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを、前記上位階層に関連付けられているパーティクルノードに統合することにより、前記ツリー構造を更新する更新部と、
を有することを特徴とする更新装置。
【０１１７】
（付記４）前記検出部によって検出されたパーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを選択する選択部と、
前記選択部によって選択されたランドマークノードについて、上位階層および下位階層に関連付けられているランドマークノードを特定する特定部と、を有し、
前記更新部は、
前記特定部によって特定された特定結果に基づいて、前記選択されたランドマークノードの生成元である前記検出されたパーティクルノードを、当該検出されたパーティクルノードの生成元である前記上位階層に関連付けられているパーティクルノードに統合することにより、前記ツリー構造を更新することを特徴とする付記３に記載の更新装置。
【０１１８】
（付記５）前記更新部は、
前記特定部により上位階層のランドマークノードのみ特定された場合、前記上位階層に関連付けられているパーティクルノードを前記選択されたランドマークノードにより更新し、前記選択されたランドマークノードを削除することを特徴とする付記４に記載の更新装置。
【０１１９】
（付記６）前記更新部は、
前記特定部により下位階層のランドマークノードのみ特定された場合、前記選択されたランドマークノードを、前記上位階層に関連付けられているパーティクルノードに関連付けることを特徴とする付記４に記載の更新装置。
【０１２０】
（付記７）前記更新部は、
前記特定部により上位階層および下位階層のランドマークノードが特定された場合、上位階層のランドマークノードを前記選択されたランドマークノードにより更新し、かつ、更新後の上位階層のランドマークノードを下位階層のランドマークノードに関連付けることを特徴とする付記４に記載の更新装置。
【０１２１】
（付記８）前記更新部は、
前記特定部によりランドマークノードが特定されなかった場合、前記選択されたランドマークノードを削除することを特徴とする付記４に記載の更新装置。
【０１２２】
（付記９）最上位階層のパーティクルノードを生成元とするランドマークノード群のうち、下位階層のランドマークノードに関連付けられていないランドマークノードを抽出する抽出部と、
最下位階層のパーティクルノードにより特定される自装置の位置および向きに応じた観測範囲に、前記抽出部によって抽出されたランドマークノードが示すランドマークが存在するか否かを判断する判断部と、
前記判断部によって存在しないと判断されたランドマークを示すランドマークノードを前記記憶部から前記記憶部とは異なる他の記憶部に格納する格納部と、
を有することを特徴とする付記１〜８のいずれか一つに記載の更新装置。
【０１２３】
（付記１０）前記抽出部は、
前記他の記憶部に記憶されているランドマークノード群のうち、前記最下位階層のパーティクルノードにより特定される自装置の位置および向きに応じた観測範囲に存在するランドマークを示すランドマークノードを抽出し、
前記格納部は、
前記抽出部によって抽出されたランドマークノードを、前記記憶部内のツリー構造における前記最上位階層のパーティクルノードに関連付けて格納し、
前記構築部は、
前記格納部によって格納されたランドマークノードと、当該ランドマークノードが示すランドマークと同一ランドマークを示す下位階層のランドマークノードとを関連付けることを特徴とする付記９に記載の更新装置。
【０１２４】
（付記１１）コンピュータに、
各々自装置の位置および向きを示すパーティクルノード群を生成して時系列に階層化し、前記パーティクルノード群の各パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを生成元のパーティクルノードに関連付けて生成して時系列に階層化し、階層間で同一ランドマークを示すランドマークノードを関連付けることにより、記憶部内でツリー構造を構築し、
前記ツリー構造を参照して、最下層のパーティクルノードを除く残余のパーティクルノード群の中から、下位階層に関連付けられていないパーティクルノードを検出し、
前記検出されたパーティクルノードおよび当該パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを、前記ツリー構造から削除することにより、前記ツリー構造を更新する、
処理を実行させることを特徴とする更新プログラム。
【０１２５】
（付記１２）コンピュータが、
各々自装置の位置および向きを示すパーティクルノード群を生成して時系列に階層化し、前記パーティクルノード群の各パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを生成元のパーティクルノードに関連付けて生成して時系列に階層化し、階層間で同一ランドマークを示すランドマークノードを関連付けることにより、記憶部内でツリー構造を構築し、
前記ツリー構造を参照して、最下層のパーティクルノードを除く残余のパーティクルノード群の中から、下位階層に関連付けられていないパーティクルノードを検出し、
前記検出されたパーティクルノードおよび当該パーティクルノードが示す位置および向きで自装置から観測されたランドマークの位置を示すランドマークノードを、前記ツリー構造から削除することにより、前記ツリー構造を更新する、
処理を実行することを特徴とする更新方法。
【符号の説明】
【０１２６】
２００  更新装置
１６０１  第１の記憶部
１６０２  第２の記憶部
１６０３  構築部
１６０４  検出部
１６０５  更新部
１６０６  選択部
１６０７  特定部
１６０８  抽出部
１６０９  判断部
１６１０  格納部
【図１】
2014016831.tif 000006
【図２】
2014016831.tif 000007
【図３】
2014016831.tif 000008
【図４】
2014016831.tif 000009
【図５】
2014016831.tif 000010
【図６】
2014016831.tif 000011
【図７】
2014016831.tif 000012
【図８】
2014016831.tif 000013
【図９】
2014016831.tif 000014
【図１０】
2014016831.tif 000015
【図１１】
2014016831.tif 000016
【図１２】
2014016831.tif 000017
【図１３】
2014016831.tif 000018
【図１４】
2014016831.tif 000019
【図１５】
2014016831.tif 000020
【図１６】
2014016831.tif 000021
【図１７】
2014016831.tif 000022
【図１８】
2014016831.tif 000023
【図１９】
2014016831.tif 000024
【図２０】
2014016831.tif 000025
【図２１】
2014016831.tif 000026