(57)【要約】  本開示は、時空間マップに基づく、航走体のための表面航行のためのシステムおよび方法に関する。本方法は、第1の領域の時空間マップを決定するステップを含む。時空間マップは、複数の時空間グリッドを含み得る。各時空間グリッドは、時空間グリッドに対応する時間的情報および地理的情報を含み得る。本方法はまた、第1の時間期間に対応する1つ以上の障害物のそれぞれの障害物ステータスを取得するステップを含む。本方法はまた、障害物ステータスに基づいて、複数の時空間グリッドのうちの複数の航行可能グリッドおよび複数の航行不可能グリッドを決定するステップを含む。本方法は、複数の航行可能グリッドに基づいて、航走体のための経路を決定するステップをさらに含む。
2021513124.tif 000002
【特許請求の範囲】
【請求項１】
時空間マップに基づく、航走体のための表面航行のためのコンピューティングデバイス上で実施される方法であって、前記コンピューティングデバイスは、メモリと、複数のプロセッサと、を備え、前記方法は、
第1の領域の時空間マップを決定するステップであって、前記時空間マップは、複数の時空間グリッドを含み、各時空間グリッドは、前記時空間グリッドに対応する時間的情報および地理的情報を含む、ステップと、
第1の時間期間に対応する1つ以上の障害物のそれぞれの障害物ステータスを取得するステップと、
前記障害物ステータスに基づいて、前記複数の時空間グリッドのうちの複数の航行可能グリッドおよび複数の航行不可能グリッドを決定するステップと、
前記複数の航行可能グリッドに基づいて、前記航走体のための経路を決定するステップと、
を含む、方法。
【請求項２】
前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定するステップは、
前記障害物ステータスに基づいて、前記1つ以上の障害物のそれぞれについて障害物体積を決定するステップと、
前記1つ以上の障害物の前記障害物体積に基づいて、前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定するステップと、
をさらに含む、請求項1に記載の方法。
【請求項３】
前記方法は、
前記第1の時間期間に対応する前記障害物体積に基づいて、前記1つ以上の障害物のそれぞれの障害物軌道投影を決定するステップと、
前記1つ以上の障害物の前記障害物軌道投影に基づいて、前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定するステップと、
をさらに含む、請求項2に記載の方法。
【請求項４】
前記障害物体積は、前記障害物の輪郭に基づいて決定される、請求項2または3に記載の方法。
【請求項５】
前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定するステップは、
前記障害物ステータスに基づいて、前記1つ以上の障害物のそれぞれに関連するファジィ集合を決定するステップと、
前記ファジィ集合に基づいて、前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定するステップと、
をさらに含む、請求項1から4のいずれか一項に記載の方法。
【請求項６】
前記ファジィ集合を決定するステップは、
第1の基準に基づいて、前記障害物に関連する航行不可能領域を決定するステップと、
前記航行不可能領域に基づいて、前記ファジィ集合を決定するステップと、
をさらに含む、請求項5に記載の方法。
【請求項７】
前記方法は、
前記航走体の目的地を決定するステップと、
前記複数の航行可能グリッドの少なくとも一部について、2つの隣接する航行可能グリッド間のコスト関数を決定するステップと、
前記航走体の現在のグリッドと前記航走体の前記目的地との間のヒューリスティック関数を決定するステップと、
前記航走体の前記目的地、複数のコスト関数、および前記ヒューリスティック関数に基づいて、前記航走体のための前記経路を決定するステップと、
をさらに含む、請求項1から6のいずれか一項に記載の方法。
【請求項８】
前記コスト関数は、前記2つの隣接する航行可能グリッドの時間的情報および地理的情報に基づいて決定される、請求項7に記載の方法。
【請求項９】
前記ヒューリスティック関数は、前記航走体の前記現在のグリッドおよび前記航走体の前記目的地の時間的情報および地理的情報に基づいて決定される、請求項7または8に記載の方法。
【請求項１０】
時空間マップに基づく、航走体のための表面航行のためのシステムであって、
命令のセットを含む少なくとも1つの非一時的記憶媒体と、
前記少なくとも1つの非一時的記憶媒体と通信する少なくとも1つのプロセッサであって、前記命令のセットを実行するとき、前記少なくとも1つのプロセッサは、
第1の領域の時空間マップを決定し、前記時空間マップは複数の時空間グリッドを含み、各時空間グリッドは、前記時空間グリッドに対応する時間的情報および地理的情報を含み、
第1の時間期間に対応する1つ以上の障害物のそれぞれの障害物ステータスを取得し、
前記障害物ステータスに基づいて、前記複数の時空間グリッドのうちの複数の航行可能グリッドおよび複数の航行不可能グリッドを決定し、
前記複数の航行可能グリッドに基づいて、前記航走体のための経路を決定する、
ように指示される、少なくとも1つのプロセッサと、
を備える、システム。
【請求項１１】
前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定することは、
前記障害物ステータスに基づいて、前記1つ以上の障害物のそれぞれについて障害物体積を決定することと、
前記1つ以上の障害物の前記障害物体積に基づいて、前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定することと、
をさらに含む、請求項10に記載のシステム。
【請求項１２】
前記システムは、
前記第1の時間期間に対応する前記障害物体積に基づいて、前記1つ以上の障害物のそれぞれの障害物軌道投影を決定し、
前記1つ以上の障害物の前記障害物軌道投影に基づいて、前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定する、
ようにさらに構成される、請求項11に記載のシステム。
【請求項１３】
前記障害物体積は、前記障害物の輪郭に基づいて決定される、請求項11または12に記載のシステム。
【請求項１４】
前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定することは、
前記障害物ステータスに基づいて、前記1つ以上の障害物のそれぞれに関連するファジィ集合を決定することと、
前記ファジィ集合に基づいて、前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定することと、
をさらに含む、請求項10から13のいずれか一項に記載のシステム。
【請求項１５】
前記ファジィ集合を決定することは、
第1の基準に基づいて、前記障害物に関連する航行不可能領域を決定することと、
前記航行不可能領域に基づいて、前記ファジィ集合を決定することと、
をさらに含む、請求項14に記載のシステム。
【請求項１６】
前記システムは、
前記航走体の目的地を決定し、
前記複数の航行可能グリッドの少なくとも一部について、2つの隣接する航行可能グリッド間のコスト関数を決定し、
前記航走体の現在のグリッドと前記航走体の前記目的地との間のヒューリスティック関数を決定し、
前記航走体の前記目的地、複数のコスト関数、および前記ヒューリスティック関数に基づいて、前記航走体のための前記経路を決定する、
ようにさらに構成される、請求項10から15のいずれか一項に記載のシステム。
【請求項１７】
前記コスト関数は、前記2つの隣接する航行可能グリッドの時間的情報および地理的情報に基づいて決定される、請求項16に記載のシステム。
【請求項１８】
前記ヒューリスティック関数は、前記航走体の前記現在のグリッドおよび前記航走体の前記目的地の時間的情報および地理的情報に基づいて決定される、請求項16または17に記載のシステム。
【請求項１９】
実行可能命令を含む非一時的コンピュータ可読媒体であって、前記実行可能命令は、少なくとも1つのプロセッサによって実行されると、前記少なくとも1つのプロセッサに、
第1の領域の時空間マップを決定するステップであって、前記時空間マップは、複数の時空間グリッドを含み、各時空間グリッドは、前記時空間グリッドに対応する時間的情報および地理的情報を含む、ステップと、
第1の時間期間に対応する1つ以上の障害物のそれぞれの障害物ステータスを取得するステップと、
前記障害物ステータスに基づいて、前記複数の時空間グリッドのうちの複数の航行可能グリッドおよび複数の航行不可能グリッドを決定するステップと、
前記複数の航行可能グリッドに基づいて、前記航走体のための経路を決定するステップと、
を含む、方法を実行させる、非一時的コンピュータ可読媒体。
【請求項２０】
前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定するステップは、
前記障害物ステータスに基づいて、前記1つ以上の障害物のそれぞれについて障害物体積を決定するステップと、
前記1つ以上の障害物の前記障害物体積に基づいて、前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定するステップと、
をさらに含む、請求項19に記載の非一時的コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、2018年12月27日に出願された中国特許出願第201811615760．8号の優先権を主張するものであり、その内容は、参照により本明細書に組み込まれる。
【０００２】
本開示は、一般に、自動航行技術のためのシステムおよび方法に関し、より詳細には、自動航行システムにおける経路決定のためのシステムおよび方法に関する。
【背景技術】
【０００３】
無人航走体の局所的障害物回避のための既存の方法は、単一の障害物、例えばvelocity obstaclesアルゴリズム、人工ポテンシャル場アルゴリズムに主に焦点を合わせている。しかしながら、複雑で不規則な動的環境では、無人航走体の自動航行システムは、複数の障害物の状態、および海上における衝突の予防のため国際規則に関する条約（COLREGs）や無人航走体の操縦性能などの複数の制約を考慮していないため、これらの方法を使用してリアルタイムで経路を計画することが困難であり得る。したがって、自動航行システムにおいて無人航走体のための最適経路を決定するための方法およびシステムを提供することが望ましい。
【発明の概要】
【課題を解決するための手段】
【０００４】
本開示の一態様によれば、時空間マップに基づく、航走体のための表面航行のためのコンピューティングデバイス上で実施される方法が提供される。コンピューティングデバイスは、メモリと複数のプロセッサとを備え得る。本方法は、第1の領域の時空間マップを決定するステップを含み得る。時空間マップは、複数の時空間グリッドを含み得る。各時空間グリッドは、時空間グリッドに対応する時間的情報および地理的情報を含み得る。本方法はまた、第1の時間期間に対応する1つ以上の障害物のそれぞれの障害物ステータスを取得するステップを含み得る。本方法は、障害物ステータスに基づいて、複数の時空間グリッドのうちの複数の航行可能グリッドおよび複数の航行不可能グリッドを決定するステップをさらに含み得る。本方法は、複数の航行可能グリッドに基づいて、航走体のための経路を決定するステップをまたさらに含み得る。
【０００５】
一部の実施形態では、本方法はまた、障害物ステータスに基づいて、1つ以上の障害物のそれぞれについて障害物体積を決定するステップを含み得る。本方法は、1つ以上の障害物の障害物体積に基づいて、複数の航行可能グリッドおよび複数の航行不可能グリッドを決定するステップをさらに含み得る。
【０００６】
一部の実施形態では、本方法はまた、時間期間に対応する障害物体積に基づいて、1つ以上の障害物のそれぞれの障害物軌道投影を決定するステップを含み得る。本方法は、1つ以上の障害物の障害物軌道投影に基づいて、複数の航行可能グリッドおよび複数の航行不可能グリッドを決定するステップをさらに含み得る。
【０００７】
一部の実施形態では、障害物体積は、障害物の輪郭に基づいて決定され得る。
【０００８】
一部の実施形態では、本方法はまた、障害物ステータスに基づいて、1つ以上の障害物のそれぞれに関連するファジィ集合を決定するステップを含み得る。本方法は、ファジィ集合に基づいて、複数の航行可能グリッドおよび複数の航行不可能グリッドを決定するステップをさらに含み得る。
【０００９】
一部の実施形態では、本方法はまた、第1の基準に基づいて、障害物に関連する航行不可能領域を決定するステップを含み得る。本方法は、航行不可能領域に基づいて、ファジィ集合を決定するステップをさらに含み得る。
【００１０】
一部の実施形態では、本方法はまた、航走体の目的地を決定するステップを含み得る。複数の航行可能グリッドの少なくとも一部について、本方法は、2つの隣接する航行可能グリッド間のコスト関数を決定するステップをさらに含み得る。本方法は、航走体の現在のグリッドと航走体の目的地との間のヒューリスティック関数を決定するステップをさらに含み得る。本方法は、航走体の目的地、複数のコスト関数、およびヒューリスティック関数に基づいて、航走体のための経路を決定するステップをさらに含み得る。
【００１１】
一部の実施形態では、コスト関数は、2つの隣接する航行可能グリッドの時間的情報および地理的情報に基づいて決定され得る。
【００１２】
一部の実施形態では、ヒューリスティック関数は、航走体の現在のグリッドおよび航走体の目的地の時間的情報および地理的情報に基づいて決定され得る。
【００１３】
本開示の別の態様によれば、時空間マップに基づく、航走体のための表面航行のためのシステムは、命令のセットを含む少なくとも1つの非一時的記憶媒体と、少なくとも1つの非一時的記憶媒体と通信する少なくとも1つのプロセッサと、を備え得る。命令のセットを実行するとき、少なくとも1つのプロセッサは、第1の領域の時空間マップを決定するように指示され、時空間マップは複数の時空間グリッドを含み、各時空間グリッドは、時空間グリッドに対応する時間的情報および地理的情報を含み得る。少なくとも1つのプロセッサはまた、第1の時間期間に対応する1つ以上の障害物のそれぞれの障害物ステータスを取得するように指示され得る。少なくとも1つのプロセッサはまた、障害物ステータスに基づいて、複数の時空間グリッドのうちの複数の航行可能グリッドおよび複数の航行不可能グリッドを決定するように指示され得る。少なくとも1つのプロセッサは、複数の航行可能グリッドに基づいて、航走体のための経路を決定するようにさらに指示され得る。
【００１４】
本開示のさらに別の態様によれば、非一時的コンピュータ可読媒体は、実行可能命令を含み、実行可能命令は、少なくとも1つのプロセッサによって実行されると、少なくとも1つのプロセッサに方法を実行させ得る。本方法は、第1の領域の時空間マップを決定するステップを含み得る。時空間マップは、複数の時空間グリッドを含み得る。各時空間グリッドは、時空間グリッドに対応する時間的情報および地理的情報を含み得る。本方法はまた、第1の時間期間に対応する1つ以上の障害物のそれぞれの障害物ステータスを取得するステップを含み得る。本方法はまた、障害物ステータスに基づいて、複数の時空間グリッドのうちの複数の航行可能グリッドおよび複数の航行不可能グリッドを決定するステップを含み得る。本方法はまた、複数の航行可能グリッドに基づいて、航走体のための経路を決定するステップを含み得る。
【００１５】
さらなる特徴が、一部は以下の説明で説明され、また一部は以下および添付の図面を検討することにより当業者に明らかになる、または各例の製造または動作によって把握され得る。本開示の特徴は、以下に論じられる詳細な例に示される方法論、手段、および組み合わせの様々な態様の実践または使用によって実現および達成され得る。
【００１６】
本開示は、例示的な実施形態に関してさらに説明される。これらの例示的な実施形態は、図面を参照して詳細に説明される。これらの実施形態は、非限定的な例示的な実施形態であり、図面中のいくつかの図を通して、同様の参照番号は同様の構造を表す。
【図面の簡単な説明】
【００１７】
【図１】本開示の一部の実施形態による航走体に関連する例示的な自動航行システムを示す概略図である。
【図２】本開示の一部の実施形態による、例示的なコンピューティングデバイスの例示的なハードウェアおよび／またはソフトウェアのコンポーネントを示す概略図である。
【図３】本開示の一部の実施形態による例示的な処理エンジンを示すブロック図である。
【図４】本開示の一部の実施形態による例示的な時空間マップを示す概略図である。
【図５Ａ】本開示の一部の実施形態による三次元空間をグリッド化するための例示的なプロセスを示す概略図である。
【図５Ｂ】本開示の一部の実施形態によるX−Y平面上の障害物の例示的な境界ボックスを示す概略図である。
【図６Ａ】本開示の一部の実施形態による、障害物の運動領域に関連する例示的なメンバーシップ関数を示す概略図である。
【図６Ｂ】本開示の一部の実施形態による、障害物の運動領域に関連するメンバーシップ関数の例示的な等高線を示す概略図である。
【図７】本開示の一部の実施形態による、時空間マップに基づいて、航走体のための経路を決定するための例示的なプロセスを示すフローチャートである。
【発明を実施するための形態】
【００１８】
以下の説明は、当業者が本開示を製造および使用することを可能にするために提示され、特定の用途およびその要件の文脈において提供される。開示された実施形態に対する様々な修正は当業者には容易に明らかとなるはずであり、そして本明細書に定義された一般原理は、本開示の趣旨および範囲から逸脱することなく他の実施形態および応用に適用され得る。よって、本開示は、示されている実施形態に限定されず、特許請求の範囲と一致する最も広い範囲を認められるべきである。
【００１９】
本明細書で使用される用語は、特定の例示的な実施形態を説明する目的のためだけのものであり、限定することを意図するものではない。本明細書で使用されるとき、単数形「a」、「an」、および「the」は、文脈上、明らかに他の意味を示しているのでない限り、複数形も含むことが意図され得る。本明細書で使用されるとき、「備える（comprise）」、「備える（comprises）」、および／または「備える（comprising）」、「含む（include）」、「含む（includes）」、および／または「含む（including）」という用語は、述べられた特徴、整数、ステップ、動作、要素、および／または構成要素の存在を指定するが、1つ以上の他の特徴、整数、ステップ、動作、要素、構成要素、および／またはそれらのグループの存在または追加を排除するものではないことをさらに理解されたい。
【００２０】
本開示のこれらおよび他の特徴ならびに特性と、動作方法ならびに構造の関連する要素および部品の組み合わせの機能と、製造の経済性とは、本開示の一部をいずれも形成する添付の図面を参照して以下の説明を検討すれば、より明らかになり得る。しかしながら、図面は、例示および説明のみを目的としており、本開示の範囲を限定することを意図していないことを明確に理解されたい。図面は原寸に比例していないことを理解されたい。
【００２１】
本開示で使用されるフローチャートは、本開示の一部の実施形態による、システムが実施する動作を示している。フローチャートの動作は順不同で実施されてもよいことを明確に理解されたい。逆に、動作は逆の順序で、または同時に実施されてもよい。さらに、1つ以上の他の動作がフローチャートに追加されてもよい。1つ以上の動作が、フローチャートから削除されてもよい。
【００２２】
本開示で使用される測位技法は、全地球測位システム（GPS）、全地球航法衛星システム（GLONASS）、コンパス航法システム（COMPASS）、ガリレオ測位システム、準天頂衛星システム（QZSS）、ワイヤレスフィデリティ（Wi−Fi）（登録商標）測位技法など、またはそれらの任意の組み合わせに基づき得る。本開示では、上記の測位システムのうちの1つ以上を交換可能に使用することができる。
【００２３】
さらに、本開示において開示されるシステムおよび方法は、航走体の経路を決定することに関して主に説明されているが、これは1つの例示的な実施形態に過ぎないことを理解されたい。本開示のシステムまたは方法は、任意の他の種類の航行システムにも適用され得る。例えば、本開示のシステムまたは方法は、陸上、海上、航空宇宙など、またはそれらの任意の組み合わせを含む、異なる環境の輸送システムに適用することができる。輸送システムの航走体は、タクシー、自家用車、ヒッチ（hitch）、バス、列車、超特急列車、高速鉄道、地下鉄、船、航空機、宇宙船、熱気球、無人運転車など、またはそれらの任意の組み合わせを含み得る。
【００２４】
本開示で使用される測位技法は、全地球測位システム（GPS）、全地球航法衛星システム（GLONASS）、コンパス航法システム（COMPASS）、ガリレオ測位システム、準天頂衛星システム（QZSS）、ワイヤレスフィデリティ（Wi−Fi）（登録商標）測位技法など、またはそれらの任意の組み合わせに基づき得る。本開示では、上記の測位システムのうちの1つ以上を交換可能に使用することができる。
【００２５】
図1は、本開示の一部の実施形態による航走体に関連する例示的な自動航行システム100を示す概略図である。一部の実施形態では、自動航行システム100は、サーバ110と、ネットワーク120と、航走体130と、記憶装置140と、を備え得る。
【００２６】
一部の実施形態では、サーバ110は、単一のサーバであってもサーバグループであってもよい。サーバグループは、集中型であっても分散型であってもよい（例えば、サーバ110は、分散型システムであってもよい）。一部の実施形態では、サーバ110はローカルであってもリモートであってもよい。例えば、サーバ110は、ネットワーク120を介して、航走体130および／または記憶装置140に記憶されている情報および／またはデータにアクセスすることができる。別の例として、サーバ110は、記憶された情報および／またはデータにアクセスするために、航走体130および／または記憶装置140に直接接続されてもよい。一部の実施形態では、サーバ110は、クラウドプラットフォームまたは車載コンピュータ上に実装され得る。ほんの一例として、クラウドプラットフォームは、プライベートクラウド、パブリッククラウド、ハイブリッドクラウド、コミュニティクラウド、分散型クラウド、インタークラウド、マルチクラウドなど、またはそれらの任意の組み合わせを含むことができる。一部の実施形態では、サーバ110は、本開示において図2に示される1つ以上の構成要素を有するコンピューティングデバイス200上に実装され得る。
【００２７】
一部の実施形態では、サーバ110は、処理エンジン112を備え得る。処理エンジン112は、本開示で説明されている1つ以上の機能を実行するために運転情報および／または航走体130の状態に関連する情報および／またはデータを処理することができる。一部の実施形態では、処理エンジン112は、1つ以上の処理エンジン（例えば、シングルコア処理エンジン（複数可）またはマルチコアプロセッサ（複数可））を備え得る。ほんの一例として、処理エンジン112は、中央処理装置（CPU）、特定用途向け集積回路（ASIC）、特定用途向け命令セットプロセッサ（ASIP）、グラフィック処理装置（GPU）、物理処理ユニット（PPU）、デジタルシグナルプロセッサ（DSP）、フィールドプログラマブルゲートアレイ（FPGA）、プログラマブルロジックデバイス（PLD）、コントローラ、マイクロコントローラユニット、縮小命令セットコンピュータ（RISC）、マイクロプロセッサなど、またはそれらの任意の組み合わせを含むことができる。
【００２８】
一部の実施形態では、サーバ110は、自動航行システム100の1つ以上の構成要素（例えば、航走体130、記憶装置140）と通信するために、ネットワーク120に接続され得る。一部の実施形態では、サーバ110は、自動航行システム100の1つ以上の構成要素（例えば、航走体130、記憶装置140）と通信するために、ネットワーク120に直接接続され得る、またはこれと直接通信し得る。一部の実施形態では、サーバ110は航走体130に統合され得る。
【００２９】
ネットワーク120は、情報および／またはデータの交換を助けることができる。一部の実施形態では、自動航行システム100の1つ以上の構成要素（例えば、サーバ110、航走体130、または記憶装置140）は、ネットワーク120を介して、自動航行システム100内の他の構成要素（複数可）に情報および／またはデータを送信し得る。一部の実施形態では、ネットワーク120は、任意の種類の有線もしくは無線ネットワーク、またはそれらの組み合わせとすることができる。ほんの一例として、ネットワーク120は、ケーブルネットワーク、有線ネットワーク、光ファイバネットワーク、電気通信ネットワーク、イントラネット、インターネット、ローカルエリアネットワーク（LAN）、広域ネットワーク（WAN）、ワイヤレスローカルエリアネットワーク（WLAN）、メトロポリタンエリアネットワーク（MAN）、広域ネットワーク（WAN）、公衆電話交換網（PSTN）、Bluetooth（登録商標）ネットワーク、ZigBee（登録商標）ネットワーク、近距離無線通信（NFC）ネットワークなど、またはそれらの任意の組み合わせを含むことができる。一部の実施形態では、ネットワーク120は、1つ以上のネットワークアクセスポイントを含み得る。例えば、ネットワーク120は、有線または無線ネットワークアクセスポイントを含むことができ、それを介して、データおよび／または情報を交換するために、自動航行システム100の1つ以上の構成要素をネットワーク120に接続することができる。
【００３０】
航走体130は、任意の種類の自律型航走体であり得る。自律型航走体は、その環境を検知し、人間の操縦なしに航行することが可能であり得る。一部の実施形態では、航走体130は、無人水上航走体（USV）であり得る。航走体130は、従来の船の構造、例えば、船体（例えば、船首、キール、船尾）、推進システム（例えば、プロペラを回すモータもしくはエンジン、インペラ、または波浪推進フィン）、操舵システム（例えば、舵）などを備え得る。推進システムは、航走体130の移動速度を制御するように構成され得る。操舵システムは、航走体130の方位および／または方向を調整するように構成され得る。推進システムおよび／または操舵システムは、それらの機能を実施するための機構の任意の組み合わせを含み得る。
【００３１】
航走体130はまた、航走体130に関連する航海情報を検出するように構成された複数の検出ユニットを備え得る。複数の検出ユニットは、カメラ、全地球測位システム（GPS）モジュール、加速度センサ（例えば、圧電センサ）、速度センサ（例えば、ホールセンサ）、距離センサ（例えば、レーダ、LIDAR、赤外線センサ）などを含み得る。
【００３２】
例えば、距離センサ（例えば、レーダ、LiDAR、赤外線センサ）は、航走体130と他の物体（例えば、静止障害物、運動障害物、別の航走体）との間の距離を測定することができる。速度センサ（例えば、ホール効果センサ）は、航走体130の速度（例えば、瞬間速度、平均速度）を測定することができる。加速度センサ（例えば、加速度計）は、航走体130の加速度（例えば、瞬間加速度、平均加速度）を測定することができる。
【００３３】
一部の実施形態では、複数の検出ユニットは、航走体130の周囲の環境を検知し得る。例えば、1つ以上の検出ユニットが、航走体130の周囲の障害物（例えば、静止障害物、運動障害物）を検出し得る。静止障害物は、島、礁など、またはそれらの任意の組み合わせを含み得る。運動障害物は、動いている船、動物など、またはそれらの任意の組み合わせを含むことができる。
【００３４】
記憶装置140は、データおよび／または命令を記憶することができる。一部の実施形態では、記憶装置140は、運転情報および複数のセンサによって取得された航走体130の状態など、航走体130から取得されたデータを記憶することができる。一部の実施形態では、記憶装置140は、本開示で説明される例示的な方法を実行するためにサーバ110が実行または使用することができるデータおよび／または命令を記憶することができる。一部の実施形態では、記憶装置140は、大容量記憶装置、取り外し可能記憶装置、揮発性読み出し書き込みメモリ、読み出し専用メモリ（ROM）など、またはそれらの任意の組み合わせを含むことができる。例示的な大容量記憶装置は、磁気ディスク、光ディスク、ソリッドステートドライブなどを含み得る。例示的な取り外し可能記憶装置は、フラッシュドライブ、フロッピーディスク、光ディスク、メモリカード、ジップディスク、磁気テープなどを含み得る。例示的な揮発性読み出し書き込みメモリは、ランダムアクセスメモリ（RAM）を含み得る。例示的なRAMは、ダイナミックRAM（DRAM）、ダブルデータレート同期ダイナミックRAM（DDR SDRAM）、スタティックRAM（SRAM）、サイリスタRAM（T−RAM）、およびゼロキャパシタRAM（Z−RAM）などを含み得る。例示的なROMは、マスクROM（MROM）、プログラマブルROM（PROM）、消去可能プログラマブルROM（EPROM）、電気的消去可能プログラマブルROM（EEPROM）、コンパクトディスクROM（CD−ROM）、およびデジタル多用途ディスクROMなどを含み得る。一部の実施形態では、記憶装置140は、クラウドプラットフォーム上に実装することができる。ほんの一例として、クラウドプラットフォームは、プライベートクラウド、パブリッククラウド、ハイブリッドクラウド、コミュニティクラウド、分散型クラウド、インタークラウド、マルチクラウドなど、またはそれらの任意の組み合わせを含むことができる。
【００３５】
一部の実施形態では、記憶装置140は、自動航行システム100の1つ以上の構成要素（例えば、サーバ110、航走体130）と通信するために、ネットワーク120に接続され得る。自動航行システム100の1つ以上の構成要素は、ネットワーク120を介して、記憶装置140に記憶されているデータまたは命令にアクセスすることができる。一部の実施形態では、記憶装置140は、自動航行システム100の1つ以上の構成要素（例えば、サーバ110および航走体130）に直接接続され得る、またはこれと直接通信し得る。一部の実施形態では、記憶装置140はサーバ110の一部であり得る。
【００３６】
自動航行システム100は例示の目的で提供されたものに過ぎず、本開示の範囲を限定することを意図していないことに留意されたい。当業者であれば、本開示の教示の下で複数の変形または修正をなし得る。例えば、自動航行システム100は、データベース、情報源などをさらに備え得る。別の例として、自動航行システム100は、同様のまたは異なる機能を実現するために他の装置に実装され得る。しかしながら、それらの変形および修正は、本開示の範囲から逸脱しない。
【００３７】
図2は、本開示の一部の実施形態による、例示的なコンピューティングデバイスの例示的なハードウェアおよび／またはソフトウェアのコンポーネントを示す概略図である。一部の実施形態では、サーバ110は、コンピューティングデバイス200上に実装され得る。例えば、処理エンジン112は、コンピューティングデバイス200上に実装され、本開示に開示されている処理エンジン112の機能を実行するように構成され得る。
【００３８】
コンピューティングデバイス200は、本開示の自動航行システム100の任意の構成要素を実施するために使用され得る。例えば、自動航行システム100の処理エンジン112は、ハードウェア、ソフトウェアプログラム、ファームウェア、またはそれらの組み合わせを介して、コンピューティングデバイス200上に実装することができる。便宜上、このようなコンピュータは1つしか示されていないが、本明細書に記載の自動航行システム100に関連するコンピュータ機能は、処理負荷を分散させるためにいくつかの同様のプラットフォーム上に分散方式で実装することができる。
【００３９】
例えば、コンピューティングデバイス200は、データ通信を容易にするためにそれに接続されたネットワーク（例えば、ネットワーク120）に接続された通信（COMM）ポート250を備えることができる。コンピューティングデバイス200はまた、プログラム命令を実行するための、1つ以上のプロセッサ（例えば、論理回路）の形態のプロセッサ（例えば、プロセッサ220）を備えることができる。例えば、プロセッサは、内部にインターフェース回路および処理回路を備え得る。インターフェース回路は、バス210から電子信号を受信し、電子信号は、処理回路が処理するための構造化データおよび／または命令を符号化する、ように構成され得る。処理回路は論理計算を実行し、次いで、電子信号として符号化された結論、結果、および／または命令を決定することができる。次いで、インターフェース回路は、バス210を介して処理回路から電気信号を送信することができる。
【００４０】
例示的なコンピューティングデバイス200は、様々なデータファイルをコンピューティングデバイス200によって処理および／または送信するために、異なる形式のプログラム記憶装置およびデータ記憶装置、例えばディスク270、および読み出し専用メモリ（ROM）230、またはランダムアクセスメモリ（RAM）240をさらに備えることができる。例示的なコンピューティングデバイス200はまた、プロセッサ220によって実行されるように、ROM230、RAM240、および／または他の種類の非一時的記憶媒体に記憶されたプログラム命令を含むことができる。本開示の方法および／またはプロセスは、プログラム命令として実施することができる。コンピューティングデバイス200はまた、コンピューティングデバイス200と内部の他の構成要素との間の入出力をサポートするI／O構成要素260を備える。コンピューティングデバイス200はまた、ネットワーク通信を介してプログラミングおよびデータを受信し得る。
【００４１】
単なる例示として、コンピューティングデバイス200には1つのプロセッサのみが記載されている。しかしながら、本開示におけるコンピューティングデバイス200はまた、複数のプロセッサを備えることができ、よって、本開示において説明される1つのプロセッサによって実行される動作はまた、複数のプロセッサによって共同または別々に実行され得ることに留意されたい。例えば、コンピューティングデバイス200のプロセッサは、動作Aと動作Bとの両方を実行する。別の例のように、動作Aと動作Bとはまた、コンピューティングデバイス200において2つの異なるプロセッサによって共同または別々に実行されてもよい（例えば、第1のプロセッサが動作Aを実行し、第2のプロセッサが動作Bを実行する、または第1および第2のプロセッサが共同で動作AおよびBを実行する）。
【００４２】
図3は、本開示の一部の実施形態による例示的な処理エンジンを示すブロック図である。処理エンジン112は、マップ決定モジュール310と、障害物決定モジュール320と、グリッド決定モジュール330と、経路決定モジュール340と、を備え得る。
【００４３】
マップ決定モジュール310は、マップ上の探索領域を決定することができる。一部の実施形態では、マップ決定モジュール310は、本開示の他の場所に開示されているものなどの記憶装置（例えば、記憶装置140）からマップを取得することができる。探索領域は、航走体の開始地点および目的地を含むことができる。マップ決定モジュール310は、探索領域内で開始地点から目的地点まで到達するための航走体のための最適経路を探索するように構成され得る。探索領域は、動的探索領域であっても静的探索領域であってもよい。探索領域内の障害物が未知であるか動いている場合、探索領域は動的探索領域であり得る。探索領域内の障害物が既知であるか動いていない場合、探索領域は静的探索であり得る。一部の実施形態では、探索領域は、二次元平面であっても三次元空間であってもよい。例えば、航走体が車または船である場合、探索領域は二次元領域であり得る。航走体が航空機または海中航走体である場合、探索領域は三次元空間であり得る。
【００４４】
経路探索タスクを単純化するために、マップ決定モジュール310は、探索領域を複数の空間グリッドに分割することができる。最適経路は、複数のグリッドに基づいて決定され得る。一部の実施形態では、空間グリッドの形状は、正方形、長方形、六角形、三角形など、またはそれらの任意の組み合わせを含み得るが、これらに限定されない。空間グリッドはノードを含み得る。一部の実施形態では、ノードは空間グリッドの中心であり得る。空間グリッドは、グリッドに対応する地理的情報を含み得る。一部の実施形態では、地理的情報は探索領域内の中心の座標であり得る。経路探索タスクは、空間グリッドの中心を交差しながら航走体を移動させることと見なすことができる。
【００４５】
空間グリッドは、航行可能ステータスまたは航行不可能ステータスを含み得る。航行可能ステータスは、航走体が空間グリッド内に移動できることを表し得る。航行不可能ステータスは、航走体が空間グリッド内に移動できないことを表し得る。例えば、空間グリッドAが障害物によって占有されている場合、航走体は、空間グリッドA内に移動することができず、よって空間グリッドAは航行不能ステータスにある。
【００４６】
マップ決定モジュール310は、探索領域に対応する複数の時空間グリッドを含む時空間マップをさらに決定してもよい。一部の実施形態では、マップ決定モジュール310は、図4または図5Aに示す時空間マップを決定することができる。時空間マップおよび時空間グリッドに関する詳細な説明は、本開示の他の場所、例えば図4、図5A、図5B、およびその説明に見出すことができる。
【００４７】
マップ決定モジュール310は、複数の時空間グリッドを生成するために、時空間グリッドの時間的情報を追加することができる。図5Aに示すように、x−y平面は探索領域を表し、z軸は時間次元を表すことができる。時空間グリッドは、ある期間にわたる空間グリッドのステータス変化を表すことができる。例えば、処理エンジン112は、時間的情報Tを空間グリッドA（A1，A2）に追加し、時空間グリッド（A1，A2，T）を決定することができる。時空間グリッド（A1，A2，T）は、空間グリッドA（A1，A2）のステータス（航行可能ステータスまたは航行不可能ステータス）を表すように構成され得る。例えば、時空間グリッド（A1，A2，T1）は、グリッドA（A1，A2）が時点T1で航行可能であるか否かを表すように構成され得る。
【００４８】
一部の実施形態では、マップ決定モジュール310は、探索領域が三次元空間である場合、複数の時空間グリッドを生成するために、時空間グリッドの時間的情報を追加することができる。探索領域が三次元空間である場合、時空間マップおよび時空間グリッドは四次元であり得る（図示せず）。例えば、処理エンジン112は、時間的情報Tを三次元空間グリッドA（A1，A2，A3）に追加し、時空間グリッド（A1，A2，A3，T）を決定することができる。時空間グリッド（A1，A2，A3，T）は、空間グリッドA（A1，A2，A3）のステータス（航行可能ステータスまたは航行不可能ステータス）を表すように構成され得る。例えば、時空間グリッド（A1，A2，A3，T1）は、グリッドA（A1，A2，A3，T1）が時点T1で航行可能であるか否かを表すように構成され得る。
【００４９】
障害物決定モジュール320は、障害物の障害物情報を決定することができる。障害物情報は、障害物の種類（例えば、航走体、歩行者、動物、建物、木、道路防塞）、障害物の位置、障害物のサイズ、障害物の速度、航走体の現在位置と障害物の位置との間の距離など、またはそれらの任意の組み合わせを含むことができる。
【００５０】
一部の実施形態では、障害物は静止障害物であり得る。例えば、障害物は、建物、木、道路防塞、海の岩、島など、またはそれらの任意の組み合わせであり得る。静止障害物が既知である場合、処理エンジン112は、本開示の他の場所に開示されているものなどの記憶装置（例えば、記憶装置140）から静止障害物情報を取得することができる。
【００５１】
一部の実施形態では、障害物は、動いている障害物または未知の障害物であり得る。例えば、障害物は、動いている航走体、歩行者、動物、未知の岩、未知の島であり得る。処理エンジン112は、航走体の検出ユニット（例えば、カメラ、レーダ）から、動いている障害物または未知の障害物の障害物情報を取得することができる。
【００５２】
グリッド決定モジュール330は、障害物情報に基づいて、複数の時空間グリッドのうちの複数の航行可能グリッドおよび複数の航行不可能グリッドを決定することができる。処理エンジン112は、障害物情報に基づいて、ある時点で時空間グリッドが障害物によって占有されているか否かを決定することができる。
【００５３】
例えば、障害物が（A1，A2）に位置する静止障害物である場合、処理エンジン112は、位置（A1，A2）に対応する複数の時空間グリッド（例えば、（A1，A2，T1）、（A1，A2，T2）、（A1，A2，T3）であり、ここで、T1，T2，およびT3は異なる時点を表す）のステータスを航行不能と決定することができる。
【００５４】
障害物が動いている場合、グリッド決定モジュール330は、障害物情報に基づいて、時空間マップにおける障害物の移動軌道を決定することができる。次いで、グリッド決定モジュール330は、時空間マップにおける障害物の移動軌道に基づいて、複数の航行可能グリッドおよび複数の航行不可能グリッドを決定することができる。
【００５５】
経路決定モジュール340は、複数の航行可能グリッドに基づいて、航走体のための経路を決定することができる。航行可能グリッドを決定した後、経路決定モジュール340は、航行可能グリッドを探索し、探索領域内で開始地点から目的地点まで到達するための航走体のための最適経路を発見することができる。
【００５６】
経路決定モジュール340は、探索領域内で開始地点から目的地点まで到達するための航走体のための最適経路を決定することができる。経路探索タスクの場合、時空間グリッドは、総コスト値およびヒューリスティック値を含み得る。時空間グリッドAの総コスト値は、時空間グリッドAに到達するために生成された経路に従って、開始グリッドから時空間グリッドAに移動するための移動コストに関係し得る。時空間グリッドAのヒューリスティック値は、時空間グリッドAから目的地グリッドに移動するための推定移動コストに関係し得る。経路決定モジュール340は、開始グリッドの複数の隣接するグリッドを探索し、コスト値とヒューリスティック値との合計が最小であるグリッドを親グリッドとして決定することができる。次いで、経路決定モジュール340は、親グリッドの複数の隣接するグリッドを探索し、コスト値とヒューリスティック値との合計が最小であるグリッドを新たな親グリッドとして決定することができる。経路決定モジュール340は、経路が目的地グリッドに到達するまで、新しい親グリッドを繰り返し探索し得る。
【００５７】
処理エンジン112におけるモジュールは、有線接続または無線接続を介して互いに接続または通信することができる。有線接続は、金属ケーブル、光ケーブル、ハイブリッドケーブルなど、またはそれらの任意の組み合わせを含み得る。無線接続は、ローカルエリアネットワーク（LAN）、広域ネットワーク（WAN）、Bluetooth（登録商標）、ZigBee（登録商標）、近距離無線通信（NFC）など、またはそれらの任意の組み合わせを含み得る。モジュールのうちの2つ以上を組み合わせて1つのモジュールとしてもよいし、モジュールのうちのいずれか1つを2つ以上のユニットに分割してもよい。
【００５８】
図4は、本開示の一部の実施形態による例示的な時空間マップを示す概略図である。図4に示すように、OA、OB、およびOCは、第1の地理的方向（例えば、X軸として表される地理的東方向）、第2の地理的方向（例えば、Y軸として表される地理的北方向）、時間次元（Z軸として表される）にそれぞれ対応し得る。時点Tにおいて、障害物が、点M（x1，y1）から移動速度v（t）、かつ移動方向h（t）で移動すると仮定する。時間期間Δtの後、障害物は点Nに到達でき、X−Y−Z座標系における点Nの座標は、式（1）に従って（x（T＋Δt），y（T＋Δt），T＋Δt）として表すことができる。
【数１】
2021513124.tif 000003
ここで、
x1は、点MのX軸上への垂直投影の位置を指すことができ、y1は、点MのY軸上への垂直投影の位置を指すことができ、Tは、障害物が点Mに位置する時点を指すことができ、Δtは、障害物が点Mから点Nに移動する時間期間を指すことができ、x（T＋Δt）は、点NのX軸上への垂直投影の位置を指すことができ、y（T＋Δt）は、点NのY軸上への垂直投影の位置を指すことができ、v（t）は、障害物の移動速度を指すことができ、h（t）は、障害物の移動方向を指すことができる。
【００５９】
図4では、障害物は質点と見なされる。よって、図4に示す軌道は線であり、時間に対する障害物の質量中心または幾何学的中心の移動軌道を表す。一部の実施形態では、障害物は、輪郭を有し得る。したがって、図5Aに示すように、特定の時間期間における障害物の移動軌道は、X−Y−Z空間における3D形状として表現することができる。
【００６０】
図5Aは、本開示の一部の実施形態による三次元空間をグリッド化するための例示的なプロセスを示す概略図である。図5Aに示すように、図4に示すX−Y−Z空間（例えば、時空間マップ）は、複数の時空間グリッドに分割することができる。時空間グリッドは、時空間グリッドの中心点の座標によって表すことができる。時空間グリッドの長さΔLおよび幅ΔWは、X−Y平面の特定の領域に対応し得る。時空間グリッドの高さΔTは、特定の時間期間に対応し得る。時空間グリッドは、航走体の経路探索タスクのための基本単位として使用することができる。一部の実施形態では、時空間グリッドのサイズは、航走体の1つ以上の特徴に基づいて決定され得る。航走体の1つ以上の特徴は、航走体の種類、航走体の重量、航走体の型式、エンジン出力、ブレーキ効率など、またはそれらの任意の組み合わせを含み得る。
【００６１】
時空間グリッドのそれぞれは、ある時点における地理的領域の航行可能性に対応し得る。本明細書で使用されるとき、特定の地理的領域の航行可能性は、航走体が障害物に衝突することなく特定の地理的領域内を移動することができることを示し得る。例えば、時空間グリッド（x，y，T）は、時間期間Tにおける地理的領域（x，y）の航行可能性に対応し得る。時空間グリッド（x，y，T）が障害物の移動軌道によって占有されている場合、例えば図5Aに示すグリッド410の場合、位置（x，y）は、時間Tにおいて航走体が航行可能ではないことを表す。時空間グリッド（x，y，T）が障害物の移動軌道によって占有されていない場合、例えば図5Aに示すグリッド420の場合、位置（x，y）は、時間Tにおいて航走体が航行可能であることを表す。
【００６２】
一部の実施形態では、地理的領域の航行可能性は、地理的領域に対応する時空間グリッドと障害物に対応する移動軌道との間の空間的関係に基づいて決定され得る。例えば、処理エンジン112は、地理的領域に対応する時空間グリッドが障害物に対応する移動軌道と重なるか否かを決定し得る。その時間期間中の地理的領域に対応する時空間グリッドが障害物に対応する移動軌道と重なるという決定に応じて、処理エンジン112は、その時間期間中、時空間グリッドによって表される地理的領域が航行可能ではないと決定することができる。その時間期間中の地理的領域に対応する時空間グリッドが障害物に対応する三次元移動軌道と重ならないという決定に応じて、処理エンジン112は、その時間期間中、時空間グリッドによって表される地理的領域が航行可能であると決定することができる。
【００６３】
一部の実施形態では、処理エンジン112は、衝突検出を実行することによって、地理的領域に対応する時空間グリッドが障害物に対応する移動軌道と重なるか否かを決定し得る。一部の実施形態では、処理エンジン112は、1つ以上の衝突検出アルゴリズムに基づいて、地理的領域に対応する時空間グリッドと障害物に対応する移動軌道との間の衝突検出を実行することができる。衝突検出アルゴリズムは、軸平行境界ボックス（AABB）アルゴリズム、有向境界ボックス（OBB）アルゴリズムなどを含み得る。例えば、処理エンジン112は、物体（例えば、障害物）を境界体積で完全に包むことができる。境界体積は、境界ボックス（例えば、直方体、立方体）、境界カプセル、境界円筒、境界球などであり得る。AABBアルゴリズムでは、境界ボックスは、座標系の軸に対して平行に並べられ得る。処理エンジン112は、物体を含む境界体積のサイズおよび位置に基づいて、X−Y−Z空間において物体を含む境界体積と複数の時空間グリッドのそれぞれとの間で衝突が生じるか否かをさらに決定し得る。例えば、処理エンジン112は、障害物を含む境界体積を複数の時空間グリッドのそれぞれと比較することによって、X−Y−Z空間において物体を含む境界体積と複数の時空間グリッドのそれぞれとの間で衝突が生じるか否かを決定し得る。X−Y−Z空間において物体を含む境界体積と複数の時空間グリッドのうちの1つとの間に衝突が生じるとの決定に応じて、処理エンジン112は、物体を含む境界体積が時空間グリッドと重なると決定し得る。したがって、処理エンジン112は、時空間グリッドがその時間期間中に航行可能ではないと決定することができる。
【００６４】
一部の実施形態では、処理エンジン112は、障害物のX−Y平面上への投影に基づいて、複数の時空間グリッドのそれぞれと障害物との間の衝突検出を実行することができる。図5Bに示すように、障害物が立方体であり、障害物の移動の開始時点および終了時点がそれぞれt1およびt2であると仮定すると、処理エンジン112は、時点t1および時点t2における障害物の中心点の座標は、式（1）より、それぞれ（xt1，yt1）および（xt2，yt2）となると決定することができる。処理エンジン112は、図5Aに示すように、時点t1および時点t2における障害物の位置をX−Y平面上に投影し得る。処理エンジン112は、障害物の移動方向に従って障害物の頂点を結ぶことにより、X−Y平面上に2D境界ボックス（例えば、境界ボックスABCDE）を生成することができ、これは、図5Bに示すように、障害物が時点t1から時点t2まで移動する領域を示す。図5Bは、本開示の一部の実施形態によるX−Y平面上の障害物の例示的な境界ボックスを示す概略図である。
【００６５】
一部の実施形態では、処理エンジン112は、長さΔLおよび幅ΔWを有する複数の2DグリッドによってX−Y平面を分割することができ、これは、X−Y−Z空間におけるX−Y平面上の複数の時空間グリッドの投影と同じである。したがって、処理エンジン112は、X−Y平面において、ある時間期間における移動障害物の2D境界ボックスと2Dグリッドのそれぞれとを比較することによって、時間期間中の地理的領域に対応する時空間グリッドが航行可能であるか否かを決定することができる。例えば、処理エンジン112は、X−Y平面において、時間期間における移動障害物の2D境界ボックスが複数の2Dグリッドのそれぞれと重なるか否かを決定することができる。X−Y平面において、時間期間における移動障害物の2D境界ボックスが2Dグリッドと重なるという決定に応じて、処理エンジン112は、時間期間において、X−Y−Z空間における対応する時空間グリッドが航行可能ではないと決定することができる。X−Y平面において、時間期間における移動障害物の2D境界ボックスが2Dグリッドと重ならないという決定に応じて、処理エンジン112は、時間期間において、X−Y−Z空間における対応する時空間グリッドが航行可能であると決定することができる。
【００６６】
上述のように、処理エンジン112は、境界ボックスが時空間グリッドのそれぞれと重なるか否かを決定するために、X−Y−Z空間において障害物を含む境界ボックスをすべての時空間グリッドと比較する必要がある場合があり、このことは、低い計算効率をもたらし得る。さらに、AABBアルゴリズムでは、障害物を含む境界ボックスは、軸と平行に並べる必要がある場合があり、それは障害物の方向の影響を受ける。一部のシナリオでは、障害物を含む境界ボックスは、障害物と重ならない1つ以上の時空間グリッドを含む場合があり、このことは、衝突検出の精度を低下させる場合がある。本開示において開示される方法は、3D構造衝突問題を2D平面重なり問題に変換し、このことは、衝突検出の計算効率および精度を大幅に改善することができる。
【００６７】
図6Aは、本開示の一部の実施形態による、障害物の運動領域に関連する例示的なメンバーシップ関数を示す概略図である。図6Bは、本開示の一部の実施形態による、障害物の運動領域に関連するメンバーシップ関数の例示的な等高線を示す概略図である。
【００６８】
一部の実施形態では、航走体は点と見なすことができ、障害物のサイズは、航走体のサイズ、航走体の安全な航行距離、および1つ以上の規則（例えば、海上における衝突の予防のため国際規則に関する条約（COLREGs））に基づいて決定され得る。本明細書で使用するとき、航走体の安全な航行距離は、航走体と障害物との間の衝突を回避するための、航走体と障害物との間の最小距離を指し得る。
【００６９】
一部の実施形態では、処理エンジン112は、COLREGsに従って障害物の周りの航行不可能領域を決定し得る。本明細書で使用されるとき、航行不可能領域は、経路計画を実行するときに航走体が進入することができない領域を指し得る。例えば、COLREGsの第14条（a）によれば、「二隻の動力船が真向かいまたはほとんど真向かいに行き会う場合において衝突のおそれがあるときは、各船舶は、互いに他の船舶の左げん側を通航するようにそれぞれ針路を右に転じなければならない」。したがって、処理エンジン112は、SUVが障害物船舶を回避するために右に転じ得るなど、障害物船舶の右側にある航行不可能な領域を決定することができる。別の例として、COLREGsの第15条によれば、「二隻の動力船が互いに進路を横切る場合において衝突のおそれがあるときは、他の船舶を右げん側に見る船舶は、当該他の船舶の進路を避けなければならず、状況の許す限り、当該他の船舶の船首方向を横切ることを避けなければならない」。したがって、処理エンジン112は、航走体が障害物船舶を回避するために障害物船舶の船尾の後ろを走行するなど、障害物船舶の前方の航行不可能領域を決定することができる。
【００７０】
一部の実施形態では、障害物は、それら自身の運動の法則に従って水上を移動する場合があり、また障害物の移動状態は、他の障害物の移動に起因して変化する場合がある。したがって、障害物の位置および移動状態は時間とともに変化し得る。一般に、障害物に関連する運動情報がより包括的であるほど、障害物の運動状態を正確に予測することがより期待でき、これにより、無効な動作を減らし、経路計画の効率を改善することができる。一部の実施形態では、処理エンジン112は、ファジィ集合論に従って、障害物に関連する運動情報（例えば、障害物の位置、障害物の移動速度、障害物の移動方向）、航走体のサイズ、航走体の安全な航行距離、および1つ以上の規則（例えば、海上における衝突の予防のため国際規則に関する条約（COLREGs））に基づいて、障害物の移動領域モデルを決定し得る。本明細書で使用されるとき、ファジィ集合は、その要素がメンバーシップの度合いを有する集合を指し得る。処理エンジン112は、障害物の運動領域モデルに基づいて、障害物の運動領域を決定し得る。航走体の経路計画において、航走体は、障害物の運動領域に入ることができない場合がある。
【００７１】
一部の実施形態では、処理エンジン112は、図6Aに示すように、式（2）に従ってファジィ集合理論に基づいて、障害物の運動領域に関連するメンバーシップ関数を決定することができる。
【数２】
2021513124.tif 000004
ここで
【数３】
2021513124.tif 000005
は、点（xc，yc）から点（x，y）への方向ベクトルを指すことができ、
【数４】
2021513124.tif 000006
は、速度ベクトルを指すことができ、
【数５】
2021513124.tif 000007
は、
【数６】
2021513124.tif 000008
と
【数７】
2021513124.tif 000009
との間の関係を表す方向因子を指すことができる。一部の実施形態では、
【数８】
2021513124.tif 000010
は式（3）に従って決定され得る。
【数９】
2021513124.tif 000011
ここで、λは、0＜λ＜1である定数を指すことができ、Tは、
【数１０】
2021513124.tif 000012
と
【数１１】
2021513124.tif 000013
との間の角度を指すことができる。本明細書で使用されるとき、メンバーシップ関数は、指定された集合のメンバーである可能性に基づいて、入力データを0から1のスケールに再分類または変換するために使用され得る。例えば、絶対に指定された集合のメンバーではない場所に0が割り当てられ、確実に指定された集合のメンバーである値に1が割り当てられ、0〜1の可能性の範囲全体が、あるレベルの可能なメンバーシップに割り当てられる（例えば、数が大きいほど、可能性が高い）。障害物の運動領域に関連するメンバーシップ関数は、障害物に関連する移動状態（例えば、障害物の位置、障害物の移動速度、障害物の移動方向）、障害物の移動傾向、および障害物の移動範囲を示すことができる。より高い値のメンバーシップ関数を有する位置は、その位置における衝突のリスクがより高いことに対応し得る。
【００７２】
図6Bに示されるように、610および620は、航走体および障害物をそれぞれ指す。640は、障害物620の移動方向を示す。領域1は、障害物の航行不可能領域を指す。領域2は、障害物620の運動領域を指す。線650−1、650−2．．．および650−3は、障害物620の運動領域（例えば、領域2）に関連するメンバーシップ関数の等高線を指す。障害物の移動方向におけるメンバーシップ関数の減衰は、他の方向におけるよりも遅くなり得る。障害物の移動方向における位置のメンバーシップ関数の値は、他の位置のものよりも大きくなり得る。
【００７３】
図7は、本開示の一部の実施形態による、時空間マップに基づいて、航走体のための経路を決定するための例示的なプロセスを示すフローチャートである。プロセス700は、航行駆動システム100によって実行され得る。例えば、プロセス700は、記憶装置ROM230またはRAM240に記憶された命令のセットとして実施され得る。プロセッサ220は命令のセットを実行することができ、命令を実行するとき、プロセッサ220は、プロセス700を実行するように構成され得る。以下に提示される例示されたプロセスの動作は、例示的であることが意図されている。一部の実施形態では、プロセス700は、説明されていない1つ以上の追加の動作と共に、および／または説明された動作のうちの1つ以上を伴わずに達成することができる。加えて、図7に示され以下に説明されるプロセス700の動作の順序は、限定されることを意図されていない。
【００７４】
701において、処理エンジン112は、複数の時空間グリッドを含む第1の領域の時空間マップを決定し得る。
【００７５】
処理エンジン112は、マップ上の探索領域（例えば、第1の領域）を決定することができる。一部の実施形態では、処理エンジン112は、本開示の他の場所に開示されているものなどの記憶装置（例えば、記憶装置140）からマップを取得することができる。探索領域は、航走体の開始地点および目的地点を含むことができる。処理エンジン112は、探索領域内で開始地点から目的地点まで到達するための航走体のための最適経路を探索するように構成され得る。探索領域は、動的探索領域であっても静的探索領域であってもよい。探索領域内の障害物が未知であるか動いている場合、探索領域は動的探索領域であり得る。探索領域内の障害物が既知であるか動いていない場合、探索領域は静的探索であり得る。一部の実施形態では、探索領域は、二次元平面であっても三次元空間であってもよい。例えば、航走体が車または船である場合、探索領域は二次元領域であり得る。航走体が航空機または海中航走体である場合、探索領域は三次元空間であり得る。
【００７６】
経路探索タスクを単純化するために、処理エンジン112は、探索領域を複数の空間グリッドに分割することができる。最適経路は、複数のグリッドに基づいて決定され得る。一部の実施形態では、空間グリッドの形状は、正方形、長方形、六角形、三角形など、またはそれらの任意の組み合わせを含み得るが、これらに限定されない。空間グリッドはノードを含み得る。一部の実施形態では、ノードは空間グリッドの中心であり得る。空間グリッドは、グリッドに対応する地理的情報を含み得る。一部の実施形態では、地理的情報は探索領域内の中心の座標であり得る。経路探索タスクは、空間グリッドの中心を交差しながら航走体を移動させることと見なすことができる。
【００７７】
空間グリッドは、航行可能ステータスまたは航行不可能ステータスを含み得る。航行可能ステータスは、航走体が空間グリッド内に移動できることを表し得る。航行不可能ステータスは、航走体が空間グリッド内に移動できないことを表し得る。例えば、空間グリッドAが障害物によって占有されている場合、航走体は、空間グリッドA内に移動することができず、よって空間グリッドAは航行不能ステータスにある。
【００７８】
処理エンジン112は、探索領域（例えば、第1の領域）に対応する複数の時空間グリッドを含む時空間マップをさらに決定してもよい。一部の実施形態では、処理エンジン112は、図4または図5Aに示す時空間マップを決定することができる。時空間マップおよび時空間グリッドに関する詳細な説明は、本開示の他の場所、例えば図4、図5A、図5B、およびその説明に見出すことができる。
【００７９】
処理エンジン112は、複数の時空間グリッドを生成するために、時空間グリッドの時間的情報を追加することができる。図5Aに示すように、x−y平面は探索領域を表し、z軸は時間次元を表すことができる。時空間グリッドは、ある期間にわたる空間グリッドのステータス変化を表すことができる。例えば、処理エンジン112は、時間的情報Tを空間グリッドA（A1，A2）に追加し、時空間グリッド（A1，A2，T）を決定することができる。時空間グリッド（A1，A2，T）は、空間グリッドA（A1，A2）のステータス（航行可能ステータスまたは航行不可能ステータス）を表すように構成され得る。例えば、時空間グリッド（A1，A2，T1）は、グリッドA（A1，A2）が時点T1で航行可能であるか否かを表すように構成され得る。
【００８０】
一部の実施形態では、処理エンジン112は、探索領域が三次元空間である場合、複数の時空間グリッドを生成するために、時空間グリッドの時間的情報を追加することができる。探索領域が三次元空間である場合、時空間マップおよび時空間グリッドは四次元であり得る（図示せず）。例えば、処理エンジン112は、時間的情報Tを三次元空間グリッドA（A1，A2，A3）に追加し、時空間グリッド（A1，A2，A3，T）を決定することができる。時空間グリッド（A1，A2，A3，T）は、空間グリッドA（A1，A2，A3）のステータス（航行可能ステータスまたは航行不可能ステータス）を表すように構成され得る。例えば、時空間グリッド（A1，A2，A3，T1）は、グリッドA（A1，A2，A3）が時点T1で航行可能であるか否かを表すように構成され得る。
【００８１】
702において、処理エンジン112は、第1の時間期間（例えば，t1からt2）に対応する障害物の障害物情報を決定することができる。動作701で説明したように、時空間グリッドのステータス（例えば、航行可能または航行不可能）は、時空間グリッドが特定の時間期間またはある時点で占有されているか否かに関係する。時空間グリッドのステータスは、後続の動作（例えば、動作703）において障害物情報に基づいて決定されてもよい。
【００８２】
障害物情報は、障害物の種類（例えば、航走体、歩行者、動物、建物、木、道路防塞）、障害物の位置、障害物のサイズ、障害物の速度、航走体の現在位置と障害物の位置との間の距離など、またはそれらの任意の組み合わせを含むことができる。
【００８３】
一部の実施形態では、障害物は静止障害物であり得る。例えば、障害物は、建物、木、道路防塞、海の岩、島など、またはそれらの任意の組み合わせであり得る。静止障害物が既知である場合、処理エンジン112は、本開示の他の場所に開示されているものなどの記憶装置（例えば、記憶装置140）から静止障害物情報を取得することができる。
【００８４】
一部の実施形態では、障害物は、動いている障害物または未知の障害物であり得る。例えば、障害物は、動いている航走体、歩行者、動物、未知の岩、未知の島であり得る。処理エンジン112は、航走体の検出ユニット（例えば、カメラ、レーダ）から、動いている障害物または未知の障害物の障害物情報を取得することができる。
【００８５】
703において、処理エンジン112は、障害物情報に基づいて、複数の時空間グリッドのうちの複数の航行可能グリッドと複数の航行不可能グリッドを決定することができる。処理エンジン112は、障害物情報に基づいて、ある時点で時空間グリッドが障害物によって占有されているか否かを決定することができる。
【００８６】
例えば、障害物が（A1，A2）に位置する静止障害物である場合、処理エンジン112は、位置（A1，A2）に対応する複数の時空間グリッド（例えば、（A1，A2，T1）、（A1，A2，T2）、（A1，A2，T3）であり、ここで、T1，T2，およびT3は異なる時点を表す）のステータスを航行不能と決定することができる。
【００８７】
障害物が動いている場合、処理エンジン112は、障害物情報に基づいて、時空間マップにおける障害物の移動軌道または障害物体積を決定することができる。次いで、処理エンジン112は、時空間マップにおける障害物の移動軌道または障害物体積に基づいて、複数の航行可能グリッドおよび複数の航行不可能グリッドを決定することができる。
【００８８】
図5Aに示されているように、地理的領域の航行可能性は、その時間期間における、地理的領域に対応する時空間グリッドと障害物に対応する移動軌道との間の空間的関係に基づいて決定され得る。例えば、処理エンジン112は、その時間期間において、地理的領域に対応する時空間グリッドが障害物に対応する移動軌道と重なるか否かを決定し得る。その時間期間中の地理的領域に対応する時空間グリッドが障害物に対応する軌道と重なるという決定に応じて、処理エンジン112は、その時間期間中、時空間グリッドによって表される地理的領域が航行可能ではないと決定することができる。その時間期間中の地理的領域に対応する時空間グリッドが障害物に対応する移動軌道と重ならないという決定に応じて、処理エンジン112は、その時間期間中、時空間グリッドによって表される地理的領域が航行可能であると決定することができる。
【００８９】
図4では、障害物は質点と見なされる。よって、図4に示す軌道は線であり、時間に対する障害物の質量中心または幾何学的中心の移動軌道を表す。一部の実施形態では、障害物は、輪郭を有し得る。したがって、図5Aに示すように、特定の時間期間における障害物の移動軌道は、X−Y−Z空間における体積として表現することができる。
【００９０】
一部の実施形態では、処理エンジン112は、衝突検出を実行することによって、その時間期間中、地理的領域に対応する時空間グリッドが、移動軌道と重なるか否かを決定し得る。一部の実施形態では、処理エンジン112は、1つ以上の衝突検出アルゴリズムに基づいて、時空間グリッドと障害物に対応する移動軌道との間の衝突検出を実行することができる。衝突検出アルゴリズムは、軸平行境界ボックス（AABB）アルゴリズム、有向境界ボックス（OBB）アルゴリズムなどを含み得る。例えば、処理エンジン112は、物体（例えば、障害物）を境界体積で完全に包むことができる。境界体積は、境界ボックス（例えば、直方体、立方体）、境界カプセル、境界円筒、境界球などであり得る。AABBアルゴリズムでは、境界ボックスは、座標系の軸に対して平行に並べられ得る。処理エンジン112は、物体を含む境界体積のサイズおよび位置に基づいて、X−Y−Z空間において物体を含む境界体積と複数の時空間グリッドのそれぞれとの間で衝突が生じるか否かをさらに決定し得る。例えば、処理エンジン112は、障害物を含む境界体積を複数の時空間グリッドのそれぞれと比較することによって、X−Y−Z空間において物体を含む境界体積と複数の時空間グリッドのそれぞれとの間で衝突が生じるか否かを決定し得る。X−Y−Z空間において物体を含む境界体積と複数の時空間グリッドのうちの1つとの間に衝突が生じるとの決定に応じて、処理エンジン112は、物体を含む境界体積が時空間グリッドと重なると決定し得る。したがって、処理エンジン112は、時空間グリッドがその時間期間中に航行可能ではないと決定することができる。
【００９１】
一部の実施形態では、処理エンジン112は、第1の時間期間に対応する障害物体積に基づいて、1つ以上の障害物のそれぞれの障害物軌道投影を決定し、1つ以上の障害物の障害物軌道投影に基づいて、複数の航行可能グリッドおよび複数の航行不可能グリッドを決定することができる。
【００９２】
一部の実施形態では、処理エンジン112は、障害物のX−Y平面上への投影に基づいて、複数の時空間グリッドのそれぞれと障害物との間の衝突検出を実行することができる。図示のように、障害物のサイズが立方体であり、障害物の移動の開始時点および終了時点がそれぞれt1およびt2であると仮定すると、処理エンジン112は、時点t1および時点t2における障害物の中心点の座標は、式（1）より、それぞれ（xt1，yt1）および（xt2，yt2）となると決定することができる。処理エンジン112は、図5Bに示すように、時点t1および時点t2における障害物の位置をX−Y平面上に投影し得る。処理エンジン112は、障害物の移動方向に従って障害物の頂点を結ぶことにより、X−Y平面上に2D境界ボックス（例えば、境界ボックスABCDE）を生成することができ、これは、図5Bに示すように、障害物が時点t1から時点t2まで移動する領域を示す。図5Bは、本開示の一部の実施形態によるX−Y平面上の障害物の例示的な境界ボックスを示す概略図である。
【００９３】
一部の実施形態では、処理エンジン112は、長さΔLおよび幅ΔWを有する複数の2DグリッドによってX−Y平面を分割することができ、これは、X−Y−Z空間におけるX−Y平面上の複数の時空間グリッドの投影と同じである。したがって、処理エンジン112は、X−Y平面において、ある時間期間における移動障害物の2D境界ボックスと2Dグリッドのそれぞれとを比較することによって、時間期間中の地理的領域に対応する時空間グリッドが航行可能であるか否かを決定することができる。例えば、処理エンジン112は、X−Y平面において、時間期間における移動障害物の2D境界ボックスが複数の2Dグリッドのそれぞれと重なるか否かを決定することができる。X−Y平面において、時間期間における移動障害物の2D境界ボックスが2Dグリッドと重なるという決定に応じて、処理エンジン112は、時間期間において、X−Y−Z空間における対応する時空間グリッドが航行可能ではないと決定することができる。X−Y平面において、時間期間における移動障害物の2D境界ボックスが2Dグリッドと重ならないという決定に応じて、処理エンジン112は、時間期間において、X−Y−Z空間における対応する時空間グリッドが航行可能であると決定することができる。
【００９４】
上述のように、処理エンジン112は、境界ボックスが時空間グリッドのそれぞれと重なるか否かを決定するために、X−Y−Z空間において障害物を含む境界ボックスをすべての時空間グリッドと比較する必要がある場合があり、このことは、低い計算効率をもたらし得る。さらに、AABBアルゴリズムでは、障害物を含む境界ボックスは、軸と平行に並べる必要がある場合があり、それは障害物の方向の影響を受ける。一部のシナリオでは、障害物を含む境界ボックスは、障害物と重ならない1つ以上の時空間グリッドを含む場合があり、このことは、衝突検出の精度を低下させる場合がある。本開示において開示される方法は、3D構造衝突問題を2D平面重なり問題に変換し、このことは、衝突検出の計算効率および精度を大幅に改善することができる。
【００９５】
一部の実施形態では、処理エンジン112は、障害物ステータスに基づいて、1つ以上の障害物のそれぞれに関するファジィ集合を決定し、ファジィ集合に基づいて、複数の航行可能グリッドおよび複数の航行不可能グリッドを決定することができる。例えば。処理エンジン112は、障害物情報に基づいて、メンバーシップ関数を決定してもよい。次いで、処理エンジン112は、障害物のメンバーシップ関数に基づいて、複数の航行可能グリッドおよび複数の航行不可能グリッドを決定することができる。
【００９６】
一部の実施形態では、処理エンジン112は、第1の基準（例えば、COLREGs）に従って障害物の周りの航行不可能領域を決定し得る。本明細書で使用されるとき、航行不可能領域は、経路計画を実行するときに航走体が進入することができない領域を指し得る。次いで、処理エンジン112は、航行不可能領域に基づいて、ファジィ集合（例えば、メンバーシップ関数）を決定することができる。例えば、COLREGsの第14条（a）によれば、「二隻の動力船が真向かいまたはほとんど真向かいに行き会う場合において衝突のおそれがあるときは、各船舶は、互いに他の船舶の左げん側を通航するようにそれぞれ針路を右に転じなければならない」。したがって、処理エンジン112は、SUVが障害物船舶を回避するために右に転じ得るなど、障害物船舶の右側にある航行不可能な領域を決定することができる。別の例として、COLREGsの第15条によれば、「二隻の動力船が互いに進路を横切る場合において衝突のおそれがあるときは、他の船舶を右げん側に見る船舶は、当該他の船舶の進路を避けなければならず、状況の許す限り、当該他の船舶の船首方向を横切ることを避けなければならない」。したがって、処理エンジン112は、航走体が障害物船舶を回避するために障害物船舶の船尾の後ろを走行するなど、障害物船舶の前方の航行不可能領域を決定することができる。
【００９７】
一部の実施形態では、処理エンジン112は、図6Aおよび図6Bに示すように、式（2）に従ってファジィ集合理論に基づいて、障害物の運動領域に関連するメンバーシップ関数を決定することができる。本明細書で使用されるとき、メンバーシップ関数は、指定された集合のメンバーである可能性に基づいて、入力データを0から1のスケールに再分類または変換するために使用され得る。例えば、絶対に指定された集合のメンバーではない場所に0が割り当てられ、確実に指定された集合のメンバーである値に1が割り当てられ、0〜1の可能性の範囲全体が、あるレベルの可能なメンバーシップに割り当てられる（例えば、数が大きいほど、可能性が高い）。障害物の運動領域に関連するメンバーシップ関数は、障害物に関連する移動状態（例えば、障害物の位置、障害物の移動速度、障害物の移動方向）、障害物の移動傾向、および障害物の移動範囲を示すことができる。より高い値のメンバーシップ関数を有する位置は、その位置における衝突のリスクがより高いことに対応し得る。位置（x1，y1）に対応するメンバーシップ関数が閾値（例えば、0．2）よりも高い場合、処理エンジン112は、位置（x1，y1）に対応する時空間グリッドが（例えば、（x1，y1，T1）、（x2，y2，T2）、ここで、T1、T2は異なる時点を表す）は航行可能ではないと判定し得る。
【００９８】
704において、処理エンジン112は、複数の航行可能グリッドに基づいて、航走体のための経路を決定することができる。航行可能グリッドを決定した後、処理エンジン112は、航行可能グリッドを探索し、探索領域内で開始地点から目的地点まで到達するための航走体のための最適経路を発見することができる。
【００９９】
処理エンジン112は、探索領域内で開始地点から目的地点まで到達するための航走体のための最適経路を決定することができる。経路探索タスクの場合、時空間グリッドは、総コスト値およびヒューリスティック値を含み得る。時空間グリッドAの総コスト値は、時空間グリッドAに到達するために生成された経路に従って、開始グリッドから時空間グリッドAに移動するための移動コストに関係し得る。処理エンジン112は、2つの隣接する航行可能グリッドの時間的情報および地理的情報に基づいて、コスト関数を決定し得る。総コスト値は、コスト関数に基づいて決定され得る。例えば、経路に開始グリッド、グリッドA、およびグリッドBが含まれ、開始グリッドは、グリッドAに隣接し、グリッドAはグリッドBに隣接する場合、グリッドBの総コスト値は、開始グリッドからグリッドAに移動するためのコスト値と、グリッドAからグリッドBに移動するためのコスト値との和である。時空間グリッドAのヒューリスティック値は、時空間グリッドAから目的地グリッドに移動するための推定移動コストに関係し得る。
【０１００】
処理エンジンは、開始グリッドの複数の隣接するグリッドを探索し、コスト値とヒューリスティック値との合計が最小であるグリッドを親グリッドとして決定することができる。次いで、処理エンジン112は、親グリッドの複数の隣接するグリッドを探索し、コスト値とヒューリスティック値との合計が最小であるグリッドを新たな親グリッドとして決定することができる。処理エンジン112は、経路が目的地グリッドに到達するまで、新しい親グリッドを繰り返し探索し得る。処理エンジンは、目的地グリッドの複数の隣接するグリッドを探索し、コスト値とヒューリスティック値との合計が最小であるグリッドを親グリッドとして決定することができる。次いで、処理エンジン112は、親グリッドの複数の隣接するグリッドを探索し、コスト値とヒューリスティック値との合計が最小であるグリッドを新たな親グリッドとして決定することができる。処理エンジン112は、経路が現在のグリッドに到達するまで、新しい親グリッドを繰り返し探索し得る。
【０１０１】
処理エンジン112は、航走体の目的地を決定することができる。複数の航行可能グリッドの少なくとも一部について、処理エンジン112は、2つの隣接する航行可能グリッド間のコスト関数を決定し得る。次いで、処理エンジン112は、航走体の現在のグリッドと航走体の目的地との間のヒューリスティック関数を決定し得る。次いで、処理エンジン112は、航走体の目的地、複数のコスト関数、およびヒューリスティック関数に基づいて、航走体のための経路を決定し得る。
【０１０２】
処理エンジン112は、航走体の現在のグリッドおよび航走体の目的地の時間的情報および地理的情報に基づいて、ヒューリスティック関数を決定し得る。ヒューリスティック値は、ヒューリスティック関数に基づいて決定され得る。ヒューリスティック関数h（s，s”）は、位置sから別の位置s”への移動の推定コストを示し得る。ヒューリスティック関数は、非負であり前後方向に一貫している、つまり、式（4）に従う。
h（s，s”）≦h（s，s’）＋h（s’，s”）（4）、
ここで、h（s，s”）は、ヒューリスティック関数を指すことができ、s、s’、およびs”は、障害物の位置を指すことができる。ヒューリスティック関数は、目標位置が何であれ、許容可能であり得、つまり、式（5）に従う。
h（s，s’）≦c＊（s，s’）（5）、
ここで、s、s’、およびs”は、障害物の位置を表すことができ、h（s，s’）は、ヒューリスティック関数を指すことができ、c＊（s，s’）は、位置sから位置s’への最小コスト経路に関連するコストを指すことができる。
【０１０３】
処理エンジン112は、2つの隣接する航行可能グリッドの時間的情報および地理的情報に基づいて、コスト関数を決定し得る。コスト値は、コスト関数に基づいて決定され得る。一部の実施形態では、X−Y−Z空間において、ある位置から別の位置への最小コスト経路に関連するコストは、2つの位置間の距離コストと2つの位置間の時間コストとに基づいて決定され得る。2つの位置間の距離コストおよび／または時間コストは、2つの位置間のマンハッタン距離に基づいて決定されてもよい。本明細書で使用されるとき、2点間のマンハッタン距離は、直交軸に沿って測定された2点間の距離を指し得る。一部の実施形態では、位置p（xi，yi，zi）から位置q（xi＋1，yi＋1，zi＋1）への最小コスト経路に関連するコストは、式（6）に従って決定され得る。
c（p，q）＝｜xi＋1−xi｜＋｜yi＋1−yi｜＋α｜zi＋1−zi｜（6）、
ここで、c（p，q）は、位置pから位置qへの最小コスト経路に関連するコストを指すことができ、xi、yi、ziは、位置pのX軸座標、Y軸座標、およびZ軸座標をそれぞれ指すことができ、xi＋1、yi＋1、zi＋1は、位置qのX軸座標、Y軸座標、およびZ軸座標を指すことができ、αは、重みを表し、α＞0である。重みαは、コストc（p，q）の決定における距離コストおよび／または時間コストの重要性を示し得る。例えば、α＝1であると仮定すると、それは距離コストと時間コストとの重要性が同じであることを示し得る。α＞1であると仮定すると、コストc（p，q）の決定において、時間コストが距離コストよりも重要であり得ることを示し得る。0＜α＜1であると仮定すると、それは、コストc（p，q）の決定において、距離コストが時間コストより重要であり得ることを示し得る。重みαは、自動航行システム100のデフォルトの設定であってもよいし、異なる状況下で調整可能であってもよい。
【０１０４】
一部の実施形態では、X−Y−Z空間における時空間グリッドの中心位置Aの座標および別の時空間グリッドの中心位置Bの座標は、それぞれ（xj，yj，Tj）および（xk，yk，Tk）であると仮定すると、ヒューリスティック関数h（j，k）は、式（7）に従って決定され得る。
【数１２】
2021513124.tif 000014
ここで、h（j，k）は、ヒューリスティック関数を指すことができ、xj、yj，Tjは、位置AのX軸座標、Y軸座標、およびZ軸座標をそれぞれ指すことができ、xk、yk，Tkは、位置BのX軸座標、Y軸座標、およびZ軸座標を指すことができ、Δxは、X−Y−Z空間における時空間グリッドの長さを指すことができ、Δyは、X−Y−Z空間における時空間グリッドの幅を指すことができ、ΔTは、X−Y−Z空間における時空間グリッドの高さを指すことができ、kは、時間に関連する係数を指すことができ、0＜k＜1である。係数kは、時間次元においてヒューリスティック関数に影響を及ぼし得る。例えば、航走体の開始位置と目標位置との間に複数の経路がある場合、処理エンジン112は、比較的小さい係数に基づいて、複数の経路から、かかる時間が比較的短い最適経路を決定し得る、つまり、航走体は、可能な限り早く目標位置に到達し得る。係数kは、自動航行システム100のデフォルトの設定であってもよいし、異なる状況下で調整可能であってもよい。
【０１０５】
一部の実施形態では、まず、処理エンジン112は、開始グリッドAをオープンリストに追加し得る。次に、処理エンジン112は、開始グリッドAに隣接するすべての航行可能グリッドを探索し、それらをオープンリストに追加し得る。開始グリッドAに隣接するすべての航行可能グリッドのそれぞれに対して、処理エンジン112は、開始グリッドAをその親グリッドとして保存し得る。次いで、処理エンジン112は、オープンリストから開始グリッドAをドロップし、それをクローズドリストに追加し得る。次に、処理エンジンは、以下の動作を繰り返して進め得る。
（1）オープンリストにおいて、処理エンジン112は、オープンリスト内のコスト値とヒューリスティック値との合計が最小であるグリッドBを探索し、次いで、グリッドBを現在のグリッドとして決定し得る。
（2）次いで、処理エンジン112は、オープンリストからグリッドBをドロップし、それをクローズドリストに追加し得る。
（3）次に、処理エンジン112は、現在のグリッド（すなわち、グリッドB）に隣接するすべての航行可能グリッドを探索し得る。現在のグリッド（すなわち、グリッドB）に隣接する航行可能グリッドのそれぞれについて、それがオープンリストにない場合、処理エンジン112は、それをオープンリストに追加し、現在のグリッド（すなわち、グリッドB）をこのグリッドの親グリッドにすることができる。
【０１０６】
処理エンジン112は、目的地グリッドがクローズドリストに追加されたときに、反復プロセスを中止し得る。処理エンジン112は、目的地グリッドから逆方向に働き、各グリッドからその親グリッドに行き、すべての親グリッドを最適経路として保存することができる。
【０１０７】
上記の説明は例示の目的で提供されたものに過ぎず、本開示の範囲を限定することを意図していないことに留意されたい。当業者であれば、本開示の教示の下で複数の変形および修正をなし得る。しかしながら、それらの変形および修正は、本開示の範囲から逸脱しない。例えば、1つ以上の他の任意の動作（例えば、記憶動作）をプロセス700の他の場所に追加することができる。記憶動作では、処理エンジン112は、本開示の他の場所に開示されている記憶装置（例えば、記憶装置140）においてサンプル航走体に関連する情報および／またはデータを記憶することができる。別の例として、動作702と動作703とは同時に実行されてもよい。
【０１０８】
このように基本概念を説明してきたが、この詳細な開示を読めば、前述の詳細な開示が、例として提示されるように意図されたものに過ぎず、限定するものではないことが当業者にはある程度明らかになろう。本明細書で明示的に述べられていなくても、様々な改変、改良、および修正が当業者に想到され、想定されよう。これらの改変、改良、および修正は、本開示によって示唆されることが意図されており、本開示の例示的な実施形態の趣旨および範囲内にある。
【０１０９】
さらに、特定の用語が、本開示の実施形態を説明するのに用いられている。例えば、「1つの実施形態」、「一実施形態」、および／または「一部の実施形態」という用語は、実施形態に関して説明した特定の特徴、構造、または特性が本開示の少なくとも1つの実施形態に含まれることを意味する。したがって、本明細書の様々な部分における「一実施形態」または「1つの実施形態」、または「代替的な実施形態」への2つ以上の言及のすべてが、必ずしも同じ実施形態を指しているとは限らないことを留意および理解されたい。さらに、特定の特徴、構造、または特性は、本開示の1つ以上の実施形態において適宜組み合わされてもよい。
【０１１０】
さらに、当業者には理解されるように、本開示の態様は、任意の新規かつ有用なプロセス、機械、製品、もしくは組成物、またはそれらの任意の新規かつ有用な改良形態を含む、いくつかの特許可能な分類または文脈のいずれかにおいて、本明細書で図示および説明され得る。したがって、本開示の態様は、完全にハードウェアで実施されてもよいし、完全にソフトウェア（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）で実施されてもよいし、本明細書において「ユニット」、「モジュール」、または「システム」とすべて一般に呼ばれ得るソフトウェアとハードウェアとを組み合わせた実装で実施されてもよい。さらに、本開示の態様は、コンピュータ可読プログラムコードを具現化した1つ以上のコンピュータ可読媒体に具現化されたコンピュータプログラム製品の形態を取ってもよい。
【０１１１】
コンピュータ可読信号媒体は、内部に、例えばベースバンド内にまたは搬送波の一部分としてコンピュータ可読プログラムコードを具現化した伝播データ信号を含んでもよい。そのような伝播信号は、電磁気、光など、またはそれらの任意の好適な組み合わせを含む、様々な形態のうちのいずれかを取ってもよい。コンピュータ可読信号媒体は、コンピュータ可読記憶媒体ではなく、かつ命令実行システム、装置、またはデバイスによって、またはこれらに関して使用されるプログラムを伝達、伝播、または搬送し得る、任意のコンピュータ可読媒体としてもよい。コンピュータ可読信号媒体上に具現化されたプログラムコードは、無線、有線、光ファイバケーブル、RFなど、またはそれらの任意の好適な組み合わせを含む任意の適切な媒体を使用して送信されてもよい。
【０１１２】
本開示の態様の動作を実行するコンピュータプログラムコードは、Java（登録商標）、Scala、Smalltalk、Eiffel、JADE、Emerald、C＋＋、C＃、VB．NET、Pythonなどのオブジェクト指向型プログラミング言語、「C」プログラミング言語、Visual Basic、Fortran 2103、Perl、COBOL 2102、PHP、ABAPなどの従来の手続型プログラミング言語、Python、RubyおよびGroovyなどの動的プログラミング言語、または他のプログラミング言語を含む、1つ以上のプログラミング言語の組み合わせで記述してもよい。プログラムコードは、スタンドアロン型のソフトウェアパッケージとして、完全にユーザのコンピュータ上で実行されてもよいし、一部をユーザのコンピュータ上で実行されてもよいし、一部をユーザのコンピュータ上かつ一部をリモートコンピュータ上で実行されてもよいし、完全にリモートコンピュータまたはサーバ上で実行されてもよい。後半のシナリオにおいて、リモートコンピュータは、ローカルエリアネットワーク（LAN）または広域ネットワーク（WAN）を含む任意の種類のネットワークを介してユーザのコンピュータに接続されてもよく、接続は、（例えば、インターネットサービスプロバイダを用いてインターネットを通じて）外部コンピュータに対して行ってもよいし、クラウドコンピューティング環境において行ってもよいし、サービス型ソフトウェア（SaaS）などのサービスとして提供されてもよい。
【０１１３】
さらに、処理要素もしくはシーケンスの列挙した順序、またはそれらの数字、文字、もしくは他の名称の使用は、特許請求の範囲において指定する場合を除いて、特許請求の範囲に記載のプロセスおよび方法をいかなる順序にも限定することを意図するものではない。上記の開示は、様々な例を通じて、本開示の各種の有用な実施形態と現在考えられるものを論じているが、そのような詳細は、その目的のためのものに過ぎず、添付の特許請求の範囲は、開示された実施形態に限定されるものではなく、逆に、開示された実施形態の趣旨および範囲内にある修正形態および均等なアレンジを包含することが意図されていることを理解されたい。例えば、上述の様々な構成要素の実装は、ハードウェアデバイスに具現化されているかもしれないが、ソフトウェアのみの解決策、例えば、既存のサーバまたはモバイルデバイスに組み込まれたものとして実施されてもよい。
【０１１４】
同様に、本開示の実施形態の上記の説明では、様々な本発明の実施形態のうちの1つ以上の理解に役立つ本開示の簡素化を目的として、様々な特徴が、単一の実施形態、図、またはその説明において、グループ化されていることを理解されたい。しかしながら、この開示方法は、特許請求の範囲に記載の主題が、各請求項に明示的に列挙されたものよりも多くの特徴を必要とするという意図を反映するものと解釈されるべきではない。そうではなく、本発明の実施形態は、上で開示された単一の実施形態のすべての特徴よりも少ないものであり得る。
【０１１５】
一部の実施形態では、本出願の特定の実施形態を説明および特許請求するために使用される量または特性を表す数は、一部の例では「約（aboutもしくはapproximately）」、または「実質的に（substantially）」という用語によって修飾されると理解されたい。例えば、「約」または「実質的に」は、特に明記しない限り、それが記載する値の±20％の変動を示し得る。したがって、一部の実施形態では、明細書および添付の特許請求の範囲に記載の数値パラメータは、特定の実施形態によって得られることが求められる所望の特性に応じて変わり得る近似値である。一部の実施形態では、数値パラメータは、報告された有効数字の数に照らして、かつ通常の丸め技法を適用して解釈されるべきである。本出願の一部の実施形態の広い範囲を説明する数値範囲およびパラメータは近似値であるにもかかわらず、特定の実施例に記載された数値は実施可能な程度に正確に報告されている。
【０１１６】
特許、特許出願、特許出願の公開公報、および記事、書籍、仕様書、刊行物、文献、作品などの他の資料の本明細書で引用するそれぞれが、関連する審査経過、本開示との相反もしくは矛盾するもの、または現在または後に本開示に関連する特許請求の最も広い範囲に関して限定された影響を有し得るものを除いて、その全体がこの参照により本明細書に組み込まれる例として、組み込まれた資料のいずれかに関連する説明、定義、および／または用語の使用と、本明細書に関連する説明、定義、および／または用語の使用と、との間に相反または矛盾がある場合、本明細書における説明、定義、および／または用語の使用が優先するものとする。
【０１１７】
最後に、本明細書に開示された本出願の実施形態は、本出願の実施形態の原理の例示であることを理解されたい。採用され得る他の修正は、本出願の範囲内であり得る。よって、限定ではなく例として、本出願の実施形態の代替構成を、本明細書の教示に従って利用することができる。したがって、本出願の実施形態は、図示および説明されたものに厳密には限定されない。
【符号の説明】
【０１１８】
100  自動航行システム、航行駆動システム
110  サーバ
112  処理エンジン
120  ネットワーク
130  航走体
140  記憶装置
200  コンピューティングデバイス
210  バス
220  プロセッサ
230  読み出し専用メモリ（ROM）
240  ランダムアクセスメモリ（RAM）
250  通信（COMM）ポート
260  I／O構成要素
270  ディスク
310  マップ決定モジュール
320  障害物決定モジュール
330  グリッド決定モジュール
340  経路決定モジュール
410  グリッド
420  グリッド
610  航走体
620  障害物
640  移動方向
650−1  メンバーシップ関数の等高線
650−2  メンバーシップ関数の等高線
650−3  メンバーシップ関数の等高線
700  プロセス
701  動作
702  動作
703  動作
704  動作
2102  COBOL
2103  FORTRAN
【図１】
2021513124.tif 000015
【図２】
2021513124.tif 000016
【図３】
2021513124.tif 000017
【図４】
2021513124.tif 000018
【図５Ａ】
2021513124.tif 000019
【図５Ｂ】
2021513124.tif 000020
【図６Ａ】
2021513124.tif 000021
【図６Ｂ】
2021513124.tif 000022
【図７】
2021513124.tif 000023
【手続補正書】
【提出日】平成31年2月21日(2019.2.21)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
時空間マップに基づく、航走体のための表面航行のためのコンピューティングデバイス上で実施される方法であって、前記コンピューティングデバイスは、メモリと、複数のプロセッサと、を備え、前記方法は、
第1の領域の時空間マップを決定するステップであって、前記時空間マップは、複数の時空間グリッドを含み、各時空間グリッドは、前記時空間グリッドに対応する時間的情報および地理的情報を含む、ステップと、
第1の時間期間に対応する1つ以上の障害物のそれぞれの障害物ステータスを取得するステップと、
前記障害物ステータスに基づいて、前記複数の時空間グリッドのうちの複数の航行可能グリッドおよび複数の航行不可能グリッドを決定するステップと、
前記複数の航行可能グリッドに基づいて、前記航走体のための経路を決定するステップと、
を含む、方法。
【請求項２】
前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定するステップは、
前記障害物ステータスに基づいて、前記1つ以上の障害物のそれぞれについて障害物体積を決定するステップと、
前記1つ以上の障害物の前記障害物体積に基づいて、前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定するステップと、
をさらに含む、請求項1に記載の方法。
【請求項３】
前記方法は、
前記第1の時間期間に対応する前記障害物体積に基づいて、前記1つ以上の障害物のそれぞれの障害物軌道投影を決定するステップと、
前記1つ以上の障害物の前記障害物軌道投影に基づいて、前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定するステップと、
をさらに含む、請求項2に記載の方法。
【請求項４】
前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定するステップは、
前記障害物ステータスに基づいて、前記1つ以上の障害物のそれぞれに関連するファジィ集合を決定するステップと、
前記ファジィ集合に基づいて、前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定するステップと、
をさらに含む、請求項1から3のいずれか一項に記載の方法。
【請求項５】
前記方法は、
前記航走体の目的地を決定するステップと、
前記複数の航行可能グリッドの少なくとも一部について、2つの隣接する航行可能グリッド間のコスト関数を決定するステップと、
前記航走体の現在のグリッドと前記航走体の前記目的地との間のヒューリスティック関数を決定するステップと、
前記航走体の前記目的地、複数のコスト関数、および前記ヒューリスティック関数に基づいて、前記航走体のための前記経路を決定するステップと、
をさらに含む、請求項1から4のいずれか一項に記載の方法。
【請求項６】
時空間マップに基づく、航走体のための表面航行のためのシステムであって、
命令のセットを含む少なくとも1つの非一時的記憶媒体と、
前記少なくとも1つの非一時的記憶媒体と通信する少なくとも1つのプロセッサであって、前記命令のセットを実行するとき、前記少なくとも1つのプロセッサは、
第1の領域の時空間マップを決定し、前記時空間マップは複数の時空間グリッドを含み、各時空間グリッドは、前記時空間グリッドに対応する時間的情報および地理的情報を含み、
第1の時間期間に対応する1つ以上の障害物のそれぞれの障害物ステータスを取得し、
前記障害物ステータスに基づいて、前記複数の時空間グリッドのうちの複数の航行可能グリッドおよび複数の航行不可能グリッドを決定し、
前記複数の航行可能グリッドに基づいて、前記航走体のための経路を決定する、
ように指示される、少なくとも1つのプロセッサと、
を備える、システム。
【請求項７】
前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定することは、
前記障害物ステータスに基づいて、前記1つ以上の障害物のそれぞれについて障害物体積を決定することと、
前記1つ以上の障害物の前記障害物体積に基づいて、前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定することと、
をさらに含む、請求項6に記載のシステム。
【請求項８】
前記システムは、
前記第1の時間期間に対応する前記障害物体積に基づいて、前記1つ以上の障害物のそれぞれの障害物軌道投影を決定し、
前記1つ以上の障害物の前記障害物軌道投影に基づいて、前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定する、
ようにさらに構成される、請求項7に記載のシステム。
【請求項９】
前記障害物体積は、前記障害物の輪郭に基づいて決定される、請求項7または8に記載のシステム。
【請求項１０】
前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定することは、
前記障害物ステータスに基づいて、前記1つ以上の障害物のそれぞれに関連するファジィ集合を決定することと、
前記ファジィ集合に基づいて、前記複数の航行可能グリッドおよび前記複数の航行不可能グリッドを決定することと、
をさらに含む、請求項6から9のいずれか一項に記載のシステム。
【請求項１１】
前記ファジィ集合を決定することは、
第1の基準に基づいて、前記障害物に関連する航行不可能領域を決定することと、
前記航行不可能領域に基づいて、前記ファジィ集合を決定することと、
をさらに含む、請求項10に記載のシステム。
【請求項１２】
前記システムは、
前記航走体の目的地を決定し、
前記複数の航行可能グリッドの少なくとも一部について、2つの隣接する航行可能グリッド間のコスト関数を決定し、
前記航走体の現在のグリッドと前記航走体の前記目的地との間のヒューリスティック関数を決定し、
前記航走体の前記目的地、複数のコスト関数、および前記ヒューリスティック関数に基づいて、前記航走体のための前記経路を決定する、
ようにさらに構成される、請求項6から11のいずれか一項に記載のシステム。
【請求項１３】
前記コスト関数は、前記2つの隣接する航行可能グリッドの時間的情報および地理的情報に基づいて決定される、請求項12に記載のシステム。
【請求項１４】
前記ヒューリスティック関数は、前記航走体の前記現在のグリッドおよび前記航走体の前記目的地の時間的情報および地理的情報に基づいて決定される、請求項12または13に記載のシステム。
【請求項１５】
実行可能命令を含む非一時的コンピュータ可読媒体であって、前記実行可能命令は、少なくとも1つのプロセッサによって実行されると、前記少なくとも1つのプロセッサに、
第1の領域の時空間マップを決定するステップであって、前記時空間マップは、複数の時空間グリッドを含み、各時空間グリッドは、前記時空間グリッドに対応する時間的情報および地理的情報を含む、ステップと、
第1の時間期間に対応する1つ以上の障害物のそれぞれの障害物ステータスを取得するステップと、
前記障害物ステータスに基づいて、前記複数の時空間グリッドのうちの複数の航行可能グリッドおよび複数の航行不可能グリッドを決定するステップと、
前記複数の航行可能グリッドに基づいて、航走体のための経路を決定するステップと、
を含む、方法を実行させる、非一時的コンピュータ可読媒体。
【国際調査報告】
2021513124.tif 000024
2021513124.tif 000025