深層強化学習テクノロジーの急速な発展に伴い、ますます多くの研究チームが自動運転の意思決定にそれを適用し始めており、行動の意思決定を動作計画モジュールと統合して運転軌跡を直接学習しています。
自動運転における意思決定計画モジュールは、自動運転能力を測定・評価するための中核指標の一つであり、主なタスクは、センサーからさまざまな感覚情報を受信した後、現在の環境を分析し、指示を発行することです。基礎となる制御モジュールに送信します。一般的な意思決定計画モジュールは、グローバル パス計画、行動意思決定、動作計画の 3 つのレベルに分割できます。
完全な自動運転システムにおいて、認識モジュールを人間の目や耳にたとえると、意思決定計画は自動運転の頭脳に相当します。センサーからさまざまな感覚情報を受け取った脳は、現在の環境を分析し、その下にある制御モジュールに指示を出しますが、このプロセスが意思決定および計画モジュールの主なタスクです。同時に、意思決定計画モジュールがどれだけ複雑なシナリオに対応できるかは、自動運転機能を測定および評価するための中心的な指標の 1 つでもあります [1]。
図 1. 自動運転システムにおける意思決定計画モジュールの階層構造 ([2]
から引用) 図 1 に示すように、典型的な意思決定 計画モジュールは 3 つのレベルに分けることができます。
このうち、グローバルルートプランニング(Route Planning)は、与えられた走行目的地を受信した後、地図情報を組み合わせて、その後の具体的なルート計画の参考となるグローバルルートを生成します。グローバル パスの行動意思決定層は、認識モジュールから取得した環境情報 (他の車両や歩行者、障害物、道路上の交通規則情報など) を組み合わせて、特定の行動決定 (追い越しのための車線変更の選択など) を行います。またはフォロー);
最後に、モーション プランニング レイヤーは、特定の動作決定に基づいて、特定の制約 (車両自体の動的制約、衝突回避、乗客の快適性など) を満たす経路の生成を計画します。これは、車両の最終的な走行経路を決定するための制御モジュールの入力として使用されます。
この記事では、各層の主な機能と共通のアルゴリズムをそれぞれ紹介し、さまざまなアルゴリズムの長所と短所、および適用可能なシナリオを比較します。
02 グローバル パス プランニング (ルート プランニング)
図 2. グローバル パス プランニング ダイアグラム
ダイクストラ アルゴリズムはコンピューターによって開発されました。科学者のエドガー W. ダイクストラは、グラフ内のノード間の最短経路を見つける方法を 1956 年に提案しました。ダイクストラのアルゴリズムでは、始点からの各ノードの総移動コストを計算する必要があります。同時に、優先キュー構造も必要です。通過するすべてのノードは、優先キューに入れられるときにコストに従ってソートされます。アルゴリズムの実行中、毎回、最小コストのノードが次に通過するノードとして優先キューから選択されます。最後まで。
ダイクストラ アルゴリズムの利点は、指定されたパスが最適であることです。欠点は、明確な方向なしで周囲を探索するため、計算時間が比較的高い (O(N2)) ことです。
2. A* アルゴリズムダイクストラ アルゴリズムの検索効率の問題を解決するために、1968 年に Peter Hart、Nils Nilsson、および Nils Nilsson によって A アルゴリズムが開発されました。スタンフォード研究所の Bertram Raphael 氏が発表したこのバージョンの主な改良点は、ヒューリスティック関数を使用して検索プロセスをガイドすることです。具体的には、アルゴリズム A は次の関数を通じて各ノードの優先度を計算します:
f(n)=g(n) h(n)
ここで:
グローバル パスを決定した後、自動運転車は特定の道路状況、交通ルール、他の車両や歩行者などの行動決定に基づいて適切な決定を下す必要があります。 。
このプロセスは 3 つの主要な問題に直面しています。
まず、実際の運転シーンは常に変化しています。それらをどのようにカバーするか?
第二に、実際の運転シーンはマルチエージェントの意思決定環境であり、メイン車両を含む各参加者の行動は、環境内の他の参加者に影響を与えるため、環境内の他の参加者の行動を予測する;
最後に、自動運転車が環境情報を 100% 認識することは不可能です。たとえば、障害物によって妨げられる危険な状況が数多く考えられます。
上記の点に基づいて、自動運転行動の意思決定層で解決する必要があるのは、マルチエージェントの意思決定の複雑な環境における知覚の不確実性の計画問題です。この問題は、L4およびL5レベルの自動運転技術を真に実現する上での中心的なボトルネックの1つであると言えますが、近年、深層強化学習などの急速な発展により、この問題を解決する新たなアイデアと夜明けがもたらされています。問題。
行動意思決定層のモデルは 4 つのカテゴリに分類され、個別に紹介されています [5]:
1. 有限状態マシン モデル
自動運転車両 初期の意思決定モデルは有限状態機械モデル [6] であり、車両は駐車、車線変更、追い越し、回避、徐行など、現在の環境に応じて適切な運転行動を選択します。機械モデルは、有限の有向接続グラフを構築し、さまざまな運転状態と状態間の遷移関係を記述し、運転状態の遷移に基づいて運転アクションを反応的に生成します。
有限状態マシン モデルは、そのシンプルさと実装の容易さから、自動運転の分野で最も広く使用されている行動意思決定モデルです。ただし、このタイプのモデルは環境のダイナミクスと不確実性を無視しています。また、運転シーンの特性が異なる場合、多くの場合、状態の分割と管理は煩雑であり、単純なシナリオにほとんど適していますが、構造的特徴が豊富な都市部の道路環境では、行動に関する意思決定タスクを実行することは困難です。
2. デシジョン ツリー モデル
デシジョン/動作ツリー モデル [7] はステート マシン モデルに似ており、属性値を通じてさまざまなパラメーターを反応的に選択します。現在の運転状態の運転アクションですが、このタイプのモデルが運転状態と制御ロジックをツリー構造に固定化し、トップダウンの「ポーリング」メカニズムを通じて運転戦略を探索する点が異なります。このタイプの意思決定モデルは視覚的な制御ロジックを備えており、制御ノードは再利用できますが、運転シナリオごとにオフラインで意思決定ネットワークを定義する必要があり、状態空間と動作空間が大きい場合、制御ロジックはもっと複雑になります。さらに、このタイプのモデルは、交通環境に存在する不確実要素を考慮することもできません。
3. 知識ベースの推論および意思決定モデル
知識ベースの推論および意思決定モデルは、次のマッピング関係によって人間のドライバーの行動を模倣します。 「シーン特性 - 駆動アクション」意思決定プロセス。このタイプのモデルは、運転知識を知識ベースまたはニューラル ネットワークに保存します。ここでの運転知識は、主に、ルール、ケース、またはシーンの特徴と運転アクションとの間のマッピング関係によって表されます。次に、運転アクションは、「クエリ」メカニズムを通じて知識ベースまたは訓練されたネットワーク構造から推測されます。
このタイプのモデルには主に、ルールベースの推論システム [8]、ケースベースの推論システム [9]、およびニューラル ネットワーク ベースのマッピング モデル [10] が含まれます。
このタイプのモデルは、事前の運転知識とトレーニング データに大きく依存しており、運転知識の慎重な編成、管理、更新が必要です。ニューラル ネットワークに基づくマッピング モデルでは、データの注釈と知識の統合プロセスを省略できますが、
4. 価値に基づく意思決定モデル
最大効用理論によると、効用/価値に基づく意思決定の基本的な考え方モデル作成モデルは，選択基準に基づいて複数の条件を選択し，選択肢の中から最適な運転戦略・行動を選択するものである [12]．
各運転行動の質を評価するために、このタイプのモデルはユーティリティ (効用) 関数または価値 (価値) 関数を定義し、特定の基準属性に基づいて運転戦略が運転タスクの目的をどの程度満たしているかを定量的に評価します。無人運転タスクの場合、これらの基準属性は、安全性、快適性、運転効率などになります。有用性と価値は、単一の属性または複数の属性によって決定できます。
オーストラリアのグリフィス大学の Furda と Vlacic は、候補行動セットから最適な運転行動を選択するための多基準意思決定方法を提案しました [13]; シンガポール国立大学の Bandyopadhyay らは、不確実性が認識されている状況を解決するために、POMDP モデル [14] に基づく行動的意思決定; カーネギーメロン大学の Wei J らは、PCB (予測とコスト関数に基づく) に基づく行動的意思決定モデル [15] を提案しました。 、環境の予測を導くための適切なコスト関数をどのように構築するかに焦点を当てています。複数のエージェントが関与する複雑な環境における意思決定の問題を解決するために、ゲーム理論に基づく多くのモデルも研究者によって使用されています。車両間の相互作用を推論するため [16]、[17]、さらに、特徴抽出における利点により、深層強化学習技術も最適な運転行動の生成を完了するために広く使用され始めています [18]。
特定の運転行動を決定した後、私たちがしなければならないことは、最終的にシリーズを生成できるように、「行動」をより具体的な運転「軌道」に変換することです。計画された目標に従って車両の運転を達成するための、車両の特定の制御信号。このプロセスは動作計画と呼ばれます。動作計画の概念は、ロボット工学の分野で長い研究の歴史があります。数学的な観点からは、次のような最適化問題とみなすことができます:
Path計画
#図 3. 経路計画の定義
ロボットに代表される多くのシナリオでは、私たちは周囲を確実なものと考えることができます。この場合、いわゆるパス プランニングは、特定の状態空間 Χ 内で特定の制約を満たすマッピング σ:[0,1]➞Χ を見つけることを指します。これらの制約には次のものが含まれます。開始状態とターゲット ポイントが位置する領域
図 4. 軌道計画の定義
時間次元の増加が大きな課題を引き起こす計画の問題に。たとえば、単一点として抽象化される 2D 環境内で移動するロボットの場合、環境内の障害物は多角形として近似されます。経路計画問題は多項式時間で解くことができますが、時間次元を追加する軌道計画問題は NP 困難問題であることが証明されています。
自動運転の実際のシナリオでは、車両自体であれ、周囲の環境であれ、より正確なモデルを確立することは、最適化問題に対する制約がより複雑になることを意味し、また、解決がより困難になることを意味します。したがって、実際に使用されるアルゴリズムは実際のシナリオの近似に基づいており、モデルの精度とソリューションの効率の間の最適なバランスを追求します。
以下では、自動運転の分野におけるいくつかの一般的なタイプの動作計画アルゴリズムを紹介します。実際には、多くの場合、最終的により良い計画結果を達成し、よりさまざまなニーズを満たすことができる、いくつかのタイプのアイデアの組み合わせです。 。
1. 検索ベースの計画アルゴリズム検索を通じて動作計画の問題を解決することは、最も単純なアイデアの 1 つです。基本的なアイデアは、決定された空間を介して状態空間を渡すことです。この方法はグラフに離散化され、その後、さまざまなヒューリスティック検索アルゴリズムを使用して、実行可能なソリューション、さらには最適なソリューションが検索されます。 状態空間を離散化するプロセスでは、最終的なグリッドが最大のカバーエリアを持ち、重複しないように注意する必要があります。図 5 に示すように、左側のグリッドは 3 つの動作 (直進、左 90 度回転、右 90 度回転) によって生成されます。また、3 つの動作を選択した場合、直進、左 89 度、右 89 度回転します。 °の場合、エリア全体をカバーするグリッド構造を生成することはできません。
図 5. ラスター グラフの構築 ([2] から引用)
状態空間をラスター化した後、以前に紹介したダイクストラを使用できます。検索アルゴリズムを使用して最終計画を完了します。しかし、実際の複雑な環境では、多数のグリッドが存在し、時間の経過とともに環境が動的に変化するため、検索ノードが多すぎることになります。そのため、さまざまな特定のシナリオに対処するために、さまざまな改良されたアルゴリズムが開発されています。 # 1) ハイブリッド A* アルゴリズムは、A* アルゴリズムに基づいており、車両の最大ステアリング問題を考慮します。たとえば、計算された経路上の車両の最大ステアリング方向は 5° 以下に制限されます。このアルゴリズムの現在の適用シナリオには、車の U ターン (DARPA チャレンジに参加するためにスタンフォード大学が使用したジュニアカーは、U ターンを実行するためにこのアルゴリズムを使用しました)、駐車、および高度なハンドル制御を必要とするその他のシナリオが含まれます。
2) D* および D*Lite アルゴリズムは、ダイクストラ アルゴリズムを使用して終点から始点までを事前に検索し、目標点から道路ネットワーク内の各点までの最短経路長 k を保存します。ノードからターゲット ポイントまでの最短経路長 k 実際の長さの値 h (初期ケースでは k==h)、および各ノードの前のノードは、リンクをたどることができることを保証するために保存されます。
計算が完了すると、その時点での最適なパスが求められます。自動車が特定のノードに到達し、そのノードが通行できない（障害物がある）ことをセンサーで検出すると、保存されている道路ネットワーク情報の一部の該当点の h 値が変更（増加）され、そのノードに適合する近傍点が選択されます。 h==k、つまり最適経路上の点は依然として次の点です。
それでは最後まで歩きます。このタイプのアルゴリズムは、未知の環境でのナビゲーションや経路計画に適しており、火星探査車「オポチュニティ」や「スピリット」など、現在のさまざまな移動ロボットや自律走行車で広く使用されています。
2. サンプリングベースの計画アルゴリズム連続状態空間をサンプリングすることで、元の問題を離散系列最適化問題に近似します。コンピューターサイエンスで最も広く使用されているアルゴリズム。動作計画の問題では、基本的なサンプリング ベースのアルゴリズムには、確率的ロードマップ (PRM) アルゴリズムと高速検索ランダム ツリー (RRT) アルゴリズムが含まれます。
図 6. RRT アルゴリズムを使用した U 字型曲線の軌道計画。[19]
ツリーの初期化: ツリーのノード セットとエッジ セットを初期化します。ノード セット 初期状態のみが含まれており、エッジ セットは空です。
上記の基本的なアルゴリズムの説明から、状態空間をサンプリングすることで開始点と終了点を保証できることがわかります。実現可能なソリューションですが、サンプリング プロセスでは空間全体を均一にサンプリングするため、効率が非常に低くなります。複雑なシナリオではリアルタイムのソリューションを実現できません。さらに、最終的な計画結果は、得られた実現可能なソリューションが適切であることを保証できません。最適な解決策。これらの欠点に対応して、さまざまな改良されたアルゴリズムが提案され、自動運転の問題に適用されています。
#効率の向上 - 不均一なサンプリング- ヒューリスティック (hRRT): ヒューリスティック関数を使用して、拡張コストが低いノードがサンプリングされる確率を高めます。
- ドライバー モデルとの組み合わせ: ドライバーの視覚的注意モデルと組み合わせて偏ったサンプリングを行い、視覚的な特徴情報を使用して動作計画をガイドし、計画された軌道が人間の運転行動とより一致するようにします。
#- 新しいメトリクス RG-RRT (到達可能性ガイド付き RT) を構築する: 従来のユークリッド距離メトリクスは、構成または状態間の距離を正確に反映できません。RG-RRT は、ツリー内のノードの到達可能性セットを計算します。サンプリング ポイントからノードまでの距離が、サンプリング ポイントからノードの到達可能なセットまでの距離より大きい場合、そのノードは拡張用に選択される可能性があります。#- 障害物ペナルティの追加 (RC-RRT、EG-RRT、ADD-RRT など): 障害物に近いノードが拡張される確率を減らします。
リアルタイムの改善最適性の向上
ほとんどの場合、高さの変化に関係なく、自動運転の軌道計画問題は 3 次元の制約付き最適化問題 (2D 時空 T) です。元の問題をいくつかの低次元の問題に分解するデカップリング戦略により、問題を解決する難易度が大幅に軽減されます。
1) フレネ座標系
現実世界の道路はすべて曲線であり、自動運転では最適化問題を解く際のパラメータ表現を簡略化するために、通常フレネ座標系が使用されます。
フレネ座標系では、図に示すように、道路の中心線を基準線として使用し、基準線の接線ベクトル t と法線ベクトル n を使用して座標系を確立します。右は車両自体を原点とし、座標軸は互いに直交し、s方向（つまり、基準線に沿った方向、縦方向、Longitudinalと呼ばれることが多い）とd方向（またはL方向）に分けられます。方向、つまり、基準線の現在の法線方向 (水平、Lateral と呼ばれます)、デカルト座標系 (左の図) と比較して、フレネ座標系では問題が大幅に単純化されます。
道路を走行するとき、道路の基準線(つまり、道路の中心線)をいつでも簡単に見つけることができるため、基準線に基づく位置は縦断座標を使用して簡単に表すことができます。距離 S (つまり、道路方向に沿った距離で表されます) と横方向の距離 L (つまり、基準線からの距離) です。
2) パス速度デカップリング手法#フレネ座標系では、パス速度デカップリング手法によりパスと速度がそれぞれ最適化されます。主に静的な障害物を考慮し、動的計画により静的な基準経路（SL寸法）を生成し、生成した経路に基づいて速度計画（ST寸法）を検討します。このプロセスは継続的に繰り返すことができるため、軌道をリアルタイムで更新できます。 Baidu のオープンソース自動運転プラットフォーム Apollo で使用されている EM プランナーは、同様のソリューションに基づいています。このソリューションは高い柔軟性を備えており、多くのシナリオに広く適用できます。
さらに、縦方向の軌道 (ST 寸法) と横方向の軌道 (LT 寸法) を別々に計画するなど、さまざまなデカップリング方法を選択することもできます。ただし、デカップリング手法によって得られる解決策は最適ではない可能性があり、このアルゴリズムは完全ではなく、一部の複雑な環境では実行可能な解決策が見つからない可能性があることに注意してください。
図 8. 一般的なパラメトリック曲線の構築方法 ([19]
より引用) 
パラメトリック曲線構築法の出発点は、運動学や力学制約を含む車両自体の制約であるため、一般的に計画される経路は連続した曲率を持つ必要があります。このタイプの方法では、開始点と目標点に基づいて障害物を考慮し、車両の制約に適合する一連の曲線を構築することで滑らかな経路を提供します。
図 8 に示すように、一般的な曲線には、デュビン曲線 (直線と円弧で構成され、2 次元空間内の単純な車両モデル デュビン モデルの最短曲線族)、クロソイド曲線、および多項式が含まれます。曲線、ベジェ曲線、スプライン曲線など実際の複雑なシナリオに合わせてパラメトリック曲線構築手法を単純に適用することは困難であるため、現在、ますます多くの自動運転システムが他の手法と組み合わせて、計画および生成された軌道を滑らかにして、車両の運動学と力学を満たすようにしています。
5. 人工ポテンシャル場法人工ポテンシャル フィールド法は、物理学の電磁場にヒントを得ており、障害物とターゲットの位置がそれぞれ反発力と重力を発生させることを想定しているため、ポテンシャル フィールドの最速の勾配降下に沿って経路を計画できます。このタイプの方法における重要な問題は、適切なポテンシャル フィールド関数をどのように選択するかということです。たとえば、Stephen Waydo はスムーズな経路計画に流量関数を使用しています [20]。また、Robert Daily は高速車両での調和ポテンシャル フィールド 経路計画法を提案しています。 [21]。単純なシナリオでは、人工ポテンシャル場法は高い解効率を示しますが、最大の問題は、極小値に陥る可能性があり、この場合、得られる経路は最適ではなく、経路が見つからない可能性もあります。
問題を計画する際、時間と空間の複雑さを考慮することに加えて、アルゴリズムの評価では、アルゴリズムが完全性と最適性を備えているかどうかも考慮する必要があります。戻って、確率的な完全性と漸近的な最適性があるかどうかを検討してください。これらの特性の理解に基づいてのみ、モデルの複雑さと最適な効率の間の最適なバランスを達成するために、さまざまな実際のシナリオにさまざまなアルゴリズムを設計および適用できます。
1) 完全性: 始点と目標点の間に経路解が存在する場合は解が得られる必要があり、解が得られない場合は解が存在しないことを意味します。
#2) 確率的完全性: 開始点と目標点の間に経路解がある場合、計画または検索時間が十分に長い限り、必ず経路解が見つかります。 3) 最適性: 計画されたパスは特定の評価指標で最適です (評価指標は一般にパスの長さです) 4) 漸近的最適性: 有限回の計画反復後に得られるパスは最適に近い準最適パスであり、反復ごとに最適パスに近づきます。これは段階的な収束プロセスです
# より引用) ##人類の自動運転への関心は 1925 年にまで遡ることができ、近年では 2004 年から 2007 年にかけて米国国防高等研究計画局 (DARPA) を中心に自動運転の研究ブームが始まり、第 3 回自動運転チャレンジが開催されました [22]図 9 に示します。その後、上記のさまざまな意思決定計画手法の有効性を実際に検証しました。同時に、動作計画手法と制御理論、状態パラメータ推定、機械学習、その他の多分野手法を組み合わせたソリューションが次々と登場し、将来の開発トレンドになります:
1) 車両ダイナミクスとの組み合わせ:動的パラメータの評価指標と最適計画を組み合わせ、最適制御の観点から計画を立てる手法は近年よく用いられており、車両運動要素を十分に考慮し、より合理的な計画軌道を作成することができます。たとえば、モデル予測制御理論 (Model Predictive Control) を使用します。欠点は、車両に対する制約が増えるほど、軌道の最適化が難しくなり、オンラインでのリアルタイム計算の実現が難しくなることです。
2) 状態パラメータ推定と組み合わせる: 状態パラメータ推定により車両パラメータをより正確に取得できるため、状態推定器を計画モジュールに追加して、車両の状態をオンラインで推定してフィードバックすることで軌道を改善できます。プランナーのクオリティの高さ。たとえば、地面の種類が異なると車両の滑り特性が変化し、車両の状態に影響を与えるため、推定されたパラメータを組み合わせることで、軌道をリアルタイムで再計画し、閉ループ計画により軌道の安全性を向上させることができます。
3) 機械学習との組み合わせ: ニューラル ネットワークに代表される人工知能の急速な発展に伴い、多くの従来の計画問題にも新しい解決策がもたらされました。自動運転の分野における開発動向には次のようなものがあります。
以上が自動運転意思決定技術について詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
