読み解くNDT Scan Matchingの計算 [前編]

こんにちは、ティアフォーパートタイムエンジニアの上野と、ティアフォーエンジニアの村上です。

今回読み解いたのは、自動運転位置推定のターニングポイントとなった、Scan Matchingによる高精度自己位置推定技術の華、NDT Scan Matchingです。点と点のMatchingから、点と分布のMatchingにすることで、計算負荷が現実的な程度まで削減されました。方法としては博士論文 M. Magnusson, “The three-dimensional normal-distributions transform : an efficient representation for registration, surface analysis, and loop detection,” PhD dissertation, Örebro universitet, Örebro, 2009. で説かれており、また論文中の方程式は、Autoware実装コードの中でも度々言及されています。

しかしながら、LiDARを使用した高精度な位置推定に今や必須となったこの方法は、なおも計算負荷が比較的高いままです。計算負荷の観点でも目にする機会が多いこのアルゴリズムを、定量的/実装的な観点からあらためて見てみましょう。

NDT Scan Matcherについて、Autowareが用いている実装としては、全体的には ndt_scan_matcher_core.cpp、部分的には ndt_omp_impl.hpp に主要な処理が記述されています。

主要な処理は、その負荷の大きさや計算の姿から大きくは、1. 移動がある自動運転におけるMatchingスコア値収束性能向上のための「近傍地図点群の取得処理」と、2. LiDAR点群と近傍地図点群のDistributionを用いた「Matchingスコア値計算処理」との2つの処理に大別されます。

以下にndt scan matcherのflame-graph画像を上げます。初期位置/姿勢の推定処理である alignUsingMonteCarlo 部分を除外し callbackSensorPoints 直下に注目します。

f:id:james-murakami:20210430102443j:plain

ndt scan matcher; flame graph

KdTreeFLANN::radiusSearchが1. 近傍地図点群の取得の部分で、これが大体40%近い処理量となります。その他の computeDerivatives がおおよそ2. Matchingスコア値の計算をしている、演算中心の部分です。

前半の今回は、まず入力として入ってきたLiDAR点それぞれに対し、物理的に近傍な地図点群を取得する方法を詳しく見ていきたいと思います。

Radius Search on KD-Tree

近傍地図点群(のvoxel)を取得する方法には、木探索による方法と、位置をkeyとしたhashからvoxel(とその上下左右前後にあるvoxel)を直ちに求める方法の、大きく2種類があります。

ここで取得される近傍voxelの数は、続く演算処理量を線形に増加させることに注意します。代表的な関数だけを抽出すると、以下の図のような関係となります。

f:id:james-murakami:20210430102547p:plain

木探索は近傍判定を精密にし、それ自体の処理量は重いですが、結果として近傍数が減少傾向となります。対してhash引きは、近傍判定を等閑にするため軽く、結果として近傍数が増加傾向となり、Scan Matching全体の処理量は増加する可能性があります。下のグラフにもこのことは表れています。

f:id:TierIV:20210504213000p:plain

Radius Search(木探索)の場合のLiDAR InputsとNeighbor Voxelsの関係

(縦: 個数, 横: LiDAR frame)

f:id:TierIV:20210504213051p:plain

HASH引き(周辺26voxel)の場合のLiDAR InputsとNeighbor Voxelsの関係

(縦: 個数, 横: LiDAR frame)

近傍の多寡による処理量のトレードオフとともに、”近さ”の正確さは、位置推定精度にも大きく関わるため、判定方法の選択にはこれらを総合的に勘案して採用することになります。Autowareを使用する際のTuning対象として、様々な近傍探索の実装例や実証実験での採用例があります。

ティアフォーでは表題の通りKD木(K-Dimensions tree)上でのRadius Searchを使用しており、今回はこの探索を見ていきたいと思います。

地図のKD木の構築方法

KD木とは多次元(K-Dimensions)空間を分割して作る二分木です。KD木の構築は、多次元空間を各座標軸に垂直に分割していくことで行われます。KD木の各ノードは多次元空間の部分空間に対応しており、あるノードの子ノードに対応する空間は、親ノードの空間に包含されるという関係にあります。

以下、地図点群からKD木を構築する方法について、具体的に説明します。なお、簡単にするために2次元を例として用いますが、実際にAutowareで用いられている地図は3次元であることは留意してください。また、空間の分割はX軸 → Y軸 → X軸 → … と交互に行われることとします。

{(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)}という6つの点から成る点群から構築する手順を以下のGIFで示します。

f:id:james-murakami:20210430102818g:plain

まず最初に、全体の空間をX軸で2分割するにあたって、点群全体をX軸の値でソートし中央の点 (7, 2)を中心とし、全体を分割します。この時の中心が木のルートノードとなります。

続いて、ルートノードから見て左側の子ノードを構築します。2段目ではY軸の値でソートし、中央となる(5, 4)を中心に2分割します。ルートノードから見て左側の構築が葉まで完了したら、最後に右側の子ノードを構築していきます。

このようにKD木を構築すると、この2次元空間は下図のような領域に分割されることになります。

f:id:james-murakami:20210430102931p:plain

Radius Search

次に、上で構築した木構造に対してクエリ点(入力点)を与え、Radius Searchを行う方法について説明します。例として、点(6, 1)から半径2以内の距離にあるノードを、Radius Searchで取得します。

f:id:james-murakami:20210430103024g:plain

アニメーションの通り、深さ優先探索となります。近傍点の判定は、木を降りていく途中で各ノードに対応する分割点と与えられた点との距離を比較し、所与の半径以内であるか否かで行います。

まず最初に、ルートノードの分割点とクエリ点のX軸の値を比較します。今回は、クエリ点のX軸の値の方が小さいため、左側の子ノードに降りていきます。また、ルートノードの分割点 (7, 2) とクエリ点 (6, 1) の距離は2以下であるので、このノード(7, 2)自身も近傍として判定します。

次に、分割点とクエリ点のY軸の値を比べ、先と同様に、左右どちらの子ノードに降りるかを決定します。今回は(2, 3) のノードに降ります。さて、(5, 4)のノードとの距離は2より大なので、これは近傍点ではありません。また、(2, 3)のノードは葉ノードとなり、これ以上は探索しません。そして(2, 3)のノードもまた近傍点とは判定されません。

正確に近傍点を探すためには、木を降りるだけではなく「登る」処理が必要となります。葉ノードに到達した後、一度1つ上の(5, 4)のノードに登ります。そして、最初に探索しなかった側の子ノード以下に近傍点が存在するかどうかの判定を行います。

判定には、分割点 (5, 4) とクエリ点 (6, 1) のY軸の値の差の絶対値と探索半径との比較を用います。この時、探索半径の方が小さくなり、このことは (5, 4) のノードから見て右側の子ノード以下には近傍点が存在し得ないことを意味しますので、右側の子ノードに降りる必要はなく、探索は打切となります。

上の手順で降りた方向とは逆の枝を判定しつつ、木を順に登っていき、ルートノードまで登ってくることになります。ルートノードでも、最初に降りた方向とは逆、つまり例の場合右側の子ノード以下に近傍点が存在するか確かめましょう。ルートノードにおいて、分割点とクエリ点のX軸の値の差は探索半径よりも小さいので、右側の子ノード以下に近傍点が存在する可能性があります。よって、右側の子ノード側へも改めて降りていき、探索を行っていきます。

後は同様の手順を行い、結果として (7, 2) と (8, 1) の2点がクエリ点 (6, 1) の近傍として取得されます。

ただし、近傍探索の精度よりも高速性を重視する場合、葉ノードに到達した時点で近傍探索を打ち切る、すなわち「登る」処理を行わないことも考えられます。Autowareにおけるこの近傍探索はFLANN (Fast Library for Approximate Nearest Neighbors) というライブラリを用いていますが、このライブラリにおいても、実際「登る」側の処理は行われていません。

以下、OpenCLとして再実装を行いますが、同様の方針を取ることにします。

木構築とRadius Searchの再実装

この節ではKD木の構築を純粋なCとして再実装し、KD木を用いたRadius SearchをLiDAR点に対して並列化するためにOpenCLを用いて実装します。

LiDARの各点の処理や探索は、各点独立して並列に行うことができ、並列化のうまみが大きい部分です。また、KD木の構築も移植性やメモリ配置の透明性をもたせるため、Cとして再実装を行っています。

探索コード: https://github.com/yuteno/kdtree_radius_search_opencl

なお、KD木の構築はhttps://github.com/fj-th/kd-tree-C-language- のコードを参考にし、kdtree_construction.hに実装しています。(元のコードは2次元平面上の点群の分割を行なっているため、これを3次元に拡張する形で変更しています。)

