狠狠撸

論文読んだよ
“State Lattice-based Motion Planning
for Autonomous On-Road Driving”
summarized by oei
Thesis author : Wang, Shuiying
url : https://d-nb.info/1069105651/34

コンテンツ 1,2
1. イントロ
1. 動機
1. 自律車両の社会的影響
2. オンロードモーションプランナの評価基
準
3. 自律車両開発におけるシミュレーショ
ンの応用
2. この論文の貢献
3. 論文構成
2. 関連研究
1. 用語
2. オンロード運動計画
1. DUCでのオンロード運動計画
2. DUC後のオンロードモーション計画のさ
らなる改善
3. ラティスベースモーション計画のサブ問
題へのアプローチ
1. 時空間サンプリング
2. 軌道表現
3. 軌道評価
4. グラフ探索
3. スキャンセンサシミュレーション
1. 空中スキャンセンサシミュレーション
2. ロボット分野におけるスキャンセンサシ
ミュレーション

コンテンツ 3,4
3. オンロードモーション計画アルゴリズム
1. 地平計画と計画周期の長さ
2. 空間的な地平線の指定
1. 前提
2. 定義と構築の原則
3. 空間的地平構築のためのデータ構造とアルゴリ
ズム
3. 空間サンプリング
1. 車線対応座標系
2. 空間ノード
3. 経路モデル
4. 接続パターン
4. 時間サンプリング
5. グラフ探索
6. 軌道評価
1. コストマップ
2. 障害物の拡張
7. まとめ
4. 滑らかな軌道のための加速度プロファイ
ル
1. 滑らかな軌道
2. プランナに適用される一般的な加速度プロ
ファイルのタイプ
1. 加速度遷移のプロファイル
2. 加速を一定に保つためのプロファイル
3. 目標速度を達成するためのプロファイル
3. 加速度プロファイルの適用
4. 評価
1. プランナに適用された具体的な加速プロファイ
ル
2. パフォーマンス評価
5. まとめ

コンテンツ 5,6
5. モーションプランナの実装とシステムインテグ
レーション
1. モーションプランナの実装
1. CPU上でのプランナの実装
1. プランナの初期化
2. 空間的地平線の指定とサンプリング
3. XYSLマップの構築
4. レーンセンタリングコストマップの更新
5. 障害物コストマップの作成
6. パスエッジの保存
2. GPUでのプランナの実装
1. GPUの並列計算アーキテクチャ
2. 経路サンプリング
3. State Lattice 構造
3. ベストターゲット選択と軌道再構成
4. コスト関数
2. システムインテグレーション
1. 計画立案者に基づく計画アーキテクチャ
2. レイテンシ補正
3. Spatial Latticeの整合性
3. まとめ
6. スキャンセンサシミュレーション
1. スキャンセンサモデリング
1. 実際のRadarとLiDAR Radarについて
2. Radar モデリング
3. LiDAR モデリング
2. GPU上でのスキャンセンサシミュレーションの実装
1. OpenGL と OpenSceneGraph
2. シェーダベースのスキャンセンサシミュレーション
3. レーザーと仮想光線の不一致によるエラーの軽減
3. パフォーマンス評価
4. まとめ

コンテンツ 7,8
7. モーションプランナ評価
1. 基準に基づく評価
1. 最適性
1. 地平線の最適性
2. シナリオに依存した最適性
3. 解像度の最適性
2. 完全性
3. 実現可能性
4. ランタイム
2. タイムクリティカルなシナリオでの
プランナのパフォーマンス
3. 道路網実験におけるプランナのパ
フォーマンス
4. 現状との比較
5. まとめ
8. 結論
1. 結論
2. 未来の展望
1. State Latticeの適応
2. 効率的で効果的で一貫したコスト
マップ
3. 軌道の実現可能性
4. 計算効率
5. 現実的なシミュレーション
6. 現実的で複雑な実験

主題になっているのはどんなもの？
? State latticeとその周辺
? 実装とか
? センサシミュレーションとか
? 加速度プロファイルとか

どんなペーパー？
? これ一枚でstate lattice完全に理解できそうな深さと広さ
? 顽张ってちゃんと読みます

このスライドはどこらへんがまとまってる？
? 全部読むのつらいので、コンテンツで赤字になってるとこまとめる
? センサシミュレーションとかの関連技術はほとんどすっ飛ばすので、
興味ある人は元論文読んでください

