(57)【要約】  地理的探索タスク及び他の探索タスクを行うエージェントチームの分散型協調制御のためのシステム及び方法。このアプローチは挙動ベースであり、探索問題に確率粒子アプローチを用いる。エージェントは、地理的エリア又はデータ空間における関心物体の存在に関する仮説を表す仮想の確率粒子の形態の確率分布に引き寄せられる。定期的な更新メッセージの合間に他のチームメンバ及び関心物体の移動をモデル化することによって信頼性の高い高帯域幅通信に対する依存が低減される。
2008507049.tif 000002
【特許請求の範囲】
【請求項１】
関心物体を検出する第１の手段と、
前記物体の挙動を予測する第２の手段と、
前記挙動を予測する手段に応答して前記第１の手段を前記物体へ導く第３の手段と、
を備える探索システム。
【請求項２】
前記第１の手段、前記第２の手段及び前記第３の手段は移動プラットフォーム内に配設される、請求項１に記載の発明。
【請求項３】
前記移動プラットフォームはロボットである、請求項２に記載の発明。
【請求項４】
前記移動プラットフォームは無人機である、請求項３に記載の発明。
【請求項５】
前記挙動を予測する手段は予測モデルを含む、請求項１に記載の発明。
【請求項６】
前記モデルは一組の粒子の形態の確率分布を含む、請求項５に記載の発明。
【請求項７】
前記第２の手段は、前記物体の前記挙動を反映するように前記粒子を移動させる手段を含む、請求項６に記載の発明。
【請求項８】
前記第２の手段は、前記物体の各仮説アイデンティティ毎に１つずつの複数のモデルを含む、請求項７に記載の発明。
【請求項９】
前記物体のロケーションに関する更新を受信する手段をさらに備える、請求項８に記載の発明。
【請求項１０】
前記物体のアイデンティティに関する更新を受信する手段をさらに備える、請求項９に記載の発明。
【請求項１１】
前記更新は前記物体に関する確率情報を含む、請求項１０に記載の発明。
【請求項１２】
前記更新の頻度又は入手可能性は不確定である、請求項１１に記載の発明。
【請求項１３】
前記第１の手段は探索エリア内で導かれる、請求項６に記載の発明。
【請求項１４】
前記第１の手段、前記第２の手段及び前記第３の手段は移動プラットフォーム内に配設される、請求項１３に記載の発明。
【請求項１５】
前記移動プラットフォームはロボットである、請求項１４に記載の発明。
【請求項１６】
前記システムは複数のロボットを含む、請求項１５に記載の発明。
【請求項１７】
前記モデルは、各ロボットを前記探索空間の一意のエリアを探索するように導くようになっている、請求項１６に記載の発明。
【請求項１８】
前記モデルは、粒子の形態の確率分布を用いて、各ロボットを前記探索空間の一意のエリアを探索するように導くようになっている、請求項１７に記載の発明。
【請求項１９】
前記モデルは、前記粒子を各探索機につき１つの群に分けるクラスタリング技法を用いて、各ロボットを前記探索空間の一意のエリアを探索するように導くようになっている、請求項１８に記載の発明。
【請求項２０】
前記モデルは、ロボットを粒子群に一意に割り当てるようになっている、請求項１８に記載の発明。
【請求項２１】
前記モデルは、ロボットを粒子群に、該ロボットの所定の特性を用いて各ロボットによって計算される方法で割り当てるようになっている、請求項１８に記載の発明。
【請求項２２】
前記クラスタリング技法はＫ平均である、請求項１９に記載の発明。
【請求項２３】
前記粒子の前記確率分布はクラスタである、請求項１９に記載の発明。
【請求項２４】
前記ロボットの各々は、前記モデルにより選択されたそれぞれのクラスタを探索するように導かれる、請求項２３に記載の発明。
【請求項２５】
各ロボットの各第３の手段は、その前記第１の手段を前記粒子の確率分布の質量中心へ導くようになっている、請求項２４に記載の発明。
【請求項２６】
前記モデルは、各ロボットの前記検出器を、該モデルにより選択された前記クラスタ内の前記粒子のうちの選択された１つへ導くようになっている、請求項２４に記載の発明。
【請求項２７】
各ロボットは、そのセンサ及び他の探索機のセンサにより観測される前記探索空間の前記エリアを表す粒子を排除する、請求項２６に記載の発明。
【請求項２８】
前記排除された粒子の各々は、所定時間後に再び現れる、請求項２６に記載の発明。
【請求項２９】
前記モデルは、各ロボットが関心物体に関して追加情報を得ると、その関心物体に関連する粒子の分布又は密度が、該新たな情報をより正確に表すように変更されるようになっている、請求項２６に記載の発明。
【請求項３０】
前記粒子を用いて前記物体を追跡する手段を備える、請求項１８に記載の発明。
【請求項３１】
他のロボットに関する更新を受信する手段をさらに備える、請求項１６に記載の発明。
【請求項３２】
他の探索機の活動に関する更新の時間間隔において該他の探索機の活動をモデル化する手段をさらに備える、請求項３１に記載の発明。
【請求項３３】
前記更新は、他の探索機のロケーションに関する情報を含む、請求項３２に記載の発明。
【請求項３４】
前記更新は、他の探索機の現在の注視焦点に関する情報を含む、請求項３２に記載の発明。
【請求項３５】
前記現在の注視焦点は、探索機の物理センサの対象領域である、請求項３４に記載の発明。
【請求項３６】
前記更新は、他の探索機の前の注視点に関する情報を含む、請求項３２に記載の発明。
【請求項３７】
前記更新は、他の探索機の速度に関する情報を含む、請求項３２に記載の発明。
【請求項３８】
前記更新は、他の探索機の将来の移動に関する情報を含む、請求項３２に記載の発明。
【請求項３９】
前記更新は、他の探索機により確認された物体の特性に関する情報を含む、請求項３２に記載の発明。
【請求項４０】
前記挙動は、３Ｄの物理的な空間における移動である、請求項１に記載の発明。
【請求項４１】
前記挙動は、変化する観測可能な特性を伴う、請求項１に記載の発明。
【請求項４２】
前記挙動は、非物理的なデータ空間における移動である、請求項１に記載の発明。
【請求項４３】
複数の移動プラットフォームと、
各プラットフォームに搭載されて関心物体を検出する検出器と、
各プラットフォームに搭載されて前記物体の挙動を予測するとともに、予測された挙動に応答してそれぞれのプラットフォームを前記物体へ導くプロセッサと、
を備える探索システム。
【請求項４４】
前記プロセッサは、予測モデルを含むソフトウェアを実行する、請求項４３に記載の発明。
【請求項４５】
前記モデルは一組の粒子の形態の確率分布を含む、請求項４４に記載の発明。
【請求項４６】
前記モデルは、前記物体の前記挙動を反映するように前記粒子を移動させる、請求項４５に記載の発明。
【請求項４７】
前記モデルは、複数のモデルを前記物体の各仮説アイデンティティ毎に１つずつ含む、請求項４６に記載の発明。
【請求項４８】
前記モデルは、前記物体のロケーションに関する更新を受信するようになっている、請求項４７に記載の発明。
【請求項４９】
前記モデルは、前記物体のアイデンティティに関する更新を受信するようになっている、請求項４８に記載の発明。
【請求項５０】
前記更新は前記物体に関する確率情報を含む、請求項４９に記載の発明。
【請求項５１】
前記更新の頻度又は入手可能性は不確定である、請求項５０に記載の発明。
【請求項５２】
前記検出器は探索エリア内で導かれる、請求項４３に記載の発明。
【請求項５３】
前記移動プラットフォームはロボットである、請求項５２に記載の発明。
【請求項５４】
前記システムは複数のロボットを含む、請求項５３に記載の発明。
【請求項５５】
前記モデルは、各ロボットを前記探索空間の一意のエリアを探索するように導くようになっている、請求項５４に記載の発明。
【請求項５６】
前記モデルは、粒子の形態の確率分布を用いて、各ロボットを前記探索空間の一意のエリアを探索するように導くようになっている、請求項５５に記載の発明。
【請求項５７】
前記モデルは、前記粒子を各探索機につき１つの群に分けるクラスタリング技法を用いて、各ロボットを前記探索空間の一意のエリアを探索するように導くようになっている、請求項５６に記載の発明。
【請求項５８】
前記クラスタリング技法はＫ平均である、請求項５７に記載の発明。
【請求項５９】
前記モデルは、ロボットを粒子群に一意に割り当てるようになっている、請求項５７に記載の発明。
【請求項６０】
前記モデルは、ロボットを粒子群に、該ロボットの所定の特性を用いて各ロボットによって計算される方法で割り当てるようになっている、請求項５７に記載の発明。
【請求項６１】
前記粒子の前記確率分布はクラスタである、請求項６０に記載の発明。
【請求項６２】
前記ロボットの各々は、前記モデルにより選択されたそれぞれのクラスタを探索するように導かれる、請求項６１に記載の発明。
【請求項６３】
各ロボットの各第３の手段は、その前記第１の手段を前記粒子の確率分布の質量中心へ導くようになっている、請求項６２に記載の発明。
【請求項６４】
前記モデルは、各ロボットの前記検出器を、該モデルにより選択された前記クラスタ内の前記粒子のうちの選択された１つへ導くようになっている、請求項６２に記載の発明。
【請求項６５】
各ロボットは、そのセンサ及び他の探索機のセンサにより観測される前記探索空間の前記エリアを表す粒子を除去する、請求項６４に記載の発明。
【請求項６６】
前記除去された粒子の各々は、所定時間後に再び現れる、請求項６４に記載の発明。
【請求項６７】
前記モデルは、各ロボットが関心物体に関して追加情報を得ると、その関心物体に関連する粒子の分布又は密度が、該新たな情報をより正確に表すように変更されるようになっている、請求項６４に記載の発明。
【請求項６８】
前記粒子を用いて前記物体を追跡する手段を備える、請求項４３に記載の発明。
【請求項６９】
他のロボットに関する更新を受信する手段をさらに備える、請求項５３に記載の発明。
【請求項７０】
他の探索機の活動に関する更新の時間間隔において該他の探索機の活動をモデル化する手段をさらに備える、請求項６９に記載の発明。
【請求項７１】
前記更新は、他の探索機のロケーションに関する情報を含む、請求項７０に記載の発明。
【請求項７２】
前記更新は、他の探索機の現在の注視焦点に関する情報を含む、請求項７０に記載の発明。
【請求項７３】
前記現在の注視点は、探索機の物理センサの対象領域である、請求項７２に記載の発明。
【請求項７４】
前記更新は、他の探索機の前の注視点に関する情報を含む、請求項７０に記載の発明。
【請求項７５】
前記更新は、他の探索機の速度に関する情報を含む、請求項７４に記載の発明。
【請求項７６】
前記更新は、他の探索機の将来の移動に関する情報を含む、請求項７５に記載の発明。
【請求項７７】
前記更新は、他の探索機により確認された物体の特性に関する情報を含む、請求項７６に記載の発明。
【請求項７８】
前記挙動は、３Ｄの物理的な空間における移動である、請求項４３に記載の発明。
【請求項７９】
前記挙動は、変化する観測可能な特性を伴う、請求項４３に記載の発明。
【請求項８０】
前記挙動は、非物理的なデータ空間における移動である、請求項４３に記載の発明。
【請求項８１】
関心物体を検出する検出器を設けるステップと、
前記検出器からのデータを、前記物体の挙動を予測するためのモデルを用いて処理するステップと、
前記モデルにより出力されるデータに応答して前記検出器を前記物体へ導くステップと、
を含む探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自動探索を行うシステム及び方法に関する。より具体的には、本発明は、複数の自律的エージェントにより自動地理探索を行うシステム及び方法に関する。
【背景技術】
【０００２】
ロボットは、退屈なタスク、汚いタスク、及び危険なタスクにますます用いられるようになっている。多くの多様な用途で、共同任務を行う３機〜２０機のロボットから成るチームを、人間による監督を最小限にして制御するシステム及び方法が必要とされている。ロボットチームは、湾を捜索するために水中で用いられ、また研究者たちは、海洋化学の変化を監視するためにロボットを用いている。ＮＡＳＡは、ロボットチームを利用することが可能な任務を検討している。市販のロボットは安価になってきており、研究、探索及び救助、並びに他の用途に用いられるであろう。
【０００３】
この点で、ロボットは通常、中央システムにより制御される。中央プランナ（planner）が通常、特定の協調（coordination）プリミティブを用いて、タスクをどのようにロボット間で割り振るかを確認する。各ロボットは、探索空間において或る状態を有する。各ロボットのロケーションに関するデータが中央プロセッサに伝達され、協調のために分析され、ロボットに返送されなければならない。
【０００４】
この中央集中型アプローチは、帯域幅集約的であるため、簡単にはスケーラブルにはできない。このことがこのアプローチを、より要求の高い現在及び将来の用途に対して制約となっている。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
したがって、当該技術分野において、複数のロボットが自律的に、尚且つ協調的に、ロボット間のデータフローを最小限にして動作することを可能にする分散型アプローチが必要とされている。
【課題を解決するための手段】
【０００６】
当該技術分野におけるこの必要性は、データ空間を特定のタイプの目標物／物体について探索する必要があるあらゆる用途に対して効率的な自動分散探索機構を提供する本発明により解決される。最も汎用的な実施態様において、本発明のシステムは、関心物体を検出する検出器と、物体の挙動を予測するモデルと、モデルにより出力されるデータに応答して検出器を物体へ導く機構とを備える。
【０００７】
特定用途において、本発明のシステムは、複数の移動プラットフォーム上に配設される。これらのプラットフォームは、例として、ロボット、無人航空機（ＵＡＶ）又は移動データ構造であってもよい。最良の形態において、モデルは、一組の粒子の形態の物体又は目標物の確率分布特性を提供するようになっている予測モデルである。粒子を移動させて、物体の挙動を反映させる。物体の他の仮説アイデンティティ又は特性を説明するために複数のモデルが含まれてもよい。物体の挙動及び／又は特性（例えばロケーション）に関する更新が受信されると、それに従って、各移動プラットフォームにおいてモデルが更新される。粒子はクラスタにグループ化され、各ロボットが割り当てられて、それぞれのクラスタの質量中心において探索が開始される。
【発明を実施するための最良の形態】
【０００８】
例示的な実施形態及び典型的な応用形態を、添付図面に関連して以下に説明し、本発明の有益な教示を開示する。
本明細書において、本発明の特定用途のための例示的な実施形態に関して説明するが、本発明はそれらに限定されないことを理解すべきである。本明細書中に提示される教示を利用できる当業者は、本発明の範囲内のさらなる修正形態、応用形態、及び実施形態、並びに本発明が特に役立つであろうさらなる分野を認識するであろう。
【０００９】
本発明の教示によれば、物体が存在する確率が動的な粒子クラスタにより表される。各粒子（メモリ内にのみ存在する）は同じ一定の値を有するため、密な粒子クラスタは、そのエリアに物体が存在する確率が高いことを暗示する。各ロボットは、新たな物体の可能性を通知されると、そのメモリ内の独自のエリアマップ上に粒子分布を作成する。ロボットは、以前に通知されていた物体に関する更新を得ると、その粒子分布を必要に応じて、新たな情報を表すように調節する。粒子はタイプ（種類）を有し、優先順位又は重みも有し得る。
【００１０】
各ロボットは、システムのユーザから、１つ又は複数の既知の又は疑わしい物体に関する確率情報を含む定期的な更新を受信し、その物体を見つけて識別するタスクを受ける。更新は、物体が属し得る、関連する非ゼロの尤度をそれぞれ有する１つ又は複数の考え得るクラスを含んでもよい。例えば、移動物体は、タンク（３０％確率）であるか、乗用車（６０％）であるか、又はスクールバス（１０％）であり得る。クラスが伝達されない場合、ロボットは全ての可能性に等しい尤度を与える。このメッセージを受信する各ロボットは、各可能性を表す確率粒子クラスタを作成する。例えば、その物体がタンクを表す確率が３０％である場合、３０個のタンククラスの粒子が、その物体が認められたマップ上のロケーションを中心におそらくは擬似ガウス分布でメモリに作成される。同様に、ロボットは、６０個の乗用車クラスの粒子及び１０個のバスクラスの粒子を同ロケーションに作成する。
【００１１】
その後、定期的に、ロボットは、挙動モデル（例えば複数仮説粒子フィルタ）を実行し、各粒子をそのタイプに応じて、そのタイプの物体が移動するとモデルが予測する方向に、多少ランダムに移動させる。したがって、バス粒子は概ね近隣の学校に向かって移動するかもしれないが、定期的な更新が行われない場合、それらの粒子は住宅又はより遠方の学校に向かって拡散してしまう可能性がある。
【００１２】
本発明によれば、各ロボットは密な粒子エリアに引き寄せられる。このことがロボットの探索挙動を駆動する。各ロボットは、独自のメモリ内の粒子を個別にクラスタリングし、探索を行うクラスタを選択する。ロボット同士は、粒子を生成及び移動させる際に同一アルゴリズムを使用することによって、またその位置に関する時折のメッセージによって更新される互いの挙動をモデル化することによって、探索を協調させる。このモデル化アプローチは、正確な通信に対するアルゴリズムの依存を低減する。各ロボットは、Ｋ個のクラスタを各ロボットにつき１つずつ作成するクラスタリング技法を用いて敵又は目標物の確率粒子をクラスタリングする。Ｋ平均は、そのようなクラスタリング技法の単純な例であるが、よりインテリジェントで適応的なクラスタリング技法を用いてより高い性能を引き出すこともできる。各ロボットは、その現在位置に最も近い平均を有するクラスタをとる。事実上、ロボットは、粒子のロケーションによって表される一意の探索タスクの割り当てを選択している。
【００１３】
航空機等の輸送手段がエリアを探索する際、そのエリア内のあらゆる粒子がその内部マップから一時的に除去される。それらの粒子は、物体が見つからない限り、後に内部マップに戻される。本発明は、監視され続けるべき地理領域上の静的なクラスの粒子も用いる。この種の粒子は移動せず、除去されてから一定時間が経つと常に戻ってくる。
【００１４】
本発明の目的で、「ロボット」という用語は、移動性、センサ及び通信機能を備える状況依存型（situated）の自律エージェントを意味するものとする。ロボットは、任意のタイプの次元空間（例えばデータベース）に位置していてもよい。経路追従、障害物回避、及びセンサ管理は、本発明のアルゴリズムが依存する低レベルのプロセスによって管理される。本発明は、どこへ進むべきかに関して高レベルの決定を行うが、どのようにそこへ向かうべきかに関する詳細を提供するものではない。本発明の目的で、「物体（object）」という用語は、探索すべき関心物を意味するものとする。物体は、建物のような静止物であっても、又は、車両のような移動体であってもよい。それは既知のアイデンティティを有しても、又は有しなくてもよい。本明細書中に提供される例のほとんどは、アイデンティティが分からず、探索の１つの目的はその物体を識別することであると仮定する。物体が建物のような静止物体である場合、そのアイデンティティは二次的なものに過ぎない場合が多い。一番の関心事はその建物に出入りするエンティティである。
【００１５】
例示的な一実施形態において、本発明の方法は、図１〜図４に図示するステップから成る。図１〜図４に示す方法は、各ロボットにおいて並行して行われる挙動を表し、各挙動は、「状況マップ」と呼ばれるローカルデータ構造内にある「粒子メモリ」上で行われる。
【００１６】
図１は、本発明の教示による各ロボットの通信機能の挙動の例示的な実施態様を示すフロー図である。方法１０は、無線を監視するステップ１２を含む。メッセージを受信すると、本方法は、ステップ１４においてメッセージ中に物体の更新があるかチェックする。各ロボットは、更新の合間のチームメイトの移動をモデル化しているため、更新を受信すると、そのチームメイトのロケーションを訂正しなければならない場合がある。ロボットはまた、探索したエリアを反映するためにチームメイトの移動に伴って粒子を除去しているため、チームメイトの更新がモデルと大幅に異なる場合、ロボットは、粒子分布も訂正する必要があるであろう。よって、物体の更新が受信されない場合、方法はステップ１６において、チームメイトのロケーションに関する更新があるかチェックする。そのメッセージがチームメイトのロケーションの更新である場合、ステップ１８において、チームメイトのロケーションを更新する。そうでない場合、システムは無線の監視を続ける。
【００１７】
一方、メッセージが物体の更新を含む場合、方法は、それが現在モデル化している物体であるかをチェックして確かめる。現在モデル化している物体である場合、ステップ２０において、現在モデル化している物体に関連する粒子を必要に応じて移動させ、不確定性が低くなる結果として分散を減少させる。そうでない場合、ステップ２２において、新たな仮説毎に粒子クラスタを作成する。これに関連して、「粒子の移動」とは、物体を表す確率分布を、物体のアイデンティティの各仮説が移動させるであろう方法の何らかのモデルに従って移動させるプロセスを指す。例えば、（レーダ追跡文献に記載されているような）マルチ（複数）仮説粒子フィルタはこれを実施する１つの方法である。粒子の分散は、新たな情報が受信されると、不確定性が低くなるため、減少する。
【００１８】
図２は、本発明の教示の例示的な一実施形態による、各ロボットによって実行されるセンサ管理機能を示すフロー図である。センサ管理機能及び通信機能はともに、確率粒子の集合に働きかける。図５に示し、且つ下記のアーキテクチャの項において説明するように、センサ管理機能及び通信機能は並行して働き、粒子メモリ上で個別に動作する。運動制御機能は、後述のように、これらの粒子の影響を受ける。図２では、ステップ３２において、ロボットが自身のセンサをチェックする。ステップ３４において物体が見つからない場合、ステップ３６において、システムは、センサフットプリント下にある粒子を有効性の確率に従って除去することによって粒子を更新する。
【００１９】
一方で、ステップ３４において物体が見つかった場合、ステップ３８において、システムは、その物体を追跡すべきかどうかを決定する。システムが物体を追跡することに決定した場合、ステップ４０において、全ての関連粒子が、見つかった物体のタイプに変換される。システムが物体を追跡しないことに決定した場合、全ての物体に関連する粒子を削除する。追跡するか、又は追跡しないかという決定は、最終的にユーザによって、明示的な通信により、又は暗黙的に、特定の物体タイプ又は環境条件に対して規定されるポリシとして行われる。本発明の教示によれば、運動及び感知は並行して実行される。これらのロボットサブシステムは、粒子メモリに働きかけることによって間接的に通信する。
粒子管理
本発明の教示によれば、チームメンバ間の通信の必要性が最小限にされ、通信が妨害されても探索性能の低下が目立たない。これは、各チームメンバが全ての他のチームメンバをモデル化し、ロケーションが視覚的に又は通信により確認される度にそのモデルを更新するという事実に起因する。一時的な通信途絶は、時間が経つにつれて、チームメイトモデルの予測がチームメイト機の実際の移動から逸れる可能性があることを意味する。この逸脱は、輸送手段（航空機）の速度及び操縦性、予期せぬ障害物に遭遇する尤度、及び所与の粒子クラスタをどのように探索するかという決定関数において使用されるランダム性の量の関数である。図３及び図４は、所与のクラスタの探索を編成するための１つの可能な方法を示す。
【００２０】
図３は、本発明の教示による各ロボットにより実行される例示的な運動制御方法のフロー図である。運動制御ループはステータスを常時チェックし、ロボットが正しい方向に移動していることを確認する。図３に示すように、ステップ５２において、システムは、タイマをチェックして、粒子の再クラスタに適した時期であるかどうかを確認する。再クラスタのタイミングは、実際のタイマとして、又は動的負荷分散アルゴリズムのような粒子に対する何らかのメトリックの結果として実施することができる。再クラスタに適した時期である場合、ステップ５４において粒子を再クラスタリングし、ステップ５６においてウェイポイント（中間点）をクラスタの重心に設定する。タスクの割り当ては、クラスタを、探索を行うＫ個のロボットそれぞれにつき１つずつ、Ｋ個の別個のサブセットに分割することによって実施される。これを達成する１つの方法は、Ｋ平均等のクラスタリングアルゴリズムによって行うことである。
【００２１】
ステップ５２において、ロボットが、再クラスタに適した時期でないと判断した場合、方法５０は、ステップ５６における運動制御ループを実行する。運動制御ループは、ステップ５８において、ロボットが中間点に到達又は中間点を通過したかどうかをチェックする。到達又は通過した場合、ステップ６０において、ループは次の中間点を選択し、ステップ６２及び６４において、そこへ向かうために必要に応じて方位を調節する。ステップ５８において、ロボットが未だ中間点に到達していない場合、ループはステップ６２に進み、ロボットは、現在の方位が中間点に向かうものであるかどうかをチェックする。方位が合っている場合、ループは再クラスタの時期かを確認するステップ（ステップ５２）に戻る。そうでない場合、ステップ６４において方位を更新してからステップ５２に戻る。
【００２２】
この挙動は、輸送手段（航空機）のアクチュエータへ送られる最後の制御信号への入力を有する障害物回避等の他の挙動又は機能と並行して実行され得る。
ステップ６０において中間点を選択するステップは、現在のクラスタ内の粒子を重要度（重み）、距離、及び他の要因によりソートし、向かうべき最良の粒子を選択することによって達成され得る。他の要因は、その粒子に向かうために必要な最大旋回半径等の、ロボットの移動性に関する考慮事項を含み得る。
【００２３】
粒子をクラスタリングするステップ（ステップ５４）は、粒子をＫ個の一意のサブセットに分割し、どのロボットがどのサブセット又はクラスタを探索すべきかが全てのロボットに分かるようにすることを含む。このような１つの方法を、粒子のクラスタリングと題する項でいくらか詳細に後述する。
【００２４】
場合によっては、ロボットの選択したクラスタは断片的で、断片（パッチ）同士は大きく離間している場合がある。以下の図４に示すＬ２クラスタは、これらのサブパッチを見出す。各サブパッチが順番に探索される。サブパッチ毎に、ロボットは、進むべき粒子を１度に１つ選択し、進む途中で（図２のステップ３６により）粒子を消去し、粒子の密度が十分に低下して、他のサブパッチの緊急度が高くなるまで行う。
【００２５】
図４は、本発明の教示による運動制御方法の代替的な実施態様である。図４の実施態様７０において、システムは、第１のクラスタＬ１においてこの２回目の粒子クラスタリングを行う。第１のクラスタＬ１内の各サブクラスタＬ２を探索してから、次のサブクラスタに移る。したがって、図４は図３と同様であり、Ｌ２のクラスタリングステップが追加されている。
【００２６】
図４に示すように、レベル１のクラスタ（Ｌ１）を処理（do）してグローバルな探索空間をチームメンバ間で分割した後、各メンバはレベル２のクラスタ（Ｌ２）を処理する。Ｌ２はそのメンバのＬ１クラスタ内にサブクラスタを見出す。Ｌ２クラスタを処理する１つの方法はＫ平均アルゴリズムを用いることであり、ここでＫは、密なサブクラスタを見つけるのに十分な大きさの或る小さな任意数に等しい。「Ｋ平均」は、「粒子のクラスタリング」という項で後述する。数Ｋは、ドメインの必要性に完全に依存する。本発明の教示範囲から逸脱することなく、よりインテリジェントなクラスタリングアルゴリズムをパラメータ化して、ドメインに依存しない方法で正しいサイズのクラスタを見出すこともできる。
【００２７】
したがって、図４では、ステップ７２において、Ｌ１を再クラスタリングする時期であると判定された場合、ステップ７４において、Ｌ１のＫ平均を行う。上記ステップ５２と同様に、再クラスタのタイミングは、実際のタイマとして、又は動的負荷分散アルゴリズムのような粒子に対する何らかのメトリックの結果として実施することができる。次に、ステップ７６において、上記ステップ５６と同様に、中間点がＬ１クラスタの重心になるように設定する。ステップ７８において、ロボットは、現在の中間点に到達又は現在の中間点を通過したかどうか判定する。到達又は通過していない場合、ロボットはステップ９２においてをチェックし、中間点に向かっていることを確かめる。方位が合っている場合、ステップ７２に戻る。そうでない場合、ステップ９４において方位を更新してからステップ７２に戻る。
【００２８】
ステップ７８において、現在の中間点に到達したと判定された場合、方法７０は、ステップ８０において、Ｌ１粒子のＬ２クラスタリングが行われたかどうかをチェックする。行われていない場合、ステップ８４においてＬ２クラスタリングを行い、ステップ８６において中間点を選択されたＬ２サブクラスタの重心に設定する。どのサブクラスタを選択しても問題ではないか、又はそのサブクラスタにおける粒子の優先順位又は数等といった要因に基づいて選択を行ってもよい。中間点が選択されると、方法はステップ９２に進み、上記のように方位をチェックする。ステップ８０においてＬ２サブクラスタが作成されていると判断された場合、ステップ８２において、ロボットが現在探索を行っているＬ２サブクラスタから別のＬ２サブクラスタへ移る時期であるかどうかをテストする。
【００２９】
この決定には多くの基準が存在し得る。いずれにせよ、システムは、他のエリアを無視することなく各エリアをくまなく探索しなければならない。ステップ８２において、移る時期であると決定された場合、ステップ８８において新たなサブクラスタが選択され、ステップ８６において中間点が設定され、次にステップ９２において方位がチェックされる。そうでない場合、ロボットは、図３のステップ６０において説明したのと同様に、同じＬ２サブクラスタ内で新たな中間点を選択することによって、そのサブクラスタの探索を続ける。
【００３０】
最良の形態において、サブパッチを選択するための決定は、そのパッチ内にある粒子のタイプの優先順位、そのパッチ内の粒子数、及びパッチの密度の関数である。これを行う１つの単純な方法は、各パッチ内の粒子の和をそれらの優先順位により重み付けし、境界円の面積で割ることによるものである。最初に進むべき粒子を選択する１つの方法は、サブパッチ内の粒子をそれらの優先順位レベル及びロボットからの距離によりソートし、リストの１番目に進むことである。この方式は、敵対勢力に予測し難い不規則な経路を生じるが、他の方式よりも高い操縦性が必要とされ、且つエネルギー効率が低くなる場合がある。本発明の教示範囲から逸脱することなく、特定用途に対してはよりインテリジェントな方式を想定して、最も優先順位の高い粒子を最大限にスイープ（掃出）する軌跡を計算することができる。
【００３１】
１つのサブパッチを離れて別のサブパッチへ進むべき時期に関する決定は、ここでも、上の段落で説明したサブパッチ決定関数に基づくが、フリップフロップを防ぐために、現在のサブパッチの探索を、その決定関数の値（例えば上述の加重和）が次善のパッチのそれを或る閾値だけ下回るまで続けることが妥当であろう。
【００３２】
時間が経過するにつれて、各物体の移動をモデル化するために作成された粒子分布が挙動モデルによって移動される。粒子分布は多少ランダムに移動し、位置に関する不確定性の増加を反映するために移動するにつれて拡散する。
【００３３】
図１は、これらの物体のうちの１つについて情報が受信されると、その物体の分布が或る程度収束し、物体の位置の確定性の増加を反映するために分散が減少することを示す。メッセージが、物体が属し得る１つ又は複数のクラスを除外する可能性もある。これは、別の探索プラットフォームが物体を見つけ識別したときに起こる。ロボットが、仮説のいくつかを表すクラスタによって覆われたエリアを探索して何も見つからないときは、物体が検出を回避している可能性があるため、説得力が低い。その場合、それらの仮説は低減され得るが、排除されることはない。
操作画像（operational picture）のコヒーレンス
本発明の教示によれば、各ロボットに物体のロケーションが伝えられると、ロボットは、独自の粒子分布を作り出す。ここでもまた、擬似ガウス分布の作成にはランダムな要素が伴う。各ロボットは、移動するにつれて、そのセンサ範囲の粒子を或る確率で消去する。同様に、各ロボットは、そのチームメイトの移動（例えば、最後に報告された位置、測度、及び方位のまっすぐな延長）をモデル化し、自身のメモリ内の、チームメイトのセンサ範囲にある粒子を消去する。これは、各ロボットのメモリ内の同一物体に関する同一仮説の粒子分布間のいくらかの変形であり得る。これは、各ロボットが、同一の決定メトリックを実行しているにもかかわらず、いくらか異なるクラスタリングを行い、わずかに異なる時期に再クラスタリングを決定し得ることを意味する。
【００３４】
制御可能なパラメータは、ロボットのステータス報告の時間間隔、これらのステータス報告で共有される情報量、並びに粒子が配置、移動及び除去される確率及びランダム性である。ドメイン毎に、パラメータは多少異なるものとなり、最適パラメータを確認するための実験が必要とされ得る。
探索効率
或るエリアを移動物体について効率良く探索するために必要な機数は、探索エリアの地理的範囲、探索ロボットの速度及び探索対象物の可能な最高速度、並びに探索ロボットがそのセンサ範囲で物体を検出する尤度の関数である。
アーキテクチャ
図５は、本発明の教示を実施するようになっている例示的なロボット制御アーキテクチャのブロック図を示す。図５では、ハードウェアが矩形の枠で表され、ソフトウェアプロセスが丸みを帯びた枠又は楕円で表される。各ロボットは、無線トランシーバ１０２と、例としてレーザレーダ（ＬＡＤＡＲ）１０５、赤外線（ＩＲ）１０６及びカメラ１０７を含む内蔵センサ１０４とを備えるシステム１００を有する。さらに、システム１００は、信号及びデータプロセッサ１１０（破線で示す）を、全地球測位センサ１０８、運動制御サブシステム１１２及び運動アクチュエータ１２２とともに備える。
【００３５】
無線１０２は、他のロボット及び／又は中央制御局からメッセージを受信し、それらのメッセージを、メッセージ処理ソフトウェアルーチン１０で処理するためにプロセッサ１１０へ送る。メッセージ処理ルーチン１０は図１に関して上述した。内蔵センサ１０４からのデータは、図２のセンサ処理ルーチン３０によって処理される。運動及び感知は、チームモデル４４又は敵モデル４６に従って粒子メモリ４８に働きかけることによって並行して実行される。
【００３６】
チームモデル及び敵モデルは、ロボットに事前にロードされており、経験から学習しても、学習しなくてもよい。敵モデルは、ユーザ及び他の探索チームメイトから受信する報告を適切に表すために必要に応じて確率分布を作成し、維持し、且つ移動させる挙動モデルである。敵モデルは、関心物体の移動をモデル化する。チームモデルは、この共同探索に参加している他機の別個の挙動モデルであり、他のチームメイトからの状況報告によって更新される。チームモデルは、チームメイトの移動を推定し、他のチームメイトが探索するエリアを表すように粒子を移動させる。これらの分布は、図３及び図４に関して上述したようにＬ１クラスタ及びＬ２クラスタのクラスタリング及び選択を行う探索エリアセレクタ５０に進む。Ｌ１クラスタの選択は、各チームメートの場所に関するチームモデル情報に依存する。
【００３７】
クラスタが探索のために選択されると、中間点選択関数７０が、そのクラスタ内の目的地を選択する。この場合、本発明では、その選択を挙動アービトレーション（調停）ユニット１１２において、障害物の回避等といった他の考慮事項と混合する。決定は、David Paytonの引用特許により実施され得る運動アービタ１２０によって行われる。速度コマンド及び旋回率コマンドが運動アービタ１２０によって出力され、ロボットの方向及び運動速度を制御するために運動アクチュエータ１２２によって使用される。
動作
「電子インテリジェンス」データ（ＥＬＩＮＴ）は、現場の人員からの確認報告と、インテリジェンスアナリストの理論と、衛星、航空機、及び他の情報源からのセンサデータとの融合である。ＥＬＩＮＴの更新は不確定情報を表し、何かが疑わしく見えたり振舞ったりしても、それが敵のタンクであるのか、民間車両であるのか、スクールバスであるのか等の詳細な確認を得る必要がある。本発明の教示によれば、このようなメッセージが受信されると、各ロボット又はＵＡＶはそれを、状況マップと呼ばれるローカルな動的データ構造に、各仮説を表す粒子のクラスタの形態で記録する。異なるクラスの粒子は、物体のアイデンティティに関する異なる仮説を、関連する危険レベル又は優先順位とともに表す。
【００３８】
ＥＬＩＮＴ更新の合間に、各ＵＡＶは、そのタイプのエンティティの挙動モデルを実施する単純な複数仮説粒子フィルタを用いて粒子を移動させる。例えば、スクールバスを表す粒子は、スクールゾーンに向かって移動するかもしれず、敵のタンクを表す粒子は、疑わしい燃料ダンプ又は発電所等の考え得る目標物に誘引されるであろう。これを下記の図６に示す。
【００３９】
図６は、ＥＬＩＮＴ更新の数分後に本発明の教示によりシミュレートされるシナリオである。右上のＵＡＶは考え得る目標物に関するＥＬＩＮＴ（電子インテリジェンス）報告を、そのアイデンティティ（乗用車、タンク、又はバス）の尤度とともに取得する。各ＵＡＶは、目標物を表す確率粒子をその粒子メモリに作成する。厳密な粒子のロケーションはＵＡＶ毎に異なるが、分布は統計的に等しい。図６において、幹線道路の南東の街及び数個の識別された建物が挙動モデルのアトラクタである。粒子の分布は他のＵＡＶのローカル粒子メモリに統計的に等しいが、個々の粒子のロケーションは同じではない。
【００４０】
図７は、ＥＬＩＮＴ更新の１０分後の時点で本発明の教示によりシミュレートされるシナリオである。各仮説の確率粒子分布は、適切な挙動モデルによって個別に移動される。粒子がこのように拡散するためには、物体位置に関する更新がしばらくの間なかったであろうことに留意されたい。
【００４１】
図８は、図６及び図７に示すシナリオのコンピュータシミュレーションのスクリーンショットである。ＰｌａｙｅｒＳｔａｇｅ（Gerkey et al 2003）と呼ばれるパブリックドメインのシミュレーションを用いた。現実的なフットプリントを有するセンサと、ＧＰＳと、マルチチャネル無線と、基準検出を用いる単純な物体認識とをそれぞれ有するＵＡＶのチームを本発明の教示に従って構成した。図示の実施形態において、ＵＡＶ制御システムは、３つの挙動（すなわち、ポイントへ進む、障害物を回避する、及び旋回を続ける）の間でアービトレーションを行う。アービトレーションの結果は、いくらか現実的な制約に従う移動アクチュエータへの速度コマンド及び旋回率コマンドである（Payton et al 1990）。ＰｌａｙｅｒＳｔａｇｅでは、各エージェントは独自のメモリを有し、共有されるべき情報はメッセージで明示的に送られなければならない。
【００４２】
図８の右側の３つの暗いウインドウは、各ＵＡＶの状況マップを表す。これらのマップの粒子分布は同じでないことに留意されたい。左上象限のＵＡＶ（ＵＡＶはセンサの扇形領域を有する）はその状況マップ内の粒子クラスタによってそのエリアに誘引され、タンクを検出している。右下象限のＵＡＶはスクールバスをちょうど識別し、その状況マップの粒子を一掃したところである（一番上）。他の２つのＵＡＶは未だ、その車両を表す粒子をそのマップから消去していない。右下のＵＡＶは今、道路に沿って、ＥＬＩＮＴによって報告されたばかりのタンクを表す粒子群が現れたばかりの左下象限に向かっている。
【００４３】
目標物及びチームメイトのロケーションに関する定期的なＥＬＩＮＴ更新を受信するための通信が必要である。しかし、これらのドメインにおける通信は信頼性が低く、妨害、（操縦中の）アンテナ不整合、及び気象効果を受けやすい。この問題に対する本発明のアプローチは、各ＵＡＶに、通信事象の合間のチームメンバ及び目標物の移動を確率的にモデル化させることである。これにより、通信の瞬断時の低下が目立たない探索挙動がもたらされる。
【００４４】
上述のように、航空機は、探索を行う際、そのセンサフットプリント下のエリア内の粒子をその状況マップから、検出確率に応じて除去する。これらの粒子は、タイムアウト後にマップに戻される。粒子の消去は、各ＵＡＶがわずかに異なるセットを有するため、チームメイト間で通信されない。その代わりに、各ＵＡＶは、チームメイトの移動モデルを用いて自身のマップ内の粒子を消去する。チームメイトの位置を報告するメッセージを受信すると、その位置がモデルによって予測したものと大幅に異なる場合、粒子マップを修正することができる。物体が見つかった場合、そのアイデンティティが確認され、誤った仮説を表す全ての粒子が破壊される。物体情報は他機に通信され、それらの航空機は自身のプライベートな状況マップに対して同様の変更を行う。
【００４５】
静的な地理領域を監視下に保つために、特別なクラスの静的な粒子を使用してもよい。この種の粒子は移動せず、タイムアウト後には常に戻る。粒子が戻る速度を調節することによって、エリアの探索頻度に対して統計的制御を行うことができる。
粒子のクラスタリング
各ＵＡＶは、密な粒子エリアに誘引される。これは探索挙動を駆動する。特定の探索エリア又はタスクの割り当てについてチームメイトとネゴシエーションを行う必要性を回避するために、各ＵＡＶは、同一のクラスタリングアルゴリズムを用いて粒子を分割し、最も近いものを選択する。これは、単純な分散型タスク割り当て技法を実施する。ＵＡＶは、それらの位置に関する時折（数秒毎）のメッセージによって更新される互いの挙動をモデル化することによって探索を協調させる。
【００４６】
敵の確率粒子をクラスタリングするためにＫ平均アルゴリズム（Lloyd 1982）が用いられる。簡略して言えば、確率粒子がベクトル｛ｐ１，．．．，ｐｎ｝（ｐｉ∈ＩＲ２）で表される場合、目標は、それぞれベクトルｍｋ∈ＩＲ２（ｋ＝｛１．．．Ｋ｝）によって表されるＫ個のクラスタを見つけること、及び「小さな」クラスタが形成されるようにデータ点をクラスタに割り当てることである。本発明では、ＵＡＶの数にＫを選択し、各ＵＡＶｉは、その現在位置に最も近い平均を有するクラスタをとる。クラスタリングは以下の目的関数Ｈを最小化する。
【００４７】
【数１】
2008507049.tif 000003
【００４８】
ここで、ｃは粒子ｐｉを、ｍｃ（ｉ）に位置するクラスタ上に写像し、Ｈは、各粒子を写像ｃにより表す際の歪みの測度である。アルゴリズムは、ｍｃ（ｉ）がＵＡＶｉのロケーションに設定されることにより初期化される。反復毎に、各確率粒子ｐｉは、最近傍のクラスタロケーションｍｃ（ｉ）に割り当てられ、次に、各ｍｃ（ｉ）は、その割り当てられた粒子の重心に移動され、或る時点でそれ以上の改良がなくなり、写像ｃが変化を止めるまで歪みＨが低減される。各ＵＡＶｉは一意のｍｃ（ｉ）に写像されるため、結果として、粒子がＵＡＶに一意に割り当てられる。
【００４９】
本発明の教示範囲から逸脱することなく、他のクラスタリング技法を用いてもよい。標準的なＫ平均アルゴリズムは、各平均に特定数の点が割り当てられることを保証せず、点を含まないクラスタが生じ得る。また、特定タイプの粒子に付加される優先順位又は緊急度による重み等のパラメータを考慮することが有用であろう（すなわち、ｐｉ∈ＩＲｄ（ｄ＞２））。
クラスタ内の探索
本発明の教示によれば、ＵＡＶは、自身に割り当てられたクラスタの重心に達すると、クラスタ内で向かうべき確率粒子を選択する。これは、単純に最も近い確率粒子へ進むこととすることもできるが、本発明では、操縦性の制約に応じて粒子の優先順位又は緊急度も考慮する。したがって、ＵＡＶは、バスの仮説をチェックする前にタンクの仮説粒子をチェックしなければならない。これは、クラスタ内の粒子を優先順位、距離、及び現在の速度ベクトルからのヨー（yaw）角によりソートすることによって実施される。優先順位が高く、距離が短く、必要なヨーが小さいものが最良である。いくらかのランダム性を加えるために、次の中間点は、上位２０％の最良粒子からのランダムな選択であってもよい。
【００５０】
敵性勢力探索では、敵によって利用される可能性のある予測可能な探索パターンの実行を防ぐことが望ましい。上述の手順は、非常に予測し難い移動を生じる。当然、予測可能性と効率との間にはトレードオフがあり、様々な意味で、探索パターンが予測し難くなるほどエネルギー効率は低下する。このトレードオフは、上述の「次の粒子」のソートにおいてヨー基準に対する重みを調節すること、及び／又はランダムな選択における粒子数を変化させることによって制御することができる。
【００５１】
状況は動的である。新たな物体が報告され、古い物体は識別され、時には目標に設定される。全てのデータは、優先順位を有する粒子のこの共通の操作画像に融合されるため、探索決定を行うために必要な理由付けは極めて単純であり、挙動ベースのアプローチに適している。
【００５２】
粒子分布が、時折の情報更新に基づいて各ＵＡＶによって個別に生成され、移動され、消去される。再クラスタリングすべき時期である場合、各ＵＡＶが維持する状況画面間の差異がいくぶん異なるクラスタロケーション（ｍｃ（ｉ））を生じる可能性があり、それが驚くべき挙動につながる可能性がある。再クラスタの決定は、探索が進行する粒子分布の変化に関するメトリックに基づくものであってもよい。別のアプローチは、より変化の遅いクラスタリング技法を使用すること、又は再クラスタリングの前により高い協調を要求することであろう。
情報のコヒーレンスの問題
ＥＬＩＮＴメッセージが新たな目標物を知らせると、各ＵＡＶは、メッセージ情報に基づいて独自の擬似ランダムな粒子分布を作り出す。以後のＥＬＩＮＴメッセージは、目標物のロケーション及び／又はアイデンティティを更新しても、更新しなくてもよい。各ＵＡＶは、移動するにつれて、そのセンサフットプリント下の粒子を或る確率で消去する。同様に、各ＵＡＶは、そのチームメイトの移動（ここでは最後に報告された位置、速度、及び方位からの単純な線形補間）をモデル化し、各チームメイトのセンサ範囲の粒子を消去する。
【００５３】
図８の右側には、３つのＵＡＶのそれぞれに対して１つのウインドウがあり、それらの状況マップ上の粒子のロケーションを示している。３つの比較は、各チームメイトがモデル化する粒子分布間の小さくランダムな変化を示す。これは、航空機が再クラスタを決定するとき、それらのクラスタは或る程度異なることを意味する。
【００５４】
通常、ＵＡＶ間のクラスタの差異はわずかであり、システムは良好な挙動を生じる。これは、目標物が数分毎にマップ上の主に３つのロケーションで出現し、ほぼ道路上を移動するとしても関係ない。これはしばしば、目標物が互いに接近することを意味するが、ＵＡＶが位置及び速度のみを含む状況報告を５秒毎に送信すれば良好な結果が得られ得る。時折、この差異は大きくなり、無用に見える探索パターンを生じる場合がある。状況のコヒーレンスという見出し下で、この問題に寄与する要因がいくつかある。制御可能なパラメータは、ＵＡＶステータス報告の時間間隔、これらのステータス報告で共有される情報量、並びに粒子が配置、移動及び除去される確率及びランダム性である。パラメータ値の最良の選択は、目標物の互いに対する近接度に依存すべきである。目標物同士が近いほど、ＵＡＶ同士は近くなり、各ＵＡＶの状況画面はコヒーレントになり、適切に相互干渉を排除するはずである。
【００５５】
別のＵＡＶの動作の正確な予測は、その他機が決定を行う際に用いる各変数の値の正確な知識を必要とする。それを行うために必要とされるような種類の、高帯域の信頼性の高い通信に対する依存を避けることが好ましい場合がある。より良い解決策は、各ＵＡＶがその現在のロケーション及び速度をより頻繁に通信することであり得る。ほとんどの場合に、物体に関するＥＬＩＮＴ更新が頻繁であるとき、各ＵＡＶの状況画面間で非常に高いコヒーレンスを達成するようにＵＡＶ報告速度を調節することができる。しかし、ＥＬＩＮＴ更新が妨害されるか、関心物体に関する新たな情報が単にない場合、ＵＡＶは、互いの再クラスタリングを協調させる必要がある。本発明の教示によれば、再クラスタ動作は、定期的に通知され、その時点で、全てのＵＡＶはその過去のロケーションの短い履歴を通知する。これは、コヒーレントな粒子マップを常に維持するために必要なものよりも遥かに短く頻度の低いメッセージであるであろう。各ＵＡＶはその場合、自身の状況マップを正して再クラスタリングする。これは、非常に類似したタスクの割り当てを生じることになる。最悪の場合、再クラスタリングの後に確認ステップを加えて、結果として得られる、各ＵＡＶが計算するクラスタ中心が十分に類似することを保証することができる。
【００５６】
要約すれば、協調がコヒーレントでなくなってくる時期に通信帯域幅を増やすことができる。これらの時期は、ＵＡＶ間の距離、及び位置更新が受信される速度を含むローカル情報に基づいて予測することができる。
【００５７】
本発明のエンドユーザは、より焦点及び的を絞った探索が必要であろう。現在用いられている組織的な探索機構又は他の強引な探索機構（エリアを地理的に分割して探索パターンを実行すること等）は、成功確率を上げるために速度及び／又は資源の増加に依存しなければならない。本発明は、探索プラットフォームの物理的能力をアップグレードしたり、プラットフォーム数を増やしたりすることなく、目標物体を発見する確率を高める。本発明はこの価値を高めた確率の上昇を、時間領域において探索エリアを狭める機構を探索プラットフォームに設けることによって達成する。必須ではないが、更新時間に基づく状況情報が、確率クラスタを再グループ化して新たな情報をより正確に表し、探索の焦点をさらに絞ることにより、この探索エリアをさらに縮小する。
【００５８】
本発明は、報告が特定の時間にわたって定期的に入力され、各報告が前出の物体に関する更新情報又は新たな物体に関するニュースを有し、各物体がそのアイデンティティに関していくつかの仮説を有する、複雑で動的に変化する状況に特に有用である。本発明のアプローチは、これらの報告を融合して共通の操作画像にするために非常に単純で明瞭な方法を用いる。マップ上に配置される確率粒子の集合を用いることによって、物体の位置及び考え得るアイデンティティは、探索を駆動する共通の表現に変換される。本発明は、複雑な融合エンジン及び任務管理に対する必要性を軽減し、融合は自然な確率の重複により生じる。したがって、この機能は、任務にかかる費用を増加させることなく探索が成功する確率を高めることによって、エンドユーザに価値をもたらすはずである。
【００５９】
本発明はまた、分散探索チームを多くの個人ユーザによって誘導する可能性を提供する。例えば、６機のＵＡＶが軍の戦闘地帯を飛行している場合、戦場の至る所にいる司令官が疑わしい敵の活動の報告を供給することができる。ＵＡＶは、報告された敵がどこにいてもその敵を探索するように自動的に組織化する全般支援資産（アセット）となる。この組織化は自動的であり、オペレータ（operator）が要求を処理し最も良い対応方法を決定する中央制御施設は必要ない。軍務（service）は優先順位に基づいて行われ得る。例えば、攻撃の主な努力は、支援部隊よりも高い優先順位を有するかもしれず、これは、各部隊の要求がマップに配置させる粒子の優先順位に反映され得る。
【００６０】
最も協調的な制御技法は、頻繁で信頼度の高い通信をロボット間に必要とする。本発明はこの依存を、更新の合間に他のチームメイトの動作をモデル化することに依存することによって軽減するものである。これは、探索効率の低下を目立たなくする。
【００６１】
探索タスクの自動分割は、複数のロボットの間接的で高レベルの制御をユーザに与える。ユーザは、探索すべきエリア上の確率分布を指定することによって探索タスクを直接、直感的な方法で表現する。これは、ユーザが一組のロボットを明示的に指定し、それらにタスクを割り当てなければならない現行システムに対する進歩である。しかし、ユーザは、どのエリアをどの優先順位で探索すべきかを高精度で指定することができる。本発明はこれを、移動目標物を表す粒子を挙動モデルを用いて実際に移動させることによって別のレベルへ導く。
【００６２】
複数のモデルを目標物の各仮説アイデンティティに対して１つずつ組み込んでもよい。これらのモデルは、例としてロケーション、アイデンティティ、他の探索機（サーチャ）の現在の焦点、他の探索機の前の焦点、他の探索機の速度、他の探索機の将来の移動及び成功を含む様々なデータにより更新される。探索は、物理的な３次元（３Ｄ）空間、仮想データ構造又は他の用途において行われてもよい。
【００６３】
このように、本発明を本明細書中において、特定用途のための特定の実施形態に関して説明してきた。本発明の教示にアクセスできる当業者は、本発明の範囲内においてさらなる修正形態、応用形態及び実施形態を認識するであろう。
【００６４】
したがって、特許請求の範囲は、本発明の範囲内のあらゆる全てのそのような応用形態、修正形態及び実施形態を網羅することを意図している。
【図面の簡単な説明】
【００６５】
【図１】本発明の教示による各ロボットの通信機能の挙動の例示的な一実施態様を示すフロー図である。
【図２】本発明の教示の例示的な一実施形態による各ロボットにより実行されるセンサ管理機能を示すフロー図である。
【図３】本発明の教示による各ロボットにより実行される例示的な運動制御方法のフロー図である。
【図４】本発明の教示による運動制御方法の代替的な一実施態様である。
【図５】本発明の教示を実施するよう適応された例示的なロボット制御アーキテクチャのブロック図である。
【図６】情報更新の数分後に本発明の教示によりシミュレートされるシナリオである。
【図７】情報更新の１０分後に本発明の教示によりシミュレートされるシナリオである。
【図８】図６及び図７に示すシナリオのシミュレーションのスクリーンショットである。
【図１】
2008507049.tif 000004
【図２】
2008507049.tif 000005
【図３】
2008507049.tif 000006
【図４】
2008507049.tif 000007
【図５】
2008507049.tif 000008
【図６】
2008507049.tif 000009
【図７】
2008507049.tif 000010
【図８】
2008507049.tif 000011
【国際調査報告】
2008507049.tif 000012
2008507049.tif 000013
2008507049.tif 000014