ロボットは未知の環境でどのように位置を特定し、マッピングし、移動できるのでしょうか?

1. はじめにコンピュータ技術の急速な発展に伴い、ロボット研究の深化とロボットに対する人々の需要の拡大に伴い、インテリジェントに移動し、自律的にナビゲートできるロボットが研究の焦点となっています。 既知の環境におけるロボットの自律的な位置特定と、既知のロボット位置の地図作成のための実用的なソリューションがいくつかあります。 しかし、多くの環境ではロボットは測位に全地球測位システムを使用できず、ロボットの作業環境の地図を事前に入手することは困難です。 このときロボットは、位置が不確実な全く未知の環境で地図を作成し、その地図を自律測位・ナビゲーションに利用する必要がある。 スラム（同期測位および地図構築）技術は、真の自律移動ロボットを実現するための核となるキー技術と考えられています。ロボットは未知の環境、未知の位置から動き始めます。 移動の過程で、位置推定とセンサーデータに従って自身の位置を特定し、徐々に改良して完全な地図を構築します。 これはスラムプロセスです。 スラムでは、ロボットは独自のセンサーを使用して未知の環境で特徴マークを識別し、ロボットと特徴マークの相対位置と走行距離計の読み取り値に基づいてロボットと特徴マークのグローバル座標を推定します。 このオンライン測位と地図作成では、ロボットと特徴マークの間で詳細な情報を維持する必要があります。 近年、スラムの研究は大きく進歩し、ロボット、AR、VR、UAV、オートパイロットなど様々な環境に応用されています。2. スラムの主要な問題 2.1 地図の表現 現在、一般的な地図の表現方法は、グリッド表現、幾何情報表現、トポロジー表現の 3 つに大別できます。 各方法には独自の長所と短所があります。 (1) 幾何情報マップ 幾何情報マップ表現とは、ロボットが環境の知覚情報を収集し、線分や曲線などのより抽象的な幾何特徴を抽出し、これらの幾何情報を使用して環境を記述することを意味します。 利点: よりコンパクトで、位置推定とターゲット認識に便利です。 幾何学的手法ではカルマンフィルターを使用し、局所領域での高精度かつ少ない計算量を実現します。 短所: 幾何学的情報の抽出には知覚情報の追加処理が必要であり、結果を得るには一定量の知覚データが必要です。 広域環境では正確な座標情報を維持することが困難です。 (2) グリッドマップ グリッドマップとは、環境全体を同じ大きさのいくつかのグリッドに分割し、グリッドごとに障害物の有無を指摘するものです。 利点: 作成と保守が簡単で、環境全体のあらゆる種類の情報を保持しようとします。 地図の助けを借りて、自己位置決めと経路計画を便利に実行できます。 デメリット：グリッドの数が増えると（大規模な環境や環境が細かく分かれている場合）、マップのメンテナンスが困難になります。 同時に、測位プロセスには大きな探索スペースが存在します。 適切な簡易アルゴリズムがなければ、リアルタイムアプリケーションを実現することは困難です。 (3) トポロジカル マップ トポロジカル マップは、特に大規模で単純な環境の場合に非常に抽象的です。 この方法では、環境はトポロジーの意味でグラフとして表現され、グラフ内のノードは環境内の特徴的な状態と位置に対応します。 ノード間に直接接続経路がある場合は、図のノード間を結ぶ円弧に相当します。 利点: さらなるパスとタスクの計画に役立ちます。 ストレージと検索スペースは比較的小さく、コンピューティング効率は高いです。 多くの成熟した効率的な検索および推論アルゴリズムを使用できます。 短所: 使用する場合は、トポロジ ノードの識別とマッチングに基づいて行う必要があります。 たとえば、環境内に非常によく似た 2 つの場所がある場合、トポロジ マップ手法ではそれらが同じ点であるかどうかを判断するのが困難になります。2.2 不確実な情報の説明環境がまったく未知の場合、ロボットが地図を作成して歩きたい場合は、走行距離計、ソナー、レーザー距離計、ビジョンなどの他のセンサーの助けを借りて情報を取得する必要があります。 センサー自体の制限により、センシング情報にはさまざまな程度の不確実性が存在します。 例えば、レーザー距離計の不確実性は主に、反射鏡の回転やレーザーの散乱によって生じる距離の測定誤差と測定角度の誤差によって生じます。 上の図に示すように、知覚される情報の不確実性により、構築された環境モデルが完全に正確であることは必然的に不可能になります。 同様に、モデルと認識に基づいて意思決定を行う場合、不確実性が生じます。つまり、不確実性は推移的です。 不確実性を測定する方法には、主に確率測定、信頼測定、可能性測定、ファジィ測定、証拠理論などがあります。 現在、確率測定とファジー測定が AMR マップの構築に広く使用されています。 確率測定には主に 2 つの形式があります。 (1) 不確実な情報は、平均、分散、共分散などの確率特性によって記述されます。 この測定方法の利点は、平均値などの確率特性が幾何学的に明確な意味を持つことですが、欠点は、確率特性の離散的な計算式が定まっていないことです。 (2) 確率モデルは、主にベイズ則とマルコフ仮説を使用して、不確実な情報を記述するために使用されます。 この計測方法の利点は、ロボットの位置、姿勢、環境情報がランダム確率モデルで記述され、ロバスト性が非常に優れていることです。 欠点は、確率モデルの計算量が非常に多く、モデルの事前確率を事前に知っておく必要があるため、実用化が難しいことです。2.3 位置および環境特徴の抽出移動ロボットの自己位置特定は、環境モデリングと密接に関連しています。 環境モデルの精度は測位精度に依存し、測位の実装は環境モデルから切り離せません。 未知の環境では、ロボットは基準を持たず、未知の環境で手探りする盲人のように、自身の不正確なセンサーに頼って外部情報を取得することしかできません。 この場合、位置決めが難しい。 地図の位置決めと位置決めを伴う地図の作成はどちらも簡単に解決できますが、地図を使わない位置決めや位置決めをしない地図の作成は「鶏の卵」問題のようなものです。 既存の研究では、このような問題の解決策は次の 2 つのカテゴリに分類できます。 (1) 自身の動きを推定するために内部センサーに依存する一方で、環境を認識するために外部センサー (レーザー距離計、視覚など) が使用されます。 、取得した情報を分析し、環境の特徴を抽出して保存します。 次のステップでは、環境の特徴を比較することによって自分自身の位置を修正します。 しかし、この方法は環境特性を取得する能力に依存します。 (2) 自身に搭載された各種センサー（オドメーター、コンパス、加速度センサー等）を利用し、各種センサー情報を融合することで測位誤差を低減します。 使用される融合アルゴリズムのほとんどはカルマン フィルターに基づいています。 これらの方式は外部情報を参照しないため、長時間ローミングを行うとエラーの蓄積が大きくなります。 環境特徴の抽出方法には次のようなものがあります。 1) 。 ハフ変換は、グレー画像に基づいて直線やその他の曲線を検出する手法の一種です。 この方法では、検索可能な事前に準備された特定の曲線のクラスターが必要で、表示されたグレー画像内の曲線のクラスターに従って曲線パラメーターを生成します。 2) 。 クラスタリング分析は、未分類のサンプルに対して効果的なデータ検出ツールです。 同時に、その目標は、対象となるオブジェクトを類似性や距離に基づいて自然なカテゴリまたはクラスター クラスに分類することです。 抽出されたオブジェクトのカテゴリが不明な場合には、ハフトランスフォームよりもクラスタリング技術の方が有効な技術です。 クラスター クラスは、断片的でバラバラではなく、「結合」を中心とする必要があります。 環境の特徴を抽出するのが難しい場合があります。 例えば、環境の特徴が十分に明らかではない場合や、センサー情報が少ない場合、一度の知覚情報から環境の特徴を取得することは困難です。2.4 データの関連付けデータの関連付けでは、2 つの特徴マークを照合して、それらが環境内の同じオブジェクトに対応するかどうかを判断します。 スラムでのデータ関連付けは主に 3 つのタスクを完了する必要があります。(1) マップ間のマッチング。 （２）特徴マークのマッチング。 （３）新たな特徴マークの検出。 データの関連付けはターゲット追跡やセンサーフュージョンの分野でうまく解決されていますが、これらの方法では大量の計算が必要であり、スラムのリアルタイム要件を満たすことができません。 M 個の符号と n 個の符号を持つマップ間のデータ関連付けの複雑さは、M で指数関数的になります。観測された各符号 I に一致する可能性があると仮定すると、M 個の符号に対して、指数空間 = で正しい一致を検索する必要があります。 データ関連付けの探索空間は、環境の複雑さやロボットの位置決め誤差に関係します。 環境の複雑さが増加すると m が増加し、誤差が増加すると Ni が増加します。2.5 累積誤差スラムのエラーは主に 3 つの側面から発生します。(1) 観察エラー。 (2) オドメーターの誤差。 (3) 不正なデータ関連付けによって引き起こされるエラー。 ロボットが既知の地図の環境に位置する場合、ロボットは既知の位置の特徴マークを観察することでオドメーターの誤差を補正できます。 各観測により、ロボットの位置誤差は観測誤差と特徴マークの位置誤差の合計になる傾向があります。 しかし、スラムでは、環境内のロボットの位置と特徴マークの位置が不明であるため、観測情報は走行距離計の誤差を効果的に補正できず、ロボットの位置誤差は移動距離とともに増加します。ロボット。 ロボットの位置誤差が増加すると、誤ったデータの関連付けが発生し、特徴マークの位置誤差が増加します。 ひいては、特徴マークの誤差によりロボットの位置誤差が増大することになる。 したがって、ロボットの位置誤差は、特徴マークの位置誤差と密接な関係がある。 それらの間の相互作用により、ロボットとフィーチャマークの位置推定に累積誤差が生じ、マップの一貫性を確保することが困難になります。 3. スラムの実装方式 現在、スラム方式は大きく 2 つに分類できます。 (1) 確率モデルに基づく方式：カルマンフィルタ、圧縮フィルタ、FastSLAM などに基づく完全なスラム方式 (2) 非確率モデル方式：sm -スラム、スキャンマッチング、ファジーロジックに基づくデータ関連付けなど。3.1 カルマンフィルターに基づく実装方法統計的な観点から見ると、スラムはフィルタリング問題です。つまり、システムの初期状態と、0 から t までの観測情報および制御情報 (走行距離計の読み取り値) に従って、システムの現在の状態を推定します。 スラムでは、システムの状態はロボットの姿勢 R とマップ情報 m (各特徴マークの位置情報を含む) から構成されます。 システムの運動モデルと観測モデルがガウスノイズを伴う線形モデルであり、システムの状態がガウス分布に従うと仮定すると、スラムはカルマンフィルターによって実現できます。 カルマン フィルターに基づく SLAM には、システム状態の予測と更新という 2 つのステップが含まれます。 同時に、新たな地物マークの追加や地物マークの削除などの地図情報の管理も必要になります。 カルマン フィルターはシステムが線形システムであることを前提としていますが、実際にはロボットの運動モデルや観測モデルは非線形です。 したがって、通常は拡張カルマン フィルターが使用されます。 拡張カルマン フィルターは、一次テイラー展開を通じて非線形モデルを近似的に表します。 非線形モデルに適したもう 1 つのカルマン フィルターは、UKF (アンセンテッド カルマン フィルター) です。 UKF は、条件付きガウス分布を使用して事後確率分布を近似します。 EKF と比較して、UKF は線形化精度が高く、ヤコビ行列を計算する必要がありません。 カルマンフィルターはスラムを実現する基本的な手法となっています。 その共分散行列には、ロボットの位置とマップの不確実な情報が含まれています。 ロボットが環境内の特徴的な兆候を継続的に観察すると、共分散行列の任意の部分行列の行列式は単調減少します。 理論的には、観測値の数が無限大になる傾向がある場合、各特徴マークの共分散はロボットの開始位置の共分散にのみ関係します。 カルマン フィルターの時間計算量は O () です。 ロボットは一度にいくつかの特徴マークしか観察できないため、カルマン フィルターに基づく SLAM の時間計算量は O () として最適化でき、N はマップ内の特徴マークの数を表します。3.2 ローカルサブマップ方式ローカル サブ マップ手法は、空間の観点からスラムをいくつかの小さなサブ問題に分解します。 サブマップ方式では次のような問題点を考慮する必要がある。（１）サブマップをどのように分割するか。 （２）サブマップ間の関係をどのように表現するか。 （３）サブマップの情報をグローバルマップにどのように移行するか、グローバルマップの整合性は保証できるか。 最も単純なローカルサブマップ手法は、サブマップ間の関係を考慮せず、グローバルマップを一定数の特徴マーカーを含む独立したサブマップに分割し、各サブマップにそれぞれスラムを実装する方法である。 この方法の時間計算量は O (1) です。 ただし、異なるサブマップ間の相関関係を表す有用な情報が失われるため、この方法ではマップのグローバルな一貫性を保証できません。 この点に関して、Leonard et al. 提案された DSM (分離確率マッピング) 手法。 DSM の各サブマップは、独自のロボット位置推定を保存します。 ロボットが 1 つのサブマップ a から別のサブマップ B に入るとき、EKF ベースの方法を使用してサブマップ a の情報がサブマップ B に送信されます。 B.ウィリアムズら。 CLSF (Constrained Local Submap Filter) に基づくスラム法を提案しました。 CLSF は、マップ内に既知のグローバル座標を使用してサブマップを作成します。 ロボットの進行中は観測情報のみを用いてロボット内の特徴マークの位置とローカルサブマップを更新し、ローカルサブマップの情報は一定時間間隔でグローバルマップに送信されます。 実験では 2 つのアルゴリズムが優れたパフォーマンスを持っていることが示されていますが、マップの一貫性を維持できるかどうかは理論的に証明されていません。 J. Guivant et al. 情報損失のないスラム最適化アルゴリズム cekf (圧縮拡張カルマン フィルター) を提案しました。 Cekf は、観測された特徴マークを部分 A と B に分割します。A は、ロボットの現在位置に隣接する領域を表し、アクティブ サブ マップと呼ばれます。 ロボットがアクティブなサブマップ a 内で移動すると、観測情報を使用してロボットとサブマップ a の位置がリアルタイムで更新され、サブマップ B に対する観測情報の影響が再帰的方法で記録されます。 ロボットがアクティブサブマップａから離れると、観測情報はロスなくサブマップＢに送信され、サブマップＢを一括更新すると同時に新たなアクティブサブマップを作成する。 この方法の計算時間は 2 つの部分で構成されます。アクティビティ サブ マップ内のスラム。その時間計算量は O () であり、アクティビティ サブ マップ a 内の特徴マークの数です。 サブマップ B の更新の時間計算量は O () で、これはマップ B 内の特徴マークの数です。サブマップのマージの時間間隔が長い場合、cekf はスラム計算の量を効果的に削減できます。3.3 無相関化法スラムの複雑さを軽減するもう 1 つの方法は、相関関係を表す共分散行列内の値が小さい一部の要素を無視し、それを疎行列に変えることです。 ただし、情報が失われるため、マップの一貫性も失われます。 ただし、共分散行列の要素の多くがゼロに近いかゼロに等しいように共分散行列の表現を変更できる場合は、無視しても問題ありません。 SLAM Based on Extended Information Filter (EIF) は、この考え方に基づいています。 EIF は EKF を情報ベースで表現したものです。 それらの違いは、情報を異なる形式で表すことです。 EIFでは、情報行列と呼ばれるスラムの不確実な情報を共分散行列の逆行列で表現します。 2 つの無関係な情報行列の融合は、2 つの行列の加算として単純に表現できます。 情報行列の非対角要素のそれぞれは、ロボットと特徴マークの間、または特徴マークと特徴マークの間の制約関係を表します。 これらの制約関係は、システム状態の信号関係を通じてローカルに更新できます。 この局所的な更新により、情報行列は疎行列に近似し、間引きによって生じる誤差は非常に小さくなります。 これによると、S. Thrun et al。 スパース情報フィルタseif(スパース拡張情報フィルタ)に基づくスラム法を提案し、スパース情報行列を用いたスラムの時間計算量がOであることを証明した(1)。 EIF はスラムの時間計算量を効果的に軽減できますが、マップ情報の表現と管理には依然としていくつかの問題があります。 まず、システム状態の平均値は一定時間内でしか計算できません。 第２に、ＥＩＦに基づくスラム法では、特徴マークの追加や削除が不便である。