オンロードモーションプランナの評価基準
? 完全性(離散化の隙間に解があるのは許せねぇ)
? より高密度なサンプリング
? より多様な軌道
? 実現可能性(車両の制約を満たさない軌道は追従できねぇ)
? より連続的な軌道
? 車両の制約を考慮した軌道
? 最適性
? ばらまくstate latticeの最適性？選択する道の最適性？
? 計算複雑性(無視すれば連続性が失われる、衝突回避も遅れる)
? 複数の車両状態を考慮し自車から各目標状態への軌道を構築するものとState latticeをグラフ探
索するものを比較
? 前者より後者が最適性は優れるも後者は計算が複雑であり連続性を欠く
? 後者は一般的にGPUで加速される

自律車両開発におけるシミュレータの
基本的なコンポーネント
? 自動車物理シミュレーション
? センサーシミュレーション
? 交通シナリオモデリング（静的および動的オブジェクト、交通関連イ
ンフラストラクチャなど）

さえない自動運転シミュレータの育て方
1. 空の道路を持つ物理シミュレーション環境
↓
2. 静的及び動的トラフィック参加者追加
↓
3. 情報のセンサデータへの置き換え
↓
4. 車を実際の車に置き換え(ハードウェアインループテスト)
時間と労力
節約できるよ！！
by Wang, Shuiying
ベンチマーク、デモは教育や広告にも使えるよ！！

この論文の貢献
道路適合state latticeにより、運動計画問題をグラフ探索問題に定式化
貢献1. 軌道の多様性を高めながら軌道の滑らかさを改善
Vs.[22],[24],[25],[26]
貢献2. センサシミュレータの开発

貢献1. 軌道平滑化について
? 軌道の非平滑性はロボットが扱うオブジェクトの破壊や機械の共振
振動や早期消耗につながる
? そのため躍度は最小化する必要がある
([27]で動きの滑らかさがジャークの関数として定量化できることが提案されている)

素晴らしき躍度最小化
? それは乗客のための快適な移動を提供するのに役立つ
? それはエネルギー効率と環境保全に貢献することができる
[30]でスムーズな運転戦略に従う軌道が燃料消費量とCO2排出量を平均約
12％削減するのに役立つことを示している
? 軌道追跡を容易にし、制御を容易にすることができる
モデル化されてないアクチュエータ挙動などの暗黙的に非調和のシステム動
力学を考慮に入れているため生じる

貢献2. センサシミュレータの开発
? 興味はあるが今回はスルーする

オンロードモーションプランニング
? 祖となるのはロボットのモーションプランニング
? 違いは交通ルールの有無、環境変化の速さ(道路上は極めて動的)
? 以降のページで顿鲍颁から最近までの开発状况报告

DUCでのオンロードモーション計画
? 完走6車
? 主にサンプリングベース
? 低密度、低速(30mph以下)な競技シナリオ内では問題なく動いた
? これ以降CMUで開発された自律車両Bossのフレームワークについて

自律車両Bossのフレームワーク
? Mission module
? グローバルルートとブロックの検出を担当
? 効率的なレーン選定
? Behaviour module
? ルールベースによる行動決定(交差点、車線変更等…)
? 必要に応じてエラーのリカバリ戦略も実行
? 先取り距離(計画地平)や最高速度の決定
? Motion planning module
? モーションコマンドの生成
? サンプル姿勢を定義後、曲率指定スプラインで軌道計画
? 車両モデルで実行可能性チェック
? いくつかの速度プロファイルを定義(一定、リニア、ランプリニア、台形)

DUC後のオンロードモーション計画の進化1
? Bossに基づき時空間 state lattice
? stateに曲率も姿勢の要素として追加
? 曲率多項式(二次→三次)で経路エッジを定式化
? →WP上での曲率連続性を保証
? 一定数の速度プロファイルが螺旋状の経路エッジに適用されて、軌
道端部をレンダリング
? PD制御でのパスフォローイング加速度プロファイルも考慮
? 同じ姿勢で終了するものをプルーニング

DUC後のオンロードモーション計画の進化2
? [22]で自車からstate latticeへの軌道セグメントに使用された曲率立方螺旋は
曲率四次螺旋に置き換えられる
→2つの連続する計画の接合部における曲率の変化率に関して突発的なジャンプを緩
和
? 速度多項式の係数は、固定速度と、エッジの2つの端点におけるゼロ加速度
の仮定とを考慮して決定→WP上での加速度連続性
? グラフの頂点の固定によって課せられる横方向のオフセット、曲率、進行方
向、速度および加速度に関して制約を緩和することによってさらに最適化
? 車線変更、静的障害、動的障害に関する3つの実験シナリオでは、得られた
軌道の性能が10％向上し、計算時間が50％以上短縮されたと言われている

