EurekaMoments

ロボットや自動車の自律移動に関する知識や技術、プログラミング、ソフトウェア開発について勉強したことをメモするブログ

論文 Autonomous Driving in Urban Environmentsを読んだメモ(更新中)

目次

背景・目的

自動運転におけるブレーキ制御やACCに関する論文を調べていたら、アメリカ屈指の名門私立研究大学であるカーネギーメロン大学の研究室が開発した無人ロボット車「Boss」の技術論文が公開されているのをネットで見つけました。自動運転分野では超有名ですが、今までしっかりと論文を読もうとしていなかったので、これを機会に精読してメモを残そうと思います。論文の原本のPDFはこちら↓

http://file:///C:/Users/shisa/Works/Papers/Collision%20Detection/Urmson_et_al-2008-Journal_of_Field_Robotics.pdf

大学と研究室について

この論文を出したカーネギーメロン大学と、その研究室である「General Motors - Carnegie Mellon Autonomous Driving Collaborative Research Lab」については、以下のリンクをご覧ください。

カーネギーメロン大学 - Wikipedia

www.ri.cmu.edu

1. Introduction

f:id:sy4310:20180804134400p:plain この論文では、Figure 1にある無人ロボット車「Boss」の組み込まれた自動運転技術のアルゴリズムとメカニズムについて述べる。Bossの開発は、カーネギーメロン大学の学生とスタッフ、そしてGeneral Mortors, Caterpillar, Continental, Intelといった企業からの研究者達により行われた。
周囲の車両や静的な障害物を検知し、走路に追従するための位置計測を行うためのGPS、レーザー、レーダー、そしてカメラが搭載されている。また、Motion Planning, Perception, Mission Planning, Behavioralという複数のサブシステムで構成されている。

2. Boss

Bossはゼネラルモーターズ製のSUVであるシボレー・タホの2007年モデルを自動運転のために改造したものである。通常よりも素早くブレーキを踏めるようにし、ブレーキをかけた際に発生する熱も抑えるようにしている。都市環境を安全に走行するための冗長性と検知範囲を提供するために複数のセンサを組み合わせている。搭載されるセンサの一覧をTable 1、Bossの車体上での取付位置をFigure 2に示す。
f:id:sy4310:20180804143230p:plain

3. Motion Planning

Behavioral 層から送られた目標に到達するための行動を実行する層である。その行動は従来の交通ルールを守る上で実行される。全てのケースにおいて、Motion Plannerは目標地点に到達するための経路を生成し、その経路を追従するための様々なパターンの軌道候補を作り、どれが最適なものかを評価しながら走行する。この評価は、周囲の静的、動的な障害物、カーブかどうか、速度、経路の曲率、経路からの偏差に基づいて行われる。

3-1. Trajectory Generation

車両の初期状態と目標とする最終状態を考慮して、取るべき行動パターンを動的に決定する。一般的にこのアルゴリズムは、微分方程式の形で表現される車両のダイナミクスfが持つ状態xの制約C(x)を満足するようなパラメータ化された制御入力u(p, x)を生成する問題を解くためのアルゴリズムである。
f:id:sy4310:20180804154618p:plain
最終的な車両の状態において、走路上で車両が正しい位置と方向に置かれるための車両位置と方位角度の制約が要求される。その制約方程式xcは、車両の運動モデルの積算と目標終端状態との差分であり式(2)と(3)で表される。
f:id:sy4310:20180804160912p:plain
Bossに適用される運動モデルは、最小旋回半径、ステアリングが切られた時点での最大速度、最大加速度と減速度、制御入力を送ってからの反応遅れを考慮したものである。制御入力は、時間ベースの線形速度関数Vcmdと孤長ベースの曲率関数Kcmdの二つで構成される。
f:id:sy4310:20180804163020p:plain
Vcmdによって生成される速度プロファイルはFigure 3のパターンを持ち、Local Motion Plannerはこの中から状況に応じて適切なパターンとパラメータを決定する。
f:id:sy4310:20180804163840p:plain
車両運動モデルによる曲率指令関数によって走行する経路の形状が決まる。速度プロファイルは、三つの独立したパラメータ(K0, K1, K2)と経路の長さSfで構成される。状態の制約を満足するのに十分な4自由度を持つことから、2次のスプライン曲線プロファイルが採用される。
f:id:sy4310:20180804170950p:plain
(5)のように、システムは二つのスプライン曲線のノット点(K1, K2)と経路の長さであるSという3つのパラメータを持つ。経路の長さsと時間tの双対関係が、線形速度プロファイルによって目標点まで走行するまでの時間を推定することによって求められる。
システムにおける3自由度パラメータと3つの制約条件が与えられ、その制約方程式を最小化するパラメータを解くために様々な最適化技術を用いることができる。ルックアップテーブルにおける状態空間からパラメータ空間への適切なマッピングにより、パラメータ値の初期推定が行われる。運動の微分方程式の線形化と反転を繰り返しながらパラメータ推定が行われ、パラメータ値は修正されていく。補正率はヤコビアンの逆行列と状態制約誤差によって決まる。
f:id:sy4310:20180804174911p:plain
制御入力パラメータは、状態制約境界が許容範囲内になるまで、あるいは最適化計算が発散するまで修正され続ける。例えば、最小旋回半径よりもさらに内側、といったような実行不可能な特定のパラメータが求められた場合は、その最適化計算は発散したという事になる。最終的に決まったパラメータから生成された経路は一番ベストなものとしてMotion Plannerに渡されて評価される。

