(57)【要約】３次元（３Ｄ）環境内で位置特定を実施する際に使用するための方法であって、本方法は、１つ以上の電子処理デバイスにおいて、少なくとも１つのレーザセンサによって実施されるローカル走査から、少なくとも部分的に、ローカル走査から取得されるローカル点群内の点から少なくとも１つのレーザセンサに返される放射のパワーに基づいて、強度データを決定するステップと、強度データを使用して、ローカル点群に関する第１の強度記述子を計算するステップと、それぞれ３Ｄ環境のマップの個別の部分と関連付けられる、複数の事前に計算された第２の強度記述子を読み出すステップと、第１の強度記述子と第２の強度記述子のうちの少なくともいくつかを比較するステップと、少なくとも部分的に、比較の結果に従って、マップに対する場所を決定するステップとを含む。
2020532734.tif 000002
【特許請求の範囲】
【請求項１】
３次元（３Ｄ）環境内で位置特定を実施する際に使用するための方法であって、前記方法は、１つ以上の電子処理デバイスにおいて、
ａ）少なくとも１つのレーザセンサによって実施されるローカル走査から、少なくとも部分的に、前記ローカル走査から取得されるローカル点群内の点から前記少なくとも１つのレーザセンサに返される放射のパワーに基づいて、強度データを決定することと、
ｂ）前記強度データを使用して、前記ローカル点群に関する第１の強度記述子を計算することと、
ｃ）複数の事前に計算された第２の強度記述子を読み出すことであって、前記複数の事前に計算された第２の強度記述子は、それぞれが前記３Ｄ環境のマップの個別の部分と関連付けられる、ことと、
ｄ）前記第１の強度記述子と前記第２の強度記述子のうちの少なくともいくつかとを比較することと、
ｅ）少なくとも部分的に、前記比較の結果に従って、前記マップに対する場所を決定することと
を含む、方法。
【請求項２】
前記方法は、前記１つ以上の電子処理デバイスにおいて、前記ローカル点群内の強度データの分布に関する少なくとも１つの統計的測定値に基づいて、前記第１の強度記述子を計算することを含む、請求項１に記載の方法。
【請求項３】
前記方法は、前記１つ以上の電子処理デバイスにおいて、前記第１の強度記述子を計算することを含み、前記第１の強度記述子を計算することは、
ａ）前記ローカル点群を複数の空間的に分散されたローカル点群セグメントに分割することと、
ｂ）各ローカル点群セグメントに対し、前記ローカル点群セグメント内の強度データの分布に関する統計的測定値に基づいて、第１の強度記述子セグメントを計算することと、
ｃ）各第１の強度記述子セグメントを使用して、前記第１の強度記述子を計算することと
によって行われる、請求項２に記載の方法。
【請求項４】
前記統計的測定値は、複数の強度値のそれぞれの周波数の分布を示す、請求項２または請求項３に記載の方法。
【請求項５】
前記ローカル点群セグメントは、少なくとも部分的に、球状構造を有する、請求項４に記載の方法。
【請求項６】
前記ローカル点群セグメントは、
ａ）複数の同心球状領域と、
ｂ）八分円にセグメント化された少なくとも２つの同心球状領域と
のうちの少なくとも１つを含む、請求項５に記載の方法。
【請求項７】
外側球状領域の半径は、前記センサの範囲に基づいており、１つ以上の内側球状領域の半径は、各球状領域が類似数のローカル点群点を含有するように選択される、請求項６に記載の方法。
【請求項８】
前記第２の強度記述子は、前記３Ｄ環境のマップに対応する点群内の点と関連付けられた強度データを使用して、事前に計算され、前記強度データは、少なくとも部分的に、前記３Ｄ環境の事前に実施された走査内の前記点群内の点から前記少なくとも１つのレーザセンサに返される放射のパワーに基づいている、前記請求項のいずれか１項に記載の方法。
【請求項９】
各第２の強度記述子は、前記マップの個別の部分に対応する前記点群の一部の点群セグメントに関して取得される第２の強度記述子セグメントを含む、請求項８に記載の方法。
【請求項１０】
前記複数の第２の強度記述子は、データ記憶装置内に記憶され、前記方法は、前記１つ以上の電子処理デバイスにおいて、前記複数の第２の強度記述子を前記データ記憶装置から読み出すことを含む、請求項９に記載の方法。
【請求項１１】
前記方法は、前記１つ以上の電子処理デバイスにおいて、
ａ）前記第１の強度記述子を第２の強度記述子と比較することであって、前記第１の強度記述子を第２の強度記述子と比較することは、
ｉ）前記第１の強度記述子セグメントと前記第２の強度記述子セグメントとを比較することと、
ｉｉ）前記比較の結果に基づいて、類似性値を決定することと
によって行われる、ことと、
ｂ）前記類似性値に基づいて、１つ以上の第２の強度記述子を選択することと
を含む、請求項９または請求項１０に記載の方法。
【請求項１２】
前記方法は、前記１つ以上の電子処理デバイスにおいて、
ａ）前記第１の強度記述子と第２の強度記述子との間の各比較に対し、
ｉ）前記第２の強度記述子の複数の相対的配向を決定することと、
ｉｉ）前記第２の強度記述子の複数の相対的配向の各々に対し、前記第１の強度記述子セグメントと前記第２の強度記述子セグメントとを比較することと、
ｂ）各配向に対し、類似性値を決定することと、
ｃ）最小類似性値を選択することと
を含む、請求項１１に記載の方法。
【請求項１３】
前記方法は、前記１つ以上の電子処理デバイスにおいて、前記第１の強度記述子と個別の第２の強度記述子との間の類似性値を使用して、前記マップの部分を潜在的場所としてランク付けすることを含む、請求項１１または請求項１２に記載の方法。
【請求項１４】
前記方法は、前記１つ以上の電子処理デバイスにおいて、
ａ）前記マップの部分の潜在的場所としてのランク付けに基づいて選択された前記マップの少なくとも一部を使用して、サブマップを生成することと、
ｂ）幾何学的認識を前記サブマップ内で実施することと
を含む、請求項１３に記載の方法。
【請求項１５】
前記方法は、前記１つ以上の電子処理デバイスにおいて、前記幾何学的認識を実施することを含み、前記幾何学的認識を実施することは、
ａ）ローカル特徴点を前記ローカル点群から抽出することと、
ｂ）各ローカル特徴点に対し、ローカル幾何学的記述子を計算することと、
ｃ）前記サブマップ内に含まれる前記マップの部分と関連付けられたサブマップ特徴点を使用して計算された事前に計算されたサブマップ幾何学的記述子を読み出すことと、
ｄ）ローカル幾何学的記述子とサブマップ幾何学的記述子との間の対応を決定することと、
ｅ）幾何学的一貫性に基づいて、対応をクラスタ化し、１つ以上の候補クラスタを形成することと、
ｆ）各候補クラスタに対し、変換を決定することと
によって行われる、請求項１４に記載の方法。
【請求項１６】
前記方法は、前記１つ以上の電子処理デバイスにおいて、
ａ）最高数の対応を有する候補クラスタを選択することと、
ｂ）前記選択された候補クラスタ内の対応の数を第１の閾値と比較することと、
ｃ）ｉ）対応の数が前記第１の閾値を下回る場合、前記選択された候補クラスタが偽マッチングであることを決定すること、および
ｉｉ）対応の数が前記第１の閾値を上回る場合、前記選択された候補クラスタが最も可能性が高い場所を示すことを決定すること
のうちの少なくとも１つと
を含む、請求項１５に記載の方法。
【請求項１７】
最も可能性が高い場所を示す前記候補クラスタに関して、前記方法は、前記１つ以上の電子処理デバイスにおいて、前記変換を精緻化し、前記ローカル点群と前記サブマップと関連付けられたサブマップ点群とを整合させることを含む、請求項１６に記載の方法。
【請求項１８】
前記方法は、前記１つ以上の電子処理デバイスにおいて、反復最近傍点（ＩＣＰ）を前記ローカルおよびサブマップ点群の少なくとも一部上で実施し、前記変換を精緻化し、姿勢を決定することを含む、請求項１７に記載の方法。
【請求項１９】
前記方法は、前記１つ以上の電子処理デバイスにおいて、
ａ）前記ローカルおよびサブマップ点群が整合される程度を示す適合性スコアを決定することと、
ｂ）前記適合性スコアを第２の閾値と比較することと、
ｃ）前記比較の結果に応じて、前記場所を選択的に照合することと
を含む、請求項１８に記載の方法。
【請求項２０】
前記方法は、前記１つ以上の電子処理デバイスにおいて、新しいサブマップを生成することを含み、前記新しいサブマップを生成することは、
ａ）対応の数が前記第１の閾値を下回ることと、
ｂ）前記適合性スコアが前記第２の閾値を上回ることと
のうちの１つの場合に行われる、請求項１９に記載の方法。
【請求項２１】
前記方法は、前記１つ以上の電子処理デバイスにおいて、少なくとも部分的に、前記マップの部分の潜在的場所としてのランク付けに基づいて選択された前記マップの他の部分を使用して、新しいサブマップを生成することを含む、請求項２０に記載の方法。
【請求項２２】
前記方法は、前記１つ以上の処理デバイスにおいて、
ａ）前記サブマップ内に含まれている潜在的場所の数を決定することと、
ｂ）ｉ）潜在的場所の数が定義された最大値に到達した場合、前記位置特定方法を終了することと、
ｉｉ）潜在的場所の数が前記定義された最大値を下回る場合、前記サブマップのサイズを増加させることと
のうちの少なくとも１つと
を含む、請求項２１に記載の方法。
【請求項２３】
前記ローカル走査は、
ａ）定常走査と、
ｂ）モバイルロボットまたは自律車両と関連付けられたウェイクアップ走査と、
ｃ）ループ閉鎖走査と
のうちの少なくとも１つである、前記請求項のいずれか１項に記載の方法。
【請求項２４】
前記少なくとも１つのレーザセンサは、光結像検出および測距（ＬｉＤＡＲ）センサである、前記請求項のいずれか１項に記載の方法。
【請求項２５】
前記マップの部分は、マッピング軌道に沿って前記マップから抽出される、前記請求項のいずれか１項に記載の方法。
【請求項２６】
前記マッピング軌道は、事前に定義された長さのセグメントに分割され、前記マップの各部分は、前記マッピング軌道の個別のセグメントに沿って進行されるにつれて前記少なくとも１つのセンサから取得される点群として定義される、請求項２５に記載の方法。
【請求項２７】
３次元（３Ｄ）環境内で位置特定を実施する際に使用するためのシステムであって、前記システムは、１つ以上の電子処理デバイスを含み、前記１つ以上の電子処理デバイスは、
ａ）少なくとも１つのレーザセンサによって実施されるローカル走査から、少なくとも部分的に、前記ローカル走査から取得されるローカル点群内の点から前記少なくとも１つのレーザセンサに返される放射のパワーに基づいて、強度データを決定することと、
ｂ）前記強度データを使用して、前記ローカル点群に関する第１の強度記述子を計算することと、
ｃ）複数の事前に計算された第２の強度記述子を読み出すことであって、前記複数の事前に計算された第２の強度記述子は、それぞれが前記３Ｄ環境のマップの個別の部分と関連付けられる、ことと、
ｄ）前記第１の強度記述子と前記第２の強度記述子のうちの少なくともいくつかとを比較することと、
ｅ）少なくとも部分的に、前記比較の結果に従って、前記マップに対する場所を決定することと
を行うように構成される、システム。
【請求項２８】
前記システムは、前記ローカル走査を実施するように構成される少なくとも１つのレーザセンサを含む、請求項２７に記載のシステム。
【請求項２９】
前記少なくとも１つのセンサは、光結像検出および測距（ＬｉＤＡＲ）センサである、請求項２８に記載のシステム。
【請求項３０】
前記システムはさらに、前記複数の第２の強度記述子を含有するデータ記憶装置を含み、前記データ記憶装置は、前記複数の第２の強度記述子を読み出すために、１つ以上の電子処理デバイスによってアクセス可能である、請求項２７−２９のいずれか１項に記載のシステム。
【請求項３１】
前記少なくとも１つのレーザセンサ、１つ以上の電子処理デバイス、およびデータ記憶装置は、モバイルロボットまたは自律車両にオンボードで位置する、請求項２７または請求項３０に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元（３Ｄ）環境内で位置特定を実施する際に使用するための方法およびシステムに関する。本方法およびシステムは、モバイルロボットおよび自律車両ナビゲーションに対する特定の用途を有する。
【背景技術】
【０００２】
任意の以前の刊行物（またはそれから導出される情報）または公知の任意の事物の本明細書における参照は、以前の刊行物（またはそれから導出される情報）または公知の事物が、本明細書が関連する努力傾注分野における共通の一般的知識の一部を形成することの確認または承認または任意の形態の提案ではなく、かつそのように捉えられるべきではない。
【０００３】
グローバル位置特定は、自律的ロボットナビゲーションのための重要な要素である。これは、ロボット「ウェイクアップ」問題、「迷子または誘拐」ロボット問題、および同時位置特定およびマッピング（ＳＬＡＭ）におけるループ閉鎖等のタスクのために使用される。グローバル位置特定タスクは、２つの主要な要素、すなわち、ｉ）以前に訪問した場所の認識と、ｉｉ）再訪問した場所の基準フレームに対する位置および配向（姿勢）推定とから成る。場所認識および姿勢推定の両方が、完全グローバル位置特定を達成するために要求される。典型的には、グローバル位置特定が実施されるとき、環境内のある場所を走査すること（ローカル走査）によって取得される小点群が、事前に取得された走査データ（グローバルマップ）に対して比較され、相対的変換が、算出される。
【０００４】
グローバル位置特定タスクに取り組む古典的アプローチは、カルマンフィルタまたはモンテカルロ位置特定（粒子フィルタアプローチ）等の回帰的推定方法を使用するためのものである。これらのアルゴリズムは、ロボットセンサによって取得されるデータが、限定され、雑音が多い時代に開発されている。グローバルマップ内のロボットの位置は、周囲の静的観察によって一意に決定することが不可能であった。したがって、これらの方法では、ロボットは、最初に、動き回り、環境を観察し、確実性が容認可能レベルまで増加するまで、ある位置にあることの確率を更新しなければならない。
【０００５】
また、全地球測位システム（ＧＰＳ）または外部ビーコン等の外部センサインフラストラクチャを使用して位置特定を実施することが可能性として考えられるが、これは、自律車両またはロボットが、例えば、ＧＰＳが拒否される屋内場所においてナビゲートし得る、多くの環境において利用不可能であるため、限定される。カメラもまた、場所認識のために使用され得るが、しかしながら、それらは、好ましくない照明条件下では、より低い性能に悩まされ、暗所で位置特定を実施するためには使用不可能である。
【０００６】
例えば、３Ｄ光結像検出および測距（ＬｉＤＡＲ）センサを使用する、３Ｄ点群内のグローバル位置特定のためのいくつかの方法が、提案されている。グローバル記述子（幾何学情報に基づいて、ローカル走査全体に関する単一統計を算出する）の使用が、点仰角のヒストグラムによって場所を説明するためのものとして公知である。代替方法は、点群を立方体グリッドに分割し、密度関数を計算することによって、記述子を作成するものであって、これは、後にヒストグラムにまとめられる形状を説明する。グローバル記述子に関する１つの問題は、グローバルマップが、軌道に沿った場所の離散セットとして解釈され、各場所が、グラフ状構造を形成する定義された原点を有するという事実である。この場合、可能性として考えられるロボット場所のみが、グラフ頂点内にある。ロボットが、頂点間にある、またはオリジナル軌道からずれているとき、正確な場所は、決定されることができない。
【０００７】
また、点群内の幾何学特徴に基づいて、ローカル記述子を使用して位置特定を実施することが公知である。複数の特徴点が、点群から選択され、（点群より有意に小さい半径の）ローカル記述子が、それらの周囲で計算される。認識が、異なる群間の最も類似する記述子を見出すことによって実施される。本タイプの幾何学的認識プロシージャは、特に、大規模マップに関して、非効率的かつ算出上複雑である。
【０００８】
ローカル幾何学的記述子は、変換および正確な姿勢を取得するために使用されることができるが、本アプローチに基づく位置特定方法は、算出上非効率的であって、リアルタイム用途に好適ではない。グローバル記述子の使用は、次元低減および対応検索のための効率的方法を提供する限りにおいて有用であるが、しかしながら、それらは、相対的変換および姿勢を提供することができない。
【０００９】
ＧＰＳインフラストラクチャおよび同等物を伴わずに、かつ任意の照明条件下において、非構造化環境内で迅速に位置特定することが可能である、位置特定のためのより効率的アルゴリズムが、したがって、必要とされる。
【００１０】
さらに、３Ｄ  ＬｉＤＡＲ等のレーザセンサのみを使用して、定常走査から位置特定することが可能であることが有利であろう。
【００１１】
本背景およびそれと関連付けられた問題および難点に照らして、本発明が開発された。
【発明の概要】
【課題を解決するための手段】
【００１２】
１つの広範な形態では、本発明の側面は、３次元（３Ｄ）環境内で位置特定を実施する際に使用するための方法であって、該方法は、１つ以上の電子処理デバイスにおいて、
ａ）少なくとも１つのレーザセンサによって実施されるローカル走査から、少なくとも部分的に、ローカル走査から取得されるローカル点群内の点から少なくとも１つのレーザセンサに返される放射のパワーに基づいて、強度データを決定することと、
ｂ）強度データを使用して、ローカル点群に関する第１の強度記述子を計算することと、
ｃ）複数の事前に計算された第２の強度記述子を読み出すことであって、該複数の事前に計算された第２の強度記述子は、それぞれが３Ｄ環境のマップの個別の部分と関連付けられる、ことと、
ｄ）第１の強度記述子と第２の強度記述子のうちの少なくともいくつかとを比較することと、
ｅ）少なくとも部分的に、比較の結果に従って、マップに対する場所を決定することと
を含む、方法を提供することを模索する。
【００１３】
一実施形態では、本方法は、１つ以上の電子処理デバイスにおいて、ローカル点群内の強度データの分布に関する少なくとも１つの統計的測定値に基づいて、第１の強度記述子を計算することを含む。
【００１４】
一実施形態では、本方法は、１つ以上の電子処理デバイスにおいて、第１の強度記述子を計算することを含み、該第１の強度記述子を計算することは、
ａ）ローカル点群を複数の空間的に分散されたローカル点群セグメントに分割することと、
ｂ）各ローカル点群セグメントに対し、ローカル点群セグメント内の強度データの分布に関する統計的測定値に基づいて、第１の強度記述子セグメントを計算することと、
ｃ）各第１の強度記述子セグメントを使用して、第１の強度記述子を計算することと
によって行われる。
【００１５】
一実施形態では、統計的測定値は、複数の強度値のそれぞれの周波数の分布を示す。
【００１６】
一実施形態では、ローカル点群セグメントは、少なくとも部分的に、球状構造を有する。
【００１７】
一実施形態では、ローカル点群セグメントは、
ａ）複数の同心球状領域と、
ｂ）八分円にセグメント化された少なくとも２つの同心球状領域と
のうちの少なくとも１つを含む。
【００１８】
一実施形態では、外側球状領域の半径は、センサの範囲に基づいており、１つ以上の内側球状領域の半径は、各球状領域が類似数のローカル点群点を含有するように選択される。
【００１９】
一実施形態では、第２の強度記述子は、３Ｄ環境のマップに対応する点群内の点と関連付けられた強度データを使用して、事前に計算され、強度データは、少なくとも部分的に、３Ｄ環境の事前に実施された走査内の点群内の点から少なくとも１つのレーザセンサに返される放射のパワーに基づいている。
【００２０】
一実施形態では、各第２の強度記述子は、マップの個別の部分に対応する点群の一部の点群セグメントに関して取得される第２の強度記述子セグメントを含む。
【００２１】
一実施形態では、複数の第２の強度記述子は、データ記憶装置内に記憶され、本方法は、１つ以上の電子処理デバイスにおいて、複数の第２の強度記述子をデータ記憶装置から読み出すことを含む。
【００２２】
一実施形態では、本方法は、１つ以上の電子処理デバイスにおいて、
ａ）第１の強度記述子と第２の強度記述子を比較することであって、該第１の強度記述子と第２の強度記述子を比較することは、
ｉ）第１の強度記述子セグメントと第２の強度記述子セグメントとを比較することと、
ｉｉ）比較の結果に基づいて、類似性値を決定することと
によって行われる、ステップと、
ｂ）類似性値に基づいて、１つ以上の第２の強度記述子を選択することと
を含む。
【００２３】
一実施形態では、本方法は、１つ以上の電子処理デバイスにおいて、
ａ）第１の強度記述子と第２の強度記述子との間の各比較に対し、
ｉ）第２の強度記述子の複数の相対的配向を決定すること、
ｉｉ）第２の強度記述子の複数の相対的配向の各々に対し、第１の強度記述子セグメントと第２の強度記述子セグメントとを比較することと、
ｂ）各配向に対し、類似性値を決定することと、
ｃ）最小類似性値を決定することと
を含む。
【００２４】
一実施形態では、本方法は、１つ以上の電子処理デバイスにおいて、第１の強度記述子と個別の第２の強度記述子との間の類似性値を使用して、マップの部分を潜在的場所としてランク付けすることを含む。
【００２５】
一実施形態では、本方法は、１つ以上の電子処理デバイスにおいて、
ａ）マップの部分の潜在的場所としてのランク付けに基づいて、選択されたマップの少なくとも一部を使用して、サブマップを生成することと、
ｂ）幾何学的認識をサブマップ内で実施することと
を含む。
【００２６】
一実施形態では、本方法は、１つ以上の電子処理デバイスにおいて、幾何学的認識を実施することを含み、該幾何学的認識を実施することは、
ａ）ローカル特徴点をローカル点群から抽出することと、
ｂ）各ローカル特徴点に対し、ローカル幾何学的記述子を計算することと、
ｃ）サブマップ内に含まれるマップの部分と関連付けられたサブマップ特徴点を使用して計算された事前に計算されたサブマップ幾何学的記述子を読み出すことと、
ｄ）ローカル幾何学的記述子とサブマップ幾何学的記述子との間の対応を決定することと、
ｅ）幾何学的一貫性に基づいて、対応をクラスタ化し、１つ以上の候補クラスタを形成することと、
ｆ）各候補クラスタに対し、変換を決定することと
によって行われる。
【００２７】
一実施形態では、本方法は、１つ以上の電子処理デバイスにおいて、
ａ）最高数の対応を有する候補クラスタを選択することと、
ｂ）選択された候補クラスタ内の対応の数を第１の閾値と比較することと、
ｃ）ｉ）対応の数が第１の閾値を下回る場合、選択された候補クラスタが偽マッチングであることを決定すること、および
ｉｉ）対応の数が第１の閾値を上回る場合、選択された候補クラスタが最も可能性が高い場所を示すことを決定することと
のうちの少なくとも１つと
を含む。
【００２８】
一実施形態では、最も可能性が高い場所を示す候補クラスタに関して、本方法は、１つ以上の電子処理デバイスにおいて、変換を精緻化し、ローカル点群とサブマップと関連付けられたサブマップ点群を整合させることを含む。
【００２９】
一実施形態では、本方法は、１つ以上の電子処理デバイスにおいて、反復最近傍点（ＩＣＰ）をローカルおよびサブマップ点群の少なくとも一部上で実施し、変換を精緻化し、姿勢を決定することを含む。
【００３０】
一実施形態では、本方法は、１つ以上の電子処理デバイスにおいて、
ａ）ローカルおよびサブマップ点群が整合される程度を示す適合性スコアを決定することと、
ｂ）適合性スコアを第２の閾値と比較することと、
ｃ）比較の結果に応じて、場所を選択的に照合することと
を含む。
【００３１】
一実施形態では、本方法は、１つ以上の電子処理デバイスにおいて、新しいサブマップを生成することを含み、該新しいサブマップを生成することは、
ａ）対応の数が第１の閾値を下回ることと、
ｂ）適合性スコアが第２の閾値を上回ることと
のうちの１つの場合に行われる。
【００３２】
一実施形態では、本方法は、１つ以上の電子処理デバイスにおいて、少なくとも部分的に、マップの部分の潜在的場所としてのランク付けに基づいて選択されたマップの他の部分を使用して、新しいサブマップを生成することを含む。
【００３３】
一実施形態では、本方法は、１つ以上の処理デバイスにおいて、
ａ）サブマップ内に含まれている潜在的場所の数を決定することと、
ｂ）ｉ）潜在的場所の数が定義された最大値に到達した場合、位置特定方法を終了することと、
ｉｉ）潜在的場所の数が定義された最大値を下回る場合、サブマップのサイズを増加させることと
のうちの少なくとも１つと
を含む。
【００３４】
一実施形態では、ローカル走査は、
ａ）定常走査と、
ｂ）モバイルロボットまたは自律車両と関連付けられたウェイクアップ走査と、
ｃ）ループ閉鎖走査と
のうちの少なくとも１つである。
【００３５】
一実施形態では、少なくとも１つのレーザセンサは、光結像検出および測距（ＬｉＤＡＲ）センサである。
【００３６】
一実施形態では、マップの部分は、マッピング軌道に沿ったマップから抽出される。
【００３７】
一実施形態では、マッピング軌道は、事前に定義された長さのセグメントに分割され、マップの各部分は、マッピング軌道の個別のセグメントに沿って進行されるにつれて少なくとも１つのセンサから取得される、点群として定義される。
【００３８】
別の広範な形態では、本発明の側面は、３次元（３Ｄ）環境内で位置特定を実施する際に使用するためのシステムであって、該システムは、１つ以上の電子処理デバイスを含み、該１つ以上の電子処理デバイスは、
ａ）少なくとも１つのレーザセンサによって実施されるローカル走査から、少なくとも部分的に、ローカル走査から取得されるローカル点群内の点から少なくとも１つのレーザセンサに返される放射のパワーに基づいて、強度データを決定することと、
ｂ）強度データを使用して、ローカル点群に関する第１の強度記述子を計算することと、
ｃ）複数の事前に計算された第２の強度記述子を読み出すことであって、該複数の事前に計算された第２の強度記述子は、それぞれが３Ｄ環境のマップの個別の部分と関連付けられる、ことと、
ｄ）第１の強度記述子と第２の強度記述子のうちの少なくともいくつかとを比較することと、
ｅ）少なくとも部分的に、比較の結果に従って、マップに対する場所を決定することと
を行うように構成される、システムを提供することを模索する。
【００３９】
一実施形態では、システムは、ローカル走査を実施するように構成される、少なくとも１つのレーザセンサを含む。
【００４０】
一実施形態では、少なくとも１つのセンサは、光結像検出および測距（ＬｉＤＡＲ）センサである。
【００４１】
一実施形態では、本システムはさらに、複数の第２の強度記述子を含有するデータ記憶装置を含み、データ記憶装置は、複数の第２の強度記述子を読み出すために、１つ以上の電子処理デバイスによってアクセス可能である。
【００４２】
一実施形態では、少なくとも１つのレーザセンサ、１つ以上の電子処理デバイス、およびデータ記憶装置は、モバイルロボットまたは自律車両にオンボードで位置する。
【００４３】
本発明の広範な形態およびその個別の特徴は、相互互換的におよび／または独立して併用されることができ、別個の広範な形態の参照は、限定することを意図するものではないことを理解されたい。
【図面の簡単な説明】
【００４４】
本発明の非限定的実施例が、ここで、付随の図面を参照して説明されるであろう。
【００４５】
【図１】図１は、３Ｄ環境内で位置特定を実施する際に使用するための方法の実施例のフローチャートである。
【００４６】
【図２】図２は、３Ｄ環境内で位置特定を実施する際に使用するためのシステムの実施例の概略図である。
【００４７】
【図３】図３は、図２の処理システムの実施例の概略図である。
【００４８】
【図４Ａ】図４Ａ−４Ｃは、３Ｄ環境内で位置特定を実施する具体的プロセスの実施例のフローチャートを提供する。
【図４Ｂ】図４Ａ−４Ｃは、３Ｄ環境内で位置特定を実施する具体的プロセスの実施例のフローチャートを提供する。
【図４Ｃ】図４Ａ−４Ｃは、３Ｄ環境内で位置特定を実施する具体的プロセスの実施例のフローチャートを提供する。
【００４９】
【図５】図５は、ローカル走査と関連付けられた第１の強度記述子を計算する実施例のフローチャートである。
【００５０】
【図６Ａ】図６Ａは、強度記述子の構造の実施例である。
【００５１】
【図６Ｂ】図６Ｂは、空間的に分散されたセグメントに分割される例示的ウェイクアップ走査の実施例である。
【００５２】
【図７】図７は、完全に異なる場所に関する強度記述子間の比較の例示的略図である。
【００５３】
【図８】図８は、第１の強度記述子との比較目的のための４つの可能性として考えられる方向に配向される基準フレームを示す、第２の強度記述子の実施例である。
【００５４】
【図９】図９は、３Ｄ環境のマップの事前処理を実施する実施例のフローチャートである。
【００５５】
【図１０Ａ】図１０Ａは、実験が実施された敷地の衛星写真である。
【００５６】
【図１０Ｂ】図１０Ｂは、マッピング軌道が白色で示される、図１０Ａの敷地をマッピングすることによって取得される点群の実施例である。
【００５７】
【図１０Ｃ】図１０Ｃは、従来における場所の数に対する位置特定成功率のグラフである。
【００５８】
【図１０Ｄ】図１０Ｄは、マッピング軌道から異なる距離におけるウェイクアップ場所に関する位置特定成功率のグラフである。
【００５９】
【図１０Ｅ】図１０Ｅは、マッピング軌道から異なる距離におけるウェイクアップ場所に関して正常に位置特定するために要求される場所候補の数のグラフである。
【００６０】
【図１０Ｆ】図１０Ｆは、伝統的幾何学形状ベースのアプローチのみの使用と比較した、本方法を使用した位置特定に関する算出時間の対数グラフである。
【００６１】
【図１０Ｇ】図１０Ｇは、強度ベースの認識を使用してマップから抽出された場所候補を示すことによる、システムを使用して取得される検索空間の低減の実施例を図示する。
【発明を実施するための形態】
【００６２】
３次元（３Ｄ）環境内で位置特定を実施する際に使用するための方法の実施例が、ここで、図１を参照して説明されるであろう。
【００６３】
例証目的のために、本方法は、少なくとも部分的に、自律車両またはモバイルロボット（以降、「ロボット」）と関連付けられた１つ以上の処理システムの一部を形成する１つ以上の電子処理デバイスを使用して実施されると仮定される。１つ以上の電子処理デバイスは、データを、ロボットにオンボードで搭載され、ロボットの周囲の走査を実施することが可能である、光結像検出および測距（ＬｉＤＡＲ）センサ等の少なくとも１つのレーザセンサから受信するように構成される。
【００６４】
本実施例では、ステップ１００において、本方法は、少なくとも１つのレーザセンサによって実施されるローカル走査から、少なくとも部分的に、ローカル走査から取得されるローカル点群内の点から少なくとも１つのレーザセンサに返される放射のパワーに基づいて、強度データを決定するステップを含む。ローカル走査とは、「ウェイクアップ」に応じた、３Ｄ環境の一部、例えば、ロボットのすぐ周囲の走査であることを理解されたい。ローカル走査は、ロボットが定常である間に実施され、ロボットが、移動する前に、３Ｄ環境内のその位置を決定することを可能にしてもよい。
【００６５】
レーザセンサによって実施されるローカル走査は、ロボットの周囲のローカル点群から成る。ローカル点群は、そこから環境の構造が決定される、空間情報から成る。測距情報に加え、レーザセンサはまた、点毎に、強度の測定値を提供することができ、これは、表面から反射後の戻り強度である。より精密には、強度は、レーザによって放出されたパワーとそれに返されるパワーの比率を指す。用語「強度」は、概して、本開示全体を通して使用されるが、反射率等の関連パラメータもまた、用語「強度」の範囲内に入ると見なされるべきであることを理解されたい。反射率は、センサの固有のパラメータおよび付帯特徴（物体までの距離、入射角、空気密度等）を補償することによって、強度から取得される表面の性質である。
【００６６】
本明細書全体を通して使用されるような用語「ｄｅｔｅｒｍｉｎｉｎｇ（〜を決定する）」または「ｄｅｔｅｒｍｉｎｅ（〜を決定する）」等の関連用語の範囲は、必要データまたは情報を「ｏｂｔａｉｎｉｎｇ（取得する）」、「ｒｅｃｅｉｖｉｎｇ（受信する）」、「ｃａｌｃｕｌａｔｉｎｇ（計算する）」、または「ｄｒｉｖｉｎｇ（導出する）」ことを含むと見なされるものとすることを理解されたい。用語「ｄｅｔｅｒｍｉｎｉｎｇ（〜を決定する）」の使用は、したがって、任意の処理がデータを確認するために要求されることを含意するものではない。
【００６７】
ステップ１１０では、本方法は、強度データを使用して、ローカル点群に関する第１の強度記述子を計算するステップを含む。このように、単一記述子が、データセット（ここでは、約０．５百万点から成り得る、ローカル点群内の各点の強度値）の次元を低減させ、同時に、一意の情報および記述性を維持するために、ローカル点群全体に関して計算される。第１の強度記述子の構造は、下記にさらに詳細に説明されるであろう。
【００６８】
ステップ１２０では、本方法は、下記にさらに詳細に説明されるであろうように、それぞれ３Ｄ環境のマップの個別の部分と関連付けられる、複数の事前に計算された第２の強度記述子を読み出すステップを含む。
【００６９】
第１および第２の強度記述子は、それらが基づく点群をエンコード／説明する、グローバル記述子であることを理解されたい。第１の強度記述子は、ローカル走査から取得されるローカル点群に関するグローバル記述子である。各第２の強度記述子は、マップの個別の部分と関連付けられた点群に関するグローバル記述子である。この点において、下記にさらに説明されるであろうように、３Ｄ環境のマップは、それぞれ、マップ上の一意の場所に対応する、複数のより小さい点群にセグメント化される、グローバルマップ（すなわち、グローバル点群）と見なされ得る。
【００７０】
したがって、本方法は、レーザセンサを使用したマッピング演習、例えば、環境のＳＬＡＭベースのマッピングにおいて事前に決定されている３Ｄ環境の既存のマップ（すなわち、グローバル点群）に依拠することを認識することが重要である。マッピング後、マップは、それぞれ、個別の点群を有する、複数の部分にセグメント化され、第２の強度記述子が、マップの部分またはセグメント毎に決定される。マップの各部分と関連付けられた点群は、原点を部分の中心に有する、「場所」とも称され得る。第２の強度記述子は、データ記憶装置内に記憶され、マップ内で位置特定するために、処理デバイスによってロードされてもよい。
【００７１】
ステップ１３０では、本方法は、第１の強度記述子と第２の強度記述子のうちの少なくともいくつかを比較するステップを含む。典型的には、これは、ローカル走査の第１の強度記述子とマップから抽出された全ての部分（すなわち、場所）の第２の強度記述子との間で実施される、単純線形対応検索（総当たりアプローチである）。マップ内の全ての部分の第２の強度記述子が、比較において使用されてもよいが、正しい場所が見出されていることの信頼度に到達した場合、全ての第２の強度記述子を使用する前に、比較プロセスを終了するためのアルゴリズムが可能性として考えられ得る。
【００７２】
最後に、ステップ１４０では、本方法は、少なくとも部分的に、比較の結果に従って、マップに対する場所を決定するステップを含む。比較ステップの出力は、最も確率の高い場所の選択であって、これは、ローカル走査との最高類似性（強度データに基づく）を有するマップの部分に対応する。いくつかの実施例では、強度ベースの認識は、単独で、マップ内の位置特定を達成するために十分であり得る。しかしながら、場所の正確度は、マップのセグメント化の分解能より良好ではないであろうことを理解されたい。より正確な位置および配向（すなわち、姿勢）は、強度記述子の基準フレーム間の回転差異に基づいて推定され得るが、正確度は、依然として、基準フレーム推定の精度に影響を及ぼすであろう群内の雑音のため、限定されるであろう。他の実施例では、幾何学的認識もまた、強度ベースの認識から決定された最も確率の高い場所を使用して実施されてもよい。下記にさらに詳細に説明されるであろうように、幾何学的認識は、点群間の変換を決定し、姿勢の正確な決定を可能にするために使用されてもよい。さらに、幾何学的認識は、強度ベースの認識が正しいことを検証するために使用されてもよい。
【００７３】
上記に説明される方法は、いくつかの利点を提供する。
【００７４】
最初に、本方法は、グローバル位置特定がレーザセンサ（ＬｉＤＡＲ等）のみからのデータを使用して実施されることを可能にする。本方法は、カメラ等の付加的センサからの情報に依拠せず、ＧＰＳまたはビーコン等の外部センサインフラストラクチャを欠いている非構造化環境内で実施されることができる。実施例として、本方法は、ＧＰＳが拒否される、屋内環境内、またはＧＰＳが、深刻な多重経路に悩まされ、使用不可能になる、産業エリア内のナビゲーションのために利用され得る。本方法はまた、例えば、伝統的カメラが非効果的であろう、好ましくない照明条件および暗所下で実施されてもよい。
【００７５】
本方法は、マップに対するローカル走査の最も可能性が高い位置を決定するための強度記述子の使用に起因して、算出上効率的である。このように、強度ベースの認識は、検索空間を、ロボットの位置の「従来（ｐｒｉｏｒ）」推定値と称され得る、マップの小部分に低減させるために使用されることが可能である。幾何学的認識が、次いで、膨大な算出複雑性を有する、伝統的幾何学的場所認識アルゴリズムに当てはまる、検索空間全体の代わりに、低減された検索空間上で実施され、正確な姿勢を決定し得る。本方法は、したがって、マップ内の近似場所を決定する、または幾何学的認識のための検索空間を有意に低減させ、正確な姿勢を決定するための迅速かつ効率的方法として使用され得る。
【００７６】
上記に説明される方法は、特に、動作の開始時またはトラックまたは経路を見失った場合の位置特定に有用であり得る。これらのタスクは、通常、ウェイクアップおよび迷子ロボット問題と称される。同様に、本方法は、ロボットが以前に訪問した場所に戻ったかどうかを決定することが望ましい、ループ閉鎖等の他のシナリオにおいて使用されてもよい。有利には、本方法は、動き回り、付加的データを集めることを要求せずに、定常ロボットを位置特定するために使用されることができる。これは、時として、ウェイクアップ時、ロボットが、そうでなければ環境のいくつかの部分（またはそれ自体）を損傷させ得ることから、精密に規定された方向に移動しなければならないため、安全上の理由から重要であり得る。
【００７７】
いくつかのさらなる特徴が、ここで説明されるであろう。
【００７８】
一実施例では、本方法は、１つ以上の電子処理デバイスにおいて、ローカル点群内の強度データの分布に関する少なくとも１つの統計的測定値に基づいて、第１の強度記述子を計算するステップを含む。統計的測定値は、ローカル点群内の強度データの次元を低減させながら、他の強度記述子との比較目的のために、十分な一意の情報および記述性を維持するように選択されなければならない。
【００７９】
この点において、典型的には、本方法は、１つ以上の電子処理デバイスにおいて、ローカル点群を複数の空間的に分散されたローカル点群セグメントに分割することによって、第１の強度記述子を計算するステップを含む。ローカル点群セグメント毎に、本方法はさらに、ローカル点群セグメント内の強度データの分布に関する統計的測定値に基づいて、第１の強度記述子セグメントを計算するステップと、各第１の強度記述子セグメントを使用して、第１の強度記述子を計算するステップとを含む。ローカル点群の構造化された分割は、統計と空間内の場所を関連付けることによって、記述子の一意性を確実にする。
【００８０】
単一統計的記述子は、ローカル点群全体のために使用され得るが、しかしながら、次元低減は、記述子が一意性を喪失する範囲まで大きくなりすぎる可能性が高いであろうことに留意されたい。
【００８１】
一実施例では、統計的測定値は、複数の強度値のそれぞれの周波数の分布を示す。非常にコンパクトな形態において点の分布をエンコードするための１つの方法は、ヒストグラムを使用することである。故に、各第１の強度記述子セグメントは、ローカル点群内の空間の具体的領域内の点の強度のヒストグラムであって、第１の強度記述子全体は、したがって、ヒストグラムのグループであって、これはともに、コンパクトかつ効率的様式において、ローカル点群を一意に説明する。
【００８２】
第１の強度記述子の構造が、ここで、説明されるであろう。典型的には、ローカル点群セグメントは、少なくとも部分的に、球状構造を有する。ローカル点群セグメントは、複数の同心球状領域と、八分円にセグメント化された少なくとも２つの同心球状領域とのうちの少なくとも１つを含む。複数の同心球状領域の場合、記述子は、空間セグメント化を伴わない記述子より良好に性能を発揮するであろうが、しかしながら、原点から同一距離であるが、異なる側上に位置する、類似物体を有する、群を区別することに失敗し得る。球状領域を八分円に分割する（すなわち、球体を半球に分割し、次いで、方位角分割を適用する）ことによって、点群内の「左」、「右」、「上」、および「下」の場所を定義することが可能となる。
【００８３】
一実施例では、外側球状領域の半径は、センサの範囲に基づき、１つ以上の内側球状領域の半径は、各球状領域が類似数のローカル点群点を含有するように選択される。
【００８４】
第１の強度記述子の上記の説明と同様に、第２の強度記述子は、３Ｄ環境のマップに対応する点群内の点と関連付けられた強度データを使用して、事前に計算され、強度データは、少なくとも部分的に、３Ｄ環境の事前に実施された走査内の点群内の点から少なくとも１つのレーザセンサに返される放射のパワーに基づくことを理解されたい。さらに、各第２の強度記述子は、マップの個別の部分に対応する点群の部分の個別の点群セグメントに関して取得される、第２の強度記述子セグメントを含む。したがって、第２の強度記述子は、記述子が容易に比較され得るように、第１の強度記述子と同一構造を有することを理解されたい。
【００８５】
典型的には、複数の第２の強度記述子が、データ記憶装置内に記憶され、本方法は、１つ以上の電子処理デバイスにおいて、位置特定方法が実施される度に、複数の第２の強度記述子をデータ記憶装置から読み出すステップを含む。前述のように、第２の強度記述子は、３Ｄ環境が、マッピングされ、マップを取得し、離散化が、実施され、そこから記述子が算出される、マップの部分を抽出するときより速く計算される。
【００８６】
典型的には、本方法は、１つ以上の電子処理デバイスにおいて、第１の強度記述子セグメントと第２の強度記述子セグメントを比較することによって、第１の強度記述子と第２の強度記述子を比較するステップと、比較の結果に基づいて、類似性値を決定するステップと、類似性値に基づいて、１つ以上の第２の強度記述子を選択するステップとを含む。一実施例では、本方法は、第１の強度記述子のヒストグラムと各第２の強度記述子の個別のヒストグラムを比較するステップを伴う。個別のヒストグラムは、ヒストグラム間の類似性測定値を提供する、カイ二乗検定を使用して比較されてもよい。全てのヒストグラム比較の平均が、次いで、決定され、強度記述子間の類似性測定値を提供し得る。１つ以上の最も類似する第２の強度記述子が、次いで、類似性値と、必要とされる以前の検索エリアの規模とに基づいて、選択され得る。
【００８７】
点群の基準フレームは、主成分分析（ＰＣＡ）等の技法を使用して推定されてもよいことを理解されたい。これは、個別の点群の対応する記述子セグメントが比較されていることを確実にするために必要であるため、比較のための重要な考慮点である。ＰＣＡは、直交ベクトルを決定し、基準フレームを形成することができるが、ベクトルの符号を決定することができない。本方向曖昧性解消が、したがって、慎重に検討される必要がある。
【００８８】
故に、一実施例では、本方法は、１つ以上の電子処理デバイスにおいて、第１の強度記述子と第２の強度記述子との間の比較毎に、第２の強度記述子の複数の相対的配向を決定するステップと、第２の強度記述子の複数の相対的配向毎に、第１の強度記述子セグメントと第２の強度記述子セグメントを比較するステップとを含む。類似性値が、次いで、配向毎に決定されることができ、最小類似性値が、個別の第１の強度記述子第２の強度記述子との間の類似性の測定値として選択されることができる。
【００８９】
いったん全ての類似性値が決定されると、本方法は、１つ以上の電子処理デバイスにおいて、第１の強度記述子と個別の第２の強度記述子との間の類似性値を使用して、マップの部分を潜在的場所としてランク付けするステップを含む。このように、強度ベースの認識は、ローカル走査に対応するマップから抽出された場所の類似性に基づいて、ランク付けされた順序を決定することが可能である。
【００９０】
低減された検索エリア（すなわち、マップ内のロボットの場所の「従来」推定値）のサイズが、次いで、選択され得、故に、本方法は、１つ以上の電子処理デバイスにおいて、マップの部分の潜在的場所としてのランク付けに基づいて、選択されたマップの少なくとも一部を使用して、サブマップを生成するステップと、幾何学的認識をサブマップ内で実施するステップとを含んでもよい。サブマップまたは「従来値」が、類似性ランク付けに基づいて選択されたマップの部分と関連付けられた点群をマージすることによって形成され得、マップが離散化される程度に応じて、有意な重複が隣接する部分の点群間に存在し得ることを理解されたい。
【００９１】
一実施例では、本方法は、１つ以上の電子処理デバイスにおいて、ローカル特徴点をローカル点群から抽出するステップと、ローカル特徴点毎に、ローカル幾何学的記述子を計算するステップと、サブマップ内に含まれるマップの部分と関連付けられたサブマップ特徴点を使用して計算された事前に計算されたサブマップ幾何学的記述子を読み出すステップと、ローカル幾何学的記述子とサブマップ幾何学的記述子との間の対応を決定するステップと、幾何学的一貫性に基づいて、対応をクラスタ化し、１つ以上の候補クラスタを形成するステップと、候補クラスタ毎に、変換を決定するステップとによって、幾何学的認識を実施するステップを含む。本段階の出力は、マップへの変換を伴う、ローカル走査に関する候補場所のセットである。
【００９２】
サブマップ幾何学的記述子は、３Ｄ環境がマッピングされ、データ記憶装置内に記憶された後、マップに関して第２の強度記述子とともに計算されることを理解されたい。幾何学的記述子は、マップから抽出された部分毎に計算され、したがって、マップの部分が、サブマップにマージされると、対応する幾何学的記述子が、幾何学的認識を実施する際に使用するために読み出される。
【００９３】
典型的には、本方法はさらに、１つ以上の電子処理デバイスにおいて、最高数の対応を有する、候補クラスタを選択するステップと、選択された候補クラスタ内の対応の数と第１の閾値を比較するステップと、対応の数が第１の閾値を下回る場合、選択された候補クラスタが偽マッチングであることを決定するステップと、対応の数が第１の閾値を上回る場合、選択された候補クラスタが最も可能性が高い場所を示すことを決定するステップとのうちの少なくとも１つとを含む。対応の数は、したがって、満たされなければならない幾何学特徴に基づく、第１の検証条件であって、そうでなければ、場所（マップの部分）は、正しくないマッチングとして破棄される。
【００９４】
最も可能性が高い場所を示す候補クラスタを決定されたので、本方法は、次いで、典型的には、１つ以上の電子処理デバイスにおいて、変換を精緻化し、ローカル点群とサブマップと関連付けられたサブマップ点群を整合させるステップを含む。一実施例では、これは、反復最近傍点（ＩＣＰ）プロシージャをローカルおよびサブマップ点群少なくとも一部上で実施し、変換を精緻化し、姿勢を決定することによって達成される。精緻化後、点群は、精密に整合される。ＩＣＰが正常に収束する場合、推定される変換行列が出力される。
【００９５】
さらなる検証ステップとして、本方法はさらに、１つ以上の電子処理デバイスにおいて、ローカルおよびサブマップ点群が整合される程度を示す、適合性スコアを決定するステップと、適合性スコアと第２の閾値を比較するステップと、比較の結果に応じて、場所を選択的に照合するステップとを含んでもよい。適合性スコアが、容認可能レベルを超える（すなわち、第２の閾値を上回る）場合、場所は、偽マッチングと見なされる。
【００９６】
偽マッチングは、環境が動的である程度等の複数の理由を有し得る（マッピングの間に見られた物体が、もはや可視ではなくなる場合がある、または移動している場合がある）。加えて、ロボットは、単に、オリジナルマッピング軌道から遠く外れている場合があり、その場合、ローカル走査は、マップから抽出された部分のいずれにも類似し得ない。
【００９７】
典型的には、検証条件のいずれかが失敗する場合、本方法は、サブマップ（すなわち、以前の検索エリア）のサイズを増加させることを試みる。故に、一実施例では、本方法は、１つ以上の電子処理デバイスにおいて、対応の数が第１の閾値を下回ることと、適合性スコアが第２の閾値を上回ることとのうちの１つの場合、新しいサブマップを生成するステップを含む。新しいサブマップは、少なくとも部分的に、マップの部分の潜在的場所としてのランク付け（強度ベースの認識プロシージャから）に基づいて選択されたマップの他の部分を使用して、生成されてもよい。
【００９８】
この点において、ともに組み合わせられ、サブマップまたは従来値を形成すべき、マップの抽出される部分の数の限界が存在することを理解されたい。これに関する１つの理由は、サブマップが増大するにつれて、幾何学的記述子の数も増大し、したがって、位置特定プロシージャがより低速になるためである。システムは、算出複雑性の低減に起因して有利であるが、サブマップは、使用される幾何学的記述子の総量が、伝統的方法（すなわち、マップ全体における幾何学的対応検索に基づく）より長い処理時間をもたらすことがないであろうようなサイズに限定されるべきである。
【００９９】
故に、一実施例では、本方法は、１つ以上の処理デバイスにおいて、サブマップ内に含まれている潜在的場所の数を決定するステップと、潜在的場所の数が定義された最大値に到達した場合、位置特定方法を終了するステップ、および潜在的場所の数が定義された最大値を下回る場合、サブマップのサイズを増加させるステップのうちの少なくとも１つとを含む。
【０１００】
上記に説明される方法では、マップの部分（すなわち、「場所」）は、マッピング軌道に沿ったマップから抽出される。このように、マッピング軌道は、事前に定義された長さのセグメントに分割され、マップの各部分は、マッピング軌道の個別のセグメントに沿って進行されるにつれて少なくとも１つのセンサから取得される、点群として定義される。マップをセグメント化する本方法は、半径ベースのアプローチ等の他の方法よりロバストであることが見出されている。そのようなアプローチは、マップ内の場所を選択するステップと、センサ範囲に基づいて、点群を抽出するステップとに基づく。しかしながら、これは、抽出された走査が、センサにより近い物体によってオクルードされるという事実に起因して、ロボット場所から不可視である点を含有するであろうため、正しくない。軌道に沿った場所を抽出することが、したがって、ロボットが実際にその場所から見え得る特徴のみを含むことから、抽出された場所がローカル走査に対応することを確実にするため、好ましい。
【０１０１】
さらなる広範な形態では、３次元（３Ｄ）環境内で位置特定を実施する際に使用するためのシステムであって、少なくとも１つのレーザセンサによって実施されるローカル走査から、少なくとも部分的に、ローカル走査から取得されるローカル点群内の点から少なくとも１つのレーザセンサに返される放射のパワーに基づいて、強度データを決定し、強度データを使用して、ローカル点群に関する第１の強度記述子を計算し、それぞれ３Ｄ環境のマップの個別の部分と関連付けられる、複数の事前に計算された第２の強度記述子を読み出し、第１の強度記述子と第２の強度記述子のうちの少なくともいくつかを比較し、少なくとも部分的に、比較の結果に従って、マップに対する場所を決定するように構成される、１つ以上の電子処理デバイスを含む、システムが、提供される。
【０１０２】
典型的には、本システムは、ローカル走査を実施するように構成される、少なくとも１つのレーザセンサを含む。一実施例では、少なくとも１つのレーザセンサは、光結像検出および測距（ＬｉＤＡＲ）センサである。有利には、付加的センサは、完全グローバル位置特定を達成するために要求されない。
【０１０３】
一実施例では、本システムはさらに、複数の第２の強度記述子を含有するデータ記憶装置を含み、データ記憶装置は、複数の第２の強度記述子を読み出すために、１つ以上の電子処理デバイスによってアクセス可能である。
【０１０４】
好ましくは、少なくとも１つのレーザセンサ、１つ以上の電子処理デバイス、およびデータ記憶装置は、モバイルロボットまたは自律車両にオンボードで位置する。しかしながら、他の配列では、処理デバイスは、要求される第２の強度記述子を読み出すために、遠隔データ記憶装置と無線で通信してもよい。
【０１０５】
３Ｄ環境内で位置特定を実施する際に使用するためのシステムの実施例が、ここで、図２を参照して説明されるであろう。
【０１０６】
本実施例では、システム２００は、自律車両またはロボット２０５にオンボードで位置する、少なくとも１つの電子処理デバイス２１０を含む。電子処理デバイス２１０は、データ記憶装置２３０に結合され、これは、グローバル点群、マッピング軌道、第２の強度記述子、およびマップと関連付けられた幾何学的記述子等のマップ情報を含有する。レーザセンサ２２０は、ロボット２０５にオンボードで搭載され、ロボット２０５を囲繞する環境の走査を実施するように構成される。一実施例では、レーザセンサは、Ｖｅｌｏｄｙｎｅによって生産されたＶＬＰ−１６  ３Ｄ  ＬｉＤＡＲ等の３Ｄ  ＬｉＤＡＲセンサである。センサから取得される情報を増加させるために、センサは、垂直軸を中心として回転するように搭載されてもよく、さらに、センサは、垂直から４５度の角度で傾斜されてもよい。一実施例では、ローカル走査は、上記に説明されるセンサの２回転によって生成された点群と見なされる。
【０１０７】
電子処理デバイス２１０の実施例は、図３に示される。本実施例では、処理デバイス２１０は、示されるように、少なくとも１つのマイクロプロセッサ３００と、メモリ３０１と、キーボードおよび／またはディスプレイ等の随意の入力／出力デバイス３０２と、バス３０４を介して相互接続される、外部インターフェース３０３とを含む。本実施例では、外部インターフェース３０３は、処理デバイス２１０を通信ネットワーク、データ記憶装置２３０、他の記憶デバイス、または同等物等の周辺デバイスに接続するために利用されることができる。単一外部インターフェース３０３が、示されるが、これは、実施例のみの目的のためのものであって、実際は、種々の方法（例えば、Ｅｔｈｅｒｎｅｔ（登録商標）、シリアル、ＵＳＢ、無線、または同等物）を使用する、複数のインターフェースが、提供されてもよい。
【０１０８】
使用時、マイクロプロセッサ３００は、メモリ３０１内に記憶されるアプリケーションソフトウェアの形態における命令を実行し、データ記憶装置２３０と通信し、第２の強度記述子およびマップの抽出された部分と関連付けられた幾何学的記述子を読み出すステップと、強度データおよび測距データを含む、センサデータをレーザセンサ２２０から受信するステップと、強度ベースの認識および幾何学的認識を実施するステップとを含む、要求されるプロセスが実施されることを可能にする。アプリケーションソフトウェアは、１つ以上のソフトウェアモジュールを含んでもよく、オペレーティングシステム環境または同等物等の好適な実行環境内で実行されてもよい。
【０１０９】
故に、電子処理デバイス２１０は、ロボット２０５にオンボードで搭載される、好適にプログラムされるコンピュータシステム、ＰＣ、ラップトップ、またはスマートフォン、タブレット、または同等物等のハンドヘルドＰＣ等の任意の好適な処理システムから形成されてもよいことを理解されたい。１つの特定の実施例では、電子処理デバイス２１０は、不揮発性（例えば、ハードディスク）記憶装置上に記憶されるソフトウェアアプリケーションを実行する、Ｉｎｔｅｌアーキテクチャベースの処理システム等の標準的処理システムであるが、これは、不可欠ではない。しかしながら、また、処理システムは、マイクロプロセッサ、マイクロチッププロセッサ、論理ゲート構成、ＦＰＧＡ（フィールドプログラマブルゲートアレイ）等の論理を実装することと随意に関連付けられるファームウェア、または任意の他の電子デバイス、システム、または配列等の任意の電子処理デバイスであり得ることを理解されたい。
【０１１０】
３Ｄ環境内で位置特定を実施する際に使用するための具体的プロセスが、ここで、図４Ａ−４Ｃを参照して説明されるであろう。本フローチャートに説明されるプロセスは、強度ベースの場所認識を伴う、第１の段階と、強度ベースのマッチングの正しさを検証し、また、所望の変換および姿勢を提供するための幾何学的場所認識を伴う、第２の段階とを含む、好ましい２段階位置特定パイプラインを説明する。
【０１１１】
プロセスは、ステップ４００から開始し、環境のローカル走査が、３Ｄ  ＬｉＤＡＲセンサを使用して実施される。ローカル走査は、その場所についての以前の情報を伴わない環境内における、ウェイクアップまたは初期化に応じてロボットによって実施される、「ウェイクアップ」走査であってもよい。ローカル走査は、センサが見え得る全ての点を備える、ローカル３Ｄ点群を生産する。
【０１１２】
ステップ４０５では、ローカル点群内の全ての点の強度に対応する強度データが、決定される。前述のように、本情報は、走査されている表面の反射率特性に依存する、レーザの戻りの強度の測定値に対応する。したがって、強度データは、ロボットが位置する環境を高度に説明する。一実施例では、強度データは、単に、センサから到着するメッセージから読み取られる。
【０１１３】
ステップ４１０では、第１の強度記述子が、ローカル点群内の点の強度データを使用して計算される。本強度記述子は、同心球体に半径方向に分割され、次いで、半球に水平にセグメント化され、次いで、９０度毎に方位角方向に沿ってさらにセグメント化される、球体から成る。結果として生じる記述子は、１６の空間的に分散されたセグメントを有する。１６のセグメントのそれぞれに入る点の強度のヒストグラムが、次いで、第１の強度記述子が強度の１６のヒストグラムから成るように計算される。ヒストグラムの使用は、データセットの次元を低減させる一方、記述子の構造化された分割は、統計と空間内の場所を関連付けることによって、一意性を維持する。強度記述子の構造の実施例は、図６Ｂに示される空間的に分散されたセグメントに分割される、例示的ウェイクアップ走査とともにする、図６Ａに示される。
【０１１４】
ステップ４１５では、ローカル幾何学的記述子が、計算された。これを達成するために、点群は、最初に、ダウンサンプリングされ、群の密度を低減させ、次いで、外れ値が、記述子に及ぼす雑音の影響を最小限にするように除去される。特徴点が、次いで、ランダム選択に基づいて、点群から抽出され、その周囲で幾何学的記述子が算出される、点を形成する。群内の全ての点の正規点が、次いで、算出され、最後に、記述子が、計算される。好適な幾何学的記述子は、ＳＨＯＴ記述子と称され、これは、配向のヒストグラムのシグネチャを現し、雑音に対してロバストである一方、同時に、高度に記述的である。ＳＨＯＴ記述子は、球状支持構造を有し、これは、３２の空間的に分散されたセグメントに分割される。セグメント毎に、正規点のヒストグラムが、計算され、これは、ロバスト性を与え、加えて、各セグメントの空間場所が、固定され、これは、記述性を確実にする。しかしながら、ＳＨＯＴ記述子は、使用され得るローカル記述子の例示的実施例であって、任意の他のローカル記述子が、当業者によって理解されるであろうように使用されてもよいことを理解されたい。
【０１１５】
ステップ４２０では、可能性として考えられる場所候補の数が、「ｎ」に設定される。最初に、「ｎ」は、１と等しく、これは、最も類似する強度ベースの場所候補が、幾何学的認識が実施される、「従来値」またはサブマップを形成するために使用されることを意味する。
【０１１６】
ステップ４２５では、複数の第２の強度記述子が、データ記憶装置から読み出され、プロセッサのメモリの中にロードされる。
【０１１７】
ステップ４３０では、第１の強度記述子が、第２の強度記述子に対して比較される。これは、第１の強度記述子のセグメント毎の強度のヒストグラムと、第２の強度記述子の各対応するセグメントの強度のヒストグラムを比較することによって達成される。個別のヒストグラムが、カイ二乗検定を使用して比較される。
【化１】
2020532734.tif 000003
式中、ＳＡＢｉ＝記述子Ａのｉ番目のセグメントのヒストグラムと記述子Ｂのｉ番目のセグメントのヒストグラムとの間の類似性値であって、記述子Ａ＝第１の強度記述子であって、記述子Ｂ＝第２の強度記述子であって、ｋ＝ヒストグラムのビンの数であって、ｍ＝ヒストグラム内のビンの数であって、Ａ（ｋ）＝記述子Ａのｋ番目のビンの値であって、Ｂ（ｋ）＝記述子Ｂのｋ番目のビンの値である。
【０１１８】
比較の出力は、類似性値ＳＡＢｉである。２つの記述子の類似性メトリックＳＡＢが、全てのセグメントのカイ二乗検定の結果の平均として取得される。異なる場所における２つの強度記述子に関するヒストグラム間の比較の視覚的例証が、図７に示される。第１の場所「２」は、建物を伴う構造化された環境を示す、稠密群に対応する。第２の場所「９１７」は、木々および灌木を伴う非構造化環境を示す、疎密群に対応する。
【０１１９】
さらに、典型的には、基準フレームが、主成分分析（ＰＣＡ）を使用して、強度記述子に関して算出されることに留意されたい。基準フレームを構成するベクトルの符号を決定することが不可能であるため、これは、記述子の対応するセグメントのヒストグラムが相互に比較されていることを確実にするために考慮されなければならない。第１の強度記述子は、したがって、各第２の強度記述子の４つの異なるバージョンと比較される。異なるバージョンによって、図８に示されるように、記述子の基準フレームの異なる配向を検討することによって取得される、セグメントの異なるシーケンスが、理解されるはずである。本方法は、本質的に、基準フレーム配向の全４つの組み合わせが、可能性として考えられると仮定する。類似性値ＳＡＢが、４つの比較毎に決定され、記述子間の類似性の全体的測定値が、以下のように定義される。
【化２】
2020532734.tif 000004
【０１２０】
ステップ４３５では、「ｎ」個の最も類似する場所候補が、比較の結果に従って（すなわち、記述子間の類似性メトリックに基づいて）選択される。場所候補は、ステップ４４０において、個別の場所の点群を組み合わせることによって、サブマップまたは「従来値」にマージされる。
【０１２１】
ステップ４４０では、サブマップ幾何学的記述子が、データ記憶装置から読み出され、サブマップ幾何学的記述子は、「従来値」におけるマップの部分毎に決定された幾何学的記述子に基づく。
【０１２２】
ステップ４５０では、幾何学的対応が、決定される。各サブマップ幾何学的記述子は、ローカル走査から取得される各ローカル幾何学的記述子に対してクエリされる。
【０１２３】
サブマップ内の特徴点毎に、１つのみの特徴点が、ローカル走査から選択される（最も類似する）。類似性レベルが定義された閾値を下回らなければならないという、付加的制約が、課される。ｋｄ−ツリーが、記述子の寸法の数に一致する次元を伴う検索方法として使用される。
【０１２４】
出力は、単一の最近傍値であって、これは、その類似性が述べられた閾値を下回る場合、対応する点と見なされる。対応は、対の特徴点のインデックスを記憶する、ベクトルにまとめられる。一般に、ローカル走査における単一特徴点は、サブマップ内のいくつかの対応する特徴点を有することができ、これは、複数のインスタンスの可能性を含む。類似性閾値は、したがって、その値が認識の厳密性に影響を及ぼすため、重要である。それを増加させることによって、システムは、場面の変化に対してあまり保守的ではなく、雑音に対してよりロバストになる一方、大きすぎる値は、偽マッチングをもたらすであろう。平衡パラメータは、実験的に見出されなければならない。
【０１２５】
ステップ４５５では、対応は、幾何学的一貫性に基づいてクラスタ化される。対応検索ステップの結果は、サブマップ内の点とローカル走査内のそれらとの間のマッチングのセットとなる。見出される対応がローカル走査の実際のインスタンスに属することを確実にするために、幾何学的制約が、それらに課される。基本仮定は、群内の点が、強固に結合されるというものである。これは、特徴点が幾何学的一貫性基準を満たすセットにクラスタ化されることを可能にする。本条件によって、サブマップ内の２つの点が、その減算の２−ノルムとローカル走査内の対応する点の減算の２−ノルムとの間の差異が、定義されたコンセンサス閾値より小さい場合、幾何学的に一貫すると見なされる。幾何学的一貫性コンセンサスは、システムの別の重要なパラメータである。経験則として、これは、ダウンサンプリング後、群の分解能より大きくなければならない（点場所の差異は、分解能に到達し得る）。しかし、特徴点は、両群において正確に同一位置にあることが保証されないため（ダウンサンプリングによって選択されるため）、かつ雑音のため、コンセンサス値は、より大きくあるべきである（いくつかの群分解能）。
【０１２６】
加えて、最小数の対応に関して、それを下回るとクラスタが破棄されるという条件が存在する。その後、ＲＡＮＳＡＣアルゴリズムが、矛盾した対応をさらに排除するために使用される。候補クラスタのセットが、次いで、ステップ４６０において、上記の制約が対応に課された後、決定される。
【０１２７】
ステップ４６５では、候補クラスタ毎に、変換行列が、絶対配向アルゴリズムを使用して算出され、姿勢を取得する。本変換は、点群全体ではなく、特徴点のセットの相対的場所に基づいて推定され、正確度は、クラスタ内の特徴点の量に依存することに留意することが重要である。本段階の出力は、サブマップへの変換を伴う、ローカル走査に関する候補場所のセットとなる。
【０１２８】
ステップ４７０では、最高数の対応を有する候補クラスタが、最も可能性が高い場所候補として選択される。
【０１２９】
ステップ４７５では、検証が、２ステッププロセスにおいて実施される。最初に、最も可能性が高い場所候補内の対応の数が、定義された閾値と比較される。対応の数は、閾値より大きくなければならず、そうでなければ、場所候補は、偽マッチングとして破棄される。
【０１３０】
最も可能性が高い場所の取得される変換行列が、次いで、反復最近傍点（ＩＣＰ）アルゴリズムを使用して精緻化される。ＩＣＰは、サブマップおよびローカル走査内の最高数の対応を伴う、クラスタの各点に適用される。精緻化後、点群は、精密に整合される。ＩＣＰが、正常に収束する場合、推定された変換行列が出力される。
【０１３１】
加えて、ＩＣＰは、適合性スコア、すなわち、点群が整合される程度のメトリックを出力する。これは、適合性スコアが容認可能レベルを超える（定義された閾値を上回る）かどうかをチェックする、第２の検証条件の一部を形成する。該当する場合、場所は、偽マッチングと見なされる。
【０１３２】
ステップ４８０では、本方法は、上記の述べられた検証条件が満たされたかどうかをチェックする。それらが満たされた場合、ロボットは、位置特定されたと見なされ、本方法は、ステップ４８５において終了する。一方または両方の検証条件が満たされない場合、ステップ４９０において、本方法は、従来値に関する最大数の場所候補「ｎ」に到達したかどうかをチェックする。該当する場合、さらなる検索は、実施されず、アルゴリズムは、ステップ４９６において終了し、場所を見出すことが、不可能であると見なされる。そうでなければ、従来値のサイズが、ステップ４９５において増加され、サブマップが、さらなる場所候補を検討することによって拡張され、本方法は、ステップ４３５に戻る。
【０１３３】
ローカル走査と関連付けられた第１の強度記述子を計算する実施例のフローチャートが、ここで、図５を参照して説明されるであろう。
【０１３４】
本実施例では、ステップ５００において、ローカル点群内の点の強度データが、３Ｄ  ＬｉＤＡＲ走査から決定される。
【０１３５】
ステップ５１０では、ローカル点群が、例えば、図６Ａに示されるように、複数の空間的に分散されたローカル点群セグメントに分割される。各点群セグメント内の点の強度分布に関する統計的測定値が、次いで、ステップ５２０において計算される。好ましい実装では、強度のヒストグラムは、点群セグメント毎に決定され、これは、ステップ５３０において、第１の強度記述子セグメントを形成する。他の実施例では、代替統計的測定値は、例えば、点群セグメント内の点の強度値の平均または強度値の分散値が、使用されてもよい。
【０１３６】
最後に、第１の強度記述子セグメントが、ステップ５４０において、第１の強度記述子を定義するために使用される。ヒストグラムが、使用されるとき、第１の強度記述子は、強度のあるグループのヒストグラムを定義し、これは、コンパクトかつ一意の形態におけるローカル走査の出現を特徴付ける。
【０１３７】
マップの事前処理を実施する方法の実施例のフローチャートが、ここで、図９を参照して説明されるであろう。
【０１３８】
本実施例では、ステップ９００において、マップが、３Ｄ  ＬｉＤＡＲセンサが走査する間、自律車両またはロボットを３Ｄ環境内で動き回らせることによって取得される。ＳＬＡＭアルゴリズムが、環境のマップを取得するために使用されてもよい。
【０１３９】
マッピング軌道もまた、記録され、ステップ９１０において、本方法は、マッピング軌道を取得するステップを含む。ステップ９２０では、マップの部分が、マッピング軌道に沿って抽出される。抽出は、距離に基づき、故に、マップは、軌道を長さ「ｌ」（例えば、ｌ＝２ｍ）のチャンクにセグメント化し、点群をチャンクの中央に位置する群の原点を伴う各チャンクに沿って可視の全ての点から作成することによって、分割される。
【０１４０】
ステップ９３０では、強度データが、各抽出された部分の群内の点（前述のように、「場所」としても知られる）に関して決定される。
【０１４１】
ステップ９４０では、第２の強度記述子が、第１の強度記述子に関して前述の同一技法を使用して、抽出された部分毎に計算される。幾何学的記述子もまた、ステップ９５０において、ローカル幾何学的記述子のために使用される前述の技法（ダウンサンプリング、外れ値除去、特徴点選択、正規値算出等）を使用して、抽出された部分毎に計算される。最後に、ステップ９６０では、マップから抽出された部分毎の第２の強度記述子は、位置特定において使用するための電子処理デバイスによる後続読出のために、データ記憶装置内に記憶される。
（実験および検証）
【０１４２】
実験が、Ｂｒｉｓｂａｎｅ（Ａｕｓｔｒａｌｉａ）におけるＱｕｅｅｎｓｌａｎｄ  Ｃｅｎｔｒｅ  ｆｏｒ  Ａｄｖａｎｃｅｄ  Ｔｅｃｈｎｏｌｏｇｉｅｓの敷地内で、システムを検証するために行われた。マークされたウェイクアップ場所とともに、試験環境の衛星写真が、図１０Ａに示される。エリア全体が、ＳＬＡＭアルゴリズムを使用してマッピングされ、これは、ｌマップ（すなわち、グローバル点群）および図１０Ｂに示される対応するマッピング軌道をもたらした。
【０１４３】
試験環境は、複数の特性を有する。建物等の完全に構造化された性質の場所と、木々または灌木から成る完全に非構造化された領域とが、存在する。明らかに、両タイプの要素を含有するエリアと、構造化および非構造化周囲の組み合わせも、存在する。加えて、異なる場所に関する点の空間分布もまた、マップ全体を通して有意に変動する。建物間のスポットは、通常、非常に制限され、緊密であって、これは、そこで取得される走査が、膨大な量の点を含有することを防止するが、通常、非常に一意かつ容易に区別可能である。他方では、また、散在する木々および灌木のみを伴う、開放空間場所も存在し、これは、有意に明確に異なる特徴を欠いているが、多くの場合、多くの点（地面からの反射として測定される）を含有する。その全てが、敷地を、特に、ＬｉＤＡＲデータのみに基づくべきであるという要件を伴う認識にとって、非常に困難である環境にする。
【０１４４】
システムを検証するために、種々のウェイクアップ走査（すなわち、ローカル走査）のセットが、生成された。全体として、１０１カ所の場所が、敷地を横断して試験され、それらは全て、図１０Ａに見られ得る。気付かれ得るように、点は、マップの周囲に非常に均一に分散され、これは、種々の場所の特性を保ち、結果の統計的有意性を確実にする。さらに、走査は、改変に対するロバスト性を立証するために、オリジナルマッピング軌道からの異なる距離において生成された。また、重要なこととして、セット全体が複数の日にわたって生成されたことを述べておく。これは、種々の光条件および温度が存在し、強度ベースの記述子に及ぼすその影響の立証を可能にしたことを意味する。
【０１４５】
マップが、前述の方法に従って、場所のセットに分割された。軌道は、約４ｋｍ長であって、したがって、連続群の分解能は、２ｍに設定され、マップは、２，０５５カ所の場所に分割された。
【０１４６】
システムの検証は、多特性環境内の認識の成功率を確立することに基づく。提案されるシステムでは、認識は、アルゴリズムが、古典的幾何学形状ベースのアプローチより高速で正しい姿勢を見出すことができる場合、成功と見なされる。以下の節では、幾何学形状ベースのみのパイプラインは、古典的アプローチと称されるであろう一方、２段階強度および幾何学ベースの認識は、組み合わせられたパイプラインと称されるであろう。より具体的には、場所は、正しさ（すなわち、検証）条件が前述で定義されたように満たされる場合、正しいマッチングとみなされる。本基準のためのパラメータは、種々の実験を実施することによって調節された。
【０１４７】
走査のうちのいくつかに関して、正しさが、直接、見出された姿勢をナビゲーションパイプラインに対して解析することによって、評価された。プロシージャが、開始し得る（正しい整合）場合、姿勢が正常に見出されたことを意味する。しかしながら、大部分の場合、グローバル位置特定試験は、両パイプラインが同時に展開され、通常、相互試験を実施することが不可能であるという事実に起因して、ナビゲーションと別個に行われた。
【０１４８】
そのような場合、認識は、最初に、古典的アプローチ（すなわち、単一群としてのマップ内の位置特定）を使用して実施され、その結果は、グラウンドトゥルースとして処理された。組み合わせられたパイプラインが、同一座標の場所（ノルム＜１ｍの許容可能誤差を伴う）を見出した場合、場所は、正しいと見なされた。
【０１４９】
走査のうちのいくつか（全体として、セット全体のうち８つ）に関して、単一群から成るマップ内の幾何学形状ベースの位置特定は、失敗した。そのような状況では、古典的アプローチのパラメータは、変更された（すなわち、ダウンサンプリングの分解能が、より多くの記述子を取得するように増加された）。５つの場所に関して、変更されたパラメータは、有用ではなく、幾何学形状ベースのみのアプローチは、失敗した。これらの場合では、組み合わせられたアプローチの正しさは、マップ内の見出された場所の位置および点群の整合の外観検査によって推定された。
【０１５０】
組み合わせられたパイプラインの性能が、古典的アプローチより高速であることを確実にするために、従来値を形成する場所の最大量は、４９に限定された。この数もまた、古典的アプローチの５０％より短い処理時間を保つように実験的に確立された。しかしながら、実験が示すように、２５カ所を上回る場所の従来値の拡張は、正しい姿勢を見出す尤度の増加をもたらさなかった。
【０１５１】
全体として、システムは、非常に成功することが証明され、全体的成功率は、９７％に到達した。そのような高率は、ロバストなアルゴリズム構造、すなわち、幾何学形状ベースの検証が認識を確実にしない場合における従来値（すなわち、場所候補の数）を増加させる可能性から生じる。図１０Ｃに示されるプロットは、全体的位置特定成功率に及ぼす従来値サイズの増加の効果を可視化する。本グラフでは、次の従来値サイズの成功率は、前の従来値サイズおよび従来値サイズを増加させることによって認識された付加的場所からの成功率から成る。全ての実験の結果が、プロットされる（すなわち、１０１カ所のウェイクアップ場所）。
【０１５２】
大部分（８２％）の場合、システムは、１つのみの場所を使用して、正しく位置特定することが可能であった。プロットから明確に分かり得るように、５カ所から２５カ所の場所への従来値サイズの増加は、成功率を増加させるが、しかしながら、従来値サイズのさらなる増加は、認識における任意のさらなる改良を提供しないことが示された（その一方で、不可避的に処理時間の低下をもたらす）。
【０１５３】
多くのグローバル位置特定アルゴリズムでは、ロボットが「その場所を再訪問している」（すなわち、現在見え得る場所は、以前にすでに訪問している）という仮定が根本にある。これは、認識能力が、軌道の直近傍に限定されることを意味する。提案されるアルゴリズムは、汎用性であって、ある程度まで、軌道までのランダム距離において、ロボットの場所を取り扱うことができる。システムは、軌道から最大５メートルにあるロボットに対処することができ、これは、マッピング経路の周囲の１０ｍ幅の半径内に位置し、依然として、ロバストに位置特定することができることを意味する。加えて、さらなる距離に関して、成功率は、７０％の満足の行くレベルのままである。これは、優れた結果であって、システムのロバスト性を実証する。
【０１５４】
図１０Ｄを参照すると、軌道からの異なる距離に関する位置特定の成功率のグラフが、示される。棒グラフは、マッピング軌道に対する異なる距離範囲におけるウェイクアップ場所の割合を描写する。図１０Ｅでは、マッピング軌道から異なる距離における正常位置特定に対する場所候補の要求される数（従来値サイズの分布）のグラフが、示される。
【０１５５】
予期されるはずであるように、軌道からの増加された距離に伴って、強度ベースの認識の確実性は、減少する。これは、ロボットにオリジナル軌道から不可視の物体が見え得るという事実によって生じる。加えて、マッピング経路から遠く外れると、同一物体は、異なる入射角から可視となり、補償されないため、不確実性を強度ヒストグラムの中に導入する。ロボットが、軌道からより遠くなると、より大きい従来値が、検討される必要があることが、必然的に明らかである。その理由のうちの１つは、軌道から外れた場所から完全に可視である物体が、軌道上の種々の場所から部分的にのみ可視であるためである。したがって、部分的ビューを組み合わせることによって、幾何学形状ベースの位置特定の実施成功のために十分な情報を含有する、群を作成することが可能である。
【０１５６】
加えて、従来値サイズを増加させる必要性は、軌道に近接する走査例が少ない場合にも生じることに留意されたい。これは、環境が、動的であって、マッピングの間に不可視であったいくつかの物体が、ウェイクアップ時に生じ得るという事実によって生じる。これは、強度ベースの認識確実性の低減をもたらす。他方では、これは、従来値サイズ拡大機能性の必要性の別の正当性であって、これは、アルゴリズムが環境の動的変化に対処することを可能にする。
【０１５７】
システムの開発の最も重要な誘因のうちの１つは、処理時間の低減に関する要件であった。古典的アプローチでは、対応が、グローバルマップ点群全体において検索されるとき、プロセスは、容認不可能な時間量を要する。群の特性に応じて（建物の場合、構造化され、コンパクトである、または開放空間／低草原地帯に関して、非構造化され、広大である）、検索は、３〜２０分を要し得る。あるタスクを実施する必要がある、多目的車両に関して、動作の開始のためにそのように長時間待機することは、容認不可能である。
【０１５８】
提案されるアルゴリズムは、時間要件に完璧に適応する。強度ベースの従来値を用いることで、検索空間の限界は、膨大になる（例えば、図１０Ｇに示されるように）。古典的アプローチおよび組み合わせられたアプローチを使用した処理時間の比較は、図１０Ｆに示される。大部分の場合における時間低減は、約９９％に到達することが、明確に顕著である（垂直軸は、対数である）。２５カ所の場所から成る従来値の場合のみ、低減は、悪化するが、依然として、約９０％を達成する。結果は、非常に満足の行くものであって、大部分の場合、ソリューションは、リアルタイムグローバル位置特定アルゴリズムと見なされ得ることが証明される。
【０１５９】
故に、少なくとも一実施例では、上記に説明される方法およびシステムは、グローバル位置特定を実施する際に使用するための効率的アルゴリズムを提供し、いくつかの実施例では、ロボットが、任意の以前の知識を伴わずに、既知のマップ内でその姿勢を推定する必要がある、ウェイクアップまたは迷子ロボット問題に対する効率的ソリューションを提供することを理解されたい。しかしながら、前述から、システムは、ループ閉鎖および同等物等のグローバル位置特定を要求する他の用途においても使用を見出し得ることを理解されるであろう。システムは、任意の外部ビーコン、ＧＰＳ、ＩＭＵデータ、または同等物に依存せずに、オンボード３Ｄ  ＬｉＤＡＲセンサのみから取得されるデータを使用して、グローバル位置特定を実施することが可能である。本明細書に提示される２段階位置特定パイプラインは、新規強度ベースの記述子を使用して、ロボットの位置の従来推定値を決定し、その後、幾何学形状ベースの立証が続き、これは、姿勢および強度ベースのマッチングの正しさを決定するために実施される。プロシージャ全体は、完全に定常のロボットによって実施されてもよく、位置推定のための運動を要求しない。実験データは、方法およびシステムが、環境の変化にロバストであることを示し、システムが、実世界状況における自律的ナビゲーションに適用可能であることを示す。
【０１６０】
本明細書および続く請求項全体を通して、文脈によって別様に要求されない限り、単語「ｃｏｍｐｒｉｓｅ（〜を備える）」および「ｃｏｍｐｒｉｓｅｓ（〜を備える）」または「ｃｏｍｐｒｉｓｉｍｇ（〜を備える）」等の変形例は、述べられた整数または整数またはステップのグループの含有を含意するが、任意の他の整数または整数のグループを除外しないものと理解されるであろう。
【０１６１】
当業者は、多数の変形例および修正が明白となるであろうことを理解されるであろう。当業者に明白となる、全てのそのような変形例および修正は、広範に現れる本発明が前述に説明した精神および範囲内に入ると見なされるべきである。
【図１】
2020532734.tif 000005
【図２】
2020532734.tif 000006
【図３】
2020532734.tif 000007
【図４Ａ】
2020532734.tif 000008
【図４Ｂ】
2020532734.tif 000009
【図４Ｃ】
2020532734.tif 000010
【図５】
2020532734.tif 000011
【図６Ａ】
2020532734.tif 000012
【図６Ｂ】
2020532734.tif 000013
【図７】
2020532734.tif 000014
【図８】
2020532734.tif 000015
【図９】
2020532734.tif 000016
【図１０Ａ】
2020532734.tif 000017
【図１０Ｂ】
2020532734.tif 000018
【図１０Ｃ】
2020532734.tif 000019
【図１０Ｄ】
2020532734.tif 000020
【図１０Ｅ】
2020532734.tif 000021
【図１０Ｆ】
2020532734.tif 000022
【図１０Ｇ】
2020532734.tif 000023
【国際調査報告】
2020532734.tif 000024
2020532734.tif 000025
2020532734.tif 000026
2020532734.tif 000027