曲率三次?四次螺旋って何？
? 曲率三次螺旋:三次多項式で表現された曲率入力に起因する曲線
? 曲率四次螺旋:同様に、四次多項式で表現された曲率入力に起因

時空間サンプリングの問題点
? 多次元のため最終的に破棄される軌道を多く計算してしまう
→要するに重い
? 時空間において最適な領域で集中的にサンプリングする必要がある
→2段階計画アプローチ

2段階計画アプローチ
? 第一ステップ(基準軌道の取得)
? ノンパラメトリックシーディングパスの取得
? パスに適用可能な速度プロファイルの取得
? 時間無視で注目空間内のみでパスを探索(静的コストのみ考慮)
? 第二ステップ
? 速度制約による時間領域内で集中サンプリング
? シーディングパスを生成
この方法で生成されたパスも時空間サンプリングで得られたものと等価

車両の状態
? 道路の中心線に対する位置、速度、加速度
? 位置五次多項式はWP上での位置、速度、加速度に関する軌道の滑
らかさや連続性を確保する(横と縦バラバラに式表現するぽい)

位置五次多項式って何？
? 後日補間予定

ターミナルマニフォルド([23]よめ)
? 終点多様体に基づくモーションプランナ
? 全ての軌跡は自車から始まりサンプリングされた頂点で終わる
? →ターミナルマニフォルド
? グラフベースじゃないので軽い
? 車両速度によって車線縦方向、横方向では非ホロノミック制約によっ
て差が出るためバラバラに設計するのが吉

latticeモーション計画のサブ問題へのアプローチ
これ以降、以下の4つのサブ問題に焦点を当てていく
? 時空間サンプリング
? 軌道表現
? 軌道評価
? グラフ探索の

時空間サンプリング
? サンプリング多様化の手段として中間ターゲットを与えるものがある
? 確定的サンプリングとランダムサンプリングが存在する(これまで
扱ったのは確定的サンプリング)
? オンロードではサンプリングを道路形状に适合させる必要がある

道路形状に対するサンプリングの適合
? 通常、道路の中心線がサンプリングの基礎として設定
? 目標姿勢は中心線に沿ってサンプリングを横方向にオフセットするこ
とによって生成
? 得られた空間目標姿勢は時間、速度、加速度などの時間要素を追
加することで強化できる
? 目標姿勢の代表値はあらかじめ決定されていてもよく、その場で計
算されてもよい
時間 : [23],[22] 速度 : [24],[25],[26] 加速 : [22],[23]
事前計算 : [23],[24],[25],[26] その場計算 : [22]

RRT
? ランダムサンプリングアルゴリズムの一つとしてRRTが
あげられる
? 図はオンロードでのRRT
? 最近接ネイバー(NN)メトリックのヒューリスティック使用
? サンプリング枝伸ばして最終的に終了状態と軌道が衝
突チェックをパスすると新しいエッジとして追加される
? これを特定のサンプリングメリットを満たすか時間制限
まで繰り返す

最近接ネイバー(NN)メトリックって何？
Nearest Neighbour (NN) metric tte nannzo?

軌道プリミティブ(path primitives)って何？
? 一般に直線、円弧、クロソイド、ベジェ、三次螺旋、Akimaスプライン、
曲率三次多項式、曲率四次多項式等のことを言うらしい…
? つまり経路を表现する几何的な式のこと？

RRT2
? 決定論的サンプリンングに対するRRTの利点
? 次元に対してノード数が指数関数的に増大しない事
? 様々な探索空間に容易に適用できること
? 確率的完全性を有すること(時間があれば必ず解にたどり着ける)
? しかしタイムクリティカルなシナリオではランタイムの制約によってそれは阻
まれる
? RRTの欠点
? 効率,生成軌道の最適性がNNメトリックの選択に依存
? NNメトリックの種類
? ユークリッドメトリック(一般的)
? Dubinsパス長(採用したものもある)

軌道表現(補間って呼んでいいのか？)
? 開始状態と終了状態が境界条件で与えられている最適制御問題と
して定式化できる
? ただし制約が変動するため制御問題としての一般解は得られない
? 複数の候補がある場合、最適制御問題をパラメータ探索、制約付き
最適化問題に変換するいくつかのパラメトリック関数が推定される

パラメトリックって何？
? パラメトリック
? 母集団の分布が何分布かわかっている
? パラメータによって母集団の分布が把握できる
? 解析対象のデータが何かの分布に由来していると仮定する
? ノンパラメトリック
? 母集団の分布が何分布かわからない
? パラメータによって母集団の分布が把握できない
? 解析対象のデータにどの分布もあてはめずに考える

