(57)【要約】  輸送手段等の物体の経路計画システム及び方法は、スタート位置（ＲＮ）からゴール位置（２０２）へのランダム化適応型経路計画を提供する。このランダム化適応型経路計画は、輸送手段及び障害物（２０４ａ〜２０４ｆ）の移動の確率的知識を用いて、動的に変化する環境及び不確定な環境においてキノダイナミック制約条件下で動作する輸送手段のリアルタイム経路計画を取り扱う。
2007531110.tif 000002
【特許請求の範囲】
【請求項１】
スタート位置からゴール位置への状態空間における物体に対する少なくとも１つの経路を、複数の静的な物体及び／又は動的な物体を回避するように計画する方法であって、
（ａ）前記状態空間に位置する前記複数の静的な物体及び／又は前記複数の動的な物体に所定の属性を関連付けること、
（ｂ）前記状態空間に位置する、前記輸送手段の前記スタート位置から前記ゴール位置に向けて伸びる複数の枝を含む確率木を前記状態空間において生成すること、
（ｃ）複数のランダム木拡張ルール及び複数の決定論的木拡張ルールの少なくとも１つに基づいて、所定の停止条件を満たすまで、前記確率木の前記複数の枝を、前記状態空間に位置する前記ゴール位置に向けて拡張すること、及び
（ｄ）前記確率木の前記複数の枝の少なくとも第１の枝を評価して、該確率木の該複数の枝の該第１の枝が所定の軌道経路制約条件を満たすかどうかを判断すること、
を含む方法。
【請求項２】
前記確率木の前記複数の枝の前記第１の枝が、前記所定の軌道経路制約に従う場合、前記方法は、
（ｅ）前記確率木の前記複数の枝の前記第１の枝を、前記状態空間における前記輸送手段に対する前記少なくとも１つの好ましい軌道経路として宣言すること、及び
（ｆ）前記状態空間において前記スタート位置から前記ゴール位置へ向けて前記輸送手段を移動させるため、前記状態空間における前記少なくとも１つの好ましい軌道経路に従うように前記輸送手段を制御すること、
をさらに含む、請求項１に記載の方法。
【請求項３】
前記確率木の前記複数の枝の前記第１の枝が、前記所定の軌道経路制約に従わない場合、前記方法は、
（ｇ）前記確率木の前記複数の枝の少なくとも１つの枝が前記所定の停止条件を満たし、前記所定の軌道経路制約に従うまで、前記複数のランダム木拡張ルール及び前記複数の決定論的木拡張ルールの前記少なくとも１つに基づいて前記確率木の前記複数の枝をさらに拡張すること、
をさらに含む、請求項２に記載の方法。
【請求項４】
（ｈ）前記スタート位置を前記ゴール位置に結合し、前記所定の軌道経路制約に従う、前記確率木の前記複数の枝の前記少なくとも１つの枝を、前記状態空間における前記輸送手段に対する前記少なくとも１つの好ましい軌道経路として宣言すること、及び
（ｉ）前記状態空間において前記スタート位置から前記ゴール位置へ向けて前記輸送手段を移動させるため、前記状態空間における前記少なくとも１つの好ましい軌道経路に従うように前記輸送手段を制御すること、
をさらに含む、請求項３に記載の方法。
【請求項５】
（ｊ）前記複数の動的な物体の動きを補償するように前記少なくとも１つの好ましい軌道経路を更新するため、前記輸送手段が、前記ゴールに向けて前記少なくとも１つの好ましい軌道経路に沿って移動するにつれて、所定の時間間隔でステップ（ａ）〜（ｉ）の１つ又は２つ以上を反復すること、
をさらに含む、請求項４に記載の方法。
【請求項６】
前記所定の停止条件を満たすことは、所定の時間制約を満たすこと、及び、所定の移動距離制約を満たすことの少なくとも１つを含む、請求項１に記載の方法。
【請求項７】
前記状態空間に位置する前記複数の静的な物体及び前記複数の動的な物体に所定の属性
を関連付けることは、位置値、速度値、方向値、加速度値、及び時刻値の少なくとも１つを関連付けることを含む、請求項１に記載の方法。
【請求項８】
前記確率木を前記状態空間において生成することは、
前記確率木の前記複数の枝のそれぞれの第１の線分を形成するため、前記複数のランダム木拡張ルール及び前記複数の決定論的木拡張ルールに基づいて、第１の複数のエッジのそれぞれを、前記状態空間における前記スタート位置から、対応する第１の複数の節点のそれぞれへ、第１の所定の距離及び方向で拡張すること、
をさらに含む、請求項１に記載の方法。
【請求項９】
前記確率木の前記複数の枝の各枝の次の連続した線分を形成するため、前記複数のランダム木拡張ルール及び前記複数の決定論的木拡張ルールに基づいて、次の連続した複数のエッジの少なくとも１つを、前記第１の複数の節点のそれぞれから、対応する次の連続した複数の節点のそれぞれへ、前記状態空間における第２の所定の距離及び方向で拡張すること、
をさらに含む、請求項８に記載の方法。
【請求項１０】
前記確率木の前記複数の枝の少なくとも前記第１の枝が前記停止条件を満たすまで、該確率木の該複数の枝の各枝の拡張を循環的に反復すること、
をさらに含む、請求項９に記載の方法。
【請求項１１】
前記確率木の前記複数の枝の１つ又は２つ以上の枝の拡張が、物体回避制約に違反するかどうかを評価すること、及び
前記確率木の前記複数の枝の前記１つ又は２つ以上の枝の拡張が、前記物体回避制約に違反するとの判断がなされた場合、該複数の枝の該１つ又は２つ以上の枝のさらなる拡張を中断すること、
をさらに含む、請求項１０に記載の方法。
【請求項１２】
前記確率木の前記複数の枝の前記１つ又は２つ以上の枝の拡張が、前記物体回避制約にもはや違反しないとの判断がなされた場合、該複数の枝の該１つ又は２つ以上の枝の拡張を再開すること、
をさらに含む、請求項１１に記載の方法。
【請求項１３】
前記複数のランダム木拡張ルールに基づいて前記確率木の前記複数の枝を拡張することは、前記複数の静的な物体及び前記複数の動的な物体のない前記状態空間内に各枝を拡張すること、並びに、前記確率木の前記複数の枝の他の枝のない前記状態空間内に各枝を拡張することの少なくとも１つを含む、請求項１に記載の方法。
【請求項１４】
前記複数の決定論的木拡張ルールに基づいて前記確率木の前記複数の枝を拡張することは、前記ゴールに向けて各枝を拡張すること、及び、各枝の前の拡張に対して直線で各枝を拡張することの少なくとも１つを含む、請求項１に記載の方法。
【請求項１５】
前記確率木の前記複数の枝の前記第１の枝が前記所定の軌道経路制約を満たすかどうかを判断することは、該確率木の該複数の枝の該第１の枝が、最大移動距離値、最大旋回角値、前記複数の静的な物体及び前記複数の動的な物体への最小距離値の少なくとも１つを満たすかどうかを判断することを含む、請求項１に記載の方法。
【請求項１６】
輸送手段の経路計画方法であって、
初期スタート位置及びゴール位置を含む状態空間を定義すること、
決定論的ルール、ランダム性ルール、及び確率的ルールの少なくとも１つを含む一組の
ルールに基づいて、時間の経過に伴い節点単位で前記スタート位置から前記ゴール位置へ複数の経路を生成すること、
各確率分布に基づいて、時間の経過に伴い、前記状態空間において物体にロケーションを割り当てること、及び
前記生成された複数の経路の第１のものを選択すること、
を含む方法。
【請求項１７】
前記複数の経路のうちの、前記状態空間における所与の節点で実現可能でないものを終了すること、をさらに含む、請求項１６に記載の方法。
【請求項１８】
物体との衝突、領域回避、Ｇ力の限界、センサ情報、経路距離、経路時間、旋回数、高度変化の限界、直線経路の望ましさ、物体ロケーションの信頼レベル、旋回半径の限界、及び旋回ペナルティの１つ又は２つ以上に基づいて経路を終了すること、をさらに含む、請求項１７に記載の方法。
【請求項１９】
信頼レベルを物体ロケーションにさらに割り当てる、請求項１６に記載の方法。
【請求項２０】
位置、進行方向、速度、加速度、旋回半径、加速度制限、速度制限、Ｇ力の制限、及びロケーションの信頼レベルの１つ又は２つ以上を含む物体状態情報を割り当てること、をさらに含む、請求項１６に記載の方法。
【請求項２１】
前記物体状態情報の１つ又は２つ以上の構成要素に確率分布を割り当てること、をさらに含む、請求項２０に記載の方法。
【請求項２２】
輸送手段の適応型経路計画方法であって、
前記輸送手段及び複数の物体の状態空間を定義し、
前記輸送手段に対するルート節点を初期状態に設定し、
輸送手段のスタートロケーションからゴールロケーションへ、節点間の枝を含む複数の経路を生成し、
前記枝のそれぞれを検査して、停止条件が満たされるかどうかを判断し、
決定論的ルールを使用して、前記枝の第１のものを生成し、
ランダム拡張ルールを使用して、前記枝の第２のものを生成し、
前記複数の枝の第１のものを終了すべきかどうかを判断し、
前記複数の経路のうちの、前記ゴールロケーションに伸びる第１のものを選択する、
ことを含む方法。
【請求項２３】
位置、進行方向、速度、加速度、旋回半径、加速度制限、速度制限、Ｇ力の制限、及びロケーションの信頼レベルの１つ又は２つ以上を含む状態情報を前記複数の物体に割り当てること、をさらに含む、請求項２２に記載の方法。
【請求項２４】
輸送手段に対して経路を計画するシステムであって、
ワークステーションであり、
前記輸送手段及び複数の物体の状態空間を定義するステップと、
前記輸送手段の初期状態にルート節点を設定するステップと、
輸送手段のスタートロケーションからゴールロケーションへ、節点間の枝を含む複数の経路を生成するステップと、
前記枝のそれぞれを検査して、停止条件が満たされるかどうかを判断するステップと、
決定論的ルールを使用して、前記枝の第１のものを生成するステップと、
ランダム拡張ルールを使用して、前記枝の第２のものを生成するステップと、
前記複数の枝の第１のものを終了すべきかどうかを判断するステップと、
前記複数の経路のうちの、前記ゴールロケーションに伸びる第１のものを選択するステップと、
を可能にする命令を収容するメモリに接続されるプロセッサ、
を含むワークステーションを備えるシステム。
【請求項２５】
位置、進行方向、速度、加速度、旋回半径、加速度制限、速度制限、Ｇ力の制限、及びロケーションの信頼レベルの１つ又は２つ以上を含む状態情報を前記複数の物体に提供するプログラム命令、をさらに含む、請求項２４に記載のシステム。
【請求項２６】
前記選択された経路を前記輸送手段にダウンロードするプログラム命令、をさらに含む、請求項２４に記載のシステム。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
発明の分野
本発明は、概括的には、経路計画に関し、より詳細には、物体及び／又は輸送手段の可能な経路を計画することに関する。
発明の背景
当該技術分野で既知のように、輸送手段の経路を計画することが望ましい状況が存在する。１つの既知の経路計画技法は、高速ランダム探索木（ＲＲＴ（Rapidly-Exploring Random Tree））として知られている。しかしながら、ＲＲＴ方法は、少数の静止障害物を扱い、回避しなければならない環境の領域が固定されていることを前提とする。このような方法の１つの不利な点は、移動物体、不確定な環境、又は不確定な輸送手段の移動に対処していないということである。
【０００２】
米国特許第６，２５９，９８８号は、頂点が所定の格子におけるノード（節点）から構成される２次元又は３次元で経路を見つけるための経路計画方法を提示するリアルタイムミッション適応可能経路計画装置（real-time mission adaptable route planner）を開示している。‘９８８号特許に開示された方法は、基本的に、欲張りな方法で、存在する経路に節点を追加するグラフ探索方法である。格子における節点は、自身に関連付けられた「コスト」値を有し、これらのコストは、経路をどのように拡張するかを判断する際に使用される。候補節点は、その節点におけるコスト関数に基づく判定基準を使用して経路に追加される。節点を経路に追加するのに、コスト関数が使用される。考慮される制約は、最大旋回角、最小線分長、及び最大経路長である。
【０００３】
米国特許第６，２５９，９８８号では、さらに別の進路計画方法も開示されている。この進路計画方法では、エリア全体のコストの計算を必要とするために、所定の格子におけるあらゆるセルにコストが割り当てられる。格子全体のコストは、反復する毎に更新される。
発明の概要
本発明は、輸送手段及び障害物の移動の確率的知識を用いて、動的に変化する環境及び不確定な環境においてキノダイナミック（kinodynamic）制約条件下で動作する輸送手段のリアルタイム経路計画を取り扱うランダム化適応型経路計画方法を提供する。本明細書で使用されるように、用語「輸送手段」は、実質的には、経路を計画することが望ましいあらゆるタイプのエンティティを含むように広く解釈されることが理解される。たとえば、エンティティには、潜水艦等の輸送手段に加えて、ネットワークで動作する移動ソフトウェアエージェントも含まれ得る。
【０００４】
一般に、本発明の方法は、初期の輸送手段のスタート位置からゴールロケーションへの１つ若しくは２つ以上の経路、又は、ゴールの方向の少なくとも１つの部分経路を生成する。旋回の回数又は長さ等の経路の特性は、ユーザが制約することができる。障害物を回避すること、又は、障害物を含む或る確率を有する領域と交差する確率を低くすることも、経路に対する制約を提供することができる。出力経路は、これらの制約条件を満たすものである。また、経路は、経路に沿った（回避される物体又は領域との）接触の確率に関する情報及び評価における信頼レベルも含むことができる。さらに、経路は、時間、速度、及び加速度の情報等も含むことができる。これらの情報は、関連した状態空間情報を提供することができる。
【０００５】
回避すべき領域に加えて、航行することが望ましい領域も考慮して経路を形成することができる。たとえば、或るロケーションに向かう途中の輸送手段は、新たなターゲットを通知される場合がある。輸送手段が自身の進路に沿って移動している時に、ターゲットの
攻撃を可能にする経路を選択することが望ましい場合がある。
【０００６】
輸送手段は、たとえば、センサの雑音及び不完全なカバレッジのために、自身の環境に関する確率情報しか有しない場合がある。確率情報を、戻る経路選択肢に沿った信頼レベル（場合によりこのような評価の理由を伴う）と組み合わせることにより、さまざまなファクタに基づいて好ましい経路を選択することができる。
【０００７】
動的で不確定な環境で確率モデルを使用して経路を見つけることにより、システムは、頻繁に変更する必要をなくすことができ、且つ、確率知識を用いたシミュレーションを組み込んでいない方法よりも安全にすることができる経路を提供することができる。決定論をランダム性と組み合わせることの利点は、この組み合わせによって、後に複雑な平滑化を必要としないより直線的でより直接的な経路を提供できると同時に、ランダム性の利点（局所極小の回避及びオーバーヘッドのほとんどないより包括的な探索）を含むことである。環境及び既存のツリー（木）構造体にランダム性の量を適応させると同時に、決定論をランダム性と共に使用することによって、効率的で、さらに、比較的厳しい環境においても複数の経路選択肢を一般に見つけることができるほど十分広範な探索木の生成が可能になる。
【０００８】
本発明は、添付図面と関連する以下の詳細な説明から、より十分に理解される。
発明の詳細な説明
本発明は、添付図面と関連する以下の詳細な説明から、より十分に理解される。
【０００９】
図１は、本発明による経路計画システム１０２を有する一例示の輸送手段１００を示している。この輸送手段１００は、他の輸送手段／物体１０、２０、３０を検出するためのレーダ／ソナー１０４システムを含むことができる。レーダ／ソナー１０４システムは、経路計画システム１０２に接続されている。１つの特定の実施の形態では、輸送手段１００は潜水艦であり、輸送手段／物体１０、２０、３０は、他の潜水艦、船舶、航行不能なエリア等に対応することができる。これら他の潜水艦等は、味方であるものとすることもできるし、敵であるものとすることもできる。一般に、輸送手段／物体１０、２０、３０には、輸送手段／物体を回避するように経路を計画する時に考慮することができる、速度、進行方向、加速度等の一定の属性を割り当てることができる。
【００１０】
主として経路計画システム１０２を物体及び輸送手段を検出するためのオンボードレーダ／ソナーシステムを有するものとして図示して説明するが、輸送手段／物体情報は、リモート（遠隔）のデバイス、輸送手段、衛星等から提供できることは理解される。これに加えて、経路計画システム１０２は、輸送手段から遠隔にあるものとすることもできることが理解される。たとえば、中央コマンドセンターが、輸送手段／物体情報を確認し、所与の輸送手段の進路を計画し、その所与の輸送手段に進路情報を提供することができる。輸送手段及び物体は、たとえば衛星が識別することができ、衛星は、この情報をコマンドセンター又は輸送手段に提供することができる。さらに、輸送手段及び物体には、友好的（味方）、非友好的（敵）、中立的等とすることができる多種多様な移動アイテム及び非移動アイテムが含まれ得る。
【００１１】
本発明の経路計画システム及び方法は、動的に変化する環境及び不確定な環境においてキノダイナミック制約条件下で動作する輸送手段のリアルタイム経路計画を、輸送手段の移動の確率的知識を用いて取り扱うためのランダム化適応型（ＲＡＤ）経路計画と呼ぶことができる。
【００１２】
本発明をさらに詳細に説明する前に、いくつかの要素及び定義を提供する。状態空間が定義される。輸送手段は、この状態空間を通る進路を定められることになる。輸送手段は
、一般に、状態空間の初期スタート位置に配置され、輸送手段が到達又は移動しようと試みている状態空間におけるゴール領域が特定される。ゴールロケーションは時間と共に変化する場合があることが理解される。輸送手段が回避すべき移動物体及び静止物体並びに移動領域及び静止領域が特定されて定義される。これらの物体及び領域の状態空間のロケーション又は存在は、確率的にしか知ることができない。輸送手段が回避したいが回避する必要がない移動物体及び静止物体又は移動領域及び静止領域も定義することができる。これに加えて、輸送手段の移動に対する制約条件及び出力経路に対する制約条件も定義することができる。
【００１３】
本発明の経路計画方法は、輸送手段の初期スタート状態からゴールへの１つ若しくは２つ以上の経路、又は、ゴールの方向における１つ若しくは２つ以上の部分経路を生成する。これらの経路は、ユーザ制約条件を組み込むことができ、経路に沿った（回避される物体又は領域との）接触の確率に関する情報及び評価における信頼レベルも含むことができる。また、経路は、状態空間情報も含むことができる。
【００１４】
経路を計画する際に、さまざまなコンポーネントを考慮することができる。状態空間にわたる確率分布の位相空間を、状態空間における障害物の動き及びロケーションの確率モデルと共に定義することができる。状態空間は、その要素が、対象となるシステムの考慮された状態を含む位相空間である。たとえば、移動障害物及び輸送手段を含む３次元（３Ｄ）環境を通る輸送手段の進路を定める場合に、その環境の関連した様相（aspect）を系とみなすことができる。簡単な一例として、各障害物の状態空間をその障害物のすべての可能なロケーションから成るように定義することができる。この空間は、（Ｒ，Ｔ）として定義することができる。ここで、Ｒは次のように与えられる。
【００１５】
【数１】
2007531110.tif 000003
【００１６】
ここで、Ｌｏｎは経度を表し、Ｌａｔは緯度を表し、Ａｌｔは高度を表す。Ｔは次のように与えられる。
【００１７】
【数２】
2007531110.tif 000004
【００１８】
状態空間（Ｒ，Ｔ）を、確率空間の積（product）として標準的な方法で定義された確率空間とみなすことができる。得られた積確率測度（product probability measure）は、Ｐ（Ｒ，Ｔ）と表記することができる。また、以下の表記をすべての障害物のすべての可能なロケーションから成る状態空間とみなすこともできる。
【００１９】
【数３】
2007531110.tif 000005
【００２０】
状態空間の他の可能な変数には、速度、移動方向、及び危険レベルが含まれる。
一例示の実施の形態では、確率分布は、状態空間における障害物に対応する。各障害物Ｏについて、次の確率密度関数が存在するものと仮定する。
【００２１】
【数４】
2007531110.tif 000006
【００２２】
この確率密度関数は、任意のボレル基底系（Borel basis set）Ｂ⊂（Ｒ，Ｔ）について、ＯがＢ内にある確率は、次のように与えられる確率密度関数である。
【００２３】
【数５】
2007531110.tif 000007
【００２４】
この関数φ０は、（Ｒ，Ｔ）上の確率測度μ０を誘導する。これを、障害物Ｏに対応する確率分布とみなすことができる。一般的な場合に、φ０の閉じた形の表現は存在しない場合があり、このような閉じた形の表現が存在することも必要でないことに留意すべきである。
【００２５】
一般に、確率分布間の距離を定義することができる。たとえば、｛μｎ｝が、（Ｒ，Ｔ）上の一連の確率分布（すなわち、確率測度）である場合に、ｄ（μｎ，μ）→０であり、あらゆる有界の次の可測関数であり、
【００２６】
【数６】
2007531110.tif 000008
【００２７】
そのときに限って、次のような確率分布間の距離ｄ（・，・）を定義することができる。
【００２８】
【数７】
2007531110.tif 000009
【００２９】
あらゆるボレル系Ｂ⊂（Ｒ，Ｔ）について次のような第２の条件を示すことができる。
【００３０】
【数８】
2007531110.tif 000010
【００３１】
このメトリックを定義することに関する追加の解説はD. Crisan及びA. Doucet著「A Survey of Convergence Results on Particle Filtering Methods for Practitioners」（IEEE Trans. On Signal Proc., p.741, Vol. 50, No. 3, March 2002）に含まれている。この文献は、参照により本明細書に援用される。
【００３２】
どの距離空間も位相空間でもあること、及び、メトリックに置かれた上記条件はいわゆる「弱位相」を誘導することに留意すべきである。このように、状態空間にわたる確率分布の位相空間が得られる。確率分布、すなわち確率測度は、単純には、一定の特性を有する関数であることに留意されたい。
【００３３】
進路を定められる輸送手段のロケーションに対応する確率分布も定義できることにさらに留意すべきである。いわゆる自己船舶（ownship）の最も可能性の高いロケーションと障害物の最も可能性の高いロケーションとの間の標準的なユークリッド距離と共に、自己船舶の確率分布と障害物の確率分布との間の距離を考慮することができる。直観的には、これは、２つの確率分布の重なり合う量に対応する。ユークリッド距離がたとえ十分長いとみなされても、これらの確率分布がかなり重なり合っている場合がある。
【００３４】
状態空間を通じた輸送手段の動きに対する制約条件を組み込んだ確率的な輸送手段の動きモデルを定義することができる。たとえば、潜水艦の旋回及び停止の能力は、比較的限られている。したがって、旋回は、比較的望ましくない場合がある。決定論的木拡張の候補経路を得るための一組のメカニズム又はルールを定義することができる。各段階におけるランダム性の量を求めて、ランダム拡張の候補節点を生成することができ、その段階についてランダム拡張が終了する時を判断することができる。ランダムツリー（木）拡張の候補経路を得るための一組のメカニズム又はルールも決定することができる。これに加えて、経路が実現可能であるかどうかを判断するために、経路は、或る程度の検査を受けるべきである。木拡張を中止する時を判断するためのメカニズムを定義することができ、さらに別のメカニズムは、経路の品質を評価することができる。別のメカニズムは、最終木から一組の経路選択肢を選択することができる。
【００３５】
図２Ａ〜図２Ｌは、本発明による時間の経過に伴う連続的な経路計画を示している。図２Ａにおいて、ターゲット輸送手段２００は、ゴールロケーション２０２への到達、及び、物体２０４ａ〜２０４ｆの回避が望ましい。ターゲット輸送手段２００は、たとえば潜水艦であり、物体２０４ａ〜２０４ｆは、たとえば潜水艦及び船舶である。ターゲット潜水艦２００は、初期ロケーションＲＮからスタートする。この初期ロケーションＲＮは、時刻（Time）Ｔ０における状態空間のルート節点として定義することができる。図２Ｂは、時刻Ｔ１に対応する。この図２Ｂでは、一連の枝Ｔ１Ｂ１、Ｔ１Ｂ２、Ｔ１Ｂ３が、ルート枝から伸び、各節点Ｔ１Ｎ１、Ｔ１Ｎ２、Ｔ１Ｎ３で終端している。物体２０４のいくつかは、その時刻Ｔ０（図２Ａ）における位置に対して移動していることが分かる。
【００３６】
連続的な経路計画図である図２Ａ〜図２Ｌは、本発明の理解を容易にすることを目的としていることは理解されよう。枝の長さは、距離と或る相関を有する場合があるが、これらの図は、一律の縮尺で描かれていないことが理解される。これに加えて、枝を拡張するためのルールを厳格に適用することなく本発明による経路計画を一般的に示すために、さまざまな節点から伸びる枝が示されている。すなわち、特定の節点からの枝が存在するかしないかに基づいて図から推理を行うべきでないことが理解されよう。これに加えて、実際の実施では、図２Ａ〜図２Ｌに示されるものよりもはるかに多くの枝が生成される可能性がある。
【００３７】
物体２０４は、確率分布に対応する濃淡領域によって囲まれたものとして示されている。この確率分布は、各物体の状態情報の一部を成すことができる。物体状態情報は、位置、進行方向、速度、加速度、旋回半径等を含むことができる。たとえば、潜水艦物体は、時刻Ｔ０において進行方向及び速度が判明している場合がある。この情報が与えられると、時刻Ｔ１、Ｔ２等の物体の位置について確率分布を定義することができる。この確率分布は、状態情報の信頼レベルを考慮することができる。たとえば、或る物体が、実際に、
判明している方向においてＴ０の進行方向で引用されたとすると、位置の信頼レベルは、時刻Ｔ１について相対的に高くなる。これに加えて、たとえば、潜水艦がコースを１８０度反転する確率は、かなり低いものとすることができる。これは、この確率を示すための濃淡に反映させることができる。さらに、潜水艦の旋回能力が限られていることも考慮することができる。当業者には、多種多様なパラメータを状態情報に考慮できることが理解されよう。
【００３８】
枝は、確率的ルール、ランダムルール、及び決定論的ルールを含むさまざまなルールに基づいて拡張させることができる。図２Ａ〜図２Ｌのこの例では、枝を拡張するための第１のルールは、決定論的であり、たとえば図２Ｃの枝Ｔ２Ｂ２のように、単純な方法で枝を生成することを含む。たとえば、ルート節点とゴールロケーションとの間に障害物が配置されていないとすると、経路は、ルート節点からゴールロケーションへ直線で伸びる。第２のルールも決定論的であり、ゴールロケーションを考慮しつつオープン空間に枝を拡張する。たとえば、図２Ｃでは、枝Ｔ２Ｎ１が、第２のルールに基づいて生成される。第３のルールは、ランダム性を利用し、ゴールロケーションも考慮しつつ、オープン空間に枝を生成する。
【００３９】
図２Ｃは、時刻Ｔ２に対応する。この図２Ｃでは、枝Ｔ２Ｂ１、Ｔ２Ｂ２、Ｔ２Ｂ３、Ｔ２Ｂ４が、時刻Ｔ１において生成された各節点Ｔ１Ｎ１、Ｔ１Ｎ２、Ｔ１Ｎ３から伸び、各節点Ｔ２Ｎ１、Ｔ２Ｎ２、Ｔ２Ｎ３、Ｔ２Ｎ４で終端する。Ｔ２の枝Ｔ２Ｂ１、Ｔ２Ｂ３、Ｔ２Ｂ４の生成は、第１のルール（単純枝）に基づいている。枝Ｔ２Ｂ２は、第２のルール（ゴールに向かう枝）に基づいている。物体２０４は、時刻Ｔ１以後、移動し続けていることに留意されたい。第１の物体２０４ａは、節点Ｔ２Ｎ３に侵入しつつあり、この経路がさらに伸びると干渉するおそれがある。
【００４０】
図２Ｄは、時刻Ｔ３に対応し、節点Ｔ２Ｎ１（図２Ｃ）からのあらゆる拡張の一時停止ＰＰ１及び節点Ｔ２Ｎ３からの１サイクルの同様の一時停止ＰＰ２を示している。これらの一時停止ＰＰ１、ＰＰ２は、１サイクルの間、ルート節点２００からの経路を一時停止することに対応する。輸送手段の経路を生成するとき、一時停止ＰＰ１、ＰＰ２は、その輸送手段が所定の期間停止することに対応することができる。このような一時停止によって、たとえば、移動物体を回避することができる。一時停止ＰＰ１、ＰＰ２は、それらの経路を可能な進路として削除するものではないことに留意されたい。
【００４１】
節点Ｔ３Ｎ１で終端するさらに別の枝Ｔ３Ｂ１、節点Ｔ３Ｎ２で終端するさらに別の枝Ｔ３Ｂ２、及び節点Ｔ３Ｎ３で終端するさらに別の枝Ｔ３Ｂ３が、時刻Ｔ３で生成される。枝Ｔ３Ｂ１、Ｔ３Ｂ２は第１のルールによって生成され、枝Ｔ３Ｂ３は第３のルールによって生成されることが分かる。
【００４２】
第１の決定論的ルール及び第２の決定論的ルール（単純ルート及びゴールに向かうルート）並びに第３のルールによって生成されたすべての枝が各節点から伸びるように見えるとは限らない場合があることが理解される。
【００４３】
一例示の実施の形態では、各枝がまず候補枝として生成されて検査される。一定の枝は、たとえば、物体との接触を開始するものとして実現不可能であることが判明する場合がある。他のルールは、候補枝を除去することができる。たとえば、或るルールは、重なり合った枝又は冗長な枝を排除することができる。このような重なり合いは、空間及び時間を指示し、空間だけを指示するわけではないことに留意されたい。これに加えて、枝は、空間で重なり合うが、空間／時間では重なり合わない可能性がある。候補枝を除去するための多種多様な追加ルールは、当業者に容易に理解できる。
【００４４】
図２Ｅ〜図２Ｌは、時刻Ｔ４〜Ｔ１０にわたる枝の連続した生成、及び、経時的な連続した物体２０４の移動を示している。経時的な変化をより明確に示すために、枝及び節点のラベル付けは制限されていることが理解される。図２Ｅにおいて、第１の一時停止ＰＰ１は、枝の生成が第２のサイクルの間停止していることを示す「２」で示されている。図から分かるように、２サイクルの一時停止ＰＰ１によって、第１の物体２０４ａを回避する経路が提供される。これとは対照的に、第２の一時停止ＰＰ２は、この場合も「１」、及び、時刻Ｔ２から、節点Ｔ２Ｎ３（図示せず）から伸びる枝Ｔ４Ｂ３で示されている。この枝Ｔ４Ｂ３の相対的に短い長さは、輸送手段２００（図示せず）が停止から加速しなければならず、したがって、相対的に短い距離を移動することを反映している。
【００４５】
図２Ｈにおいて、２つの経路は、第１の３角形Ｋ１及び第２の３角形Ｋ２によって示されるように終了している。第１の経路のキル（kill）Ｋ１は、第５の物体２０４ｅとの衝突が予測されていることに起因する。第２の経路のキルＫ２は、その経路が、ゴールロケーション２０２におそらく到達する際に遠回りになりすぎることに起因する。
【００４６】
多種多様な判定基準を使用して、特定の経路のさらなる生成を抹消できることが理解されよう。経路のさらなる生成を抹消するための例示の判定基準には、以下のものが含まれる。
１．一般に：拡張が実現可能でない場合、その枝は抹消される。
【００４７】
ａ．障害物に衝突することなく動きの制約条件を満たすことが不可能な場合がある。たとえば、必要な速度又は旋回半径が限度を越えている場合がある。
ｂ．輸送手段が空挺である場合、特定の作戦行動に必要なＧ力が大きすぎる場合がある。
２．センサ又は他の情報源から得られるさらなる情報が、接触がないと考えられていた枝が実際にはそうでないことを示す場合がある。既知の障害物のロケーションに関する新たな情報が明らかになる場合がある。また、障害物が追加されて発見される場合もある。
３．経路のコストメトリックが大きくなりすぎる場合がある。いくつかの例を以下に与える。
【００４８】
ａ．進んだ距離又は要した時間が大きくなりすぎる場合がある。
ｂ．旋回の回数又は他のタイプの方向変換の回数が多くなりすぎる場合がある。たとえば、輸送手段が空挺の場合、高度の変化の回数が多くなりすぎる場合がある。
【００４９】
いくつかの経路が或る物体を横切ることが明らかとなる場合があるが、輸送手段が進む経路の枝が時間内にその特定の物体の移動から変位するので、実際の衝突がなくなることが理解される。類似のものは、車が通過する前又は通過した後に人が通りを横断することである。
【００５０】
図２Ｋは、ルート節点２００からゴールロケーション２０２に到達する第１の進路Ｒ１、第２の進路Ｒ２を示している。図２Ｌは、第２の進路Ｒ２が第１の進路Ｒ１に優先することを示すために太線で示された第２の進路Ｒ２を示している。１つの特定の実施の形態では、各経路にわたる曲線の個数（１対４）に基づいて、第２の進路Ｒ２が第１の進路Ｒ１を上回って選択される。
【００５１】
複数の進路から１つの進路を選択することは、特定の用途のニーズに基づく所望の方法で重み付けすることができる広範囲のファクタに基づくことができることが理解される。たとえば、潜水艦の場合、潜水艦の限られた旋回能力のために、旋回の回数を重く重み付けすることができる。例示のファクタには、輸送手段のタイプ、速度、旋回能力、物体のロケーションの信頼性、直接的な経路の重要度、物体をどれだけの距離、回避したいかの
レベル等が含まれる。
【００５２】
確率及び信頼レベルの情報は、エッジ（edge）の初期実現可能性を判断する際、及び、複数の進路から１つの進路を選択する際の双方で使用することができる。一般に、障害物のロケーション／障害物の脅威レベルの確率的知識と、いわゆる自己船舶のコマンドに対する応答の知識との双方に関連した信頼レベル情報がある。
【００５３】
回避される領域と接触する確率の評価に信頼レベルを使用することができる。複数のセンサから敵のいくつかの可能なロケーションを得るものと仮定する。信頼レベルを使用できる１つの簡単な方法は、それら信頼レベルをコスト関数に直接使用することである。信頼レベルは、状況の一定の知識の表示として使用することができる。たとえば、不確定な状況を回避する進路が望ましい場合がある。一実施の形態では、システムは、各経路に沿って、輸送手段が特定の敵船舶から少なくとも所定の海里数である確率の経過を追跡する。
【００５４】
図３Ａ及び図３Ｂは、一例示の物体３５０のロケーションの例示の確率分布を示している。この一例示の物体３５０は、経路が生成される輸送手段３５２に関して敵船舶とみなすことができる。図３Ａでは、物体のロケーションの確率分布３５４が、比較的分散している。一実施の形態では、この確率分布は、比較的大きな標準偏差を有するガウス分布に対応する。図３Ｂでは、物体のロケーションの確率分布３５６が、比較的小さな標準偏差を有するガウス分布のようにより集中している。
例
Πを、状態空間Σにわたる確率分布の空間を示すものとする。輸送手段の現在位置からゴールへの経路又は経路の選択を決定するために、Πにおける特定のタイプの探索木Ｔが構築される。一般に、探索木Ｔの節点は、状態空間Πにおける点であり、Ｔにおけるエッジは、Πの曲線である。
【００５５】
木Ｔに節点を追加するプロセスは、木の拡張と呼ぶことができる。探索木Ｔの既存の節点ｎ及び確率分布空間の曲線αが与えられるものと仮定する。曲線αは、ｎのロケーションから開始する。次に、探索木Ｔは、曲線αの終点に節点ｎｐを配置して、曲線αを木空間Ｔに追加することにより、曲線αによって拡張される。この場合、節点ｎが拡張されたと言うこともできる。節点が拡張されない場合、その節点はデッドであるとみなされる。また、旋回又は曲線を追加することによっても木の拡張と言うことができる。
【００５６】
木は、輸送手段の初期位置にＴのルート節点を設定することによって、木Ｔを開始することにより構築することができる。図３の擬似コードは、木を構築するための一例示の実施態様を示している。参照される方法のコンポーネントは、停止、決定論的な木の拡張、及びランダムな木の拡張の所望のルールを定義することが理解される。
【００５７】
１つの特定の実施の形態は、本発明の理解を容易にするのに比較的簡単なものであるが、この実施の形態では、決定論的な木の拡張の候補経路の拡張は、２つの簡単なルールを介して得られる。これらのルールは、図４の各モデルコンポーネントの一部を成すことができる。
【００５８】
最初に、直線経路αが追加される。この追加は、輸送手段の進行方向及び速度が、αにおいて一定となり、且つ、αによって拡張される節点における進行方向及び速度と同一となるように行われる。αの長さは、後述のように決定される。この経路は、次に、旋回を追加することによって拡張される。この旋回の追加は、旋回の終了時に、輸送手段が、ゴールに直接向かうのにできるだけ近い進行方向となるように行われる。この旋回は、輸送手段旋回モデルを調べることによって得られる。一実施の形態では、本実施態様は、旋回
が円の弧であると仮定する簡単な旋回モデルを含む。この旋回モデルでは、円の半径は、旋回開始時の輸送手段の速度に依存する。
【００５９】
ランダム拡張の場合、ランダム性の量を求めることができ、一定の判定基準に従って変化させることができる。一実施の形態では、ランダム拡張がリーフ節点の一部に追加され、この場合、この一部はリーフ節点の個数の減少関数である。これらの節点はランダムに選択することができる。ランダム拡張をリーフ節点の一部に追加することができ、この場合、この一部は、たとえば、環境の危険性の増加関数である。これらの節点はランダムに選択される。すべてのリーフ節点にランダム拡張を追加することができる。節点に追加されるランダム拡張の個数は、その節点のローカル環境の危険性に依存する関数によって変化する可能性がある。節点に追加されるランダム拡張の個数は、リーフ節点の個数に依存する関数によって変化する可能性がある。一定数のランダム拡張を節点に追加することができる。
【００６０】
一実施の形態では、ランダム性の量を求めるために、上記最初の３つの条件の１つがいわゆるグローバルランダム性条件に選ばれる。これに加えて、最後の３つの条件の１つも、いわゆるローカルランダム性条件に選ばれる。
【００６１】
ランダム性の量を求める際に、追加パラメータも存在する可能性がある。ローカル試行回数パラメータ及びグローバル試行回数パラメータである。拡張を実行する際、所望の拡張は、時に実行可能でない場合がある。節点ｎがＲ回のランダム拡張によって拡張されるが、選ばれた拡張の一部は実現可能でないものと仮定する。ローカル試行回数パラメータは、Ｒ回のランダム拡張を達成するために許容されたランダム拡張の試みの回数の上限を与える。
【００６２】
グローバル試行回数パラメータについて、或るランダムな節点を拡張することを選んだ場合に、ローカル試行回数の後、その節点が全く拡張されない可能性がある。Ｎ個のランダムな節点を拡張したいが、選んだ節点の一部が、指定された試行回数後に拡張されないものと仮定する。グローバル試行回数パラメータは、Ｎ個の節点が拡張されるために許容された、追加節点を選ぶ試みの回数の上限を与える。
【００６３】
一例示の実施の形態では、グローバルランダム性条件、ローカルランダム性条件、並びにローカル試行回数パラメータ及びグローバル試行回数パラメータが、当業者に既知の方法でユーザ入力を介して決定される。
【００６４】
ランダムに拡張する場合、状態変数座標の一部のランダム変動を選び（それら座標に対する制約条件を満たしつつ）、且つ、それ以外を、拡張される節点のものと同一のままにすることによって、ランダムな経路を選ぶことができる。また、（制約条件に従う）ランダムな終点を選び、且つ、その点を終点として有し、拡張された節点をスタート点として有する経路を輸送手段動きモデルに求めることによっても、ランダムな経路を選ぶことができる。
【００６５】
エッジ長の仕様は、状態空間又は分布空間における特定のメトリックに依存する。一般に、エッジ長は、固定することもできるし、環境の危険性、タスク要件等に依存する関数によって決まるものとすることもできる。エッジ長は、経路の終点が確率実現可能性条件（probability feasibility condition）を満たす場合に、その経路全体がその条件を満たすように選ばれるべきである。
【００６６】
以下では、図４に示す方法コンポーネント６に含めることができるいくつかの例示の要素を解説する。新たな候補節点が実現可能であるかどうかを判断する際、その節点が、時
空間座標において、回避される領域に接触する確率を評価することができる。この確率が最大実現可能確率よりも小さい場合に、確率実現可能性関数は真を返す。最大実現可能確率は、次のもの、すなわち、環境の危険性尺度、輸送手段の移動において予測できる正確度、リーフ節点の現在の個数、許容可能な危険性の量、及び回避される領域のタイプの１つ又は２つ以上に依存する関数として定義することができる。
【００６７】
環境の危険性尺度は、用途に依存し、回避される障害物及び領域の特性による危険性の量を示す任意の尺度によって与えることができることが理解される。たとえば、環境の面積に対する進入禁止領域の面積の比がこのような尺度になり得る。ローカルな環境の危険性は、輸送手段を含む環境のサブセットに限定された環境の危険性とすることができる。考慮されるサブセットのさまざまな位相表現又は距離表現を使用することができる。一例のサブセットは、物理空間のうち、輸送手段の所与の距離内にある部分である。
【００６８】
さまざまなユーザ指定パラメータを使用できることが理解される。たとえば、図４で使用できる例示のユーザ指定制約条件を以下に解説する。当業者には、さらに別の制約条件が容易に理解できることに留意すべきである。
【００６９】
−付加的進入禁止距離：付加的進入禁止距離は、Ｒが、輸送手段が回避しなければならない領域である場合に、輸送手段が、Ｒのε近傍をＲに加えることによって得られる領域も回避しなければならないような距離である。
【００７０】
−最大輸送手段速度：輸送手段がどの状況下でも移動可能な最大速度。
−所望輸送手段速度範囲：輸送手段の速度は、異常な状況を除いてこの範囲内にあるべきである。
【００７１】
−停止フラグ：このフラグは、輸送手段が停止可能である場合に真（true）に設定され、そうでない場合に偽（false）に設定される。
−指定時間範囲内で許容された最大旋回数：輸送手段がユーザ指定時間の範囲内で行うことができるコース変更の最大回数。
【００７２】
−２つの旋回の終了と開始との間の最小距離。
木の拡張を中止するための、たとえば図４の方法要素７で使用できる実例のルールを以下に解説する。現在の実施態様では、ゴールへの経路が見つかった時、又は、最短部分経路における輸送手段移動時間が移動時間制限パラメータを超える場合に、木の拡張は停止する。他の可能性を以下に与える。
【００７３】
−ゴールへの経路が見つかった場合、又は、実現可能な経路を見つけることができないと判断された場合に木の拡張を自動的に停止する。
−経路発見アプリケーションが一定の時間の間実行された後、木の拡張を自動的に停止する。
【００７４】
−ゴールへの一定数の経路が見つかった後、又は、制限時間に達した後、木の拡張を停止する。
−構築プロセスの期間中に木を表示し、ユーザの要求を介して拡張を停止する。
【００７５】
本発明の別の態様では、例示の自動経路更新条件を以下に説明するように使用することができる。
−信頼レベルが与えられると、更新された状況知識を使用して、現在の経路が接触進入禁止領域（contact no go region）と交差する確率が、許容できないほど高いと判断された場合に、経路を自動的に更新する。
【００７６】
−最後の更新から一定時間が経過した場合に経路を自動的に更新する。
−可変時間ステップを使用して経路を自動的に更新する。この場合、接触のローカル密度が時間ステップのサイズを決定する。ローカル密度が高い場合には、短い時間ステップが使用され、ローカル密度が低い場合には、長い時間ステップが使用される。
【００７７】
本発明のランダム化適応型（ＲＡＤ）経路計画方法は、輸送手段の移動の確率的知識を用いて、動的に変化する環境及び不確定な環境においてキノダイナミック制約条件下で動作する輸送手段のリアルタイム経路計画を取り扱う。輸送手段の動き及び環境のインターフェースの適切な確率モデルにより、この方法は、広範囲の輸送手段のタイプ及び環境に適用可能である。
【００７８】
図５は、本発明によるランダム化適応型経路計画の一例示の実施態様を示している。以下の表記は、上記で使用された一定の用語を定義している。
Ｔ      構築される探索木。
【００７９】
＃ＳＮ  最初にルート節点に追加しようと試みるエッジの個数。これは入力パラメータである。
＃ＲＮ  所与の繰り返しでランダムに拡張する節点の最大数。これは入力パラメータである。
【００８０】
＃ＲＥ  ランダムに拡張される節点に追加しようと試みるランダム拡張の回数。これは入力パラメータである。
ＭＥＬ  最大許容エッジ長。これは入力パラメータである。
【００８１】
ｍＥＬ  最小許容エッジ長。これは入力パラメータである。
ＭＳｐ  最大許容速度。これは入力パラメータである。
ｍＳｐ  最小許容速度。これは入力パラメータである。
【００８２】
ＭＴｒ  許容された最大旋回数。これは入力パラメータである。
ＶＭＭ  輸送手段の動きモデル。
ＥＰＭ  確率的環境モデル。
【００８３】
ターンウェッジ（Turn Wedge）  現在の輸送手段の軌道及び状態が与えられると、ターンウェッジは、左への最大可能旋回及び右への最大可能旋回によって定義される。
停止フラグ  停止が可能な場合にＴＲＵＥ（真）に設定されるブールフラグ。
【００８４】
ＭＴｍ  進路の最大許容時間。
アクティブ節点  出力経路に含めることができるＴのあらゆる節点。
停止条件  木の構築が停止する時を決定する条件。
【００８５】
一般に、輸送手段の現在位置からゴールへの進路又は進路の選択を決定するために、まず、特定のタイプの探索木をΞ、Ｔ空間に構築する。ここで、Ξは、Ｎ次元空間的座標空間であり、Ｔは時間である。木のエッジは有向線分であり、節点は点である。木は、（ｘ０，ｔ０）にルートが置かれる。ここで、ｘ０は、現在時刻ｔ０における輸送手段の現在の空間位置である。たとえば、決定論的ルール及びランダム化拡張の組み合わせを使用して、この木に節点を追加することができる。探索木の構築の際に、環境の振る舞いの確率モデル及び輸送手段の動きのモデルを使用して、時間を前進させたシミュレーションが実行される。接触の確率が或る（パラメータ）しきい値未満であると判断されず、信頼レベルが別の（パラメータ）しきい値よりも大きい場合には、新たな候補節点は木に追加され
ない。これらのしきい値は、定数とすることもできるし、環境の関数として取り入れることもできる。たとえば、環境がかなりの量のオープン空間を含む場合、輸送手段をオープン空間のより大きなエリアに強制的に進めるために、定数しきい値の確率を低く設定することができる。追加されるエッジの長さは環境に依存し、この長さは、領域にわたって、且つ、時間と共に変化し得る。追加された端部節点（end node）が、接触チェックの確率によって実現可能であると判断された場合、そのエッジも、接触判定基準の確率の下で実現可能であるように、どのエッジ長も、（空間及び時間において）十分短くあるべきである。
【００８６】
確率モデルは空間及び時間にわたって連続であると仮定される。エッジ長は、速度変化だけでなく、進んだ距離の変化によっても変更することができる。一方、速度変化の回数及び変化量は、ユーザ入力によって制限することができる。輸送手段の動き制約条件に応じて、木のエッジを経路の最大直線線分よりも短くできる（一般的には短い）ことに留意すべきである。
【００８７】
節点追加の実現可能性を判断する際に、接触の確率ではなく、ユーザ定義の条件をチェックすることも可能である。たとえば、所与の時間又は距離にわたる最大許容旋回数、旋回間の最小時間又は最小距離、最大経路長、最大時間、又は最小速度及び最大速度が存在し得る。節点及びエッジを追加する際に、輸送手段モデルに照会するコマンドが与えられると、輸送手段モデルに照会して、追加されたエッジ及び節点が輸送手段の動き制約条件を満たすかどうか、及び、輸送手段がエッジに沿って実際に進む確率について判断することもできる。
【００８８】
エッジ及び節点を既存のリーフ節点に追加するためのいくつかの可能な決定論的ルールは、現在の速度で、ゴールに向けて直接的に（旋回が含まれ、速度は動きモデルによって決定される）、見つかった前の経路の最も近い節点に向けて、（実現可能性チェックによって可能である場合に）空間に単純に節点を追加するものである。また、ツリー（木）によって求められたボロノイ図の最大のボロノイ領域の節点にのみ、ゴールに向けて単純にエッジを追加することもできる。決定論的ルールは、必ずしもこれらに限定されないことが理解される。厳しい状況では、リーフ節点以外の節点にエッジを追加することを可能にすることが望ましい場合もある。（実現可能性制約条件に従って）追加されたランダムなエッジの個数は、既存の木のサイズ及び環境条件の組み合わせによって求めることができる。環境が危険である場合、より多くのランダムな節点を追加して、より多くの選択肢を考慮することができる。
【００８９】
少なくとも１つの経路が見つかるまでか、現在利用可能な知識を使用して現在の条件の下で実現可能な経路を見つけることができないと判断されるまでか、又は、他の「停止」条件が満たされるまで、木は拡張される。木が構築された後、ゴールへの「最良」の経路又は「最良」の部分経路のいずれかが見つけられる。一実施の形態では、メトリックの加重和である全体メトリックを使用して、「最良」な経路が決定される。このような実施態様では、全体メトリックに含めることができるサブメトリックは、１）経路長、２）経路時間、３）最も近い接触ポイント、４）最も近い接触の平均ポイント、５）最大接触確率、６）平均接触確率、７）コース変更数等である。
【００９０】
メトリックの選択は、これらのメトリックに限定されるものではなく、使用される特定のメトリックは、用途に依存する場合があり、ユーザ定義とされる場合があることが理解される。全体メトリックの重みも、用途に依存する場合があり、当業者に既知の方法でユーザ定義とすることができる。
【００９１】
木が一旦構築され、所望の経路がその木で見つかると、輸送手段は次にその進路に従う
。環境が動的で不確定な場合があるので、予期しない環境の変化のためにこの進路の更新が必要な場合がある。本発明の経路計画システムは、オプションの自動進路更新のための条件も含む。このシステムは、環境条件に基づいて木の構築を変更することができる。
【００９２】
一例示の実施の形態では、木データ構造体は、節点データ構造体の集合によって指定される。木の節点接続情報は、節点データ構造体に含まれる子ポインタ及び親ポインタによって与えられる。１つの特定の実施の形態では、節点データ構造体は次のものを含む。
【００９３】
−子節点へのポインタのリスト
−親節点へのポインタ
−デッド節点フラグ
−状態空間情報
−確率分布情報
−経路のコストのメトリックに関する変数
−ルート節点からの経路のコスト
−環境情報
−親エッジへのポインタ
ここで、木を有向グラフとみなすと、親節点は、所与の節点に入るエッジの開始部分の節点である。入るエッジは親エッジである。所与の節点の子節点は、その所与の節点を親として有するすべての節点から成る。デッド節点フラグは、その節点から続けることができるか否かを示すブール変数とすることができる。このデッドフラグが真に設定されている場合、節点の親をルート節点として有する部分木であって、その節点を含む部分木は、すべて抹消される。状態空間情報は用途に依存する。移動する輸送手段を含む用途において状態空間情報として使用できるいくつかの例示の変数には、速度、加速度、進行方向、地理的ロケーション（たとえば、経度、緯度、及び高度）、及び時間が含まれる。一般に、これらの変数は確率分布に関連付けられ、これらの変数の値は、関連した確率分布の手段によって与えられることに留意されたい。
【００９４】
一般に、確率分布情報は用途に依存する。移動する輸送手段（自己船舶）を含む用途における確率分布情報に含めることができる実例の体（フィールド：field）には、１）状態空間情報に含まれる変数の１つ又は２つ以上の同時分布又は独立分布のいずれか、及び、２）表された分布のそれぞれの９９％、９５％、…の信頼区間／領域が含まれる。これらは、分布から得ることもできるので、明示的に表される必要はないことに留意すべきである。
【００９５】
上述したように、信頼レベル情報は、分布から得ることができる。また、信頼区間は、確率分布に含まれる情報の一部であり、分布をトランケートするのに使用することができる。確率分布関数（ＰＤＦ）の積分（又は領域にわたる値の総和）は１の値を有する。領域が１次元的につながっている場合、Ｘ％の信頼区間は、その領域のつながったサブセットであり、その領域のサブセットにわたるＰＤＦの積分（又はその領域にわたる値の総和）は、Ｘの値を有する。領域が１次元でない場合、信頼領域という用語を使用することができる。信頼区間は、通常、平均を中心にするように取ることができる。
【００９６】
経路のコストのメトリックに関係する変数は、用途及びメトリックに依存する場合がある。回避しなければならない移動障害物を含む領域を移動する輸送手段（自己船舶）を含む用途においてメトリックとして使用できる例示の変数には、地理的長さ、移動時間、旋回数、最大旋回角、最接近ポイントの障害物への最小距離、最接近している障害物のロケーションの経路上での９９％信頼領域、及び、自己船舶のロケーションの経路上での９９％信頼領域の平均サイズが含まれる。
【００９７】
一実施の形態では、最接近ポイントは、経路Ｐ、Ｐに沿って移動する輸送手段Ｖ、及び移動障害物の集合｛Ｏ１，Ｏ２，…，Ｏｎ｝が与えられるものと仮定する。Ｄｉを、Ｐ上の距離（Ｖ，Ｏｉ）の最小値を示すものとし、Ｄｍｉｎ＝ｍｉｎ｛Ｄｉ：１≦Ｉ≦ｎ｝とする。この場合、Ｄｍｉｎが起こるＶのすべてのロケーションは、最接近ポイントであり、Ｄｍｉｎは、最接近ポイントの障害物への最小距離である。障害物Ｏｉは、Ｄｉ＝Ｄｍｉｎである場合、最接近ポイントを有する。
【００９８】
一実例の実施の形態では、いわゆる経路のコストを求めるのに使用されるメトリックは、用途に依存する。一例示のメトリックには、メトリック関連変数の正規化された値の加重和が含まれる。メトリック関連変数の例には、上述した変数（経路のコストのメトリックに関する変数）が含まれる。
【００９９】
メトリックの一例示の加重和では、メトリックで考慮する変数が｛Ｖ１，Ｖ２，…，Ｖｎ｝であると仮定する。｛Ｗ１，Ｗ２，…，Ｗｎ｝を非負の実数の集合とする。この場合、加重和メトリックは、（Ｗ１＊Ｖ１＋Ｗ２＊Ｖ２＋…＋Ｗｎ＊Ｖｎ）／（Ｗ１＋Ｗ２＋…＋Ｗｎ）によって与えられる。メトリックで考慮される変数のうちの一定の変数は、他の変数よりも重要な場合があり、したがって、より重く重み付けされる（たとえば、Ｗがより大きい）。
【０１００】
当業者には理解されるように、正規化された値をメトリックに使用することができる。異なる尺度単位又は異なるスケールを有する量を比較する場合、それらの値を共通の基準系に正規化することができる。たとえば、メトリックで使用する値を正規化する場合、すべての値が区間［０，１］にあるように正規化を行うことができる。これを行うために、考慮される最小値及び最大値を設定して、正規化された値＝値／（最大値−最小値）を求めることができる。この簡単なケースは、小さな値／大きな値と望ましい振る舞い／望ましくない振る舞いとの間の対応がすべての変数にわたって一定であると仮定していることに留意されたい。
【０１０１】
一実施の形態では、環境情報は用途に依存する。回避しなければならない移動障害物を含む領域を移動する輸送手段（自己船舶）を含む用途において環境情報に含めることができる例示のフィールドには、節点時刻（node time）（たとえば、状態空間情報に含まれる時刻）における障害物のロケーションの確率分布マップ、及び、結果として最接近ポイントとなる障害物の９９％信頼領域が含まれる。
【０１０２】
エッジは、必ずしも直線の線分に対応するとは限らず、より一般的な曲線の可能性があることに留意すべきである。たとえば、旋回は、エッジとみなすことができる。移動する輸送手段（自己船舶）を含む用途では、エッジは、通常、節点間を移動する際に、自己船舶の最も可能性の高いロケーションを指定する。
【０１０３】
一例示の実施の形態では、エッジの仕様は用途に依存する。旋回の特定の表現は、その用途に応じて異なる形態を取ることができる。移動する輸送手段（自己船舶）を含む用途のエッジの仕様に含めることができる例示のフィールドには、
−時間によってパラメータ化された曲線として、又は、幾何学的位置／時空間若しくは位置／時間／速度において区分的に直線の経路として与えられる曲線。
【０１０４】
−エッジ上での近似速度若しくは平均速度、又は、エッジ上での時間指定速度の関数。
−「信頼度」
が含まれる。
【０１０５】
当業者には理解されるように、既知のランダム化経路計画方法は、環境の状態にも既存
の探索木構造体にもランダム性の量を適応させない。また、それらの方法は、動的に変化する環境の確率的知識を組み込むシミュレーションを使用してリアルタイム計画も行わない。また、本発明の方法は、ランダム性と共に決定論的ルールを使用する点でも従来の方法と異なる。ここで、ランダム性の量は適応的である。
【０１０６】
図６は、本発明による経路計画を実施するための一例示の一連のステップを、上述した処理の詳細な内容と共に示している。ステップ５００において、ルート節点が、ゴールロケーションへ移動している輸送手段の初期状態に設定される。ステップ５０２において、停止条件が満たされているかどうかが判断される。満たされている場合には、これは通常、経路が少なくとも部分的に計画された後になるが、「最良」の経路がステップ５０４で見つけられる。満たされていない場合には、ステップ５０６において、たとえば、図７に示すような一組の決定論的ルールを使用して、木が決定論的に拡張される。ステップ５０８において、木が、図８に示すようなランダム拡張ルールで拡張される。ステップ５１０において、まだ処理されていない節点がさらに選ばれる。
【０１０７】
ステップ５１２において、節点が拡張されたかどうかが判断される。拡張されていない場合には、ステップ５１４において、節点はデッドであるとみなされ、ステップ５１６において、すべての節点が選ばれたかどうかが判断される。すべての節点が選ばれたわけではない場合、処理はステップ５１０において継続し、ステップ５１０において、さらに節点が選択される。すべての節点が選ばれた場合には、処理はステップ５０２において継続し、ステップ５０２において、停止条件が検査される。
【０１０８】
節点が拡張されたとステップ５１２で判断された場合には、ステップ５１８において、キル条件が満たされているかどうかが判断される。満たされている場合には、処理はステップ５１４において継続し、ステップ５１４において、節点はデッドに設定され、満たされていない場合には、処理はステップ５１６において継続する。
【０１０９】
図７は、本発明による決定論的木拡張のさらに詳細な内容を示している。ステップ６００において、まだ選ばれていないライブ節点が選択される。ステップ６０２において、所定のルールに従い、候補の経路拡張が決定論的に生成される。ステップ６０４において、１つの経路拡張が選択され、ステップ６０６において、その経路拡張が、回避又は航行する領域の予測された確率分布に関して実現可能であるかどうかが判断される。実現可能である場合、その拡張は、ステップ６０８で追加される。実現可能でない場合、ステップ６１０において、すべての経路が選ばれたかどうかが判断される。すべての経路が選ばれたわけでない場合には、処理はステップ６０４において継続し、ステップ６０４において、さらに節点が選択される。すべての経路が選ばれた場合には、ステップ６１２において、すべてのライブ節点が処理されたかどうかが判断される。処理された場合には、決定論的経路拡張は完了し、そうでない場合には、さらなる節点の処理がステップ６００において継続する。
【０１１０】
図８は、本発明によるランダム経路拡張のさらに詳細な内容を示している。ステップ７００において、ランダム拡張用の一組の節点が、ランダム性の所望の量を定義するルールに基づいて決定される。次に、ステップ７０２において、節点が選択され、ステップ７０４において、その節点の候補の経路拡張が、ランダム拡張ルールを使用して得られる。ステップ７０６において、まだ処理されていない経路拡張が選択され、ステップ７０８において、その拡張が、回避又は航行する領域の予測された確率分布を考慮して実現可能であるかどうかが判断される。実現可能である場合、ステップ７１０において、ランダム拡張が追加され、実現可能でない場合、ステップ７１２において、すべての経路が選択されたかどうかが判断される。すべての経路が選択されたわけではない場合、処理はステップ７０６において継続し、ステップ７０６において、さらに経路が選択され、すべての経路が
選択された場合、その組のすべての節点が選択されたかどうかが判断される。すべての節点が選択された場合、ランダム拡張は完了する。そうでない場合、処理はステップ７０２において継続し、ステップ７０２において、さらに節点が選択される。
【０１１１】
図９は、本発明による経路計画システム８００の一例示のアーキテクチャを示している。このシステムは、モニタ８０４と、キーボード等のユーザインターフェース８０６とを有するワークステーション８０２を含む。データベース８０８は、ワークステーションの外部とすることもできるし、内部とすることもできる。
【０１１２】
１つの特定の実施の形態では、ワークステーション８０２は、メモリ８１２に接続されたプロセッサ８１０を含む。オペレーティングシステム８１４が、当該技術分野で既知の方法でメモリ８１２と連動したプロセッサ８１０上で動作する。Ｗｉｎｄｏｗｓベースのシステム、Ｕｎｉｘベースのシステム、及びＬｉｎｕｘベースのシステムを含む任意の適切なオペレーティングシステムを使用することができる。さまざまなアプリケーションを、ワークステーションにおいてオペレーティングシステムの下で実行することができる。
【０１１３】
ワークステーション８０２は、本発明による輸送手段の経路計画を提供する一連のモジュールを含む。一例示の実施の形態が示されているが、本発明から逸脱することなく、多種多様のアーキテクチャを使用できることが理解される。これに加えて、ハードウェアモジュール及びソフトウェアモジュールと、デバイスとの間の区分けは、特定のアプリケーションのニーズを満たすために変化する可能性があることが、当業者には認識されよう。
【０１１４】
状態空間モジュール８１６は、状態空間を保持する。状態空間は、上記で詳細に説明した。一般に、状態空間モジュール８１６は、状態空間情報及び物体パラメータを利用し、他のモジュールと連動して、可能性のある経路を生成する。物体モジュール８１８は、経路が計画中である輸送手段を含めて、状態空間で特定された物体を管理する。たとえば、センサインターフェースモジュール８２０から更新されたセンサ情報を受信すると、物体モジュール８１８は、物体情報を更新する。
【０１１５】
ルールモジュール８２２は、さまざまな経路生成ルールを保持し、経路ジェネレータモジュール８２４は、上記で詳細に説明したように、それらルールに基づいて経路の枝を生成する。ルールモジュール８２２は、さまざまなルールを実施するさまざまなサブモジュール８２２ａ〜８２２Ｎを含むことができる。
【０１１６】
システムのさまざまなコンポーネントを分散できることが理解される。たとえば、新しいルール及び変更されたルールを中央ロケーションからダウンロードすることができる。同様に、センサを輸送手段のオンボードに配置することができ、且つ／又は、センサ情報をシステムに提供することができる。これに加えて、経路計画は、輸送手段から遠隔で生成することもでき、所与の経路を輸送手段に送信することができる。
【０１１７】
非友好的な敵国領海を通る進路を潜水艦に定めることに関連して本発明を主に図示して説明しているが、本発明は、一般に、ゴールロケーションへの経路を計画することが望ましい移動物体に適用可能であることが理解される。本発明の経路計画システムは、高レベルの柔軟性、実際の状況に対する高レベルの忠実度、及び情報の低損失をもたらす確率分布の空間を通る経路を考慮する。たとえば、非友好的な領海を通る進路を定めるためのいくつかの既知の用途に関して、この方法は、ターゲット追跡のためのベイズ法と共存でき、ベイズ法と共に使用することができる。一例示の実施の形態では、ベイズ法から得られた確率情報を経路発見及び出力される経路に組み込むことができる。これによって、確率情報のグラフィックスディスプレイへの表示が可能になり、その結果、ユーザは、危険確率を知った上で輸送手段を案内することができる。また、これによって、輸送手段の行路
の摂動を行うことも可能になる。
【０１１８】
さらに、本発明は、物理的な輸送手段の進路を定めることだけでなく、それ以外にも適用可能であることが理解される。たとえば、本発明の経路計画システムは、コンピュータネットワークが攻撃を受けて、或るレベルの情報フローを維持することが望ましい状況で使用することができる。この場合、一定のネットワークコンポーネントが危険にさらされていた確率、又は、或る時間枠内で危険にさらされる確率を推定することができる。これらは、回避される領域とみなすことができる。
【０１１９】
当業者には、上述した実施の形態に基づく本発明のさらなる特徴及び利点が理解されよう。したがって、本発明は、特許請求の範囲によって示されるものを除いて、特に図示して説明したものによって限定されるものではない。本明細書で引用されたすべての刊行物及び参考文献は、参照によりその全体が本明細書に明示的に援用される。
【図面の簡単な説明】
【０１２０】
【図１】本発明による経路計画システムを有する輸送手段の概略図である。
【図２Ａ】本発明による連続的な経路計画プロセスの絵画的表現である。
【図２Ｂ】本発明による連続的な経路計画プロセスの絵画的表現である。
【図２Ｃ】本発明による連続的な経路計画プロセスの絵画的表現である。
【図２Ｄ】本発明による連続的な経路計画プロセスの絵画的表現である。
【図２Ｅ】本発明による連続的な経路計画プロセスの絵画的表現である。
【図２Ｆ】本発明による連続的な経路計画プロセスの絵画的表現である。
【図２Ｇ】本発明による連続的な経路計画プロセスの絵画的表現である。
【図２Ｈ】本発明による連続的な経路計画プロセスの絵画的表現である。
【図２Ｉ】本発明による連続的な経路計画プロセスの絵画的表現である。
【図２Ｊ】本発明による連続的な経路計画プロセスの絵画的表現である。
【図２Ｋ】本発明による連続的な経路計画プロセスの絵画的表現である。
【図２Ｌ】本発明による連続的な経路計画プロセスの絵画的表現である。
【図３Ａ】本発明による経路計画の一部を成すことができる、物体の一例示のロケーション確率分布の絵画的表現である。
【図３Ｂ】本発明による経路計画の一部を成すことができる、物体のさらに別の例示のロケーション確率分布の絵画的表現である。
【図４】本発明による適応型経路計画の一例示の実施態様のテキスト表現である。
【図５】本発明による適応型経路計画のさらに別の例示の実施態様のテキスト表現である。
【図６】本発明による経路計画を実施するための一例示の一連のステップを示すフロー図である。
【図７】図６の決定論的木拡張のさらに詳細な内容を示すフロー図である。
【図８】図６のランダム木拡張のさらに詳細な内容を示すフロー図である。
【図９】本発明による経路計画システムの概略図である。
【図１】
2007531110.tif 000011
【図２Ａ】
2007531110.tif 000012
【図２Ｂ】
2007531110.tif 000013
【図２Ｃ】
2007531110.tif 000014
【図２Ｄ】
2007531110.tif 000015
【図２Ｅ】
2007531110.tif 000016
【図２Ｆ】
2007531110.tif 000017
【図２Ｇ】
2007531110.tif 000018
【図２Ｈ】
2007531110.tif 000019
【図２Ｉ】
2007531110.tif 000020
【図２Ｊ】
2007531110.tif 000021
【図２Ｋ】
2007531110.tif 000022
【図２Ｌ】
2007531110.tif 000023
【図３Ａ】
2007531110.tif 000024
【図３Ｂ】
2007531110.tif 000025
【図４】
2007531110.tif 000026
【図５】
2007531110.tif 000027
【図６】
2007531110.tif 000028
【図７】
2007531110.tif 000029
【図８】
2007531110.tif 000030
【図９】
2007531110.tif 000031
【国際調査報告】
2007531110.tif 000032
2007531110.tif 000033