3-2. On-Road Navigation

走行している間、Behavioral systemから支持される目標地点は自分がいる車線上になる。このために、まずは目標とする車線の中心線に沿った曲線を生成する。そして、この曲線は車両のリアアクスル基準の座標系における経路に変換され、Motion Plannerはこれを追従しようとする。
目標コースにロバストに追従し、障害物を回避するために、Motion Plannerはコースの中心線から派生させた複数パターンのローカルゴールセットとそれに向けての経路セットを生成する。それらのローカルゴールは、車両のリアアクスル基準における縦方向に一定距離を保った場所に作られ、横方向に様々なオフセットを持った状態で作られる。これらの生成アルゴリズムは動的に生成され、生成されたローカル経路は実現可能と判断されたものである。また、一つのローカルゴールに対して2種類のローカル経路が生成される: 一つは滑らかな経路、もう一つは鋭利な経路である。前者はローカルゴールでの車両の予測状態の曲率に対して固定された曲率パラメータを持つ経路である。後者は逆にオフセットを乗せた曲率を持つ経路である。各ローカル経路に対して用いられる速度プロファイルは、Behavioral systemから与えられた最大速度、経路に設定された制限速度、経路中心線の曲率に基づいて実現可能と思われる最大速度、そしてローカルゴールへ向かうための目標速度などの要因を考慮して計算される。
f:id:sy4310:20180804221052p:plain
それらはコース中心からの距離、パスの滑らかさ、そして他の様々なメトリクスと同様に、障害物に近接するかどうかが評価され、一番良いパスが選ばれる。
走路の車線に沿って走行するローカルパスプランナーの例をFigure 5に示す。(a)は2車線のコースを走っている自車と対向車、(b)は赤線の目標車線から抽出された中心線、(c)は現在の状態、走路中心のパス、走路の境界線を考慮して計算されたローカルパスのセットであり、この中から1本のベストなパスが選ばれる。(d)は障害物に対する各パスの評価処理の様子であり、(e)が最終的に選ばれたパスである。
f:id:sy4310:20180806213004p:plain

3.3 Zone Navigation

Zone Navigationの間、Behaviorsからの目標動作は駐車スペースといったようなゾーンの中での姿勢である。モーションプランナーは、目標とする姿勢に向かって車両が動くようなパスを生成する。しかしながら、それは走路のような構造化された場所とは異なる場所を走行する場合である。
ゾーン内では、車線というものはなく車両の動きに対する制約はほとんどない。ゾーンにおける目標姿勢への滑らかなパスを効率よく生成するために、車両位置(x, y)、方位角度θ、速度Vを探索するLattice Plannerという技術を用いる。Lattice Plannerの探索空間における状態(x, y, θ, v)を考慮して、可能性のあるローカルパスのセットがコース生成と同じ運動モデルによって計算される。
広く、障害物が存在する環境下において効率よく複雑なパスを生成するために、Anytime D*として知られるパスの再計画アルゴリズムを利用する。このアルゴリズムは、初期とその次のパスを高速に生成することができ、処理時間が許す限りの間でパスの質を向上させ続ける。障害物が新たに観測された場合は、それを考慮して効率的にパスを修正する。
f:id:sy4310:20180818155852p:plain

4. Perception

Perceptionシステムは、BehaviralとMotion Planningのサブシステムに、周辺環境のモデルを提供する。そのモデルは、周囲の静的/動的な障害物も含んだものであり、走行するコースの形状を推定し、それに対する相対的な車両の位置を計算する。

4.1 Moving Obstacle Detection and Tracking

動的障害物の検知とトラッキングにより、各オブジェクトの仮説と特徴のリストがBehaviralとMotion planningのサブシステムに提供される。このフェーズでは、検知物体の明確な分類は実行されない。オブジェクトの存在に関する情報は、センサからの検知情報のみに基づいている。短い時間の間だけは観測なしで動きを予測することが可能である。ノイズや遮蔽、他の人工物によってオブジェクトの検知が途切れることがある。 異なるセンサからの情報を最大限に活かすために、個別のトラッキングモデルが用いられる。 f:id:sy4310:20180818163446p:plain

矩形の形状を持ったバイシクルモデルと、形状を持たない点で表現されるモデルの2種類が用いられ、状況に応じて適切な方が選択される。このモデルは、速度ベクトルの長さと方向に応じたノイズを付加した等加速度モデルである。
検知されたオブジェクトは、動いている or 動いていない、また動いていてかつ観測された or 動いているが観測はない、といった分類が成される。速度ベクトルに著しい変化があれば、それは動いているとする。また、動いていると判断された状態が0.4秒以上継続したら、それは観測ありの動的物体とする。車両が停車してから10秒間は各オブジェクトのデータはクリアさせない。