車両のパラメトリック軌道表現
1. 軌道の幾何的形状を特定のパラメトリックな関数に限定し、そのパ
スにいくつかの速度プロファイルを適用するもの
2. 軌道の経路タイプを仮定せず、車両の縦方向軌道、横方向軌道を
別々に計算し組み合わせるもの

経路プリミティブ(軌道表現1.)
? 一般に、直線[48]、円弧[49]、クロソ
イド[47]、ベジエ曲線[46]、立方体ら
せん[47]、明石スプライン[50]、曲率
立方体多項式[22]、曲率四次多項
式[24]など
? 経路プリミティブによってWP上での
曲率連続性に変化が出る
? 図は三次多項式で表現された曲率
入力に起因する曲線である三次螺旋

縦横アプローチ
? 軌道表現問題を縦横二つの独立した最適制御問題として定式化する
? 最適制御問題の性能指数は滑らかさであり、最小躍度によって実装
される
? 道路の中心線に対して縦横で分けられ、最適制御問題として解かれ
た後、曲率や加速度等の車両運動を検証するため組みあわせて用い
られる
? この情報は物理的制約の検証、トラッキングに利用される

軌道評価
? 評価する軌道が多数ある場合は効率的なコスト値算出のためルック
アップテーブル使用
? コストマップ構築
? スワスの占有セルの合计演算问题に还元

コストマップ
? 最初のコストマップは静的障害のみを考慮して作成
? 軌道は車両の代表点の動作軌跡を記述
? 形状と代表点との差は衝突チェックで考慮
? 評価は軌道に沿ってコストマップと車両フレームを畳み込むことに
よって実行される
? 畳み込みは複雑であるためコストマップを荒くして車両フレームの補
償が結果的に得られる軌道を許容する事で軽量化する

コストマップを用いた車両フレームの畳み込み
緑の枠 :
車両のフレーム
青い点 :
車のフレーム上の代表点
黒い曲線 :
代表点の軌跡
赤いグリッド :
コストマップのグリッド上
円に近い形状なら占有セルを円で近似できるが、
車レベルのアスペクト比でそれはできない

ここでいう畳み込みとは
? 後日補足

コストマップの効率化
? 車両フレーム内の刻印円(？)と車両境界の最小円の半径でコスト計
算し、楽観的コストマップと悲観的コストマップを得る方法
? いくつかのディスク形状を重ねて近似的な矩形を表現する方法
? オンロードにおける進行方向を道路の中央線に対して±6度以内と
仮定する方法

グラフ探索
? グラフ探索はより最適な経路を探索するために有効
? 固定ターゲットのグラフ探索は潜在的な目標点すべてに適用する必
要があるため非効率
? 包括的なアルゴリズム、動的探索アルゴリズムが選択肢として挙げ
られる
包括的なアルゴリズム : [23]
動的探索アルゴリズム : [22],[24],[25]

オンロードモーション計画アルゴリズム
? 提案されたプランナのコアアイデアは計画周期内で多様な軌道を生
成し最良かつ制約に準拠した軌道を選択すること
? それは車線に適合する state lattice を探索することで実現される
? State lattice は時空間における決定論的サンプリングによって構築さ
れる
? 複雑なグラフ構築と探索を行うための並列アルゴリズムが考案され
ている
? これ以降はこの計画戦略にかかわる主なアルゴリズムについて説
明される

地平の計画と計画周期
? 各周期の初めにサンプリングが実行できる場所で計画周期を決定
する必要がある
? 時空間運動計画において計画の地平は
? 時間的地平HT (サンプリングの時間的周期)
? 空間的地平HS (走行距離内の道路セグメントからなる) の2つ
? 計画周期をCTとする
? 空間的地平Hs周辺
? 延長距離 : dH
? そのドメイン内の道路セグメントの数 : nseg
? 各道路セグメントの幅 : wseg

今更だけど地平(Horizons)ってなんやねん
? 多分経路計画の対象となる車の前方方向の道路のことだと思うここ
まで読んできたニュアンス的に
? そこにlatticeがばらまかれる的な

HT,dH,CTの設定指標
? モーションプランナの指標(6)
? 完全性(1)
? 実行可能性(1)
? 最適性(3)
? 地平最適性
? シナリオ最適性
? 解像度最適性
? 計算複雑性(1)
赤で示した部分が
HT,dH,CTの選択に直接関係
? 周辺車両の認識が十分に機能
すると仮定すれば広い範囲の
地平が確保されるため地平最
適性は確保できる
? しかし計算資源の制約によって
必然的にCTも大きくなる
? それは安全的にNG
つまり
dHはデカく?HT,CTは小さくしたい

