[後編]こんにちは、ティアフォーエンジニアの村上です。Matchingを読み解いてみようと思います。方は、前編もあわせてぜひご覧ください。tech.tier4.jpなお、ティアフォーでは、「自動運転の民主化」をともに実現していく様々なエンジニア・リサーチャーを募集しています。ご興味があればカジュアル面談も可能ですので以下のページからコンタクトいただければと思います。Target点数]の計算量が必要となります。ここで、Target点群をいくつかの格子に分割後、"格子中の点群の正規分布"、つまり雰囲気のようなものへ変換してしまい、Sourceの各点がその分布上その位置に存在する確率を「スコア値」として考えてしまう発想に至ります。分布となってしまったTargetは(当然分割格子数は実計算の多寡に影響するとはいえ)、定数扱いとなり、計算量はぐっと減少し、O(N)となります。雰囲気との比較というのは、局所最適解に陥りやすいマッチング処理において、ロバスト性を高める点にも一役買っています。おいて大活躍しています。前編において解説した、近傍Voxelの取得によって、Source各点に対するTarget中近傍Voxel(の"雰囲気")が取得されました。スコア値計算の部分を見ていきます。MatcherをOpenCLで実装し、他のデバイス(もちろんCPUもです!)へ容易にオフロードできるパッケージを作成しました。以降コードリーディングの際にも折に触れて登場します。github.comOpenCL版のREADMEはこちらをご覧ください。Matchingにおいては、その内部の処理は、Source各点に対して、各点並列でスコアを計算していきます。最終的にはそのSource各点のスコア値は合算されますが、この処理は並列化が比較的容易なアルゴリズムとなっており、AutowareではOpenMPによる並列化実装が採用されています。Accelerator...)への適用を念頭にしたチューニングがなされています。Matcherの外観から読んでいきたいと思います。Matcherは、LiDARからの点群を受けとった時点から処理がはじまります。Matcherに限ったことではありませんが、Autowareのソースコードリーディングにおいては、まずそのnodeが購読するtopicを知り、そのtopicを処理するcallbackを見つける所が最初の一歩です。そのcallbackにあたります。処理と呼ばれるものであり、一例として経過時間を以下に添付しますが、実際の所、計算機パフォーマンス的にはalign処理さえ抑えれば良いということがわかります。Matcherの各実装を示しており、node起動時のパラメーターによってどの実装が使用されるか決まります。align関数を呼び出しており、この中で、その子クラスで実装される関数である、ndt_ocl::NormalDistributionsTransform::computeTransformationを呼び出しています。ここまでの相関関係を図示しておくと以下の通りになりますが、これは実装の形式の話であり、最終的に重要なものは、自己位置計算の実装である、computeTransformationです。満足したら、その時点での変換行列を最終的な結果として終了します。このようにalign処理は、移動とスコア計算のイテレーションという一連の流れのことであるとソースコードからわかります。これ以降の処理追跡では、重要な部分を動的な観測から"あたり"をつけつつ、行っていきます。深くへソースコード上では様々な処理が存在しますが、複雑な記述だからといって重要度が高い、あるいは処理負荷が高いといったのはよくある誤謬です。今回はperfの結果可視化ツールのFlameGraphと、ValgrindのツールであるCallgrindの2つの結果を、ソースコードリーディングの座右に置きたいと思います。あり、先程のコードリーディングで登場しました。ここを起点に下に目を移していきます。呼び出しの頻度が低いため、左に降りていきましょう。あり、これがFlameGraphにも登場している、処理割合が大きい関数です。最終的に2つの関数にたどりつきます。掘り下げて見てみましょう。成ることがわかります。align処理の主関数は下記のたった3つであり、これにより重点的に見ていく場所が明らかになりました。radiusSearchupdateDerivativescomputePointDerivativescomputeDerivativesの中では、まずSource各点に対するTarget内の近傍探索、点の雰囲気とのマッチングスコア計算、そしてスコアがよくなる方向を上記の関数を用いて計算しています。同様の並列化が、omp_parallelを用いて実装されています。地図のVoxel分割と地図KD木構築実装OpenCL版で大きく異なるのは、むしろ地図のVoxel分割(およびそのKD木の構築)の部分であり、概念としては前編の通りですが、今一度package化に際しての実装を説明しておきます。この箇所で木を構築しています。内で任意に制御できる点にあります。この点は組み込み環境の制限されたメモリ環境においては必須となります。argumentとしてkernelに渡され、デバイス側の近傍探索に使用されます。スコア計算部の"命令実行的性質"計算量といってしまうと、それはランダウ表記で示される、入力数に対するチューリングマシン上での操作手数の関係(スケーラビリティ)という抽象性を持つものになってしまいますが、ここではより具体的に、特定の命令セット命令を持つ(load/store型)計算機上における、命令の実行性質をみたいと思います。computePointDerivatives2つの行列演算といくつかの行列のエレメント生成から成ります。packedな演算化は行っていません。実際にカーネルコードを、RISC-Vのコンパイラ(RV32if)でコンパイルした結果における、命令ヒストグラムを見てみます。flwとなっていることがわかります。x0)だったりしますが、本筋とは関係ありません。ちなみに乗算加算複合命令はgccでは-O3でないと出現しないようです。updateDerivatives多数の小規模行列演算と、スカラー値演算、およびexponent演算が使用されているのが特徴的です(スカラー値演算も多数ありますが、以下では割愛しています)。Probabilityとして、推定のもっともらしさを表す数値として使用されることになります。こちらも、RISC-Vコンパイラでのコンパイル結果とその命令分布を見てみましょう。fmadd.sの比重が大きいこととちょうど符合しています。OpenCL実装について紹介したOpenCL実装とOpenMP実装について、実際に(README記載の)サンプルを動作させて比較してみます。今回は、OpenCLもCPUにoffloadする形となっています。Timeの時間は大きく、分散が小さいです。これは、OpenMPでは処理のロードバランシング等の最適化が行われており、応答性に関してはより優れた結果になっていると思われます。GPGPUやAccelerator等のCPU外のdeviceにもoffloadすることが可能な点がOpenCL版の魅力ではありますが、ナイーブな実装もあってCPUは少し苦手といった所のようです。Probabilityとしては同程度の推移です。Block)が使用されていることがわかります。2.x環境の構築の例も紹介していますので、実行する際にぜひご参照ください。リソース管理厳格化OpenCLの実装にあたっては、使用する各種のリソースにも制限を意図的に加えています(いずれも設定が可能です)。実際問題として車載環境のような組み込みによった環境では、動的で潤沢なメモリ確保ができない場合の方が多いですし、何より実行毎に予想できない挙動であることは、一つのリスクとなります。重要なことは、平均でも最小でもなく、最大値を予め設定できるということです。Matchingにおいて、その処理量に影響を与える要素は3つしかなく、以下の3要素の最大値を予め定めさえすれば、処理時間を予測できるということになります。発見近傍Voxel数スコア値計算の最大繰り返し数OpenMP実装では、3のmax_iterationのみの制限でありますが、OpenCL実装では全てに以下のような制限をかけることができます。Matchingが不安定となる恐れがあります。(MAX_NUM_OF_LIDAR_POINTS)LiDARからの入力点群数の最大値を設定する。Matchingの計算面の調査を行い、その結果を一緒に眺めてきましたが、いかがでしたでしょうか。途中から解析や、再実装の話に始終してしまいましたが、腰をすえてソースコードを追ってみる時、ただやみくもに読むよりも定量的に姿を捉えながら全体を理解していく、そんな一例をご紹介できたかと思います。魔法のような自動運転のアルゴリズムも、実装となってしまえばただの計算です。Autowareはオープンなソフトウェアです。実際に読み、触れ、動作させることで理解ができます。Engineerの須永です。ティアフォーの安全への取り組みを数回にわたって紹介していくシリーズ。時間がたってしまいましたが今回は第3回目になります。1回目は法律・ガイドラインについてでした。tech.tier4.jp2回目は安心・安全についてでした。3回目の今回は自動車のサイバーセキュリティについての取り組みを説明していこうと思います。ティアフォーでは、「自動運転の民主化」をともに実現していくサイバーセキュリティエンジニアを絶賛大募集しています。自動車および自動運転のサイバーセキュリティは最先端、かつ広域にわたる知識が必要になってきます。我こそは、という方が居ましたら、気軽にカジュアル面談からでも対応しますので是非応募ください。Cherokeeという車両のハッキングに成功したことを報告し、140万台がリコールという話になりました。このハッキングは、はじめはWi-Fi経由でオーディオ音量を調整したりGPSで車両をトラッキングするなど、いわゆる車両内のマルチメディアシステムを掌握していました。ハッキングを進めると、マルチメディアシステムとは独立した車両の運転制御用のCANバスにアクセスできるまでになり、結果として外部から車両の運転制御までできるようになりました。車両を遠隔操作できることが分かったのです。ホワイトハッカーが実験的に行ったハッキングではあったものの、もし悪意のあるハッカーが遠隔操作で車両をコントロールすれば、故意に事故を起こすこともできるわけです。youtu.be自動車へのサイバー攻撃の現状2010年から2019年の10年間に公開された世界の車両サイバー攻撃インシデントの総件数は把握されている件数のみでも400件余り、2019年は単年で150件相当とのデータがあり、把握できていないものも含めるとその数倍はある可能性があります。このように、車両のサイバー攻撃は急増してきています。(参照:自動車へのサイバー攻撃の新常識と対応の考察)サイバー攻撃対象は、キーエントリシステムやテレマティクスや自動車メーカーのサーバ、カーシェアリングや自動車警報サービスなどのモバイルアプリケーションサーバといった自動車窃盗目的が多く、ホワイトハッカーの研究目的の攻撃から、悪意あるハッカーの攻撃に移行しているのは確実なようです。Cherokeeの事例のように遠隔操作で車両をコントロールすれば、故意に事故を起こすこともできるわけです。自動車のハッキングは最悪人命に関わることから、車両のサイバーセキュリティ侵害は安全侵害の一つになりえるとし、世界中が事態を重大にとらえている状況です。Services・Electric)時代といわれる100年に一度の変革期を迎えました。これらの背景を受けて、自動車業界や自動車のサイバーセキュリティルールを定めようとする国際的な動きが本格化したのです。フォーラム)および国際規格を制定するISOでルール化が動きはじめます。21434が正式な承認を迎える一歩手前まで来ている状況です。日本は自動車のサイバーセキュリティに関して各国を先導するように、WP29では共同議長または副議長を務めてきました。その活動の中で国土交通省は、2020年8月に自動車の特定改造等に関わる許可制度を発表しており対応が必要になっています。自動運転もまだ完全に完成されたソフトウェアが存在しないことから、適宜ソフトウェアをアップデートして機能をどんどん追加・改良していく段階です。市販車に搭載された場合でもアップデートしていけるようにOTA(Over-The-Air)が行われることが想定されています。自動運転システムになると車両だけでなくそれを取り巻くサブシステムとしてクラウドを利用します。先の説明でも行ったようにサイバーセキュリティ侵害がそのまま安全侵害に直結する可能性も出てきています。これらの中でも、システムのライフサイクルの中でサイバーセキュリティの確保および適宜見直しを行ってアップデートしていくことが求められています。今まで説明してきたルールでは概ね考え方の連携ができており、サイバーセキュリティの守り方は2種類に大別されます。System)のことで、サイバーセキュリティに関わるリスクマネジメントを効果的・効率的に実施するための仕組みになります。サイバーセキュリティを完全にすることはできないため、一般的にはスイスチーズモデルのように何層かの対策を打つのが一般的ですが、深刻な脆弱性問題が出た時にすぐに対処できる組織体制が必要、かつ準備しておくことが必要ということになります。2のリスクアセスメントとは、人はミスをすることを前提に、設計手法(プロセス)の中でミスを見つけてつぶし、設計の変更があった場合はその影響を見つけて設計に反映させていくものです。26262のV字プロセスと同じ手法になるため、V字を使用した開発プロセスという意味で兄弟的存在になります。兄弟的な存在になってきます。自動車のサイバーセキュリティ開発プロセス安全とサイバーセキュリティは、同じような開発プロセスでルール化されていますが、当然全く同じというわけではないので、その違いについて簡単に説明していきます。26262は、自動車でも特に車両の電気電子機器の機能安全(壊れても安全・壊れたら分かる)設計を行うもので、V字プロセスとして開発(設計・検証)を進めるものになります。リスク評価を行います。そのリスク評価に対して安全目標を立ててリスクを許容可能なレベルまで落とせるように安全要件を作成し、設計・実装していきます。設計・実装したものが意図したとおり、効果あるものか確認・検証していきます。21448では、システムとして未知で不安全である事象を減らし、既知で安全である事象を増やすことを続けていきます。これは車両・システムが破棄されるまで継続していき、安全性をどんどん上げていく取り組みになります。21434の概要をなぞる形で説明します。含めたサイバーセキュリティのリスク管理のためのエンジニアリング要件になっています。対象となるシステムの構成でアイテムおよび守るべき資産を定義し、定義したアイテム・資産のサイバーセキュリティ侵害による影響を脅威分析として実施し、攻撃の経路および影響からリスク評価を行います。そのリスク評価に対してサイバーセキュリティ目標を立てて許容可能なリスクレベルまで落とせるように要件を作成し、設計・実装していきます。設計・実装したものが意図したとおり、効果あるものか確認・検証していきます。サイバーセキュリティポリシーを設定し、その製品に脆弱性があった場合は対策・対応およびインシデントの管理を車両が廃棄されるまで継続していきます。Team)という組織横断的なチームによって管理していきます。開発領域では似たようなプロセスであるものの、安全・サイバーセキュリティ設計では大きく違うところがあります。:Confidentiality、Integrity、Availability)の3要素に分類します。プライバシー:Safety、Financial、Operational、Privacy)に分類します。安全は万人に影響がありますが、サイバーセキュリティは非常に範囲が広いので守るべき人や物に対して領域の線引きをする必要があるということを示しています。Assessment)を実施し安全性の評価をしていきます。Analysis)などの多くの安全分析手法が使用されます。Assessment)を実施しサイバーセキュリティ評価をしていきます。ハザードが脅威(Threat)に置き換わったものになります。System)で脆弱性を評価、対策を検討し、要件化を通して設計に反映していきます。安全分析・リスクアセス・要求プロセスサイバーセキュリティ分析・リスクアセス・要求プロセス車両のサイバーセキュリティは一般のコンピュータに比べると分析結果や知見など、まだまだなところがあります。自動運転システム自体巨大なシステムになっているのでサイバーセキュリティは安全と同様、膨大な分析と対策検討が必要になってきます。ティアフォーでは自動運転システムを搭載したPoC車両を開発しています。車両を改造してのシステムになるので、できる範囲からサイバーセキュリティ分析およびその対策を入れてはいますが、まだまだ発展途上という状況です。サイバーセキュリティ分析抜粋おわりに以上、簡単ではありますが、自動車のサイバーセキュリティに関する内容を説明させて頂きました。簡単に表現しすぎているところもあるのでルールの詳細はご確認ください。自動運転のサイバーセキュリティへの対応はソフトウェアに関する部分だけでなく、ハードウェアやシステム、さらに組織体制まで見る必要があり、安全と同様、もしくはそれ以上に大変なものです。したがって自動運転車での対応はそれだけ必要かつチャレンジングになっています。最後に、改めてになりますが、ティアフォーで自動運転システムのサイバーセキュリティ構築にチャレンジしたい方がおりましたら、以下のページよりコンタクトいただければと思います。読者になる2021-06-23自動運転の地図、ベクターマップについてこんにちは、ティアフォーでベクターマップの作成ツールの開発をしている浦本と申します。今回は、Autowareで使われている地図の中でも、特にベクターマップとその作成ツールについてお話しようと思います。ティアフォーでは、「自動運転の民主化」をともに実現していく様々なエンジニア・リサーチャーを募集しています。ご興味があればカジュアル面談も可能ですので以下のページからコンタクトいただければと思います。点群地図とベクターマップについてAutowareで使われる地図には、自己位置推定のための点群地図と、その地図上の走行可能領域や信号・標識などを定義したベクターマップがあります。Autowareは、道路や周囲の環境の形状を持っている点群地図と、走行中に取得したスキャンデータが最もマッチする重ね合わせから、車両の位置や向きを推定しています。この仕組みをスキャンマッチングといいます。スキャンマッチングについての詳細はこちらをご覧ください。交通ルールや注意が必要なエリアのような情報を入れることができ、これらの情報を適切に設定することで、車両がその場所に適した走行をできるようにしています。Autowareは現在、このベクターマップのフォーマットとしてLanelet2を採用しており、このフォーマットをAutoware用に一部拡張して使っています(これ以降、この記事ではLanelet2はAutoware用に拡張したものを指します)。(VMB)もこのAutoware拡張のLanelet2の地図作成が可能です。以下の画像はこのツール上で地図を表示している例です。白い点群地図と色がついているベクターマップを重ねています。Lanelet2についてここでは、Lanelet2の詳細について説明したいと思います。Lanelet2はOpenStreetMap(OSM)形式を拡張したもので、拡張子は.osm、ファイルに出力する際にはXML形式となります。Lanelet2は以下の基本オブジェクトで構成されますが、出力時にはOSMに合わせてnode、way、relationの3種類に分類されます。各基本オブジェクトの説明とファイルに出力した際のサンプルは以下のとおりです。画像はVMBでの表示例です。Point一番基本となるオブジェクトで、座標や信号の色情報などを持ちます。OSMのnodeに分類されます。z座標はeleというタグで表されます。ローカル座標を使いたい場合は、local_x、local_yというタグを設定することもできます。lat/lonは緯度経度、local_x、local_y、eleの単位はメートルです。v="19.000"/></node>LineStringPointのリストを順番に線で結んだオブジェクト。LineString2つでLaneletを構成したり、信号機や一時停止線に使われます。OSMのwayに分類されます。構成要素のPointをndタグで持ちます。一時停止線はtypeをstop_line、点線はsubtypeをdashedにすることで表します。Laneletの境界線のLineStringをdashedにすると隣接レーンに車線変更が可能になるなど、タグの付け方を変えることで様々な設定が可能です。詳細はこちらをご覧ください。v="solid"/></way>PolygonPointで囲まれた領域を表します。障害物検知領域を表すDetectionAreaなどで使われます。OSMのwayに分類され、area=yesというタグをつけます。v="yes"/></way>Lanelet左右にLineStringを1つずつ持ち、その間の領域を表します。向きを持っており、車線や横断歩道などに使われます。OSMのrelationに分類され、type=laneletというタグをつけます。左右のLineStringをmemberとして持ちます。その車線で守る必要のある交通ルール(RegulatoryElement)がある場合は、それもmemberとして持ちます。制限速度や通行対象(車や歩行者など)、一方通行かどうかなどの情報を持てます。v="yes"/></relation>AreaLineStringで囲まれた領域を表します。車両や人の通行領域を表す場合によく使われますが、Laneletと違って向きは持ちません。OSMのrelationに分類され、type=multipolygonというタグをつけます。構成要素のLineStringをmemberとして時計回りの順番に持ちます。v="multipolygon"/></relation>※Polygonとの見た目の違いは、周囲がLineStringで囲まれているかどうかです。紐付いているのかという情報を持っています。オブジェクト間の紐付けとルール情報を持つだけなので地図上に表示されるものではなく、画像はありません。OSMのrelationに分類されます。type=regulatory_elementというタグをつけます。subtypeでルールの種類を指定します(例:traffic_lightは信号、right_of_wayは優先道路)。v="traffic_light"/></relation>RegulatoryElementはルールの種類によってmemberの数や種類も変わってきます。例としてサンプルにも記載している信号を説明します。信号のmemberは3つで、refers、ref_line、light_bulbsがあります。それぞれtypeがwayとなっているので、LineStringがPolygonを表すのですが、信号に紐付くのは全てLineStringです。refersですが、これは信号の外形を表します。ファイルに出力すると以下のwayのようになるのですが、ndの2と3は画像の丸(Point)の部分で信号機の幅を表し、heightタグで高さを表します。v="0.450000"/></way>次にlight_bulbsは、以下のwayのようになり、traffic_light_idは信号機の外形のLineStringのidを表しています。ndの4から6はPointで、以下のidが4のnodeのような形でそれぞれcolorタグで信号の色情報を持ちます(画像の信号の場合はred、yellow、greenの3つ)。最後にref_lineですが、信号のref_lineは信号が赤だった時に停止する停止線を表すため、以下のwayのように、stop_lineというtypeを設定します。v="stop_line"/></way>このようなオブジェクトを組み合わせて、ベクターマップを作っています。Builderの紹介これまで説明してきたようなベクターマップを作成するためのツールとして、ティアフォーではVMBを開発しています。ブラウザで動作するツールで、TypeScript、React、Three.jsを主に使っています。リンクはこちらになりますが、最初にティアフォーアカウントを作成いただいてからログインが可能となります。tools.tier4.jpここでは、地図を作りやすくするために実装しているVMBの機能を一部紹介します。1つ目は、点群地図の表示範囲指定機能です。この機能を使うケースとして、例えば屋内のベクターマップを作成するときに、点群に屋根が入ってしまっていてそのままでは屋内の形状が見にくいというものがあります。いう場合は、この機能で不要な屋根部分の点群をカットし、見たい範囲の点群だけを見えるようにすることで、地図作成がしやすくなります。他にも、下の画像のように木が邪魔で車線が見づらい場合にも使えたり、上下の高さを指定できるので、ビルのような複数階を含む点群があったときには、見たい階だけを残して作業することも可能です。2つ目は、地図のリアルタイムチェック機能です。車線や交通ルールが増えて地図が複雑になると、作成・編集時にミスが起こりやすくなり、チェックも大変になります。ミスが残ってしまっていても、地図作成後はシミュレータで動作チェックを実施するため、想定外の挙動をする場合はそこでわかるのですが、複数箇所が間違っているとVMBに戻って該当箇所を修正→走行チェックという作業を何度か繰り返さなければいけない場合があります。VMBではそのような作業を少しでも減らすため、フォーマットとして間違っている点に加え、ティアフォーのこれまでの地図作成経験からリストアップしたチェック項目を作成作業中にチェックするようにしています。問題のある設定をすると、その設定を行った直後に問題のあるオブジェクトとその詳細を表示し、修正を促します。修正をしないまま地図の保存を行った場合は、問題点が残っていることを表示し、問題点に気づかずに保存してしまうことをできるだけ避けられるようにしています。画像は設定している制限速度を超えたLaneletが存在する場合の例です。何が問題なのかという説明とIDを表示しており、IDをクリックすることで該当オブジェクトの設定が確認できるようになっています。チェックすべき項目は、現在も実証実験等から問題を吸い上げたりしながら増やしており、今以上に充実させていく予定です。まとめ今回は、Autowareで使われている地図の中でも、特にベクターマップについてお話しました。自動運転車がどのような地図を使って走行しているのか、イメージできたでしょうか。ベクターマップは精度が求められるので作成時は細かな作業が多く、持たせる情報も多いことから設定とチェックに時間がかかります。これらの問題を解消し、より安全な地図をより早く作ることができるツール・仕組みの開発をこれからも進めていきます。読者になる2021-06-17Autowareの開発を更に加速!Openなシナリオテストフレームワークを紹介!はじめにこんにちは!ティアフォーの片岡と申します。Teamで開発してきたシナリオテストフレームワークであるscenario_simulatorをApache-2.0ライセンスでOSS(オープンソースソフトウェア)とした件についてお話します。Engineerを募集しております。自動運転のSimulator開発は、バグの少ない高品質なコードを書くのはもちろんのこと、三次元幾何や統計、はてはプログラミング言語開発まで様々な知識が要求される分野であり、広く深く様々なことをやってみたい方には非常にマッチするポジションであると思います。興味等ございましたら以下のページよりコンタクトいただければ大変幸いです。現在ティアフォーではSimulatorによってそれぞれ得意・不得意な領域があることを認識しており、テストケースごとに適切なSimulatorを選定し評価を行っています。AutowareをサポートしているSimulator上の図で記されているのは大枠のカテゴリであり、実際にはAutoware対応のSimulatorには様々なものが存在しています。代表的なものには以下のようなものがあります。Simulatoryoutu.begithub.comLGエレクトロニクスのシリコンバレー研究所が開発しているUnityベースのSimulatorで、Pythonでテストシナリオを記述できます。LiDARやCameraを多数取り付けたリッチな自動運転システムがSimulation可能です。V1.0やPython等でテストシナリオを記述できます。野心的な機能が多数盛り込まれており、非常に高機能なSimulatorです。メンバーのAutoCoreが開発したUnityベースのSimulatorです。非常に軽量でGTX750Tiでも動作可能になっています。Simulatoryoutu.begithub.comAutowareArchitectureProposalに同梱されているSimulatorです。V0.9.2をベースとしたティアフォーの独自フォーマットでのシナリオ記述が可能で、軽量であるため非常に高速に動作します。複数のSimulatorを使ってシナリオテストを行っていく過程でティアフォーは以下のような問題に直面しました。Simulator等独自シナリオフォーマットを中心としているようなSimulatorも多いため、一度書いたシナリオを使い回すのは簡単ではありません。シナリオを異なるSimulatorの間でやり取りするには人力で動作確認をしながらポーティングを行う必要があり、シナリオ変更履歴のトレーサビリティの観点からも大きな問題があります。NPCロジックがSimulatorごとに異なる完全に等価なシナリオを人力でポーティングできたとしても、それを処理する処理系が異なるのであれば処理結果は異なってしまいます。具体的な例として、「車の前に自転車が飛び出す」という状況を考えてみましょう。これをシナリオに起こす時、以下のような処理が記述されることになります。自転車のNPCをSpawnさせ、Waypointを与える。Bでは「スプライン補間したあと単純追跡コントローラでその経路をできるだけなぞる」のように異なっていた場合、これらは等価なテストシナリオとは言えません。いったNPC行動ロジックは厳密に一致している必要があります。Simulatorに備わっているテストランナーの枠組み上で解決しようとすると、彼らのソースコードに含まれる何千行ものNPC行動ロジック記述部分に手を入れて異なる言語やプラットフォームを超えて完全に等価なロジックを実装し、メンテナンスし続けなくてはなりません。これはほとんど不可能に近いと言えます。いった問題を解決するために仕様策定されたのがOpenSCENARIOですが、例えば以下のような基本的な箇所ですら未定義動作が非常に多く、OpenSCENARIOに対応したからと言って一度書いたシナリオがすべてのSimulatorで簡単に動くということは担保できません。道路端点や世界の端に到達したNPCはどう振る舞うべきかAssignRouteActionで経路指定した結果ゴールに到達したNPCはそのまま走っていくべきか、それともその場で停止するべきかレーンチェンジができない場所でレーンチェンジ指示が出た場合はどのような挙動をすべきかSimulatorごとにIntegrationの仕方が違う例えばCARLAにおいては独自ブリッジでROSおよびAutowareとのIntegrationを行っており、ブリッジ内部でPID制御器が動いていたりと他のSimulatorと全く異なるロジックで制御がなされています。SimulatorはAutowareとrosbridgeで接続しており、ROSの標準的なツールを用いてインターフェースが設計されています。www.lgsvlsimulator.comこのように、Simulatorごとに根本的に異なるインターフェースが設計されており、これはクラウド上にテストパイプラインを構築、メンテナンスしていく上で大きな障害になります。明示的な標準仕様がないため、新しいSimulatorをIntegrationする際には毎回設計を1からやり直す必要があり莫大な工数が発生することになります。現在シナリオフォーマットには様々なものが提案されています。V2.0およびそのベースとなっているM-SDLyoutu.beといった様々なフォーマットが現在も開発されています。産業界だけでなく、2019年ので発表されたGeoSCENARIO等アカデミア方面からも研究開発が進められています。geoscenario.readthedocs.ioどのシナリオフォーマットをどう使うのがAutowareの評価を最も効率化できるのかというのは未だ結論が出ていない領域の1つです。そのため、同時に複数のシナリオフォーマットをサポートできるようなシナリオテストフレームワークが強く求められます。ティアフォーにおいてはこれらの問題点を以下のアプローチで解決しました。Modelの採用すべてのSimulatorにおいてNPCロジックを共通化するため、NPCロジックをシナリオテストフレームワーク中の交通流Simulatorに対して実装しました。センサSimulatorが交通流Simulatorとプロセス間通信を行い、歩調を合わせながらCo-SimulationをすることでNPCロジック共通化を実現しています。これにより、交通流SimulatorはセンサSimulatorに対するOpenSCENARIOの「翻訳機」かのように振る舞い、OpenSCENARIOの未定義動作によるSimulatorごとの差異を吸収します。2に依存しない部分に関しては決定性を担保しています。APIを用意し、シナリオフォーマットの解釈器がそれを叩くアーキテクチャ構成にすることで同時に複数のシナリオフォーマットをサポートしています。完全にコンポーネントが分離されているので、スッキリとしたアーキテクチャに仕上がっています。Simulatorを抽象化SimulatorとAutowareとのインターフェースを統一し、複数のSimulatorを同時にサポートできるシナリオテストフレームワークを開発しました。MapとのインテグレーションをSimulatorで独自実装する必要はありません。Autowareは非常に高い頻度で更新が行われているソフトウェアであり、常に結合確認を取りながらインテグレーションを行う必要があり、メンテナンスコストが非常に高いです。Team主体で行っているため、Simulator開発者は短期間でSimulatorとAutowareを結合し、その結合を維持することが非常に簡単になりSimulatorとしてより本質的なセンサSimulationの高精度化や車両の運動モデルといった開発に時間を使うことができるようになります。Source更に、ティアフォーではこのシナリオテストフレームワークをオープンにすることでAutowareを様々なSimulator上で動かしてAutowareの評価を更に高速化していく仕組みを担保しようと考えています。ライセンスはApache-2.0で統一されているため非常に使いやすいツール群となっています。Simulatorが含まれています。Nodeとして実装されています。シナリオテストフレームワークアーキテクチャティアフォーのシナリオテストフレームワークはAutowareとSimulatorの間をつなぐ役割を果たします。Subする部分を除いて完全に決定性があります。シナリオテストフレームワークと通信してCo-Simulationを行うSimulatorはZeroMQで同期的に通信を行います。(C++)等様々な言語、プラットフォームで作られているSimulatorと簡単に通信することができます。Buffersを使ってシリアライズすることで、スキーマを明確に定義してSimulator開発者がインターフェースが変わったことをすぐに把握できるよう工夫しています。topic群を利用して通信します。Map管理機構を内包しており、それらを操作できるC++のインターフェースを備えています。Interfaceを叩いてOpenSCENARIO規格に基づいてSimulationを行えるツールを開発しました。2ノードからシナリオテストフレームワークのインターフェースをダイレクトに操作して実現)の誕生により、はからずも複数シナリオフォーマットをサポートすることが可能なアーキテクチャであることが立証されました。Interface)を経由して出すだけでSimulator内部のNPCの行動を制御することが可能です。2と密にIntegrationされ非常に簡易に使用できるインターフェースとなっていますので、今後他のシナリオフォーマットを採用する必要が出た場合は、その解釈器さえ書いてしまえば簡単にAutoware、Simulatorと接続を行うことができます。開発時に注力した要素シナリオテストフレームワーク開発においては、以下の要素に対して開発時に大きく注力しました。レーン座標系のサポートレーン座標系とは、レーンに沿って歪んだ座標系のことです(いわゆるフレネ座標系です)。https://releases.asam.net/OpenSCENARIO/1.0.0/ASAM_OpenSCENARIO_BS-1-2_User-Guide_V1-0-0.html#_cut_inみなさんが公道で車を運転する時、「前30mにトラックがいる」というとそれはデカルト座標系で距離を計算したら30m先にトラックがいるという意味ではなくレーンに沿ってこのまま進んだら30m先にトラックがいるという意味になるかと思います。レーン座標系でシナリオが記述できないと、直感的な記述ができず非常にシナリオ記述が煩雑なものとなります。レーン座標系を計算する時にはスプライン曲線等のパラメトリック曲線で点列を補間する処理が入るのですが、どんな式の形のパラメトリック曲線を使用するかで補間の結果は全く異なります。そのため、シナリオテストフレームワークでは内部にレーン座標系、ワールド座標系、物体間の相対座標系を相互に座標変換するAPIを備えており、Simulatorとプロセス間通信する際に渡される情報ではすべての物体位置はワールド座標系で記述されています。これらの座標変換はtfを介さずにフルスクラッチで実装されていますので、完全に決定性があります。Mapを解釈する必要がなくなり、AutowareとIntegrationする際の工数を大幅に削減することができる上、どのSimulatorを使っても完全に同じロジックで座標変換が行われるのでクオリティの担保が非常にやりやすくなります。SimulatorのNPCロジックは非常にシンプルなものでした。Boxを設け、その中に他のNPCやAutowareの車両が入った場合急ブレーキを踏む実装されていたロジックはこの2点のみです。これではシナリオライターはNPCの一挙手一投足を指定しなければならず、シナリオ作成に大きな負荷が発生していました。Treeを使用してNPCロジックを大幅に強化し、以下のような挙動を明示的に指示しなくても自動的にやってくれるようにしました。レーンに沿ってNPCが移動する。赤、黄色信号の前で停止する。Mapに埋め込まれた法定速度を遵守して走行する。明示的に速度指示があった場合にはそちらを目標速度として走行する。一時停止線で一時停止後、発車する。非優先道路において優先道路に他の車両がいる場合道を譲る。レーン座標系でみて自分の前方に車両がいる場合、速度を合わせて追従する。レーンチェンジの指示が出た場合、レーンチェンジ可能な地点であればレーンチェンジを行う。レーンチェンジが不可なエリアであった場合、レーンチェンジは行わない。自動テスト自動運転のテストパイプラインを運用していく上で「Simulatorにバグがあった」というケースは非常に厄介です。徹底的にバグは潰していかないといけませんし、早期発見しなくてはなりません。Simulatorにバグがあった場合、テスト担当の方はかなり深くSimulatorのソースコードやシナリオを追って問題の根源を考えないといけません。このコストは非常に高いですし、致命的な不具合が見つかった場合過去のテスト結果が信用できなくなる可能性もありえます。2パッケージ群であるシナリオテストフレームワークはなにか致命的な問題が見つかったからといって簡単に大規模なリファクタや修正をすることはできませんし、機能追加やバグフィックスによってデグレが発生しうることは容易に想像できます。Actionsを使用して以下のテストケースをシナリオテストフレームワーク本体のCIとして継続的に回しています。Pagesに常に最新版ドキュメントがデプロイされるようになっています。これにより簡単に最新版のドキュメントにアクセスすることができます。Teamでは以下のような改良をシナリオテストフレームワークに加えることを計画しています。超過といったより抽象的な指示を簡単に出せるようにするにはNPCロジックを更に賢くしていく必要があります。現在、ICRA2020で発表されたこちらのNPCロジックを改良し、Autowareの更なるシナリオテスト効率化を推し進めていこうと考えています。www.youtube.comarxiv.org公道走行ログからのシナリオ自動起こし公道走行中にあったヒヤリハットの状況をSimulatorの中で再現し、安全であることを検証する取り組みは非常に重要です。以前紹介したRSSは公道において発生した危険な状況を数値化することが可能となります。TeamではRSS等のメトリクスを用いて検出した危険な状況のデータを取り出し、周囲の交通状況を自動的にシナリオ化する技術開発にもトライしていこうと考えています。最後に改めてですが、興味等ございましたら以下のページよりコンタクトいただければ大変ありがたいです。カジュアルな面談も大歓迎です!tier4.jpよろしくお願いいたします。[前編]こんにちは、ティアフォーパートタイムエンジニアの上野と、ティアフォーエンジニアの村上です。Matchingです。点と点のMatchingから、点と分布のMatchingにすることで、計算負荷が現実的な程度まで削減されました。説かれており、また論文中の方程式は、Autowareの実装コードの中でも度々言及されています。LiDARを使用した高精度な位置推定に今や必須となったこの方法は、なおも計算負荷が比較的高いままです。計算負荷の観点でも目にする機会が多いこのアルゴリズムを、定量的/実装的な観点からあらためて見てみましょう。主要な処理が記述されています。LiDAR点群と近傍地図点群のDistributionを用いた「Matchingスコア値計算処理」との2つの処理に大別されます。matcherのflame-graph画像を上げます。近傍地図点群の取得の部分で、これが大体40%近い処理量となります。Matchingスコア値の計算をしている、演算中心の部分です。前半の今回は、まず入力として入ってきたLiDAR点それぞれに対し、物理的に近傍な地図点群を取得する方法を詳しく見ていきたいと思います。KD-Tree近傍地図点群(のvoxel)を取得する方法には、木探索による方法と、位置をkeyとしたhashからvoxel(とその上下左右前後にあるvoxel)を直ちに求める方法の、大きく2種類があります。ここで取得される近傍voxelの数は、続く演算処理量を線形に増加させることに注意します。代表的な関数だけを抽出すると、以下の図のような関係となります。木探索は近傍判定を精密にし、それ自体の処理量は重いですが、結果として近傍数が減少傾向となります。Matching全体の処理量は増加する可能性があります。下のグラフにもこのことは表れています。frame)近傍の多寡による処理量のトレードオフとともに、”近さ”の正確さは、位置推定精度にも大きく関わるため、判定方法の選択にはこれらを総合的に勘案して採用することになります。Autowareを使用する際のTuning対象として、様々な近傍探索の実装例や実証実験での採用例があります。Searchを使用しており、今回はこの探索を見ていきたいと思います。地図のKD木の構築方法KD木とは多次元(K-Dimensions)空間を分割して作る二分木です。KD木の構築は、多次元空間を各座標軸に垂直に分割していくことで行われます。KD木の各ノードは多次元空間の部分空間に対応しており、あるノードの子ノードに対応する空間は、親ノードの空間に包含されるという関係にあります。以下、地図点群からKD木を構築する方法について、具体的に説明します。簡単にするために2次元を例として用いますが、実際にAutowareで用いられている地図は3次元であることは留意してください。交互に行われることとします。2)}という6つの点から成る点群から構築する手順を以下のGIFで示します。2)を中心とし、全体を分割します。この時の中心が木のルートノードとなります。続いて、ルートノードから見て左側の子ノードを構築します。4)を中心に2分割します。ルートノードから見て左側の構築が葉まで完了したら、最後に右側の子ノードを構築していきます。このようにKD木を構築すると、この2次元空間は下図のような領域に分割されることになります。Searchを行う方法について説明します。Searchで取得します。アニメーションの通り、深さ優先探索となります。近傍点の判定は、木を降りていく途中で各ノードに対応する分割点と与えられた点との距離を比較し、所与の半径以内であるか否かで行います。最初に、ルートノードの分割点とクエリ点のX軸の値を比較します。今回は、クエリ点のX軸の値の方が小さいため、左側の子ノードに降りていきます。2)自身も近傍として判定します。次に、分割点とクエリ点のY軸の値を比べ、先と同様に、左右どちらの子ノードに降りるかを決定します。4)のノードとの距離は2より大なので、これは近傍点ではありません。3)のノードは葉ノードとなり、これ以上は探索しません。3)のノードもまた近傍点とは判定されません。正確に近傍点を探すためには、木を降りるだけではなく「登る」処理が必要となります。4)のノードに登ります。最初に探索しなかった側の子ノード以下に近傍点が存在するかどうかの判定を行います。Y軸の値の差の絶対値と探索半径との比較を用います。ノードから見て右側の子ノード以下には近傍点が存在し得ないことを意味しますので、右側の子ノードに降りる必要はなく、探索は打切となります。上の手順で降りた方向とは逆の枝を判定しつつ、木を順に登っていき、ルートノードまで登ってくることになります。ルートノードでも、最初に降りた方向とは逆、つまり例の場合右側の子ノード以下に近傍点が存在するか確かめましょう。ルートノードにおいて、分割点とクエリ点のX軸の値の差は探索半径よりも小さいので、右側の子ノード以下に近傍点が存在する可能性があります。よって、右側の子ノード側へも改めて降りていき、探索を行っていきます。近傍として取得されます。近傍探索の精度よりも高速性を重視する場合、葉ノードに到達した時点で近傍探索を打ち切る、すなわち「登る」処理を行わないことも考えられます。いうライブラリを用いていますが、このライブラリにおいても、実際「登る」側の処理は行われていません。以下、OpenCLとして再実装を行いますが、同様の方針を取ることにします。SearchをLiDAR点に対して並列化するためにOpenCLを用いて実装します。LiDARの各点の処理や探索は、各点独立して並列に行うことができ、並列化のうまみが大きい部分です。KD木の構築も移植性やメモリ配置の透明性をもたせるため、Cとして再実装を行っています。コードを参考にし、kdtree_construction.hに実装しています(元のコードは2次元平面上の点群の分割を行なっているため、これを3次元に拡張する形で変更しています)。して与え、再帰的に木構造を構築するコードです。Zのいずれかの軸で空間を分割します。ソートし、その中央を分割点としてノードを構築する部分は、前節で説明した通りです。ソートしたpointlistのうち、分割点よりもindexが小さい点群を左の子ノード(child1)に渡し、分割点よりもindexの大きい点群が右の子ノード(child2)に渡されます。node_indexesには点群のインデックスとノードのインデックスを対応させるのに必要な情報を格納します。新たなノードを作る際に受け取った点群数が1であるか、または木の深さがMAX_DEPTHよりも大きくなれば、そのノードを葉ノードとして木の構築をそこで打ち切ります。することで表現します。root_nodeポインタにはあらかじめ木のノード数分の領域を確保しておき、alloc_pointerを用いて、木のルートノードを先頭としてノードが構築された順にメモリ上に配置されるようにすることで、配置の透明性を上げています。SearchをOpenCLで実装した際のカーネルコードkernel_radius_search.clを以下に示します。OpenCLの各スレッドはitem_indexを用いて入力点群のうちの1つを取得してクエリ点とし、構築したKD木に対して近傍探索を行います。while文で近傍探索を行ないます。else節が実行され、ノードの分割点とクエリ点の距離を計算し、近傍点かどうかの判定を行いつつ適切な子ノードに向かって木を降りていきます。if節が実行されます。葉ノードには分割点以外にも複数の点が含まれる場合があるので、それら全てとクエリ点の距離を計算し、近傍判定を行います。前述の通り木を「登る」処理は行わないので、葉ノードに到達するか、あるいは取得した近傍点の数がlimitを超えた場合にwhile文からのbreakとなり、処理が終了します。Searchの処理を各点で並列化するためには、ホスト側で構築したKD木を各スレッドが参照できるメモリに配置する必要があります。そこで、__constant修飾子を用いてコンスタントメモリに木構造を配置しますが、そのまま配置するとホスト側で、特に子ノードをポインタを使って表現されている木構造が、コンスタントメモリ上でも同様の構造を保つ保証がなくなってしまいます。いう機能を用いて上の問題を解決できます。名前の通り、ホストとデバイスで仮想メモリ空間を共有できる機能であり、今回の木構造のメモリのデバイス間共有に最適です。blogでも詳しく紹介されています。OpenCLにおいてメモリ構造の記事は、こちらの記事が大変参考になります。Searchの動作確認を行うために、Autowareの動作確認に用いられているMapとLiDARのデータを使用します。LiDARのデータは、Autoware用のサンプルデータにおいてrosbagの中のtopic群として提供されていますし、何より座標変換の処理をしたり、複数のセンサーデータの統合もしなければなりません。Matching処理直前の点群を、外部ファイルに保存するという手段を取りましょう。Matching処理が行われます。そこで、この関数内で入力として使われている点群を外部ファイルに保存します。先に座標変換の話に触れましたが、rosbagの中に存在するLiDAR点群の座標は、あくまでLiDARセンサから見たものであり、Map点群とのMatching処理入力として有効であるためには、車体およびMapに対して座標変換を行っておく必要があります。いう点群が入力として設定されていますが、この点群はまだ車体位置・姿勢に対しての座標変換が行われていません。