kdtree_node * kdtree(kdtree_node * root_node,
                     unsigned * alloc_pointer,
                     struct point * pointlist,
                     int left, int right, unsigned depth,
                     int * node_indexes) {
  if (right < 0) {
    // not allocate
    return NULL;
  }
  // allocate
  kdtree_node * new_node = &root_node[*alloc_pointer];
  *alloc_pointer = *alloc_pointer + 1; // count up

  // index list included in this node
  new_node->left_index = left;
  new_node->right_index = left + right + 1;
  // tree's depth
  new_node->depth = depth;
  int median = right / 2;

  if (right == 0 || depth > MAX_DEPTH) {
    // new_node is leaf
    new_node->location = pointlist[median];
    // no child node
    new_node->child1 = NULL;
    new_node->child2 = NULL;

    qsort(pointlist, right + 1, sizeof(struct point), comparex);
    new_node->leftmost = pointlist[0].x;
    new_node->rightmost = pointlist[right].x;

    qsort(pointlist, right + 1, sizeof(struct point), comparey);
    new_node->downmost = pointlist[0].y;
    new_node->upmost = pointlist[right].y;

    qsort(pointlist, right + 1, sizeof(struct point), comparez);
    new_node->zlowmost = pointlist[0].z;
    new_node->zupmost = pointlist[right].z;

    for (int i = 0; i < right+1; i++) {
      node_indexes[new_node->left_index+i] = pointlist[i].id;
    }

    return new_node;
  }

  // change the dividing direction
  new_node->axis = depth % 3;

  // sorting by space (1 direction) for binary division
  if (new_node->axis == XAxis) {
    // ascending sorting by point.x
    qsort(pointlist, right + 1, sizeof(struct point), comparex);
    new_node->leftmost = pointlist[0].x;
    new_node->rightmost = pointlist[right].x;
  } else if (new_node->axis == YAxis) {
    // by point.y
    qsort(pointlist, right + 1, sizeof(struct point), comparey);
    new_node->downmost = pointlist[0].y;
    new_node->upmost = pointlist[right].y;
  } else if (new_node->axis == ZAxis) {
    // by point.z
    qsort(pointlist, right + 1, sizeof(struct point), comparez);
    new_node->zlowmost = pointlist[0].z;
    new_node->zupmost = pointlist[right].z;
  }


  node_indexes[new_node->left_index+median] = pointlist[median].id;
  //printf("node->left_index+median: %d\n", new_node->left_index+median);
  new_node->location = pointlist[median];
  new_node->child2 = kdtree(root_node, alloc_pointer,
                            pointlist + median + 1,
                            /*left  =*/ left + median + 1,
                            /*right =*/ right - (median + 1),
                            /*depth =*/ depth + 1, node_indexes);

  new_node->child1 = kdtree(root_node, alloc_pointer,
                            pointlist,
                            /*left  =*/ left,
                            /*right =*/ median - 1,
                            /*depth =*/ depth + 1, node_indexes);

上記コードは、KD木を構築したい点群の配列を pointlist として与え、再帰的に木構造を構築するコードです。L. 51 ~ L. 66 では、X, Y, Zのいずれかの軸で空間を分割します。pointlistqsort でソートし、その中央を分割点としてノードを構築する部分は、前節で説明した通りです。ソートしたpointlistのうち、分割点よりもindexが小さい点群を左の子ノード(child1)に渡し、分割点よりもindexの大きい点群が右の子ノード(child2)に渡されます。また、node_indexesには点群のインデックスとノードのインデックスを対応させるのに必要な情報を格納します。

新たなノードを作る際に受け取った点群数が1であるか、または木の深さがMAX_DEPTHよりも大きくなれば、そのノードを葉ノードとして木の構築をそこで打ち切ります。この時、葉ノードであることは、child1およびchild2NULL とすることで表現します。

また、root_nodeポインタにはあらかじめ木のノード数分の領域を確保しておき、alloc_pointerを用いて、木のルートノードを先頭としてノードが構築された順にメモリ上に配置されるようにすることで、配置の透明性を上げています。

Radius SearchをOpenCLで実装した際のカーネルコードkernel_radius_search.clを以下に示します。

__kernel void radiusSearchCL(const global float * lidar_points_x,
                        const global float * lidar_points_y,
                        const global float * lidar_points_z,
                        const global float * map_points_x,
                        const global float * map_points_y,
                        const global float * map_points_z,
                        const global int * node_indexes,
                        __constant kdtree_node * root_node,
                        const int n,
                        const int limit,
                        const float radius,
                        global int * neighbor_candidate_indexes,
                        global float * neighbor_candidate_dists) {

  // 1d range kernel for the point cloud
  int item_index = get_global_id(0);
  if (item_index >= n)
    return;

  float4 reference_point = (float4)(lidar_points_x[item_index],
                                    lidar_points_y[item_index],
                                    lidar_points_z[item_index],
                                    0);

  if (item_index == 0)
    printf("ref point (%f, %f, %d), radius %f, limit %d\n", lidar_points_x[item_index], lidar_points_y[item_index], lidar_points_z[item_index], radius, limit);

  __constant kdtree_node  *current_node = root_node;
  int neighbors_count = 0;

  int level = 0;
  float dist;
  float4 dist_square;
  // radius search
  while (true) {
    if ((current_node->child1 == NULL) && (current_node->child2 == NULL)) {
      //reached to leaf node

      for (int i = current_node->left_index; i < current_node->right_index; ++i) {
        int index = node_indexes[i];
        float4 map_point = (float4)(map_points_x[index],
                                    map_points_y[index],
                                    map_points_z[index],
                                    0);
        for (int d = 0; d < 4; d++) {
          dist_square[d] = (map_point[d] - reference_point[d]) * (map_point[d] - reference_point[d]);
        }
        //float4 dist_square = (map_point - reference_point) * (map_point - reference_point);
        dist = sqrt(dist_square[0] + dist_square[1] + dist_square[2]);
        if (dist < radius) {
          neighbor_candidate_indexes[limit*item_index + neighbors_count] = index;
          neighbor_candidate_dists[limit*item_index + neighbors_count] = dist;
          neighbors_count++;
        }
        if (neighbors_count >= limit){
          break;
        }
      }
      break;
    } else {
      int index = node_indexes[current_node->left_index + (current_node->right_index - current_node->left_index-1) / 2];
      float4 map_point = (float4)(map_points_x[index],
                                  map_points_y[index],
                                  map_points_z[index],
                                  0.0f);
      //dist_square = (map_point - reference_point) * (map_point - reference_point);

      for (int d = 0; d < 4; d++) {
        dist_square[d] = (map_point[d] - reference_point[d]) * (map_point[d] - reference_point[d]);
      }
      dist = sqrt(dist_square.x + dist_square.y + dist_square.z);
      if (dist < radius) {
        neighbor_candidate_indexes[limit*item_index + neighbors_count] = index;
        neighbor_candidate_dists[limit*item_index + neighbors_count] = dist;
        neighbors_count++;
      }
      if (neighbors_count >= limit){
        break;
      }
      float val = reference_point[current_node->axis];
      float diff = val - current_node->axis_val;

      __constant kdtree_node * next;
      if (diff < 0 && current_node->child1) {
        next = current_node->child1;
        // printf("%d in (%d), select child1\n", item_index, n);
      } else {
        next = current_node->child2;
        // printf("%d in (%d), select child2\n", item_index, n);
      }
      current_node = next;
    }
  }
}

OpenCLの各スレッドはitem_indexを用いて入力点群のうちの1つを取得してクエリ点とし、構築したKD木に対して近傍探索を行います。

L. 35 からのwhile文で近傍探索を行ないます。

葉ノードに到達するまでは L. 60 からのelse節が実行され、ノードの分割点とクエリ点の距離を計算し、近傍点かどうかの判定を行いつつ適切な子ノードに向かって木を降りていきます。

葉ノードに到達すると L. 36 のif節が実行されます。葉ノードには分割点以外にも複数の点が含まれる場合があるので、それら全てとクエリ点の距離を計算し、近傍判定を行います。

また、前述の通り木を「登る」処理は行わないので、葉ノードに到達するか、あるいは取得した近傍点の数がlimitを超えた場合にwhile文からのbreakとなり、処理が終了します。

Host-Device間メモリについて

KD木を用いたRadius Searchの処理を各点で並列化するためには、ホスト側で構築したKD木を各スレッドが参照できるメモリに配置する必要があります。そこで、__constant修飾子を用いてコンスタントメモリに木構造を配置しますが、そのまま配置するとホスト側で、特に子ノードをポインタを使って表現されている木構造が、コンスタントメモリ上でも同様の構造を保つ保証がなくなってしまいます。

f:id:james-murakami:20210430103111p:plainOpenCL 2.0から実装されたShared Virtual Memory (SVM) という機能を用いて上の問題を解決できます。名前の通り、ホストとデバイスで仮想メモリ空間を共有できる機能であり、今回の木構造のメモリのデバイス間共有に最適です。SVMについてはFixstars社のTech blogでも詳しく紹介されています。また、OpenCLにおいてメモリ構造の記事は、こちらの記事が大変参考になります。

AutowareのTutorial ROSBAGとMapを用いた動作

OpenCL実装したRadius Searchの動作確認を行うために、Autowareの動作確認に用いられているMapとLiDARのデータを使用します。しかし、LiDARのデータは、Autoware用のサンプルデータにおいてrosbagの中のtopic群として提供されていますし、何より座標変換の処理をしたり、複数のセンサーデータの統合もしなければなりません。動作確認だけのために、本実装にこの処理を追加するのは面倒なので、今回はAutowareを一部改変し、Scan Matching処理直前の点群を、外部ファイルに保存するという手段を取りましょう。

再びAutowareでの実装である、localization/pose_estimator/ndt_scan_matcher/ndt_scan_matcher/src/ndt_scan_matcher_core.cpp を見ていきます。

LiDAR点群が到着するたびに、コールバック関数 callbackSensorPoints が呼ばれ、それを入力としてScan Matching処理が行われます。そこで、この関数内で入力として使われている点群を外部ファイルに保存します。

先に座標変換の話に触れましたが、rosbagの中に存在するLiDAR点群の座標は、あくまでLiDARセンサから見たものであり、Map点群とのMatching処理入力として有効であるためには、車体およびMapに対して座標変換を行っておく必要があります。

ndt_scan_matcher_core.cpp の L.310setInputSource 関数を用いて sensor_points_baselinkTF_ptr という点群が入力として設定されていますが、この点群はまだ車体位置・姿勢に対しての座標変換が行われていません。車体位置・姿勢に対しての座標変換行列は、L. 346align 関数の引数として使われているinitial_pose_matrix です。そこで、PCL (Point Cloud Libary) の pcl::transformPointCloud 関数を用いて、sensor_points_baselikTF_ptrinitial_pose_matrx で座標変換を行います。このようにして変換した点群を pcl::io::savePCDFile 関数でpcdファイルに保存することで、Autoware用サンプルデータ内の点群を、今回の実装の入力として適当な形に変換することができます。

ぜひティアフォーへ!

今回の調査や再実装の動機は、採用できる計算システムの選択肢を広げたいところにあります。実証実験のソフトウェアは実証実験のシステムや環境からの影響を多大に受け、さらに使用しているライブラリ類の制限を多分に受けます。計算機側の立場は高速な開発/実証実験とは対極ではありますが、HW/SWの双方に高水準な性能が要求される自動運転開発の両軸です。

移植性についても、あらゆるシステムに移植できることは幻想です。ただ、特定のシステムに依存することは、本質的に効率の悪い選択肢をとらざるを得なければならない危険性を抱えてしまいます。

このようにティアフォーでは、自動運転技術の精度性能のチューニングはもちろん、計算システムでの性能のチューニングも行っております。計算機およびアルゴリズムは自信あり、でも自動運転は興味があるだけ...という、そこのお方!ぜひ一緒に完全自動運転を実現する計算機を探索しましょう!下記リンクからお問い合わせお待ちしています! 

tier4.jp

筑西市における小型自動搬送ロボットの実証実験

こんにちは、ティアフォーのフィールドインテグレーションチームに所属している帯津です。今回は2021年3月29日から4月13日の期間で、茨城県筑西市にある道の駅「グランテラス筑西」と周辺地域で実施しました、小型自動搬送ロボットの実証実験の概要と小型自動搬送ロボットならではの実証ポイントについてご紹介します。

なお、ティアフォーでは、自動運転の安心・安全を確保し「自動運転の民主化」をともに実現していく、様々なエンジニア・リサーチャーを募集しています。もしご興味があればカジュアル面談も可能ですので以下のページからコンタクトいただければと思います。

tier4.jp

実証実験概要

小型自動搬送ロボットの実証実験を行う背景には大きく分けて2つの理由があります。1つ目は、eコマースの普及にともなう物流量の増大や施設管理の大規模化が進み、対応する人手不足が深刻化しているため、2つ目は新型コロナウイルス感染症拡大にともない、新しい生活様式が広まる中、非接触型の配送ニーズが高まっているためです。そして将来的には自動配送ロボットを活用した新たな配送サービスの実現が期待されています。

科学都市であるつくば市を擁する茨城県は、Society 5.0地域社会実装を強く推進、その茨城県配下の筑西市が手をあげ、本実証実験の支援を頂くこととなりました。

概要

本実証実験では、仕様が異なる2台の小型自動搬送ロボット「Logiee」(以下、Logiee)で、下記2つの自動配送を実施しました。

  1. 道の駅「グランテラス筑西」と周辺農家・民家を結ぶ公道の遠隔監視型配送
  2. 「グランテラス筑西」施設敷地内における複数地点を結ぶ近接監視型配送

上記2のルートについては、株式会社オプティマインドの配送ルートを最適化する自動配車システム「Loogia」(以下、Loogia)と、ティアフォーの自動運転車両の運行管理サービスFMS(以下、FMS)との連携によるスケジュール配信の実験を行いました。

近接監視型と遠隔監視型

小型自動搬送ロボットの運用では、自動運転システムの監視者はロボット近傍で常時監視するか、ロボットに搭載したカメラの映像を遠隔監視室で常時監視するかによって2つの監視型に分けられ、前者を近接監視型、後者を遠隔監視型としています。

近接監視型は、近接監視者が車両近傍において、車両周囲の状況を目視で随時確認を行うとともに、自動運転OS Autoware(以下、Autoware)の稼働状況も随時確認します。また、システムの異常時や危険を感じた場合は、車両の緊急停止ボタンを押下、手動走行に切り替えての危険回避などを実施し、安全性を確保します。

一方、遠隔監視型は、遠隔監視者が遠隔監視室よりモニターに映し出される車両のカメラ映像および各種情報より車両周囲の状況を確認するとともに、Autowareの稼働状況を監視し、異常が発生していないか監視します。また、必要に応じて緊急停止やシステムへの介入を行い、遠隔コントローラーを操作して危険回避などを実施し、安全性を確保します。

車両コンセプト

前述のとおり、私有地と公道をそれぞれが連携して走行させるため、異なる仕様のLogieeを使用しました。

1つは、公道走行が可能な高スペック自動搬送ロボット『LogieeS-TC』(以下、LogieeS-TC)、もう1つは、私有地での走行に限定した廉価版の自動搬送ロボット『LogieeSS』(以下、LogieeSS)です。

LogieeS-TCは一般消費者向けを想定しており、丸みを帯びたデザインとなっております。また、前後左右に搭載したカメラの映像が遠隔地からオペレータが監視可能であるほか、LogieeS-TCと遠隔室のオペレータ間に内蔵されたマイク、スピーカーを使うことで、通行する歩行者の方への呼びかけ、通話も可能となっています。さらに、商品の受け渡しの際に、オペレータと通話することで、初めて配送サービスを利用する方でも安心して利用することが可能です。事実、実証実験期間中に、地域の子どもたちとLogieeS-TC(このイベントでは「ろーじー」と称していました)が会話し、子どもたちの疑問を「ろーじー」が答えるなど、イメージキャラクターとしての役割も担いました。

一方、LogieeSSはビジネス向け用途を想定しており、今回の実証実験の場となったグランテラス筑西内を走行させるというよりも、一般には目にすることがないバックヤードでの走行を想定しているため、LogieeS-TCと比べて、LogieeSSでは遠隔監視機能、通話機能などはなく、デザインもシンプルです。

ただし、自動走行にフォーカスを当てると、LogieeS-TCとLogieeSSはコンセプト・外観は異なるものの、同一のパワーユニットを使用し、どちらもAutowareをコアアーキテクチャとした自動搬送ロボットです。なお、LogieeS-TCならびにLogieeSSの操舵方式は、後輪2輪の独立制御による差動2輪方式です。差動2輪方式は構造がシンプルである一方、2輪の駆動状況がパス追従性に大きく影響を及ぼします。例えば、2輪のタイヤエアー圧のバランスが異なると、タイヤ中心(回転軸)から接地面(地面)までの距離(タイヤ径)が変化し、直進指示を与えているにも関わらず、エアー圧が低いとタイヤ径が小さくなり、その結果、エアー圧が低い方へ曲がっていく挙動を示します。

そのため、実証実験期間中は、日々の車両点検で、外観チェック、カメラ・センサーの動作確認を実施するとともに、タイヤエアー圧の確認を実施し、安全な運行に努めました。

f:id:TierIV:20210504003334p:plain

走行ルート

走行ルートは、道の駅「グランテラス筑西」施設内と周辺の公道になります。今回、(A)施設内テナントの商品を地域住民へ配送する、(B)周辺農家から農産物をピックアップし、施設内テナントへ配送する、という2つのシナリオについて実証実験を実施しました。

(A)のルートは、以下の画像の緑のラインで示す道の駅「グランテラス筑西」施設敷地内のルートと、施設内から公道へ出て、周辺民家を周回するピンクのラインを走行するルートに分かれます。

一方、(B)のルートは、最初に公道を走行して農産物をピックアップし、施設へ戻り、その後、施設内テナントへ農産物を配送するルートです。

それぞれの走行ルートでLogieeが停車する箇所を便宜上「バス停」とし、FMSより次に向かうバス停までのルートを配信して各シナリオに即したルート指示を行いました。

f:id:majestickou:20210419093925p:plain

ODDアセスメント

Operational Design Domain(以下、ODD)とは、自動運転システムが安全に作動するための前提条件です。あらかじめ定められたODDの範囲内でのみ自動運転システムが作動するように設計することで、走行時の安全性を担保します。

Logieeが安全に走行するためには、上記よりODD設定が必要不可欠で、走行環境や運用方法を制限することで、事故などを未然に防ぎます。

ここで、設定した条件が欠けた場合などODD範囲外となった場合、安全な運行停止措置を行うか、手動運転への切り替えを行い、ODD範囲外となった原因を排除し、ODD範囲内での走行とします。

以下は、公道走行におけるODDです。道路条件では、決められたルートのみの走行であることや信号・横断歩道がないため、ODD範囲外となるケースでは、車両(自動車、自転車など)、人の接近がリスクとして挙げられます。

f:id:majestickou:20210419095231p:plain

このように、ODD範囲外となるケースを評価していく手法をODDアセスメントとして、事前に評価を実施しました。

走行ルートとODD道路条件が同一のルート区間(レーンのない道路、歩道、交差点など)をロードセクションと称し、ロードセクションごとにODD範囲外となるケースを割り出し、ODD範囲外となる確率が高いロードセクションに対し、Autowareの機能を維持・制限した状態でAutowareの稼働を継続させるフォールバックや、車両を一時停止させるミニマル・リスク・マヌーバー、手動運転への切り替えを行うなど、運行上の安全を担保する施策を行いました。

以下の図は、公道走行ルートの各ロードセクションにおけるODD範囲外ユースケースと全体に占める割合の評価結果です。(ロードセクションNo.1〜No.11は施設内のため、本稿では割愛致します。)評価結果として、車両接近によるODD外れが大きな割合を占めており、保安要員による監視が安全を担保する上で重要な役割を担うことになります。

そのため、監視・操作者と保安要員とのコミュニケーションプロトコルを定め、監視・操作者からは車両の状況を、保安要員からは接近する人・車情報を伝達することで、ODD範囲外を排除することができました。

f:id:majestickou:20210419095424p:plain

オペレーションイメージ

前述のシナリオ(A)、すなわち商品を地域住民へ配送するオペレーションイメージは以下の図のとおりです。

まずは、地域住民から電話orメールでカスタマーセンターへ注文が入ります(①)。カスタマーセンターのオペレータは、Loogiaへ情報を入力すると(②)、Loogiaは最適なルートを割り出し、画面に表示します(③)。オペレータは注文があった住民へ電話orメールで配達日時を連絡します(④)。また、該当商品を取り扱う店舗に対しては電話orメールにて集荷日時を連絡します(⑤)。

集荷先、配送先への連絡後、カスタマーセンターのオペレータは、Loogiaの画面よりルート配信を実行すると、Loogiaは、ティアフォーが開発している配車管理サービスのFMSへ、データインターフェース(API)を通してスケジュール登録を行います(⑥)。その後、FMSはLogieeへルート配信を行います(⑦)。ルート配信を受けたLogiee(今回、施設内走行はLogieeSS)は店舗前まで自動走行し、店舗スタッフより商品を受け取ります(⑧)。その後、商品を公道走行可能のLogieeS-TCへ載せ替えるため、施設内に設定したパーキングロットへ向かいます。向かった先にはLogieeS-TCが待機しているので、LogieeS-TCの隣に駐車し、そこにいる人が商品をLogieeS-TCへ載せ替えます(⑨)。商品を載せたLogieeS-TCは注文のあった住民宅まで公道を自動走行し、商品をお届けします(⑩)。

f:id:TierIV:20210504002951p:plain

上記は地域住民へ商品を配送するオペレーションイメージですが、周辺農家から農産物を受け取り、施設内テナントへお届けするオペレーションも同様のイメージです。

なお、FMSの詳細につきましては、以下の記事で紹介しています。
https://tech.tier4.jp/entry/2019/04/05/165349

tech.tier4.jp

小型自動搬送ロボットならではの実証ポイント

本実証実験では、2台の仕様が異なる小型自動搬送ロボットで行いましたが、自動運転システムとしてフォーカスすると、自動運転システムのコアアーキテクチャは、公道走行している車両のシステムと同様のAutowareです。このことは、市街地における公道走行が可能なアーキテクチャがLogieeにも採用されていることを指しており、高度な安全性、信頼性をもつ小型自動搬送ロボットとなっています。

一方、運用面のユースケースにフォーカスすると、2台の小型搬送ロボットが同じ場所に到着し、荷物の受け渡しをしやすいようにする必要があったり、公道を走行中に路肩に障害物があれば少し避けたり、遠隔監視走行から近接監視走行へ速やかに切り替え、近接操作者(ロボットの傍で監視を行っているオペレータ)によるマニュアル操作で障害物を回避したい、といった小型自動搬送システムとしての要求が発生します。

これら運用上の要求に対し、Autowareの機能となるパーキング、障害物回避を実証ポイントとして実験を行いましたので、以下にご紹介します。

パーキング

パーキングは、いわゆる駐車することを目的としているほか、LogieeSSが集荷してきた荷物をLogieeS-TCへ積み替えるためのポジショニングを主目的としています。物流業界において、トラックを荷積みのために出荷場所へ駐めるイメージです。

自動走行は地図情報にあるレーン上を走行しますが、パーキングは、レーン上で停止した位置(スタート位置)からパーキングロット(駐車エリア)上の目標位置(ゴール位置)まで移動することができるモード(シナリオ)です。

Autowareではレーン走行(lane driving)、パーキング(parking)の各シナリオを、Planningモジュール内のScenario selectorで、条件判定し切り替えを行います。

Scenario selectorは、レーン上からパーキングロットへ移動しようとした場合にパーキングへ切り替えを行います。

以下の図は、実際に施設内に設定したパーキングロット上まで移動するパス(赤色の線)です。スタートからゴールまでのパスは、Hybrid A*アルゴリズムによるパスプランニングを行うことで生成しています。

f:id:majestickou:20210419100116p:plain

パスプランニングでは、スタート、ゴールの位置、姿勢から横列、縦列の判断、さらに右折、左折、スイッチバック、方向転換などの動作を算出します。

以下の図は、シミュレーターを使用して、さまざまなスタート、ゴールの位置、姿勢に対するパスプランニングを行った結果です。なお、Vehicle model付近にある白い矢印は車両の向き、赤線は算出されたパス、ピンクの矢印は走行方向、青の点がゴール位置で、赤の線がゴール時の車両の向きを示します。

f:id:majestickou:20210419100213p:plain

下の写真は、パーキングロットにパーキングさせたLogieeSSとLogieeS-TCで、スタッフが農産物が入った箱の積み替えを行っているデモ風景です。

f:id:majestickou:20210419100340p:plain

障害物回避

小型自動搬送ロボットLogieeが障害物回避するユースケースとして、ロボットが走行するレーンに侵入している”もの”の回避があります。ここでいう”もの”とは、駐輪場から少しはみ出した自転車の車輪、置き去りにされたスーパーのカートなど、生活空間における無作為にレーンにはみ出しているものを差します。

これらの”もの”がレーン上にある場合、Logieeは障害物として認識し停止し、近接監視者、あるいは遠隔監視者がLogieeSを手動介入して障害物を回避しますが、Logieeがレーンをはみ出すことなく、ほんの少し避けるだけで”もの”を回避しても走行可能領域内にあると判断できる場合、Autowareは回避動作にともなうパスプランニングを行い、その結果、Logieeは障害物を自動回避します。

このことは、複数台の運行を鑑みた場合、ほんの少し避けるだけで自動走行が可能なケースではLogieeは自動で回避し、レーンを逸脱しなければ回避できない場合のみ手動介入して回避することで手動介入率を下げ、効率的な運行が可能となります。

今回、公道でのレーン幅は1.5mとしており、車両幅が0.75mであるため、左右のマージンは0.375m、理論上では30cmほどレーンに侵入している”もの”を回避できることになります。それ以上の侵入がある場合は、障害物停止となります。

また、物体認識にはLiDARの点群からクラスタリングを行う”Euclidean Clustering”を使用していますが、この手法では、物体全体の形状推定は行っていないことから、1つの物体を複数と認識したり、複数の物体を1つの物体と認識してしまいます。

そのため、走行する場のユースケースにあったパラメータチューニングが必要ですが、今回は、障害物回避の有効性について検証を進めました。

以下の動画は、県道に隣接した歩道で行った障害物(しゃがみこんだ人)の回避の様子です。

youtu.be

 実証実験の様子

3/29(月)から現地での実証実験準備を進め、4/2(金)が近接監視走行の警察審査、4/9(金)が遠隔監視走行の警察審査と進めていき、4/12(月)、4/13(火)の2日間がお本番というスケジュールで進めていく中、期間中に多くの方々にお越し頂きました。

以下は実証実験の様子の動画です。 

www.youtube.com

リハーサル、ならびに実証実験本番で、LogieeS-TCは、およそ30回、距離にして30kmの集荷・搬送を、LogieeSSでは、およそ30回、距離にして10kmの配送を実施し、実用化へ向けた課題などを洗い出すことができました。

今後の小型自動搬送ロボットによる実証実験について

冒頭でも触れましたが、昨今の新型コロナウィルス感染症拡大により、宅配サービスが急増し、それにともない、非接触型の配送ニーズが高まっています。

また、政府の成長戦略実行計画(令和2年7月)における低速・小型自動配送ロボットの社会実装に向けて「遠隔監視・操作」型の公道走行実証を実施するとの方針により、宅配ロボット事業へ参入する企業が増加し、実証実験も各地域でさかんに実施されています。

小型自動搬送ロボットにおける配送サービスの実用化には、法整備、インフラ整備など課題は山積みですが、その課題を解決すべく、国が動き出しています。

自動走行では、私たちティアフォー以外にも、大手メーカーが限定的ではあるものの公道での自動運転レベル3、あるいはレベル4の実用化に向け開発を進めていますが、法規制の敷居が高いのが現状です。

一方、小型自動搬送ロボットによる自動走行では、小型、低速(歩行レベル)で、歩道をメインに走行することから、リスクレベルが低く、国内における自動走行の実用化、ビジネスとして収益を得る土壌ができつつあります。

2021年度は、普及へ向けたさらなる拡大が予想されており、私たちティアフォーもパイロット企業となるべく技術改革を進めていきます。

 実証実験を終えて・・・

仕様が異なる2種類の小型自動搬送ロボットを私有地、公道を連携して走行させる今回の実証実験は国内初であることから、非常に多くの方々が訪問、見学に来られました。これは、自動配送ロボットを活用した配送サービスに対する地域住民の方々の期待の表れと感じとることができました。

また、地域住民の方々の声を直接聞くことで、自動配送サービスに対する気づきを得ることができました。

実証実験を通して得られた新たな課題は、社内へフィードバックし、より良いサービスの提供、ならびに小型自動搬送ロボットにおける自動運転レベル4の実用化にむけ、さらなる検証・評価を進めていく所存です。

自動運転データの検索システムを爆速で作った話

はじめに

こんにちは、機械学習の活用を加速させるために学習インフラの開発やワークフロー自動化に取り組むチームに所属している澁井です。今回は自動運転のためのデータ検索基盤を自作した話を書きます。

なお、ティアフォーでは「自動運転の民主化」をともに実現していくエンジニアを募集しています。今回ご紹介する機械学習だけではなく、様々なバックグラウンドをお持ちの方と開発を進めていく必要があります。下記ページから募集職種のリストをご覧いただき、興味を持った方はぜひお気軽にご連絡ください!

さて、ティアフォーでは自動運転に機械学習を活用しています。主な機械学習の用途は画像や動画データを扱った認識技術への応用です。

機械学習では意味づけ(アノテーション)されたデータが大量に必要となります。アノテーションとはネコの画像には「ネコ」、イヌの画像には「イヌ」と画像に意味を付与することです。

自動運転で扱うデータは主に実証実験で各地を走ったデータになり、機械学習の学習データも実証実験で得たデータになります。しかし実証実験のデータはアノテーションされておらず、自動運転を動かしているROS(Robot Operating System)特有のrosbagというデータ形式になっているため、人間が生データを見て理解することはできません。データを分析して学習データを作るためにはrosbagを画像や動画形式に変換し、人間に読めるようにする必要があります。

f:id:cvusk:20210412082703p:plain

自動運転からROS経由でデータを得る

実証実験で収集するデータ量はビッグデータと呼ぶに相応しく、一日に数TBを超える非構造化データが集まります。実証実験の価値を機械学習にフィードバックするためには収録したデータの中から有益なデータを探索し、学習データに加えられるようにする必要がありました。

f:id:cvusk:20210412082956p:plain

自動運転のデータ規模

社内のデータ活用の状況を確認するため、社内コミュニケーションツールで下記のような質問をしてみました。

質問:rosbagのデータを活用してる方々にオープンに質問なのですが、必要なデータはどうやって検索していますか? たとえば緯度経度や地名による検索とか、年月日、時間帯とか、どういう条件で検索できると便利でしょうか?

 

回答:ほしい!

f:id:cvusk:20210412083253p:plain

社内取引はネコ画像

その結果、みんなデータを探せなくて困っているものの、データを整備する工数が取れない、ということがわかりました。課題は見つけた人が解決する精神で、私が自分で検索システムを作ることにしました。

課題

まず、ティアフォー社内のデータ活用には3つの課題がありました。

  1. データを探せない:実証実験で得たデータは社内に大量に貯まっているが、開発者が目的のデータを簡単に見つけられない。
  2. 保管先がまばら:データは社内ストレージにアップロードされている一方、「どこ」に「いつ」の「どの」データが保管されているのか、統一して整理されていない。
  3. クラウドを使わない:データがクラウドに貯まっているのにローカルの開発端末にダウンロードして使おうとする。

他にも細かい課題は多々ありますが、データ活用を加速して機械学習開発を効率化するためにはデータが探しづらい状態です。ほしいデータを得るためには社内ドキュメントに書かれた実験記録(自動運転で走った場所、日時、天気など)を元に、社内ストレージからrosbagファイルを探してダウンロードし、開発者の端末でrosbagを解凍して必要なデータを探さなければいけませんでした。rosbagは1ファイルで1GB以上のサイズの中に、自動運転中の5、6分程度を記録しています。機械学習に必要なバラエティのあるデータを得るためには5、6分程度では足りません。漏れのないデータセットを作るためには、年間通して場所や明るさ、天気、被写体の位置、大きさ、カメラの方向、自動運転の速度などを組み合わせた多様なデータパターンを用意する必要があります。rosbagファイルをいちいちダウンロードして確認するのはあまりにも非効率です。

そこで、rosbagで収集したデータを検索できるシステムをクラウド上に作ることにしました。検索システムのゴールは社内に散らばったデータを同じインターフェイスで検索し、すぐ利用できるようにすることです。

検索システムをどのように作るか

検索システム開発で立てた目標の一つは、最速で作ってすぐ使える状態にすることです。データは貯まれば貯まるほど整理し使えるようにすることが難しくなります。データベースに登録するだけでも長時間かかりますし、バラエティが増えれば属性の整理やテーブル設計が困難になります。日々数TBの非構造化データが貯まる状況で放っておくことは良策ではありません。もちろんこれまでティアフォーでは検索システムがなくても開発できていたので、自動運転に検索システムは必要ないのかもしれません。しかし、ツールを導入することで仕事が楽になるかどうかは導入してみないとわかりません。検索の有用性(または無用性)を証明するため、スピーディに作ってPoCを進めることも目標としました。

スピード優先で開発するため、検索システムのソフトウェアスタックには下記のすぐ簡単に使えるものを選びました。 

全体像は以下のようになります。

f:id:cvusk:20210412083517p:plain

検索システム(α版)

ソフトウェアスタックと全体像からわかるとおり、主な開発言語はPythonです。検索のレスポンス速度を上げるならばJavaGolangを使ったほうが性能が改善されますが、短い期間で作り切ることを優先してPythonを選びました。ディープラーニングでデータに意味づけするためにはPythonがより扱いやすいという理由もあります。

インフラは以前構築したAmazon EKSのKubernetesクラスターを使っています。個人的にKubernetesが最も楽に使えるインフラになっているからです。データベースは私の好みでAurora PostgreSQLを使っています。

バックエンドAPIはFastAPIとSQL Alchemyで作っています。SQL (Relational) Databases - FastAPIで書かれているデータインターフェイス設計をそのまま参考にしています。Python側のデータスキーマはPydanticで定義することで、関数間のデータ受け渡しで型がわからなくなって実装に迷うことを避けました。型が定まっているとコーディングの手戻りが減ります。

バックエンドAPIPython+FastAPI+SQL Alchemyで手早く済ませたコンポーネントです。機能とデータが増えてパフォーマンス劣化してきたら、他の言語かgRPCで作り変えてORMも排除すると思います。

画面はStreamlitというPythonをベースにWeb画面を作ってデータを可視化するライブラリを使います。通常はHTML + JavaScriptで作る部分ですが、JavaScriptを書きたくないという個人的な理由でStreamlitを選びました。次はFlutterで作りたいと考えています。

以下の公式の動画のように、コンポーネントPythonコードで書くことで画面表示を定義できてとても便利です。

youtu.be

StreamlitであればPythonのグラフ作成ライブラリのMatplotlibやSeabornと組み合わせてデータのグラフを簡単に画面に表示できるため、良い選択だったと思います。 

データパイプラインとデータの意味づけではrosbagから画像を抽出し、データベースとストレージに登録します。抽出するデータは主に一般道を走る自動運転車のカメラで撮影する画像になります。

意味づけのために物体検知を使い、映っている被写体を判定しています。自動運転の機械学習では、認識のためにカメラに映っている歩行者や対向車、バイク、信号機等を検知します。学習済みの物体検知(EfficientDet)で簡易的に被写体を検知し、検索時に被写体の数で絞り込みできるようにしています。データの意味づけには物体検知以外にも、画像の明るさや逆光、緯度経度と住所、日時と場所をベースにした天気、気温による検索を可能にしています。

データパイプラインはKubernetes Jobで定期的にデータを収集、解凍し、意味づけしてデータベースに登録します。

意味づけのおかげで、たとえば以下のように「信号機」が映っている逆光画像を検索できるようにしています。

f:id:cvusk:20210412083656p:plain

うおっまぶしっ

別の例として、天気は「雪」で「自転車」が映っている画像です。

f:id:cvusk:20210412083737p:plain

雪の日の自転車

どのくらいの期間で作ったか

上記の構成と機能で検索システムを作りました。

ところどころ再開発するつもりで、さっさと使えるようにすることを優先して開発しています。以下に各コンポーネントの開発所要時間をまとめます。

  • Kubernetesは構築済みのクラスターにノードグループを追加し、各コンポーネントを動かすマニフェストを書きました。所要時間は1時間以内です。
  • バックエンドAPIとテーブル設計は最低限の機能と正規化にとどめ、2週間程度で開発しています。
  • 画面はStreamlitのおかげで3日くらいで作れました。マークダウンやテーブル、チェックボックス等Web画面に必要なコンポーネントPythonのコード数行で書くことができるため、とても楽に作れました。
  • データパイプラインはrosbagを解凍しデータベースとストレージに登録するコードをシングルプロセスで書いています。今後収集するデータ量が増えたら並列処理を検討します。データの意味づけは学習済みの物体検知モデルや簡易的な明るさ評価を活用しています。データの意味づけは開発者の要望を聞きながらオンデマンドで追加していったため所要時間はまちまちですが、1機能1週間程度です。

作ったものを適宜リリースしていく方式で、最初はバックエンドAPIと画面だけを用意し、オリジナルのrosbagデータを取得した日時や場所だけで検索できる状態で社内公開しました。ここまで大体3週間で第1弾をリリースしています。

そこから毎週1機能追加を目標としました。1週間ごとに物体検知、天気や気温による検索、画像の明るさや逆光検索を追加していきました。

他の作業をこなしながら検索システムを作っていたのですが、1ヶ月強で作ったわりには便利なものが作れたと思います。

f:id:cvusk:20210412083828p:plain

大体3週間ちょっとで作る

機能追加時は最初にモック画面と動画を作り、機能のイメージを利用者に共有してから実物を作る流れを取りました。検索の仕様を言葉で要件定義する作業を減らし、見えて使えるものを作ることにこだわっています("Working software over comprehensive documentation"または"Done is better than perfect")。これもスピード優先で作るための工夫です。

もっと検索できるようにしたいデータがあった

ここまで2021年3月中に開発とリリースを進めてきました。社内でデータ検索システムを作っていることを宣伝したおかげで、当初は存在を知らなかったデータや、課題が不明確だったデータ活用のシーンが判明しました。

その一例がアノテーションされたデータの検索です。機械学習で使うデータは外注してアノテーションしているのですが、アノテーションされたデータも画像とJSON形式でストレージに貯まったままで、データベース管理や検索可能化はされていません。アノテーションされたデータが貯まれば貯まるほど、学習条件に合うデータを探すのに人手と時間を要するようになります。そこで、アノテーションされたデータを元データの意味とアノテーションを組み合わせて検索する機能を開発しました。

信号機のアノテーションされた画像(以下は「黄色信号」の含まれる画像)を検索できるようにしています。

f:id:cvusk:20210412083926p:plain

小さくて見えないけど黄信号が写っています

この過程でアノテーションされたデータを整理し数量をまとめることになりました。そこで判明したことは、アノテーションは特定のカテゴリに偏っており、本来考慮すべきだが、アノテーションが少ないデータカテゴリが存在することです。日々扱っているデータでも、整理、集計しないと実態を知ることはできないということです。

今回は画像データをターゲットに検索データを作りましたが、その他にもポイントクラウドのデータ等、自動運転には欠かせないデータが残っています。また、社内ストレージから発掘された未知のデータを検索できるようにしたいという要望が出てきています。

個人的には「類似した状況」を条件に検索できるようにしたいと思っています。自動運転では運転中の周囲の状況が運転の判断を左右することがあります。左を並走している自動車が車線変更して先方に入ってきたり、先行している自動車が右折したり、道路幅が狭くなっていたり、周囲に建物があったり、林の中を走っていたり、自転車が並走していたり・・・。多種多様な状況を認識して自動運転するため、こうした「状況」を検索できるようにすることで、状況に応じた運転ロジックの開発を効率化することができると思います。画像や動画を入力にして似ている状況を検索する類似状況検索のようなシステムを作りたいです。

まとめ

データは貯めるだけでもシステム開発とコストが必要となりますが、貯めるだけでなく使える状態にするためにはデータの意味づけと検索が必須になります。データは容量が増えれば増えるほど整理し管理する難しさが増します。加えてデータを使えていない状態では、データを使えない不便さに気づけない事態が頻繁に発生します。データ検索のあり方はデータの使い方や目的次第で千差万別です。今回の開発では素早く作って直しながら、本当に必要なものを目指していく方針がうまくハマりました。

最後に1つだけご紹介させてください。

4月21日にティアフォー初の【Tier IV SUMMIT 2021】をオンラインで開催します!

参加は無料で自動運転の最前線を語ります!ぜひご登録ください!

tier4summit.com

自動運転の実証実験を「安全」に進めるためのリスクアセスメントの活用について

こんにちは、ティアフォーで安全に関して担当している新宅と申します。今回は、全国で進めている実証実験を「安全」に進めるためのリスクアセスメントの活用についてご紹介します。実証実験に限らず、安全を担保することは自動運転車両を開発する上で必要不可欠であり、社会受容性を高めていくための最も重要な要素の1つとなります。

なお、ティアフォーでは「自動運転の民主化」をともに実現していくエンジニアを募集しています。今回ご紹介する安全だけではなく、様々なバックグラウンドをお持ちの方と開発を進めていく必要があります。下記ページから募集職種のリストをご覧いただき、興味を持った方はぜひお気軽にご連絡ください!

安全に関わる最近のデータや動き

リスクアセスメントについてお話する前に、安全に関わる最近のデータや動きについてご紹介します。

年間の交通事故死者数

2021年1月4日、警察庁が2020年の交通事故死者数は前年よりも376人少ない2,839人だったことを発表しました。この数字は、4年連続で戦後最小を更新し、かつ初めて3,000人を下回ったとのことです。

f:id:yst4:20210322103308p:plain

出典:警察庁ウェブサイト

この数字を見て、本記事を読んでいただいている皆さまは多いと思うでしょうか?それとも戦後最小を更新し続けているのだから少ないと思うでしょうか?おそらく皆さまそれぞれの感覚があるかと思います。しかし、1つはっきりしていることは、交通事故の数が限りなくゼロに近づけば同時に交通事故死者数も減っていきます。自動運転が普及することの意義の1つには、交通事故の数が限りなくゼロに近づいていくことにあります。一方で、仮に全て自動運転車になれば事故の数はゼロになるのでしょうか?不慮の事態を考慮すると、残念ながら自動運転が実現しても事故の数がゼロになるとは言えません。それでも、事故の数を限りなくゼロにすることを目指すべく、自動運転車の開発を進めています。これをエンジニアリング観点で言えば、許容可能なリスクの発生確率や損害の程度を定量的に定め、総合的に許容可能な範囲を決めながら安全な設計を行っています。

自動走行の実現に向けた国の直近の動き

 3月はじめに、「自動走行ビジネス検討会」から「自動走行の実現及び普及に向けた
取組報告と方針」Version5.0の概要案が示されたのでこちらも簡単にご紹介します。

f:id:yst4:20210322162229p:plain

出典:経済産業省・自動走行ビジネス検討会ウェブサイト

特に(1)では、本記事の主題である安全に関する記載があります。ここでは、米国NHTSA(運輸省道路交通安全局)の項目を参照しながら日本版セーフティレポート(仮称)と称して情報発信することの重要性を示し、さらに「走行環境・運行条件で想定されるリスクを網羅的に評価し、その安全対策をあらかじめ十分に行う、セーフティアセスメント(仮称)がきわめて重要」*1と判断しており、今年度を目途にセーフティアセスメント(仮称)に係るガイドラインが作成される予定となっています。また本概要案では、2025年度までに40か所以上で自動運転レベル4の無人自動運転サービスを実現する旨の記載もあり、今後5年以内に自動運転レベル4の普及が進んでいくことが考えられます。

米国NHTSAの項目について興味のある方は、https://www.nhtsa.gov/document/automated-driving-systems-20-voluntary-guidanceをご参照ください。また、エンジニアリング観点での「安全」については、安全への取り組み:②自動運転の安心・安全について - Tier IV Tech Blogでご紹介しているので是非ご覧ください。

ティアフォーの実証実験の安全をリスクアセスメントで担保

さて、昨年の交通事故死者数から自動運転車開発の意義の1つを、そして国でも安全に自動運転車を普及・実現させていくために様々な動きがあることを見てきました。さらに「自動走行ビジネス検討会」では、セーフティアセスメント(仮称)に係るガイドライン作成が予定されている旨お話しましたが、ここからは全国で進めている実証実験を「安全」に進めるためにティアフォーが既に活用している「リスクアセスメント」についてご紹介します。現在ティアフォーでは、異なる観点から「ODDアセスメント」と「走行ルートサーベイ」という2種類の「リスクアセスメント」を行っています。

※ODD:「Operational Design Domain」の略で、「運行設計領域」と呼ばれる自動運転システムが作動する前提となる走行環境条件のことです。

ODDアセスメントとは?

まず、なぜODDアセスメントが必要なのでしょうか?ティアフォーでは下記のような理由からODDアセスメントを実施しています。

  • 走行ルートを決める際、車両を走行させることなく自動走行の可否を事前に把握するため
  • 走行限界を超えている箇所について、事前の対策を行うことが出来るため
  • アセスメントの結果をドライバーやオペレータに周知することで、より安心・安全な走行を実現するため
  • アセスメントの結果を活用し、運用面でのリスクを可視化するため

実施にあたっては地図・走行経路、ODDユースケース、Pilot.Auto性能仕様、シミュレータ実施結果を使用します。それでは、ここからODDアセスメントの実施方法をご説明します。

ODDアセスメントの実施方法
  1. コースの細分化
    下図のように、コースをODDカテゴリに分割してロードセクション番号を付加し、ロードセクション単位で評価を実施していきます。

    f:id:yst4:20210323160102p:plain

  2. 各ロードセクションごとにユースケース定義を割当
    次に、各ロードセクションにおけるユースケース分析を行います。例えば、下図のように大枠として発車、同一車線内走行、右折、左折などとし、そこから同一車線内走行-通常走行(対向車線なし)や、左折-T字路交差点(信号なし)などのユースケースに当てはめていきます。

    f:id:yst4:20210324104932p:plain

  3. シナリオによる検証確認
    ロードセクションごとにユースケース定義を割り当てたら、ロードセクションのユースケースにおけるシナリオのシミュレーション・実車での検証結果の確認を行います。
  4. 各ロードセクションの評価
    そして各ロードセクションの評価をしていきます。下図のように、これまで行ってきたシナリオ総数とそのシナリオを検証した結果のNG数の割合である「性能限界率」を算出します。さらにそれだけでなく、「ODD範囲(=人的介入が必要なのか、もしくは誘導員を配置するなど運用面の対策やそもそもソフトウェアの調整が必要なのかといったもの)」、「限界要因(=性能限界に達している要因が自車両によるものなのか、もしくはカットインしてきた車両や工事中の場所を走行する場合など、外部のものなのかといった要因をより細かく見ていくもの)」をそれぞれ4段階に分けた点数付けを行い、合計点数を算出します。

    f:id:yst4:20210323162643p:plain
    合計点数を算出したら、下表にしたがってリスク評価を行います。点数が高ければよりリスクが高いことを示しており、運行計画の変更を検討していきます。

    f:id:yst4:20210323172456p:plain

  5. 評価結果からリスク軽減策の検討・実施

    最後に、4.で出てきた結果から安全余裕を確保するよう自動運転計画を修正し、リスクの軽減を図ります。リスク軽減策には、例えば車速の低減やより車間距離を取るなど、性能限界内での運用可能な手段を講じる場合もあれば、オーバーライド(=自動運転から手動運転に切り替えること)により、ルートの一部は必ず手動運転とすることで安全を担保するといった対策があります。下図がその一例となります。

    f:id:yst4:20210324104424p:plain

このような一連の流れを経て、ODDアセスメント行っています。リスク軽減策を実施した場合には、改めて評価を行うことでより安全に実証実験が進められるようにしています。

走行ルートサーベイとは?

次に、走行ルートサーベイについてご紹介します。既にご紹介したODDアセスメントと似たようなものではありますが、アプローチの仕方でいくつか異なる点が存在します。異なる2点を中心に走行ルートサーベイについてお話します。

走行環境条件の設定のパターン化参照モデルの活用

これは、「自動走行に係る官民協議会」で日本経済再生総合事務局が策定したもので、「無人自動運転移動サービスの導入を検討している企業・団体等向けに、導入の検討段階において参考となる導入地域の環境や条件についてパターンを整理した」*2ものになっています。無人自動運転移動サービスの実施に向けて「共通言語」として使用することで、より導入の検討が進むことを意図しています。

f:id:yst4:20210322172341p:plain

出典:https://www.kantei.go.jp/jp/singi/keizaisaisei/jidousoukou/index.html

このモデルを参照し、順番に実証実験実施予定地域の走行ルートサーベイを行います。例えば、1番目の時間については、実施予定地域・場所の日の出・日の入り時刻を調べることで、実証実験を安全に行うための開始・終了時間設定の参考にします。また8番目の交通量については、自治体から情報提供いただき、その道路の交通量を可視化(例:〇〇台/24時間など)することで、安全に実証実験を進めていくルートを策定する参考にします。自動運転の技術力を上げていくため、時にはチャレンジングなルートを策定することもありますが、先ほどご紹介したODDアセスメントと合わせて確認していくことで、チャレンジングでありながらも、安全を最優先して実証実験を行っています。

保険会社の事故データの活用

さらに、保険会社の事故データを活用して「事故多発地点」と「うっかり運転地点」を本サーベイの中に含めています。「過去5年間で3回以上事故が起こった地点」を「事故多発地点」、「直近半年間で一時不停止、踏切不停止、速度超過、一方通行違反が起こった地点」を「うっかり運転地点」と定義して「リスクの高い地点」を割り出しています。ご参考までに、「うっかり運転地点」の例を下図に示しています。一時不停止や一方通行違反があることが見て取れます。

f:id:yst4:20210324103510p:plain

実際に起こった事故だけでなく、「うっかり運転地点」まで加えている理由ですが、「ハインリッヒの法則」では「1つの重大事故の背後には29の軽微な事故があり、その背景には300の異常(ヒヤリ・ハット)が存在する」*3と言われており、ヒヤリハットをきちんと分析し、対策を立てることが安全を担保するのに重要であると言われています。これを今回の「うっかり運転地点」に置き換えると、「うっかり運転地点」が発生している場所は「重大事故が起こる可能性がある」ことを示していると言えるので、これらの情報も本サーベイに活用しています。なお、事故データの活用にあたり、ティアフォーがともに「自動運転の民主化」を実現するために連携している損害保険ジャパン株式会社様から提供いただいています。このように、ティアフォーだけでは提供出来ない情報を含めてご案内することで、より安全に対する優先度が高いことをおわかりいただけるのではないでしょうか。

まとめ

今回は、「安全」というキーワードをもとに直近のデータや国の動きをお話し、安全を実現するための「リスクアセスメント」についてご紹介しました。ティアフォーでは、安全を担保しながら自動運転の社会受容性を高めていけるよう引き続き開発を進めていきます。

Autowareにおける狭路走行のための走行経路計画

こんにちは。ティアフォーで自動運転システムを開発している渡邉です。
今回は、Autowareで使われている車両の走行経路の計画について簡単にご紹介したいと思います。

なお、ティアフォーでは「自動運転の民主化」をともに実現していくエンジニアを募集しております。今回ご紹介するような計画・制御に関わる分野だけでなく、様々なバックグラウンドをお持ちの方と開発を進めていく必要があります。下記ページから募集職種のリストをご覧いただき、興味を持った方はぜひお気軽にご連絡ください!

tier4.jp

走行経路計画とは

走行経路計画とは、読んで字のごとく、車両が走行してほしい経路を計画することです。走行経路を計画するときには、道路の形状や道路上の障害物といったものを考慮しながら、車両が実際に走行できるように目標経路を計画する必要があります。走行経路の計画で必要な要件としては、次のようなものが考えられます。

  • 走行可能なエリアからはみ出さないこと
  • 障害物に衝突しないこと
  • 必要以上の蛇行といった不自然な挙動をしないこと

人間が運転している場合、無意識のうちに走行したい経路を考えながらステアを切るといった操作をすると思います。しかし、自動運転では走行する経路を明示的に算出する必要があり、どのような曲線を描けば車両は安全に走行できるのか、を考える必要があります。また、車両が通れるかどうかの狭い道を通るようなシーンでは、車両の挙動を考えながら通過できる経路を考える必要があります。このようなシーンは人間でも難しい場合があると思います。

今回は、狭い道を通るシーンを例に取り上げながら、Autowareの走行経路の計画方法についてご紹介したいと思います。

狭路走行の難しさ

狭い道を走行するシーンでは、単純に道路の中央を走行するような経路を計画すれば良いわけではありません。なぜならば、車両の大きさによってはうまく曲がりきれずに走行可能なエリアをはみ出してしまうからです。狭い道を走行するために考慮しなければならないことは、大きく分けて

  • 道路の道幅、走行可能なエリア
  • 車両の形状
  • 車両の運動

の3つになります。道路や車両の形状を考慮する必要があることは明らかだと思いますが、走行経路を決める上では車両の運動の特性も考える必要があります。例えば一般的な4輪の自動車の場合、その場で旋回して姿勢を変えるといった運動はできません。自動車の向きを変えたいときにはステアを切って前後に走行することで徐々に自動車の向きを変える必要があります。このように、一般に自動車は空間を自由に動くことはできず、自動車が動くことが可能な範囲は限定されています。そのため、自動車の運動の制限を考慮しながら走行経路の計画を行う必要があります。

車両運動を考慮した走行経路計画

車両運動を考慮した走行計画を考えるためには、車両の運動がどのように記述されるかを事前に求めておく必要があります。Autowareでは、ある速度で走行しながらステアを切ったときに、そのステア角に対する車両の位置・姿勢の変化量を数式ベースで取り扱っています。このように、ある入力に対する車両挙動の変化を表す数式を車両運動の数理モデルと呼びます。車両運動の数理モデルを用いると、与えられたステア角に対して車両が走行する経路をシミュレートすることができるようになります。これにより、車両が走行可能な範囲を考慮することができるようになります。

走行経路を計画するとき、多くの場合通過可能なパターンは多数存在します。走行経路をひとつ決めるためには、何かの評価基準を与えて一番良いものを選ぶということを考えます。今回は、必要以上の蛇行や不自然な挙動を抑えたいため、ステアの角度や角速度、角加速度といったものをできる限り小さくするような走行経路を選択すると良さそうです。

ここまでをまとめると、走行経路を計画するための目標と条件は次のようになります。 

目標:

  1. ステアを切る角度・角速度・角加速度をできる限り小さくする
  2. 道路の中央からできる限り離れないようにする

条件:

  1. 車両は数理モデルで記述された運動の法則に従って動く
  2. 車両は走行可能なエリアからはみ出さない 

これらの目標や条件が数式として定式化できれば、定量的に走行経路の計画を行うことができるようになります。このように、目標や条件を数式として定式化して何かを計画する問題を数理最適化問題と呼びます。数理最適化問題は工学の分野だけでなく金融・経済など広い分野で登場するもので、その解き方は広く研究・開発されています。数理最適化問題の形で定式化することができれば、適切なソルバを用いることで条件を満たしつつできるだけ目標に近い解を得ることができます。上述した目標1にあるステア角度・角速度・角加速度や目標2にある道路中央からの距離はその数値そのものを扱えば良く、条件1の車両運動については数理モデルとして定式化されています。したがって、走行経路計画を数理最適化問題として扱うためには、条件2の車両が走行可能なエリアからはみ出さないことを数式的に表現する必要があります。

車両形状と走行可能領域

車両が走行可能エリア内にいるかどうかの判定は様々な表現方法がありますが、表現の仕方によっては数理最適化問題の形式が難しくなってしまう場合があります。 そのため、Autowareではできる限り解きやすい形式で走行可能領域に関する条件を与えられるように工夫しています。

Autowareでは、車両の中心線(図1の破線)と道路の中心線(図1の赤線)との距離を計算し、その距離と車両幅の半分の和が道路中心線から道路の端までの距離より小さいときに車両が走行可能エリア内にいると判定します。この判定を車両の前端・中央・後端に対して行うことで、車両全体が走行可能領域の中にいるかどうかを判定しています。

この判定方法を用いることで、走行経路の計画問題を二次計画問題と呼ばれるクラスの数理最適化問題へ帰着することができます。二次計画問題は数理最適化のなかでも頻出の形式で、オープンソースのソルバもあります。Autowareでは二次計画問題を解くためにOSQP*1というソルバを利用しています。

f:id:fwatanabe-t4:20210323154240p:plain

図1:走行可能領域の表現方法

Autowareでの適用例

では、実際に狭い道を走行している例をご紹介します。ここでは、S字カーブを走行するシーンを想定して走行経路を計画してみましょう。計画した結果を図2に示します。図中の赤線が道路中心線、白線が実際に計画された(後方車輪軸中心が通る)走行経路、黄色の四角い枠が白線に沿って走行したときの車両の外形(footprint)になります。まず、カーブ入口で中心に沿って走行すると走行可能エリアを逸脱してしまうため、カーブ内側を走行するような経路が引かれていることがわかります。また、S字カーブ内では車両が走行可能エリアを逸脱しないように計画されているだけでなく、中心線よりやや内側を走行して走行経路の曲率をできるだけ小さくしており、人間が見ても自然な経路が計画されていると思います。この結果から、走行可能エリアの逸脱を避けつつ、必要以上に大きくステアを動かさないような走行経路の計画が達成できていることがわかります。

f:id:fwatanabe-t4:20210326131049p:plain

図2:S字カーブの走行経路計画結果

まとめ

今回は、狭路走行を例に取り上げて走行経路の計画方法についてご紹介しました。Autowareでは、このアルゴリズムの導入により走行できるようになったシーンが増えました。しかし、経路計画にはまだ様々な課題が残っており、引き続き有効な手法の研究および開発が必要だと考えております。経路計画に限らず自動運転には難しい課題が多数ありますが、問題解決したときの喜びは大きいです。自動運転技術の発展に興味のある方は、ぜひ本記事冒頭のリンクからコンタクトしていただければと思います!

The Challenges of Making Decisions in Autonomous Driving

Autonomously controlling a car is challenging and requires solving a number of subproblems. If perception, which understands information from sensors, corresponds to the eyes or our system while control, which turns the wheel and adjusts the velocity, corresponds to the body having a physical impact on the car, then decision making is the brain. It must connect what is perceived with how the car is controlled.

In this blog post, we discuss the challenges in designing the brain of an autonomous car that can drive safely in a variety of situations. First, we introduce the scope and motivation for decision making before presenting how it is currently implemented in Autoware. We then talk about the trends observed in recent autonomous driving conferences and briefly introduce a few works that propose interesting new directions of research.

f:id:TierIV:20210322212536p:plain

Figure 1 - Typical sense-plan-act paradigm for autonomous agents

By the way, at Tier Ⅳ, we are looking for various engineers and researchers to ensure the safety and security of autonomous driving and to realise sharing technology for safe intelligent vehicles. Anyone who is interested in joining us, please contact us from the web page below. 

tier4.jp

Introduction to Decision Making

We spend our life making decisions, carefully weighing the pros and cons of multiple options before choosing the one we deem best. Some decisions are easy to make, while others can involve more parameters than can be considered by a single human. Many works in artificial intelligence are concerned with such difficult problems. From deciding the best path in a graph, like the famous Dijkstra or A* algorithms, to finding the best sequence of actions for an autonomous robot.

For autonomous vehicles, decision making usually deals with high level decisions and can also be called behavior planning, high-level planning, or tactical decision making. These high level decisions will then be used by a motion planner to create the trajectory to be executed by the controller. Other approaches consider planning as a whole, directly outputting the trajectory to execute. Finally, end-to-end approaches attempt to perform all functions in a single module by using machine learning techniques trained directly on sensor inputs. While planning is one of the functions handled by end-to-end techniques, we will not discuss them in this blog post as they tend to make decision making indistinguishable from perception and control.

The common challenge unique to decision making systems comes from the open-endedness of the problem, even for humans. For perception, a human can easily identify the different objects in an image. For control, a human can follow a trajectory without too many issues. But for decision making, two drivers might make very different decisions in the same situation and it is almost never clear what is the best decision at any given time. The goals of an autonomous car at least seem clear: reach the destination, avoid collisions, respect the regulations, and offer a comfortable ride. The challenge then comes from finding decisions that best comply with these goals. The famous “freezing robot problem” illustrates this well: once a situation becomes too complex, not doing anything becomes the only safe decision to make and the robot “freezes”. Similarly, the best way for a car to avoid collisions is not to drive. A decision system must thus often deal with conflicting goals. Challenges also arise from uncertainties in the perception and in the other agents. Sensors are not perfect and perception systems can make mistakes, which needs to be carefully taken into account as making decisions based on wrong information can have catastrophic consequences. Moreover, cars or pedestrians around the autonomous vehicle can act in unpredictable ways, adding to the uncertainty. Dedicated prediction modules are sometimes used and focus on generating predictions for other agents. The final challenge we want to mention here comes from dealing with occluded space. It is common while driving not to be able to perfectly perceive the space around the car, especially in urban areas. We might be navigating small streets with sharp corners or obstacles might be blocking the view (parked trucks for example), potentially hiding an incoming vehicle.

f:id:TierIV:20210322212939p:plain

Figure 2 - Standard autonomous driving architecture

Schwarting, Wilko, Javier Alonso-Mora, and Daniela Rus. "Planning and decision-making for autonomous vehicles." Annual Review of Control, Robotics, and Autonomous Systems (2018)

To summarize, we are concerned with the problem of making decisions on the actions of the car based on perceptions from sensors and the main challenging points are:

  • conflicting goals that require trade-offs;
  • uncertainties from perception, localization, and from the other agents;
  • occluded parts of the environment.

In the rest of this post we will try to introduce methods to make decisions and to tackle the aforementioned challenges.

Decision Making in Autoware

f:id:TierIV:20210322213104p:plain

Figure 3 - Autoware architecture

Autoware is an open source project providing a full stack software platform for autonomous driving including modules for perception, control and decision making. In the spirit of open source, its architecture is made to have each function be an independent module, making it easy to add, remove, or modify functionalities based on everyone’s own needs.

In this architecture, decision making occurs at two stages. At the Planning stage, various planning algorithms such as A* or the Model Predictive Control are used to plan and modify trajectories. Before that, at the Decision stage, the output of perception modules is used to select which planning algorithms to use for the current situation. For example, it can be decided that the car should perform a parking maneuver, in which case a specific parking module will be used (Motion Planning Under Various Constraints - Autonomous Parking Case - Tier IV Tech Blog). This Decision stage is implemented using a Finite State Machine (FSM), a common model used in rule-based systems. A state machine is basically a graph representing possible states of the system as nodes and the conditions to transition between these states as edges. State machines are easily designed by humans and offer decisions that are easy to understand and explain, which is very desirable in autonomous driving systems.

While the decision and planning modules of Autoware offer state-of-the-art driving in nominal cases, they are not well suited to deal with uncertainties or occluded space. There are no classical approaches to deal with these challenges but they are studied by a lot of ongoing research, which we will discuss in the next part.

Current Trends

We now introduce some of the most popular approaches for decision making seen in recent autonomous driving conferences (the IEEE Intelligent Vehicles Symposium and the International Conference on Intelligent Transportation Systems).

Deep Reinforcement Learning (DRL) is an application of deep neural networks to the Reinforcement Learning framework where the goal is to learn what action works best at each state of the system, corresponding to a policy Π(s) = a representing the decision a to take at state s. This usually requires learning a function Q(s,a) which estimates the reward we can obtain when performing action a at state s. In simple environments, this function can be computed by completely exploring the search space but when the state and action spaces become too large, like in autonomous driving problems, more advanced techniques must be used. DRL leverages the power of deep neural networks to approximate the function Q(s,a), allowing the use of RL in very complex situations. This requires training on a large number of example situations, which are usually obtained using a simulator. The biggest issue with using these techniques on real vehicles is the difficulty to guarantee the safety of the resulting policy Π(s). With large state spaces, it is difficult to ensure that there does not exist a state where the policy will take an unsafe action.

Mixed-Integer Programming (MIP) is an optimization technique which maximizes a linear function of variables that are under some constraints. Some of these variables must be restricted to integer values (e.g., 0 or 1) and can be used to represent decisions (e.g., whether a lane change is performed or not). The problem of an autonomous vehicle following a route can be represented with MIP by including considerations like collisions and rules of the road as constraints. Using commonly available solvers, the problem can then be solved for an optimal solution, corresponding to the best values to assign to the variables while satisfying the constraints. Many approaches applying MIP to autonomous driving have been proposed and while they can solve many complex situations, they cannot handle uncertain or partial information and require accurate models of the agents and of the environment, making them difficult to apply to real-life situations.

Monte-Carlo Tree Search (MCTS) is an algorithm from game-theory which is used to model multiplayer games. It is most famous for being used in AlphaGo, the first program able to defeat a human professional at the game of Go. The MCTS algorithm assumes a turn-based game where agents act in succession and builds a tree where each node is a state and where a child is the expected result from an action. If complete, the tree represents the whole space of possible future states of the game. Because building a complete tree is impossible for most real problems, algorithms use trial-and-error, similar to reinforcement learning, to perform sequences of actions before simulating the resulting outcome. This approach has the advantage of considering the actions of other agents in relation to our own decisions, making it useful in collaborative scenarios where the autonomous vehicle must negotiate with other vehicles (e.g., in highway merges). The main issue with MCTS is their computational complexity. As the tree must be sufficiently explored in order to confidently choose actions, it can be hard to use in real-time situations.

In the next section, we will present some recent works related to each of these trends.

Interesting Works

Graph Neural Networks and Reinforcement Learning for Behavior Generation in Semantic Environments

Patrick Hart(1) and Alois Knoll(2)

1- fortiss GmbH, An-Institut Technische Universität München, Munich, Germany.

2- Chair of Robotics, Artificial Intelligence and Real-time Systems, Technische Universität München, Munich, Germany.

IEEE Intelligent Vehicles Symposium (2020) https://arxiv.org/abs/2006.12576 

f:id:TierIV:20210322213643p:plain

Figure 4 - Vehicles of a scene represented as a graph

An issue with reinforcement learning is that their input is usually a vector of fixed size. This causes issues when tackling situations with varying numbers of other agents. This paper proposes to use Graphic Neural Networks (GNNs) to learn the policy of a reinforcement learning problem. GNNs are a neural network architecture that uses graphs as inputs instead of vectors, offering a solution that is more flexible and more general than previous works.

The graph used in this paper represents vehicles with the nodes containing state information (coordinates and velocities) and the edges containing the distance between two vehicles. Experiments on a highway lane change scenario are used to compare the use of GNNs against the use of traditional neural networks. It shows that while results are similar in situations close to the ones used at training time, the use of GNNs generalizes much better to variations in the input without a significant loss of performance.

Autonomous Vehicle Decision-Making and Monitoring based on Signal Temporal Logic and Mixed-Integer Programming

Yunus Emre Sahin, Rien Quirynen, and Stefano Di Cairano

MITSUBISHI ELECTRIC RESEARCH LABORATORIES

American Control Conference (2020) https://www.merl.com/publications/TR2020-095

f:id:TierIV:20210322213823p:plain

Figure 5 - (a) modules targeted by this work  (b) illustration of the MIP solution space

This work uses Mixed-Integer Programming to represent the problem of finding intermediate waypoints along a given route. The interesting parts of this work are its use of Signal Temporal Logic (STL) to represent some of the constraints, and a monitoring system that can identify if the environment changes in ways that deviate from the models used.

Temporal Logic is a language used to write rules which include some time information. In this work for example, intersections are regulated by a first-in-first-out rule, which in STL is written as f:id:mclement:20210323100344p:plain, which means “the car must not be at the intersection until it is clear”. The paper proposes an efficient way to encode STL rules as constraints, reducing the solution space of the problem (like in Figure 5b) and ensuring that they are satisfied by the solution of the MIP.

The paper tackles a simulated scenario with intersections and curved roads and shows that their solution can navigate a number of situations in real-time. They also show that their monitoring system can correctly detect unexpected changes in the environment, for example when another vehicle suddenly brakes. It is then possible to fall back to another algorithm or to solve the MIP problem again but with the new information added. This alleviates the main issue of MIP which is to depend on very good models of the environment as it is now possible to detect when these models make a mistake.

Accelerating Cooperative Planning for Automated Vehicles with Learned Heuristics and Monte Carlo Tree Search

Karl Kurzer(1), Marcus Fechner(1), and J. Marius Zöllner(1,2)

1- Karlsruhe Institute of Technology, Karlsruhe, Germany

2- FZI Research Center for Information Technology, Karlsruhe, Germany

IEEE Intelligent Vehicles Symposium (2020) https://arxiv.org/abs/2002.00497

f:id:TierIV:20210322214141p:plain

Figure 6 - (a) Use of the Gaussian mixture to select actions in the MCTS (b) Gaussian mixture

(b) taken from https://angusturner.github.io/generative_models/2017/11/03/pytorch-gaussian-mixture-model.html

As discussed in the previous section, MCTS are great to model interactions with other agents but are very hard to sufficiently explore. In order to make exploring the tree more efficient, this paper learns Gaussian mixture models that associate each state (i.e., node of the MCTS) some probabilities on the action space. These probabilities are used to guide the exploration of the tree.

A Gaussian mixture is a combination of several Gaussian probability distributions, allowing multiple peaks with different means and covariances (Figure 6b). In this paper, the actions modeled by these probabilities are pairs of changes in longitudinal velocity and in lateral position. This means that for a given state, the mixture must contain as many peaks as there are possible maneuvers such that their mean will correspond to the typical trajectory for that maneuver. On the highway for example, mixtures with 2 components can be used to learn the 2 typical maneuvers of keeping or changing lanes (Figure 6a).

This technique is interesting to make the exploration faster but the experiments of the paper do not show any performance improvements once enough exploring time is given. Having to fix the number of components can also be an issue when trying to generalize to various situations.

Conclusion

Decision making for autonomous driving remains a very important topic of research with many exciting directions currently being investigated.

Researchers and engineers at Tier IV are working to bring the results of this progress to Autoware as well as to develop new techniques to help make autonomous driving safer and smarter.

Intelのad-rss-libを大解剖!RSSのライブラリのアーキテクチャと中身を解説する!

こんにちは、ティアフォーでAutowareのSimulator開発を担当している片岡と申します。

弊社ではSimulationや実車評価を通して様々な側面からAutowareの性能評価と開発へのフィードバックを行っております。

今回はその一環でIntelRSS(Responsibility Sensitive Safety)という安全評価基準のライブラリを読み解きましたのでその中身について解説したいと思います。

また、ティアフォーでは「自動運転の民主化」をともに実現していく、Simulation EngineerやSafety Engineerを募集しています。

自動運転を実現するためには、極めて幅広い分野に対する研究開発や安全担保への取り組みを進めていく必要があります。もしご興味があれば以下のページからコンタクトいただければと思います。

tier4.jp

 Intel RSSとは?

youtu.be

Intel RSSIntel (Mobileye) が提唱している自動運転車両の安全性を評価する基準です。評価基準の詳細な計算ロジックが記述されている論文はarXivにおいて公開されております。

arxiv.org

RSSの概要

RSSはHD Mapと周囲のオブジェクトの動きから、自動運転車が取ってよい動作コマンド(縦方向、横方向加速度)の範囲を計算します。

公道において自動運転車両が出会う状況を数式で表現することで自動運転車両が取った行動の危険度を数値化することが可能になります。この機能は「この危険な状況は道路上にいる誰のせいで発生したのか」を表現することができるため、公道走行ログから危険なシナリオを抽出したり、様々なパラメータで実行されたSimulation Testの結果を分析するのに使うことができます。

このロジックは本質的にはAutoware等の自動運転システムに含まれるプランナーと等価なものであり、後述するad-rss-libのサポート対象からは外れているものの、障害物回避等の動きを行うことも可能なようです。

下の動画(CARLA 0.9.10のNew Feature紹介動画)においては実際にRSSに基づいて計算された制御入力を使ってUnstructuredな環境での障害物回避が行われています。

youtu.be

RSSは内部に状態機械を持っており、様々なシチュエーションに対して適切な評価関数を選択することで自動運転システムからの出力が適切かを評価することができます。

f:id:masaya-kataoka:20210315164514p:plain

https://intel.github.io/ad-rss-lib/images/ad-rss-map-situation_analysis.png

RSSと自動運転システムのIntegration

f:id:masaya-kataoka:20210315164013p:plain

https://intel.github.io/ad-rss-lib/images/ad-rss-lib-Integrate_Into_Sense-Plan-Act.png

RSSは自動運転のサブシステムとして実装することを考慮して設計されており、認識結果からワールドモデルを構築して自動運転システムからの出力を制限するといった使い方が想定されています。

また、後述するad-rss-libは様々な外部ツールとインテグレーションされており、インテグレーションもやりやすい仕様になっていることが伺えます。

ad-rss-lib

今回紹介しますのは、この論文に有る内容をC++で実装したOSSです。

ライセンスはLGPL2.1となっていて、Ubuntu16.04、18.04、20.04で動作します。

github.com

CARLAやBaiduのApolloといった自動運転業界で有名なOSSでもこのライブラリはインテグレーションされており、その使いやすさと注目度の高さが伺えます。

現在のversion(4.4.0)においては以下の内容がサポートされています。

  • 複数のマップバージョンをサポート(Map Integration)
  • 構造化されていない道路や歩道も扱える
  • 複数車線の道路、すなわち縦方向および横方向の安全距離と適切な対応の決定
  • 交差点、つまり、異なるジオメトリの2つ以上のルート、ルートの交差点のルール、優先権/通行権、および縦方向と横方向の適切な応答の決定

逆にサポート範囲外となっているのは以下の内容になります。

  • オクルージョンの考慮
  • 回避動作を生成するロジック
  • 横方向の衝突がない交差点の対応

ad-rss-libのパッケージ構成

ad-rss-libはC++とCMakeで書かれており、PythonのC APIを使用してPython Bindingsも製作されています。

ad-rss-libのコアライブラリは以下の2つのディレクトリに格納されています。

https://github.com/intel/ad-rss-lib/tree/master/ad_rss

https://github.com/intel/ad-rss-lib/tree/master/ad_rss_map_integration

ad_rssの中身

ad_rssは以下のようなディレクトリ構造になっています。

ad_rss

├── CMakeLists.txt
├── doc
├── generated
├── gtest-cmake.txt.in
├── impl

│   ├── ad_rss.cmake
│   ├── include
│   ├── src

│   │   ├── core
│   │   ├── situation
│   │   ├── unstructured
│   │   └── world
│   └── test
└── python

 CMakeLists.txtはCMakeの設定ファイルであり、ビルド手順が記述されています。

docディレクトリにはDoxygenの設定ファイルが入っており、こちらのドキュメントを生成するのに使われています。

intel.github.io

generatedディレクトリには縦方向の反応時間といったRSSの計算で使われるデータ型を文字列等から作成するためのユーティリティが含まれています。

implディレクトリは更に4つのディレクトリに整理されており、それぞれ

  • core : 下に記したディレクトリ群の中の関数を使うための関数群を収録
  • situation:各situationにおいて実行されるロジックを収録
  • unstructured:構造化されていないシーンでのロジックを収録
  • world:レーン座標系への変換や現在のsituationの認識等のロジックを収録

に分割されています。

レーン座標系への変換等は特に加速度の連続性を維持するためにかなり工夫がなされているようです。このあたりの綺麗に実装するのが難しいロジックをオープンにしてくれるのは非常にありがたいですね!

f:id:masaya-kataoka:20210315165258p:plain

https://intel.github.io/ad-rss-lib/images/lanes_with_different_width.svg

PythonディレクトリにはPythonのC APIを利用してPythonからad-rss-libのロジックをラップして使えるようにするための関数が入っています。

ad_rss_map_integrationの中身

ad_rss_map_integrationは以下のようなディレクトリ構造になっています。

ad_rss_map_integration

├── CMakeLists.txt
├── doc
├── generated
├── impl
└── python

implディレクトリ以外はad_rssディレクトリと同様のコードが入っています。

implにはRSSの内部で使われているHD Mapに関連するコードが収録されています。

 ad-rss-libの使い方

ApolloにおけるRSSのIntegration

Apolloは自動運転車の行動計画部分にRSSのモジュールをインテグレーションしています。

japan.cnet.com

具体的な実装箇所は以下のものになります。

github.com

このドキュメントによるとApolloのEMプランナー(Apolloのプランニングアルゴリズム)は3つのカテゴリーのタスクが交錯する反復的なアプローチをとっており、この中のタスクの一種としてRSSのタスクが実装されているようです。

https://github.com/ApolloAuto/apollo/raw/master/docs/specs/images/class_architecture_planning/image008.png

f:id:masaya-kataoka:20210315130447p:plain

https://raw.githubusercontent.com/intel/ad-rss-lib/master/doc/images/apollo_integration.png

実装されている内容としては

  1. 認識系からきた情報とHD Mapの情報を合わせてWorld Modelを構築
  2. World Modelから現在のSituationを判断
  3. RSSの計算式に基づいて適切な応答を計算
  4. 実際の制御入力における適切な応答を計算
  5. 安全な車間距離を取っているかを評価

というロジックになります。

CARLAにおけるRSSのIntegration

CARLAにおいてはRSS SensorとRSS Restrictorの2種類のIntegrationがされています。

f:id:masaya-kataoka:20210315130404p:plain

https://carla.readthedocs.io/en/latest/img/rss_carla_integration_architecture.png

carla.readthedocs.io

RSS Sensor

RSS Sensorは自車両の制御コマンドがRSSの基準を満たしているかをチェックするセンサーです。

  1. SimulatorのAPIを使用してActorの一覧を取得
  2. RSSに基づいて適切な制御コマンドの範囲を計算、その値に自車両の入力が入っているかを確認

www.youtube.com

上記の動画に有るとおり、様々な状況下でRSSをメトリクスとして自車両の危険な行動をチェックできています。

CARLAのver 9.10.0からはUnstructuredな環境での実行もサポートされており、市街地環境における本格的なSimulationの実現に向けて着々と進んでいる様子が見て取れます。

youtu.be

RSS Restrictor

RSS RestrictorはRSSのメトリクスを使い、NPC車両にその場面において危険な状況をうむ制御入力を入れないようにするためのモジュールです。

具体的な実装箇所はこちらになります。

github.com

この関数はPythonから呼び出せるようになっており、CARLAのPython APIで呼び出すことによってNPCが適切に振る舞うことができるようになるようです。

まとめ

今回は自動運転システムを支える評価基準の一種であるIntelRSSとそのオープンソース実装について解説しました。今後はこのツールを活用しAutowareの性能評価をさらに加速させ、安全安心でオープンソースな自動運転システム開発を強力に押し進めていきたいと思います。