HT,dH,CTの設定
? CT
? 地平最適性の観点からは大きくしたい
? 安全性の観点から上限が決まる
? よって安全要件によって決定される
? HT
? 最後のサイクルで計算された軌道が次のサイクルまで持続する必要がある
? 下限はCT以上である必要がある
? 上限をdHの上限から設定できる
? dH
? 計画期間内の平均速度から時間地平の制約を空間地平の制約に変換
? 下限はHTの下限に沿って決定される
? HS
? CTの制約で決まるHTに沿って設定する

これ以降
? これまでHorizonのこと地平って言ってきたけど適切じゃなさそうなの
でこれ以降Horizonって表記します

空間的Horizonの設定
? 【衝撃の真実】このセクションでHorizonは走行距離dH内の関心の
ある道路セグメントを指す
? 多くのモーションプランニングの文献でこの領域はミッション(行動決
定層)の役割とされ省略される

空間的Horizon設定の前提条件
? RNDFグラフ(道路ネットワークモデル)が与えられること
? RNDFグラフにおいて各車線は一様な幅を持つこと
? RNDFグラフにおいて車線の中央から等距離の左右の車線境界が平
行であること

道路網定義ファイル(RNDF)
? RNDFはDUCのために開発された
? 運転環境を道路セグメントとゾーン(駐車場など)の2タイプに分類
? 道路セグメントはいくつかの隣接する車線を含むことができる
? 車線は交渉レーン幅とその中心線に沿ったWPのセットで表現
? WPはその場所の情報含む(車線,交通標識,停車標識)
? 車両が到達する必要があるWPはチェックポイントと呼ばれる

RNDFグラフ
RNDFからRNDFグラフが以下のように生成される
? 実際の車線
? 車線変更行動を促進するために追加される仮想車線
? 対向車線を横断しての追い越しを用意にする実際の車線をミラーし
た仮想車線
RNDFグラフのノードは隣接する実際の車線セグメントのWPか仮想車
線を定義するための仮想WPになる
車線セグメントの中心線はWPのスプライン補間
車線は隣接車線の情報を含む複数のエッジを含むことができる
2つの車線が隣接しているかどうかは統計的推定で決定できる

RNDFグラフの例
黄色い曲線 :
スプラインのエッジ
赤い点 :
ノード
白い帯 :
実際の道路セグメント

定義とアルゴリズム構築の原則
? 図3.2（a）の道路網において与えられる空間的Horizonが図3.2（b）
? 図3.2（b）の領域広すぎる→計算重い
? そのため原則3.1が適用される
色が違う部分は、
違うスプラインで表現

原則3.1
? 多くの自律車両のモーションプランナはミッションまたは行動モジュールの
決めた車線に従う
? 具体的には次のミッション目標が短くなる道路セグメントを通過
? たとえそのセグメントのコストが高くても閉鎖されて無限になっていない限
りそのセグメントを優先
? モーションプランナは次WPのみを考えればよい→グローバルを引き直さ
なくてよいので軽くなる
? 図3.2(c)は原則3.1によって修正されたHorizon
長期計画は、短期目標のコストが無限にならない限り、
短期目標のコストによって影響を受けるべきではない

原則3.1によるHorizonの軽量化
? 青、水色は次のWPを持たないためカットされたと考えられる

原則3.2
? 全てのセグメントは均一な幅を持つことを前提とする
? これで横のセグメントと統合したセグメント内で探索できる
? 図3.2（d）は、原則3.2が適用された後の更新された空間的Horizonを
示している
空間的Horizonの2つの別々のセグメントは、横方向基準（該当セグメ
ントを含む道路の中心線のいずれか）に投影されるとき、重なり合って
はならない

定義3.1
時間的整合性：
? 1つの計画サイクルから生成された最良の軌道の残りのセグメント
は、計算および追跡の誤差がないという仮定の下で、引き続く計画
サイクルにおいて少なくとも1つの候補軌道に依然として含まれ得る
? しかし、一貫性を担う軌道が制約のチェックを生き延び、次の計画サ
イクルで最良のものとして選択されるかどうかは、依然として世界モ
デルに導入された新しい情報次第である
? これに対応して、空間的なHorizonを定義する観点からTCにストレス
を与える別の原則が提案される

原則3.3
? TCの性質を持つモーションプランナは必ずしも原則3.3に従わない
? 原則3.3は、TCの要件を備えたモーションプランナにとって十分な空
間的Horizonを保証する
点（x、y）が一度でも空間的Horizonに含まれた場合、
車両の前方に位置しなくなるまで、引き続き空間的Horizonに含まれる

