Introduction to Autonomous Mobile Robots, 2004, Chapter 6. Planning and Navigation
Introduction to Autonomous Mobile Robots, 2004 * 2011年に2nd Editionが出版されているが, そちらはまだOpenになっていない
[contents:]
- 6. Planning and Navigation
6. Planning and Navigation
6.1 Introduction
この本では、堅牢なモビリティに不可欠なモバイルロボットの要素に焦点を当てています。 locomotion(移動)の運動学;ロボットの環境状況を判断するためのセンサー;そしてその地図に関してローカライズするためのテクニック; ここではロボットのcognitive(認知)レベルに目を向けます。認知は一般に、システムがその最高次の目標を達成するために利用する意図的な意思決定および実行を表します。 移動ロボットの場合、ロバストな移動に直接関連する認知の側面はナビゲーション能力です。その環境および目標位置または一連の位置についての部分的な知識が与えられると、ナビゲーションは、その目標位置にできるだけ効率的かつ確実に到達するようにその知識およびセンサ値に基づいて行動するロボットの能力を包含する。この章の焦点は、前の章のツールをどのように組み合わせてこのナビゲーションの問題を解決できるかにあります。 移動ロボット研究コミュニティ内では、ナビゲーション問題を解決するために非常に多くのアプローチが提案されてきた。この研究の背景からサンプリングすると、たとえ表面的には全く異なるように見えても、実際にこれらのアプローチのすべての間に強い類似性があることが明らかになります。さまざまなナビゲーションアーキテクチャ間の主な違いは、それらが問題をより小さなサブユニットに分解する方法です。以下の6.3節では、相対的な長所と短所を比較しながら、最も人気のあるナビゲーションアーキテクチャについて説明します。 しかし、最初に、セクション6.2では、移動ロボットナビゲーションに必要な2つの重要な追加の能力について説明します。地図および目標位置が与えられると、経路計画は、実行されたときにロボットを目標位置に到達させる軌道を識別することを含む。ロボットは目標を達成するために長期にわたって何をすべきかを決定しなければならないので、経路計画は戦略的な問題解決能力です。 2番目の能力も同様に重要ですが、反対の、戦術的な極端を占めます。リアルタイムのセンサー測定値を考慮すると、障害物回避とは軌道の軌道を調整することを意味します。 衝突を避けるためにロボット。多種多様なアプローチが有能な障害物回避を実証しており、そして我々はこれらのアプローチの多くも同様に調査する。
6.2 Competenes for Navigation: Planning and Reacting
人工知能の文脈では、計画と対応は、しばしば反対のアプローチ、あるいは反対のものと見なされます。実際、移動ロボットなどの物理システムに適用した場合、計画と反応は強力な補完性を持ち、それぞれがお互いの成功にとって重要です。ロボットにとってのナビゲーションの課題は、目標位置に到達するための一連の行動（または計画）を実行することです。実行中、ロボットはまだ目標に到達するような方法で予期しない出来事（例えば障害物）に反応しなければならない。反応しなければ、ロボットが物理的に目標に到達することはないため、計画作業は成果を上げません。計画しなければ、反応的な努力は遠い目標に到達するためにロボットの全体的な行動を導くことはできません。 - やはり、ロボットはその目標に決して到達しません。 ナビゲーション問題の情報理論的定式化はこの相補性を明確にするだろう。ある時点のロボットが地図と初期の信念状態を持っているとしましょう。ロボットの目標は、いくつかの時間的制約を満たしながら位置に到達することです。したがって、ロボットはタイムステップnまたはそれ以前の位置になければなりません。 ロボットの目的は明らかに物理的なものですが、ロボットは実際にはその信念状態を感知することができるだけで、物理的な位置を感知することはできません。この定式化では、計画はtoから1つ以上の軌跡に過ぎません。言い換えれば、計画qとは、計画がとの両方に一致する世界の状態から実行された場合、ロボットの信念状態をからに移行させます。 もちろん問題は後者の条件が満たされないかもしれないということです。ロボットの位置が完全に一致していない可能性は十分にあり、それが不完全または不正確である可能性もあります。さらに、現実の環境は動的です。たとえそれが時間内の単一のスナップショットとして正しいとしても、経時的な変化の仕方に関する計画者のモデルは通常不完全です。 それにもかかわらず、その目標を達成するために、ロボットは計画実行中に得られた新しい情報を組み入れなければならない。時間が進むにつれて、環境が変わり、ロボットのセンサーが新しい情報を収集します。これこそが、反応が重要になるところです。最良の場合では、反応することは、計画された計画の軌道を修正するためにロボットの行動を局所的に調整し、それによってロボットが依然として目標に到達するようにする。ときには、予期しない新しい情報がロボットの戦略的計画の変更を必要とするため、理想的には、計画者が新しい情報を受け取るときに新しい情報も組み入れます。 限界を考慮すると、計画担当者はすべての新しい情報をリアルタイムで組み込み、実際に新しい情報に適切に対応する新しい計画を即座に作成します。この理論的な極端さは、計画の概念と反応マージの概念を統合的な計画と実行と呼び、6.3.4.3節で説明します。 ロボットアーキテクチャに関するこの説明全体を通して有用な概念は、解決策が存在するときはいつでも、特定の設計決定がシステムの望ましい目標を達成する能力を犠牲にするかどうかを含みます。この概念は完全性と呼ばれます。より正式には、ロボットシステムは、すべての起こり得る問題（すなわち、初期の信念状態、地図、および目標）について、目標の信念状態への軌道が存在するときに限り、完全である。詳細については[27]を参照してください。したがって、システムが不完全な場合、解決策はあるもののシステムが解決策を生成できないという問題が少なくとも1つあります。ご想像のとおり、完全性を達成することは野心的な目標です。しばしば、表現や推論のレベルでの計算の複雑さのために完全性が犠牲にされます。分析的には、個々のシステムによって完全性がどのように損なわれるかを理解することが重要です。 以下の節では、移動ロボットの経路計画と障害物回避に適用される際の計画と対応の重要な側面について説明し、表現の決定がシステム全体の潜在的な完成度に与える影響について説明します。詳しくは、[21、30、第25章]を参照してください。
6.2.1 Path Planning
6.2.2 Obstacle avoidance
6.3 Navigation Architectures
経路計画、障害物回避、隠蔽、および知覚的解釈のための技術を考えれば、実世界のアプリケーションのためにこれらをすべて1つの完全なロボットシステムに組み合わせるにはどうすればよいでしょうか。 先へ進む1つの方法は、特定の目的のためにすべてを実装するアプリケーション固有のモノリシックソフトウェアシステムをカスタム設計することです。 これは、機能が少なく、計画されたデモンストレーションがさらに少ない些細な移動ロボットアプリケーションの場合には効率的であり得る。 しかし、洗練された長期の移動ロボットシステムでは、モビリティアーキテクチャの問題は原則的に対処する必要があります。 ナビゲーションアーキテクチャの研究は、移動ロボットナビゲーションシステムを構成するソフトウェアモジュールのための原理設計の研究です。 適切に設計されたナビゲーションアーキテクチャを使用すると、いくつかの具体的な利点があります。
6.3.1 Modularity for code reuse and sharing
ソフトウェア工学の基本原則はソフトウェアのモジュール性を包含しており、同じ一般的な動機が移動ロボットの用途にも等しく当てはまる。しかし、単一のプロジェクトの過程でモバイルロボットのハードウェアやその物理的な環境特性が劇的に変化する可能性があるため、ほとんどの従来のコンピュータが直面していない課題であるため、モジュール性はモバイルロボット工学においてさらに重要です。例えば、以前は超音波距離計のみを使用していたロボットにSickレーザ距離計を導入することができる。あるいは、センサが検出できない障害物がある新しい環境で既存のナビゲータロボットをテストし、それによって新しい経路計画表現を要求することができる。 ロボットの能力の一部を変更して、他のロボットの能力の機能を再検討しなければならないような一連の副作用を引き起こさないようにしたいと思います。例えば、特定の測距センサ群が変わっても、障害物回避モジュールをそのままにしておきたい。もっと極端な例では、ロボットの運動学的構造が三輪車のシャシーから差動駆動のシャシーに変わっても、非ホロノミックな障害物回避モジュールには手を加えないでおくのが理想的です。
6.3.2 Control localization
ロボット制御の位置推定は、移動式ロボットナビゲーションにおいてさらに重要な問題です。基本的な理由は、ロボットアーキテクチャが複数の種類の制御機能（例えば、障害物回避、経路計画、経路実行など）を含むことである。各機能をアーキテクチャ内の特定のユニットにローカライズすることで、個々のテストと制御構成のための原則的な戦略を可能にします。たとえば、衝突回避を考えます。ロボットソフトウェアの変更に対する安定性、および障害物回避システムが正しく実装されていることの集中的な検証のためには、ロボットの障害物回避プロセスに関連するすべてのソフトウェアをローカライズすることが重要です。それとは反対に、ロボットがその環境で有用な役割を果たすためには、高度な計画とタスクベースの意思決定が必要です。このような高レベルの意思決定ソフトウェアをローカライズして、シミュレーションで徹底的にテストし、物理ロボットに直接接続しなくても検証できるようにすることも価値があります。ローカライゼーションの最後の利点は、学習に関連しています。制御を局所化することで、特定の学習アルゴリズムを移動ロボットの全体制御システムの1つの側面にのみ適用できるようになります。このようなターゲットを絞った学習は、学習と従来のモバイルロボット工学をうまく統合する最初の戦略となる可能性があります。 ローカライゼーションとモジュール性の利点は、原則的なナビゲーションアーキテクチャの使用にとって説得力のあるケースを証明しています。 特定のアーキテクチャを特徴付ける1つの方法は、ロボットのソフトウェアを分解することです。特に人工知能レベルの意思決定と下位レベルのロボット制御との間の関係を考慮するとき、多くのお気に入りのロボットアーキテクチャがあります。そのようなハイレベルアーキテクチャの説明については、[2]と[26]を参照してください。ここではナビゲーション能力に集中します。この目的のために、２つの分解、すなわち時間分解および制御分解が特に関連している。 6.3.3節では、これら2種類の分解を定義してから、ビヘイビアの概要を説明します。ビヘイビアは、制御分解を実装するための一般的なツールです。次に、セクション6.3.4で、3種類のナビゲーションアーキテクチャを紹介し、各アーキテクチャについて実装された移動ロボットのケーススタディを説明します。
6.3.3 Techniques for decomposition
分解によって軸が特定され、それに沿ってロボットソフトウェアを区別して個別のモジュールにすることができます。 分解は、さまざまな移動ロボットをより定量的な分類法に分類する方法としても役立ちます。 時間分解は、移動ロボットの動作に対するリアルタイムの要求と非リアルタイムの要求とを区別する。 制御分解は、移動ロボットアーキテクチャ内のさまざまな制御出力を組み合わせて移動ロボットの物理的な動作を生み出す方法を識別します。 以下では、各タイプの分解について詳細に説明します。
6.3.3.1 Temporal decomposition
ロボットソフトウェアの時間的分解は、リアルタイムの要求と非リアルタイムの要求が異なるプロセスを区別します。図6.18は、ナビゲーション用の一般的な時間分解を示しています。この図では、最もリアルタイムのプロセスがスタックの一番下に表示され、最も高いカテゴリはリアルタイムの要求がないプロセスによって占められています。 この例の最下位レベルは、40 Hzの帯域幅など、保証された高速サイクルタイムで進む必要がある機能を表しています。対照的に、準リアルタイム層は、例えば許容可能な最悪の場合の個々のサイクル時間が０．１秒の応答時間を必要とするプロセスを捕捉することができる。戦術的な層は、ロボットの即時の行動に影響を与える意思決定を表すことができ、したがって、いくつかの時間的制約を受けます。 一方、戦略的な層やオフラインの層は、モジュールの応答時間に一時的な制約をほとんど与えずに、ロボットの行動に長期的に影響を与える決定を表します。 4つの相互に関連する重要な傾向は、時間分解と相関しています。これらは石ではありません。例外があります。それにもかかわらず、時間分解のこれらの一般的な性質は啓発的です。 センサーの応答時間: 特定のモジュールのセンサー応答時間は、センサーベースのイベントの取得とそれに対応するモジュールの出力の変化の間の時間として定義できます。 図6.18でスタックを上に移動すると、センサーの応答時間は長くなる傾向があります。 最低レベルのモジュールの場合、センサーの応答時間は多くの場合、rawプロセッサーとセンサーの速度によってのみ制限されます。 最高レベルのモジュールでは、センサの応答は遅くて慎重な意思決定プロセスによって制限される可能性があります。 時間的な深さ: 時間的な深さは、時間的に前後にモジュールの出力に影響を与える一時的なウィンドウに適用する便利な概念です。 時間的範囲は、出力を選択するプロセス中にモジュールによって使用される先読みの量を表します。 時間メモリは、次の出力を決定するためにモジュールによって使用されるセンサ入力の履歴タイムスパンを記述します。 最低レベルのモジュールは両方向の時間的な深さが非常に小さい傾向がありますが、最高レベルのモジュールの熟慮されたプロセスは大きな一時的な記憶を利用し、長期的な結果に基づいてアクションを検討します。 空間的局所性: 時間的なスパンと連動して、レイヤーの空間的影響は、低レベルのモジュールから高レベルのモジュールへと移行するにつれて劇的に増大します。 リアルタイムモジュールは、車輪の速度と方向を制御し、空間的に局所化された動作を制御する傾向があります。 ハイレベルの戦略的意思決定は、現地の立場にはほとんどまたはまったく関係ありませんが、将来の世界的な立場に情報を提供します。 コンテキストの特定性: モジュールは、その直接の入力の関数としてだけでなく、ロボットの環境の表現のような他の変数によって捉えられるようなロボットの文脈の関数としても決定を下します。最低レベルのモジュールは、ほとんどコンテキストを使用せず、したがって比較的コンテキストに影響されにくいため、即時のセンサー入力の結果として直接出力を生成する傾向があります。最上位モジュールは、非常に高いコンテキスト特異性を示す傾向があります。戦略的な意思決定のために、同じセンサ値が与えられたとしても、他の状況パラメータに応じて劇的に異なる出力が考えられます。 これらの傾向を示す例を図6.19に示します。これは、単純化されたナビゲーションアーキテクチャを4つのモジュールに時間分解したものです。最低レベルでは、PID制御ループがモータ速度を制御するためのフィードバックを提供します。緊急停止モジュールは、近距離の光センサーとバンパーを使用して、差し迫った衝突を予測したときにモーターへの電流を遮断します。ロボットダイナミクスの知識は、このモジュールが本来PIDモジュールよりも大きな時間的範囲を持つことを意味します。次のモジュールでは、ロボットのかなり手前の障害物を特定し、コースを少しずらすために、長距離のレーザー距離計センサーリターンを使用します。最後に、Path Plannerモジュールは、ロボットの初期位置と目標位置を取得し、実行のための初期軌道を生成します。この軌道は、ロボットがその過程で収集する実際の障害物に基づいて変更されます。 モジュールのサイクルタイム、つまり帯域幅は、隣接するモジュール間で桁違いに変化することに注意してください。 このような劇的な違いは実際のナビゲーションアーキテクチャでは一般的であるため、時間分解は移動ロボットのナビゲーションアーキテクチャの変動の大きな軸を捉える傾向があります。
6.3.3.2 Control decomposition
時間分解はソフトウェアモジュールの時間的振る舞いに基づいて区別されますが、制御分解は各モジュールの出力がロボット全体の制御出力にどのように寄与するかを識別します。 制御分解の提示は、評価者が離散システムの表現と分析の基本原則を理解することを要求する。 離散系の理論と形式論の明確な紹介については、[17、71]を参照してください。 その接続性が検査されることを望むシステム全体のメンバーであるように、ロボットアルゴリズムおよび物理的ロボットインスタンス化（すなわち、ロボット形態およびその環境）を考える。 このシステム全体は一連のモジュールで構成され、各モジュールは入力と出力を介して他のモジュールに接続されています。 システムは閉じています。つまり、すべてのモジュールの入力は、のモジュールの出力です。 各モジュールには、正確に1つの出力と1つ以上の入力があります。 1つの出力は他のモジュール入力にいくつでも接続できます。 物理的なロボットと環境を表すために、特別なモジュールをさらに名前を付けます。 通常、我々は、ロボットアルゴリズムが影響を与えることを意図している、そしてそこからロボットアルゴリズムが知覚的な入力を引き出すことを意図している物理的なオブジェクトを表します。 このモジュールには1つの入力行と1つの出力行があります。 の入力は、物理ロボットの完全な動作仕様を表します。 の出力は、ロボットへの完全な知覚的出力を表します。 当然のことながら、物理的ロボットは、多くの可能な自由度、および同様に多くの個別のセンサを有することができる。 しかし、この解析では、単に入力/出力ベクトル全体を想像して、rを単純に1つの入力と1つの出力に単純化します。 簡単にするために、asの入力とロボットのセンサー測定値を参照します。 制御システムの他の部分から見ると、ロボットのセンサー値は入力であり、ロボットの動作は出力です。 制御分解は、ロボットアルゴリズムを含むこのシステムの部分を介して異なる種類の制御経路を区別する。 極端な場合には、図6.20に示すように、完全に線形、つまり順次の制御経路を検討することができます。 このようなシリアルシステムは、関連するすべてのモジュールの内部状態とロボットの知覚の値を順番に使用して、次のロボットの動作を計算します。 純粋なシリアルアーキテクチャには、予測可能性と検証可能性に関する利点があります。 各モジュールの状態と出力は、モジュールから上流のモジュールから受け取る入力に完全に依存するため、ロボットを含むシステム全体は単一の整形式ループです。 したがって、システムの全体的な動作は、よく知られている離散フォワードシミュレーション法を使用して評価できます。 図6.21は、完全なパラレル制御アーキテクチャである純粋なシリアル制御の極端な反対を示しています。 rを厳密に1つの入力を持つモジュールとして定義することを選択したので、この並列システムには、rの消費に対して単一の出力を提供する特別なモジュールが含まれています。 直感的には、完全並列システムは、システムの制御出力に対する責任を複数のモジュールに分散させます。 純粋な順次システムでは、制御フローは一連のモジュールを通る線形シーケンスです。 ここで、制御フローには、複数のモジュールの結果が任意の方法で影響を与える可能性がある時点での組み合わせステップが含まれています。 したがって、制御の並列化は重要な問題を引き起こします。各コンポーネントモジュールの出力は、どのようにしての値に関する全体的な決定を通知するのでしょうか。 １つの単純な組み合わせ技術は時間的切り替えである。 この場合、スイッチドパラレルと呼ばれ、システムは並列分解を行いますが、特定の瞬間に出力を1つの特定のモジュールに起因させることができます。 canの値は、もちろん各連続した瞬間に異なるモジュールに依存しますが、の瞬間値は常に単一のモジュールの機能に基づいて決定することができます。 例えば、ロボットが障害物回避モジュールおよび経路追跡モジュールを有すると仮定する。 １つの切り替え制御の実施は、ロボットが全ての感知された障害物から５０ｃｍ以上離れているときはいつでも経路追従推奨の実行、及びいずれかのセンサが５０ｃｍより近い範囲を報告するときの障害物回避推奨の実行を含み得る。 このような切り替え制御の利点は、切り替えが比較的まれである場合に特に明白です。 各モジュールの振る舞いがよく理解されていれば、切り替え制御ロボットの振る舞いを特徴付けるのは簡単です。時には障害物を回避し、それ以外の場合はそれをたどります。 各モジュールが独立してテストされている場合は、切り替え制御システムもうまく機能する可能性があります。 2つの重要なデメリットがあります。 まず、切り替え自体が高頻度のイベントであると、ロボットの全体的な動作がかなり悪くなる可能性があります。 このような場合、ロボットは不安定になる可能性があり、経路追従でも障害物回避でもない行動に劇的に発展するようにモーションモードを非常に速く切り替えます。 切り替え制御のもう1つの欠点は、ロボットが障害物回避時（およびその逆）に経路追従バイアスがないことです。 したがって、制御が複数のモジュール間での推奨事項を混在させる必要がある場合、切り替え制御方法は失敗します。 対照的に、はるかに複雑な混合並列モデルでは、任意の時点で制御を複数のモジュール間で共有できます。たとえば、同じロボットが障害物回避モジュールの出力を常に取得し、それを速度ベクトルに変換して、ベクトル加算を使用して軌跡追跡モジュールの出力と組み合わせることができます。その場合、ロボットの出力は単一のモジュールによるものではなく、両方のモジュールの出力を数学的に組み合わせたものになります。混合並列制御はスイッチ制御よりも一般的ですが、その意味でも、うまく使用するのがより難しい手法です。切り替え制御では、不適切な切り替え動作から最も悪い動作が発生しますが、混在制御では、ロボットの動作が非常に簡単に悪くなることがあります。複数の推奨を数学的に組み合わせることは、障害物を回避するために急な方向を決定するときに複数のベクトルを組み合わせることがまっすぐという非常に悪い決定をもたらす可能性があるのと同様に、グローバルに優れた結果を保証しません。したがって、効果的な混合結果をもたらす混合式と個々のモジュール仕様を作成するために、混合並列制御の実装には細心の注意を払う必要があります。 交換並列アーキテクチャと混合並列アーキテクチャはどちらも、振舞いベースのロボティクスコミュニティでは一般的です。 Ａｒｋｉｎ ［２］は、動作（すなわち、上記の議論におけるモジュール）がセンサ値ベクトルをモータ値ベクトルにマッピングするモータスキーマアーキテクチャを提案する。 ロボットアルゴリズムの出力は、混合並列システムと同様に、個々の行動出力の線形結合を使用して生成されます。 対照的に、Maes [103、104]は、各行動の活性化レベルを比較および更新することによって行動が離散的に選択される行動ネットワークを作成することによって、スイッチドパラレルアーキテクチャを作成します。 能動モデルは活性化レベルではなく抑制メカニズムを介して選択されますが、Brooksの包含アーキテクチャ[45]は、スイッチドパラレルアーキテクチャの別の例です。 さらなる議論に関しては、[2]を見てください。 並列制御の1つの全体的な不利な点は、ロボット性能の検証が非常に難しいことです。 そのようなシステムはしばしば真に並列のマルチスレッド実装を含むので、考えられるすべてのモジュール - モジュール相互作用を適切に表すのに必要とされるロボット - 環境相互作用およびセンサタイミングの複雑さをシミュレートすることは困難または不可能であり得る。 したがって、並列制御コミュニティでの多くのテストは、物理的なロボットを使って経験的に行われます。 並列制御の重要な利点は、その生体模倣的側面です。 複雑な有機生物は、高度な真の並列性（例えば、人間の目）から利益を得ており、並列制御コミュニティの１つの目的は、この生物学的に共通の戦略を理解し、それをロボット工学における利点に活用することである。
6.3.4 Case studies: tiered robot architectures(階層ロボットアーキテクチャ)
ロボット技術者は常に複数のモジュールを構成してそのアーキテクチャーを構成するという共通のテーマで、ロボットアーキテクチャーの時間分解および制御分解について説明しました。このことを念頭に置いて、全体的な移動ロボットのナビゲーション作業に再び目を向けましょう。明らかに、ロボットの行動は、例えば経路追従や障害物回避などのリアルタイムレベルのロボット制御において重要な役割を果たす。より高い時間的レベルでは、意図された経路に沿ってロボットの動きを達成するために、より戦術的なタスクは行動またはモジュールの活性化を調節する必要がある。さらに高いレベルでは、グローバルプランナーはグローバルな先見性を持った戦術的なタスクを提供するためのパスを生成することができます。 第1章では、情報の流れの観点から移動ロボットナビゲータのそのようなモジュールを示す機能分解を紹介しました。関連する図は、ここでも図6.22として示されています。 そのような表現では、弧はリアルタイムおよび非リアルタイム能力の側面を表します。例えば、障害物回避は、位置特定モジュールからの入力をほとんど必要とせず、認知レベルでの迅速な決定とそれに続く運動制御の実行からなる。対照的に、PID位置フィードバックループはすべての高水準処理を迂回し、エンコーダ値の知覚をモーション制御における最低レベルのPID制御ループに直接結び付けます。 ４つのソフトウェアモジュールを通る弧の軌跡は、そのような表現における時間的情報を提供する。 この章のツールを使用して、機能の一時的な分解の観点からこれと同じアーキテクチャーを提示することができます。ナビゲーションシステムにおける戦略的プロセス、戦術的プロセス、およびリアルタイムプロセスの相互作用について説明したいので、これは特に便利です。 図6.23は、自律型宇宙船Deep Space Oneの設計に使用されたPellとその同僚のアプローチ[120]に基づく一般的な階層型アーキテクチャを示しています。この図は、ロボット能力の時間的分解を示す点で図6.19と似ています。しかしながら、各モジュールを隣接するモジュールから分離する境界はロボットナビゲーションに特有のものである。 経路計画は移動ロボットのための戦略的レベルの意思決定を具体化する。経路計画は、利用可能なすべてのグローバル情報を非リアルタイムで使用して、ロボットに対するローカルアクションの正しい順序を識別します。他の極端な例では、リアルタイム制御は広帯域幅と狭いセンサーエフェクター制御ループを必要とする能力を表します。最低レベルでは、これにはモータ速度PIDループが含まれます。その上、リアルタイム制御には、スイッチまたは混合並列アーキテクチャを形成する可能性のある低レベルの動作も含まれます。 パスプランナーとリアルタイム制御層の間には、計画と実行の間のインターフェースを仲介する責任があるエグゼクティブが配置されます。エグゼクティブは、プランナーから受け取る情報に基づいて行動の活性化を管理する責任があります。経営幹部はまた、失敗を認識し、節約し（ロボットを安定状態にする）、そして必要に応じてプランナを再起動することさえも担当する。ローカライズとマッピングの場合のように、すべての戦術的な意思決定とロボットの短期記憶の頻繁な更新を含むのは、このアーキテクチャのエグゼクティブです。 今日の移動ロボット工学で多くの特殊な形で使われているこの一般的なアーキテクチャと、1969年に最初の移動ロボットの1つであるShakeyによって実装されたアーキテクチャとの類似性に注目することは興味深いです[115]。 Shakeyは、最も低いアーキテクチャー層を形成するLLA（低レベルのアクション）を持っていました。各LLAの実装には、今日の動作と同じように、センサー値を厳密なループで使用することが含まれていました。その上、中間のアーキテクチャー層には、実行中の知覚的フィードバックに基づいて必要に応じてLLAをアクティブ化および非アクティブ化するILA（中間レベルのアクション）が含まれていました。最後に、Shakeyの最上位層はSTRIPS（Stanford Research Institute計画システム）であり、これはグローバルな先読みと計画を提供し、一連のタスクを実行のために中間管理層に提供しました。 図6.23に示した一般的なアーキテクチャはロボットナビゲーションのモデルとして有用ですが、ロボティクスコミュニティのさまざまな実装はまったく異なる可能性があります。以下では、一般的な階層型アーキテクチャの3つの特定のバージョンを提示し、各バージョンについて少なくとも1つの実世界の移動ロボットの実装について説明します。さまざまなロボットアーキテクチャのより広範な議論については、[26]を参照してください。
6.3.4.1 Off-line planning
計画と実行の最も単純で可能な統合は、まったく統合ではありません。図6.24を検討してください。この図では、2つのソフトウェア層しかありません。そのようなナビゲーションアーキテクチャでは、経営者はその計画の立案者を自由には持っていないが、所望の目的地へ旅行するための先験的にすべての関連する計画を含まなければならない。 プランナーを完全に除外する戦略は、もちろん非常に限定的です。そのようなロボットを新しい環境に移動させることは、ナビゲーションシステムの新しい具体化を要求するので、この方法はナビゲーション問題に対する一般的な解決策としては有用ではない。しかしながら、そのようなロボットシステムは存在し、そしてこの方法は２つの場合に有用であり得る。 スタティックルートベースのアプリケーション: ルートベースのナビゲーションシステムを使用してロボットが完全に静的な環境で動作する移動ロボットの用途では、離散的な目標位置の数が非常に少ないため、環境表現はすべての所望の目標点への経路を直接含むことができる。例えば、工場または倉庫の設定では、ロボットは埋設されたガイドワイヤをたどることによって単一のループ経路を移動することがあります。このような産業用アプリケーションでは、事前にコンパイルされたルートベースのソリューションのセットをロボットプログラマが簡単に生成できる場合、パス計画システムはまったく不要なことがあります。 Chipsモバイルロボットは、このアーキテクチャを使用している博物館ロボットの一例です（118）。チップは、色付きのランドマークで定義された単方向ループトラックで動作します。さらに、それはそれが止まることを許されるわずか１２の別々の場所を有する。この環境モデルは単純なので、チップスには、パスプランナーがソリューションパスを検索するための一般的なマップではなく、各目標位置に到達するために必要なパスを直接キャッシュするエグゼクティブレイヤが含まれています。 非常に高い信頼性: 当然のことながら、オンライン計画を回避するもう1つの理由は、システムの信頼性を最大にすることです。計画ソフトウェアは移動ロボットのソフトウェアシステムの最も洗練された部分であり、そして理論的には少なくとも計画は問題の複雑さに指数関数的に時間がかかり得るので、成功した計画に厳しい時間的制約を課すことは不可能ではないにしても難しい。すべての可能な解決策をオフラインで計算することによって、産業用移動ロボットは（もちろんかなりのメモリを犠牲にしながら）効果的な一定時間計画のために多用途性を交換することができる。この理由のためのオフライン計画の現実的な例は、スペースシャトル飛行のために設計された緊急時対応計画に見ることができます。オンラインで問題解決をするために宇宙飛行士を要求する代わりに、何千もの考えられる問題が地球上で仮定され、そして完全な条件付き計画がシャトル飛行の前に設計されそして公表される。基本的な目標は、宇宙飛行士が問題を解決し始める前に経過する時間の絶対的な上限を提供することであり、この性能保証を達成するために多くの地上時間と書類を犠牲にすることです。
6.3.4.2 Episodic planning
オフラインで計画することの基本的な情報理論的な欠点は、実行時にロボットが情報を提供する知覚的入力に確実に遭遇することであり、その後の実行中にこの追加情報を考慮に入れることは合理的である。エピソードプランニングは、計算上扱いやすい方法でこの問題を解決するため、今日の移動ロボットナビゲーションにおいて最も一般的な方法です。 図6.25に示すように、構造は図6.23の一般的なアーキテクチャのように3層になっています。プランナーの役割の背後にある直感は次のとおりです。計画は計算集約的であり、したがって計画が多すぎると重大なデメリットがあります。しかし、経営陣は、戦略的方向性の著しい変化を正当化するのに十分な情報（例えば、特徴抽出による）に遭遇したときを識別するのに優れた立場にある。このような時点で、エグゼクティブはプランナを呼び出して、たとえば目標への新しい道筋を生成します。 再計画の引き金となる最も明白な条件は、おそらく、意図した移動経路上の閉塞の検出です。例えば、[129]では、パスをたどる振る舞いは、数秒間進行に失敗した場合に失敗を返します。エグゼクティブはこの失敗通知を受け取り、ロボットの周囲の短期的な居住グリッド表示を変更し、このローカル環境マップへの変更を考慮してパスプランナーを起動します。 より多くの情報が取得されるまで計画を遅らせる一般的な手法は、据え置き計画と呼ばれます。この技術は、ロボットが動くにつれてより正確になる動的地図を有する移動ロボットにおいて特に有用である。例えば、市販のＣｙｅロボットは、一組の目標位置を与えられ得る。その草原の幅優先計画アルゴリズムを使用して、このロボットは最も近いゴール位置だけに詳細な経路をプロットして、この計画を実行します。このゴール位置に達すると、そのマップは動きの間に抽出された知覚情報に基づいて変化しているでしょう。そのとき初めて、Cyeのエグゼクティブはパスプランナーに新しい場所から次の目標場所へのパスを生成させるようになります。 ロボットPygmalionは、予期せぬ障害に遭遇したときに、より洗練された戦略とともにエピソード計画アーキテクチャを実装しています[36、122]。最低レベルの行動でもうまくいかない場合、エグゼクティブはロボットを90度回転させてやり直すことで障害物を乗り越える道を見つけようとします。ロボットは運動学的に対称ではないのでこれは価値があります、そしてそれ故に特定の障害物コースを通してサーボをかけることは他のものよりある方向に容易かもしれません。 Pygmalionの環境表現は、連続的な幾何学モデルとルート計画のための抽象的なトポロジカルネットワークで構成されています。したがって、障害物を取り除こうとする試みが何度も失敗した場合、ロボットの幹部は2つの適切なノード間のトポロジ接続を一時的に切断し、プランナを再度起動して、ゴールへの新しい一連のウェイポイントを生成します。次に、最近のレーザー測距データをローカルマップの一種として使用して（図6.25を参照）、幾何学的経路計画者はロボットの現在位置から次の中間地点までの経路を生成します。 要約すると、エピソード計画アーキテクチャは、移動ロボット研究コミュニティで非常に人気があります。これらは、環境変化や新しい目標への対応の多様性と、戦術的な経営層の迅速な対応、およびリアルタイムのロボット動作を制御する行動を組み合わせたものです。図6.25に示すように、このようなシステムでは、短期のローカルマップとより戦略的なグローバルマップの両方を使用するのが一般的です。そのような二重表現における役員の仕事の一部は、ローカルマップに統合された新しい情報がいつグローバルな知識ベースにコピーされるのに十分過渡的でないかを決定することです。
6.3.4.3 Integrated planning and execution
もちろん、商用の移動ロボットのアーキテクチャには、単なるナビゲーションよりも多くの機能が含まれている必要があります。しかし、この議論をナビゲーションアーキテクチャの問題に限定することは、最初は縮退した解決策のように見えるかもしれません。 図6.26に示されているアーキテクチャは、図6.24のオフライン計画アーキテクチャに似ているように見えるかもしれませんが、実際にはかなり高度です。この場合、エグゼクティブとプランナーの間に一時的な分解がなくなったため、プランナー層は消えました。計画は、役員の名目上の活動サイクルのほんの一部に過ぎません。 実行時間がもはや重要ではなくなるまで計画をスピードアップするという考えは、希望的に思えるかもしれません。しかし、特定の環境で特定のアルゴリズムを使用して、計画コストのそのような削減が実証されています。の仕事を検討 Stentz [139]。 Stentzは、部分的に知られている地形を高速で走行する大型のオフロード車用の移動ロボット制御アーキテクチャを設計しました。コンピュータサイエンスの高度なキャッシング技術を使用して、StentzはD *と呼ばれるグラスファイヤパス計画アルゴリズムを最適化し、グローバルパス計画がエグゼクティブの基本制御ループ内で可能になるようにしました。 図6.26に示す結果は、ローカル表現とグローバル表現が同じで、エグゼクティブが問題に必要なすべてのグローバル計画機能を内蔵しているアーキテクチャです。このアプローチの利点は、次のとおりです。すべてのサイクルはグローバルパスプランナーによって導かれるため、ロボットが収集したすべての情報を考慮すると最適です。もちろん、この方法は計算上困難であり、プロセッサの速度がさらに向上するまで、より複雑な環境では実用的ではありません。環境の規模が大きくなるにつれて、適用可能性の基本的な制限もありますが、この方法を実際のシナリオの規模に適用する場合、これはまだ障壁とはなっていません。 最近の統合計画および実行方法D *の成功は、ロボットナビゲーションアーキテクチャの設計者がロボットのすべての側面とその環境タスクだけでなく、プロセッサとメモリテクノロジの状態も考慮する必要があるという事実を強調しています。 。私たちは、移動ロボットのアーキテクチャ設計が今後何年にもわたり活発なイノベーション分野であり続けることを期待しています。ロボットセンサーの発明からマイクロプロセッサの高速化に至るまでのあらゆる形態の技術的進歩は、これまで想像もできなかった戦術が現実のものとなるにつれて、移動ロボットアーキテクチャにおける新たな革命を促進する可能性が高い。
End of Chapter 6