f:id:sy4310:20180818170113p:plain

路面や草木の検知によって生じる人工物は、2段階の特徴検証を通じて取り除かれる。第一にレーダモジュールの内部での速度の観測によって動いている物体と静的な地面を区別する。第2ステップでは、コース形状や3次元地図を利用して検証する。
検証されたデータは予測されたオブジェクト仮説と統合される。

4.2 Static Obstacle Detection and Mapping

スキャンレーザーからのデータを組み合わせて、静的な障害物地図を作成する。この地図は、動的な障害物のデータを抽出するために用いられる。この障害物地図は、瞬間的な障害物地図と一時的な障害物地図の2種類がある。カーブ、路肩、草木といった幾何学的特徴は、都会やオフロード環境での走路の形状を決定するための情報として用いられる。
カーブを検出するために、第1に走路の表面は比較的フラットであり、幾何学的に観測ができる程度に緩やかに変化する、エッジを持ったものであると仮定する。第2に、各LIDARのスキャンはそれぞれ独立して実行され、3次元のPoint Cloudを構築する。

4.3 Roadmap Localization

Bossは走路の幾何学的情報を推定する、あるいは走路からの相対的な位置を計測することができる。都会での走路のほとんどは形状が頻繁に変化するものではない。その中で我々がアプローチするのは、走路に対する相対的な車両位置の計算と、整備されていない走路の形状を推定である。
f:id:sy4310:20180818202214p:plain

SICKのLMSレーザが下向きに取り付けられ、走路の白線マーカを検出するために利用される。そのデータから走路の境界線の曲率、位置、方位角を推定する。この推定を行うモジュールでは、レーザとカメラからの入力データをフュージョンさせて、走路のモデルを構築する。
f:id:sy4310:20180818205046p:plain

5. Mission Planning

走行環境における繋がりを表したグラフを作成するためにRoad Network Definition File(RNDF)が用いられる。全てのポイントがグラフのノードになり、到達可能な全てのノードを結ぶ道には走路の境界を表すエッジが挿入される。エッジを横切るまでの時間、エッジの距離、対応するエリアの複雑さ等といった要因の組み合わせに基づいたコストが割り当てられる。
車両が走行する間は、新規に観測された情報に基づいてグラフは更新されていく。こういった変化に正しく反応するためには、ロボットは走路が通れない場合やゴールへの他のルートが計画されたことを検知出来なければならない。

5.1 Detecting Blockage

Bossは、走路上の妨害物を直接検知、あるいは推測することができる。静的障害物地図によって、前方にある走路を障害物が完全に塞いでいるかどうかを判定する。その障害物は5秒以上継続して検知されなければ、それはノイズとして地図上では無視される。走路誘導アルゴリズムは、走路が妨害されていることをバーチャル妨害物を置くことによってレポートすることができる。これを踏まえて、行動生成モジュールはもっともコストが小さいパスを選び出す。

5.2 Blockages

一度妨害物が検知されると、それが走路を占有することによって影響を受けるパスが決定される。妨害物の前後にある場所は、Uターンする場所として認識される。合法的にUターンが可能な場所で実行する。
以前に検知された妨害箇所に再び来てしまうことは、妨害物を横切る走路要素に適用される走行コストを徐々に減らしていくことで改善していく。妨害物を横切る走行コストを下げることにより、ロボットは妨害物が除去されたかどうかを確認しに戻ることができる。逆に下げなければ、ロボットはUターン走行を計画し続けることになる。
コストは以下の式で計算される。
f:id:sy4310:20180903231905p:plain
aは妨害物が最後に観測されてからの時間であり、hはhalf-lifeパラメータ、そしてpはコストペナルティである。この妨害物のハンドリングアプローチの弱点は、取り除かれることがない妨害物に向かって何度もアプローチしようとすることで、時間を浪費する可能性があることである。一方通行の走路においては、走路の妨害物に対するUターン経路は生成されない。しかしながら、妨害物を横切る走路のコストが上がることによって、走路を再度通ることの尤度が下がる。一方通行の走路における妨害物に対応するために、ゾーンナビゲーションプランナは、6.3節にて述べるエラーリカバリーモードを呼び出す。

6. Behavioral Reasoning<=今ここ

勉強すべき技術

最適化問題
Lattice Planner
Anytime D*

分からなかった英単語メモ

orient: 適応させる、正しい位置、方向に置く
fidelity: 忠実、忠誠、真に迫っていること
arc length: 孤長
duality: 双対性
correction factor: 補正率
invariant: 不変
residual: 残り
diverge: 発散する
infeasible: 実行不可能な
derive: 派生する
proximity: 近接
expedite: 促進する
vicinity: 近傍
explicit: 明白な、はっきりした heterogeneous: 異なる distinct: 個別の instantaneous: 瞬間的な
paved: 舗装された