原则3.4
? セグメントが必要かどうかは、原則3.1に基づいて決定
所与の走行距離内で車両の前にある
すべての道路セグメントを最初に集め、不要なセグメントのみ削除

原則3.5
? セグメントが必要かどうかは、原則3.1に基づいて決定
? 例えば、実際には、車両が図3.2（c）に示す短い隣接道路セグメント
を使用する可能性はかなり低い
? 望ましくない程度に短くなったときにその隣接するセグメントを削除
するなどの追加の処理が依然として必要
セグメント内の幅が均一でない場合、このセグメントは、
原則3.2を保証するために、より小さなセグメントにさらに分割される

空間的Horizon構築のためのデータ構造1
? LATTICE-SEC :
? 原則3.5にしたがって構成された1つのセグメントの情報をエンコード
? 要素には、セグメントの幅、縦方向の距離、横方向の参照表現、空間ノードのレ
イアウト、およびその隣の水平線分との関係が含まれる
? LATTICE-SECがいくつかの隣接するレーンからなる場合、車両に最も近いものが
セグメント全体の横方向基準を提供するように選択される
? LATTICE-SEC-ARRAY :
? LATTICE-SECの配列であり、原则3.4を満たす
? サンプリングされた空間的地平線の完全な情報を有し、グラフ構築のために直
接適用することができる
? 空間的Horizonの開始までの縦方向の距離に基づいて、昇順に編成されている

空間的Horizon構築のためのデータ構造2
? LATTICE-SEC-TREE :
? LATTICE-SEC-TREEとLATTICE-SEC-ARRAYは、前者が配列ではなくツリー構造の
形式である点で異なる
? LATTICE-SEC-RAW :
? LATTICE-SEC-RAWは、1つまたは複数のLATTICE-SECの前触れ
? その幅は均一ではない可能性もある
? LATTICE-SEC-RAW-TREE :
? 複数のLATTICE-SEC-RAWをノードとするツリー構造

空間的Horizonのアルゴリズム構築1
? ROUGH-CONSTRUCTION :
? プルーニング手順なしでも原则3.4に従い、原則3.5の最初も考慮される
? 具体的には、現在の車線の隣接車線（現在の車線自体を含む）を特定する
ために、最初に幅優先探索がRNDFグラフ上で実行される
? 次に、幅優先探索で発見された各レーンを、所与の移動距離に達するまで
追跡する深さ優先探索が実行される
? 探索中、LATTICE-SEC-RAWは、同じレーンに沿ってその優先順位を表すもの
とは異なるスプラインによって表される
? さらに、既存のLATTICE-SEC-RAWは、新たに位置する近隣または後続のレー
ンセグメントの情報を組み込むように更新される
? 全体的なプロセスにより、LATTICE-SEC-RAW-TREEが最終結果として得られる

空間的Horizonのアルゴリズム構築2
? FOCUSED-CONSTRUCTION-AND-SAMPLING :
? 最後の手順から生成されたLATTICE-SEC-RAW-TREEの各LATTICE-SEC-RAWに、
原則3.5の第2部分を適用
? この手順では、空間ノードのレイアウトも定義するが、具体的な代表値は計
算しない
? 結果としてLATTICE-SEC-TREEを得る
? PRUNING :
? 原则3.4に従い、LATTICE-SEC-TREEの望ましくない部分を除去し、LATTICE-
SEC-ARRAYを出力する

空間的Horizonの構築プロセスの例1
a. 現在の車線に沿ったエッジが見つかる
b. 配置されたエッジを記録するための
LATTICE-SEC-RAW（青色）が構成される
c. 隣接車線にもう1つのエッジがある
d. 隣接するレーンを組み合わせることを
推奨するので、新たに配置されたエッ
ジの情報は、再びLATTICE-SEC-RAW
（青色）に記録され、LATTICE-SEC-RAW
（青色）はそれに応じて更新される

e. もう一つのエッジが見つかる
f. 新たに発見されたエッジがその親エッ
ジと比較して異なるスプラインで表現さ
れると、新しいLATTICE-SEC-RAW（緑
色）が作成されてログに記録される
g. 別のエッジが発見される
h. 新しく配置されたエッジは、親エッジと
同じスプラインにあるので、親エッジと
同じLATTICE-SEC-RAWに記録され、
LATTICE-SEC-RAW（青色）が更新される

i. 別のエッジが出現
j. 新たに発見されたエッジとその親
エッジが異なるスプラインで表現さ
れると、新しいLATTICE-SEC-RAW（シ
アン）が作成されて前者を記録
k. 別のエッジが発見される
l. 新しく発見されたエッジとその親エッ
ジが同じスプラインで表現されると、
LATTICE-SEC-RAW（シアン）が更新さ
れて前者が記録される

m. 隣の車線に別のエッジが発見され
る
n. 新しく検出されたエッジとその親
エッジが同じスプラインで表現され
ると、LATTICE-SEC-RAW（青）が更
新されて前者が記録される
o. LATTICE-SEC-TREEは、集中的な構
築とサンプリングの手順から生じる
p. プルーニングの動作後、
LatticeSecVecが得られる

空間サンプリング
? 空間サンプリングの結果は、空間グラフ{ ?、 ?}（ ?と ?はそれぞれ空間
ノードとパスエッジを表す）
? 完全なサンプリングの最終出力である時空間グラフ（state latticeとも
呼ばれ、{n、e}と表される）から空間グラフを区別するために採用さ
れる

車線対応座標系
? 空間をサンプリングする簡単なアプローチは、X-Y空間に均一なグ
リッドを構築すること(直線レーンをサンプリングするの等価)
? しかし、他の道路形状（例えばカーブ）に対応できない
? 不必要な領域での努力を無駄にすることなく、路面全体をカバーす
る単一の均一なグリッドを実装することは困難(図3.4参照)
? より効率的なサンプリングのために、車線適合座標系（SL座標系と
呼ぶ）

SL座標系
? 軸線Sは車線の中心と一致し、L
は計画期間内にSに垂直な任意
の線であり得る
? SLフレーム内の点（s、l）のs座標
は、水平線の開始点からS上の
（s、l）の投影点までの中心線に
沿った円弧長を参照する
? sはstationとも呼ばれる
? （s、l）のl成分は、中心線からの
点の横方向オフセットを示す

空間ノード1
? 空間ノードは、パスプリミティブの終点として機能する
? SL空間を領域と右手座標系とすると、空間ノードは次のように表せる
（s、0）は、レーンの中央の点の座標
中心の表現が（x、y、θ、κ）に関して
与えられると、空間ノードの4つの要
素は、式に従って容易に計算するこ
とができる

空間ノード2
? 空間ノードの表示は、サンプリングされた位置での車両の方位θが
中心線に対して平行であるように制約されていることを示す
? この仮定は、高速道路運転シナリオにおける人間の運転者の共通
の挙動を模倣するという観点から有効であり、それは小さいサイズ
の格子をもたらし、したがって計画をより計算的に扱いやすくする
? 計算上の複雑さをさらに減少させるために、サンプリングされた位置
での経路の曲率kも一意であると仮定され、中心線に基づいて決定
される

空間ノード3
? 曲率は、経路の弧長の変化に対する方位θの変化率であり、車両の
旋回半径の逆数に等しい
? 規則的なグリッドを使用してSL空間をサンプリングすると、 ?isjlと表さ
れる空間ノードの集合が得られ、各 ?isjlはSLフレーム内の点（si , lj）を
表す

空間ノード4
? 長手方向および横方向の間隔、すなわちasおよびaLが与えられると、
図3.5、si と lj は、アファイン関数を使って定義される
? 図3.5のワープグリッドは、このようなマッピングのインスタンスを示し
ている
? 車両の現在の姿勢（x、y、θ、κの集合）は、 ?egoと呼ばれる空間ノード
として定義する必要がある

車両の動的モデル
? 経路モデル設計の基礎として、車両の動的モデルは次のように与えら
れる
? 車両状態は、位置（x、y）、方位θ、曲率κ、速度Vおよび加速度αを含む
? 所望の加速度耻2および曲率耻1は、车両システムへの制御入力である

経路と曲率
? 経路モデルと速度軌道が別々に生成されるので、車両モデルの速
度状態を一時的に無視し、時刻tから距離sまでの変数の変化を適
用する必要がある
? 最初の距離をゼロに設定
? 再パラメータ化された方程式を統合する
この式から分かるように、x、y、θはκに、
直接的または間接的に依存する
その結果、経路モデル設計の問題は
曲率選択の問題と同等

多項式螺旋
? この論文では、曲率立方多項式と弧長を採用して操舵の連続性を
確保している
? 曲率の高次導関数における連続性を達成するための高次多項式の
適用は、課題として残っている
? 曲率がその弧長の多項式である曲線は多項式螺旋と呼ばれる
? 曲率立方体多項式によってトレースされる経路は、3次多項式螺旋

曲率多項式による経路表現
? 曲率多項式の係数ベクトルを ?とする
? 多項式螺旋経路は以下のように表される
? ?を別の未知のsTで補うと隣接するパラメータベクトルをもたらす

境界状態
? 終点が空間ノードの対（ ?0、 ?1）であるパスプリミティブが与えられる
と、その境界状態はベクトル値関数にまとめられる
? 境界制約は以下のように与えられる

問題の定式化
? したがって、経路表現の問題は、ベクトル値 ?を見つけることとして解
釈することができ、それは ?である
? 境界条件式の量は未知数のものと同等であるため、問題は解決可
能であり、その解は固有である
? 問題の非線形性のため、数値的にしか解けない
? よって、近似解曲線を見つけるために、この研究では勾配降下検索
が適用される

近似解曲線の探索
? ?の初期推測、すなわち ?????が与えられると、勾配降下探索の主な
手順は次のようになる
?G（ ?init）は ?initの点での ?のヤコビ行列を参照
→反復更新
? ?が経路構築目的のために十分に小さくなるまで
Or反復回数が最大に達するまで繰り返し

初期推定テーブル
? 勾配降下探索の高速収束には正確な解に近い初期推測が不可欠
? そのため最初の推測テーブルが予め計算される
? 各エントリは特定の境界条件に対する曲線解を記憶
? 初期推測は、緩和法を用いて生成
? 次に、勾配降下アルゴリズムを適用
? 実行時に、任意の境界制約を持つパススパイラルの初期推測は、
推測テーブルへの単純な最近傍探索を使用することによって得るこ
とができる

緩和法(relaxation method)is何？？？
? 参考文献[45]参照
? 后日补完予定

フレネル積分と数値的な近似
? 位置座標の表現、すなわちx（s）およびy（s）は、閉形式表現がない一
般化フレネル積分の形をとる
? それらを評価し、パラメータベクトルに対するそれらの勾配を計算す
ることは困難
? その結果、Simpsonの公式と台形公式が元の超越積分の数値近似
を生成するために採用される

フレネル積分ってなんぞ？
? フレネル積分とは、オーギュスタン?ジャン?フレネルの名を冠した2つの
超越関数 S(x) と C(x) であり、光学で使われている。近接場のフレネル
回折現象を説明する際に現れ、以下のような積分で定義される。
? 定義
フレネル積分は、全ての x について収束する次の冪級数展開式で表せる
By wikipedia

光学で使われるフレネル積分がなぜ位置座標に？？
? 後日補完

このあと
? この後は積分をシンプソンで近似するか台形で近似するか議論する
? 結論としてパスプラには台形で良いって言ってる
? ぶっちゃけ見なくてもいい
? 95まで飛ばしてよい

シンプソンの公式
合成して
ここで、h =（b-a）/ nで、j = 0,1、...、n-1、nに対してxj = a + jh
合成シンプソンの法則は、各サブインターバルに適用
この式は、勾配降下探索の経路のおおよその目標位置を提供するた
めに使用され、そのシンボリックな微分はヤコビ行列を計算するため
に採用される

台形公式
? 台形公式は2種類の複合式で表されている
? 1つはドメイン[a、b]内の均一なサンプリングの結果得られた格子点
に積分し、他方は不均一である
? 区間[a、b]における等間隔h =（b - a）/ nのn + 1個の点が与えられる
と、前者は次のように表される
? ここで、j = 0,1、...、n-1、nに対してxj = a + jhである事を考慮し、

台形公式2
? ここで、a = x0 <x1 ... <xn-1 <xn = bである
? 連続する点については、サンプリング式を有することに留意
? これは、台形則とシンプソン則に基づくすべてに適用される
? 本研究では軌道サンプリングに以下の式を適用する

シンプソンの公式と台形公式
? シンプソンの法則は二次補間に基づいているが、台形法は線形補
間に従う
? 経路最適化は区間狭いからどっちでも十分精度出る
? 台形なら一つのサブインターバルで2つのポイントの计算で済む

曲率三次多項式の改変
? 曲率多項式の定式化は、特にp1とp3の場合に、係数間の潜在的に
大きな差異に起因する丸め誤差を導入するときがある
? この問題は、勾配降下探索中にヤコビ行列の逆数を計算する場合
に問題となる
? そのために、曲率多项式の再定式化は以下のように与えられる

今日はここまで
? 今日はここまで

どうやって有効だと検証した？

次に読むべき論文は？
? [16]躍度最小化オンロード自律走行
? [21]行動決定層の早期危険対処関係っぽい
? [23]より速い時空間 state lattice

狠狠撸

論文読んだよ “State Lattice-based Motion Planning for Autonomous On-Road Driving”

Recommended

More Related Content

What's hot (20)

More from Adachi (OEI) (12)

論文読んだよ “State Lattice-based Motion Planning for Autonomous On-Road Driving”