人工知能の歴史と、グーグルの自動運転車が事故を起こさないためにしていること：Google Carの自動運転技術大解剖（終）（1/2 ページ）

本連載では、公開情報を基に主にソフトウエア（AI、アルゴリズム）の観点でGoogle Carの仕組みを解説していきます。今回は、ロボットの思考と行動のサイクルのうち「行動計画の立案」と「計画した動作の実行」について解説。最後に人工知能の歴史も。

[近棟稔，ウルシステムズ]

今回の主な内容

• 【2】行動計画の立案――目的地へ至る走行ラインの算出の例
  • Google Carが走行ラインを確定していく様子
  • そもそも自動車が動ける範囲とは
  • 「判断の遅れ」は事故につながる
• 走行ラインの探索アルゴリズム
  • A*（エースター）探索アルゴリズム
  • 探索ツリーを事前に計算する
• 【3】計画した動作の実行――PIDコントロールによるステアリング操作の例
  • CTE――走行ラインから車がどれだけ離れているか
  • P（比例）コントロール
  • P（比例）D（微分）コントロール
  • P（比例）I（積分）D（微分）コントロール
  • 定数を設定するために、機械学習
• 人工知能の歴史

連載目次

　グーグルが開発した自動運転車（以下、Google Car）の仕組みについて、公開情報を基に、主にソフトウエア（人工知能、アルゴリズム）の観点で解説していく本連載。第1回の「あなたの知らない自動運転技術の歴史とGoogle Carの自動運転に使用するセンサーの基礎知識」では、自動運転技術の歴史を概説し、Google Carの自動運転に使用するセンサーについても説明しました。

　前回の「自動車を制御するロボットの思考と行動の仕組み――Google Carが現実世界を認識する際の3つのアルゴリズムと実用化への課題」では、Google Carがどのように現実世界を認識するかを説明しました。「Probabilistic Robotics」（確率ロボティクス）を導入することでGoogle Carの認識能力は格段に進歩を遂げました。さて、今回の記事ではロボットの思考と行動のサイクルのうち【2】「行動計画の立案」と【3】「計画した動作の実行」について説明します。

ロボットの思考と行動のサイクル（第2回記事より再掲）

【2】行動計画の立案――目的地へ至る走行ラインの算出の例

　前回の記事でも触れましたが、Google Carは現実世界を認識すると制御コンピューター内にドライビングシミュレーションゲームに似た仮想世界を展開します。Google Carは、この仮想世界の中で「行動計画の立案」を行います。行動計画には目的地へ至る走行ラインや走行速度など、さまざまな要素が含まれます。ここでは目的地へ至る走行ラインの算出にフォーカスして説明します。

Google Carが走行ラインを確定していく様子

　Google Carが走行ラインを確定していく様子を示したものが以下の画像です。この画像はGoogle Carが見ている仮想世界そのものです。

図1　車の動ける範囲を基に動ける範囲のツリーを検索してゴールに近づく

　車の後方に伸びている緑色の太い線が、今までGoogle Carが通ってきたルートです。赤で示されているのはセンサーで検出した障害物です。Google Carはセンサーで検出するまで障害物はどこにあるか分からないという前提を置いています。Google Carは画像の下方から迷路へ進入し、画面右側にある緑色の四角で示されたゴールを目指しています。ゴール近くの袋小路に入り込んでしまった後、いったんバックして、ハンドルを切り返して脱出し、別のルートでゴールを目指して走っていることが分かります。

　Google Carの現在位置の前後には、黄緑色の線がたくさん出ています。この線はいくつも分岐しながら長く伸びています。その中に最終的にゴールに至る水色の線があります。この水色の線はこの時点で最適だと判断されたGoogle Carの走行ラインです。黄緑色の線は走行ラインを算出する際に試行錯誤した痕跡を示したものです。

そもそも自動車が動ける範囲とは

　この試行錯誤の内容を理解するには、まずは下の図を理解する必要があります。

図2　自動車が動ける範囲

　Google Carに限らず、自動車が動ける範囲は限られています。具体的にはハンドルを左右に切ることと、前後に動くことしかできません。真横に動くことはできないのです。この制約の中で、目的地に正しい車の向きで到着できる走行ラインを算出する必要があります。そのため、Google Carは論理的に考えられる走行ラインを無数に考え、その中からゴールに到達する走行ラインを選び出すのです。

　例えば、ハンドルを3方向に切ることができるとしましょう。動く方向は前進と後退の2通りあります。つまり、6通りの動き方が考えられるわけです。ゴールに到達するルートが存在しない場合は、移動先で、さらにハンドルを切り前進したり後退したりする必要があります。6通りの場所からそれぞれ6通りの動き方を検討すると、全部で36通りの到達地点が考えられます。

　このように取り得る状態をどんどん展開していくと、図1の黄緑色の線のように、移動先の可能性がツリー状に広がっていきます。Google Carは数万通りもの可能性を検討し、ゴールへ到達可能な走行ラインを1つに絞り込みます。もちろんゴールへ至るルートは複数考えられます。Google Carは最も簡単に到達できるルート、障害物から安全な距離を保つことができるルートを優先的に選び出すのです。

「判断の遅れ」は事故につながる

　Google Carでは、走行ラインの決定を50ミリ〜300ミリ秒間隔という非常に短いサイクルで繰り返し行っています。ルートは常に変更する必要があるからです。例えば、障害物を検出したら走行ラインを変更したり、ブレーキをかけて減速したりしなければなりません。再計算のスピードはとても重要です。再計算が遅延すれば、それは人間で言う「判断の遅れ」となり、事故につながってしまうことになります。

走行ラインの探索アルゴリズム

　走行ラインの探索アルゴリズムは、人工知能（AI）の世界では古典的な問題です。

　例えば、「3目並べ」「チェス」「将棋」といったゲームのコンピューター側の思考ルーチンにおいても、大量の盤面の先読みによる探索を行い、その中から次の一手を選び出します。Google Carが走行ラインを決定する際に行っていることも、基本的には同じです。取り得る多数の走行ラインから、次の瞬間に採用するものを1つに決めるのです。

　探索アルゴリズムではいかに無駄な先読みをせず、より意味のある試行錯誤を行うかが鍵となります。Google Carの方式については論文『Practical Search Techniques in Path Planning for Autonomous Driving』に詳細に記述されています。ここでは、この論文をかいつまんで説明していきます。

A*（エースター）探索アルゴリズム

　Google Carにおける走行ラインの探索アルゴリズムは、大学の講義でもしばしば取り上げられる「A*（エースター）探索アルゴリズム」をベースにしています。

図3　A*（エースター）探索アルゴリズムの基本的な挙動

　A*探索アルゴリズムの基本的な考え方は単純です。車の走行ラインを決めようとしているときに、ゴールから離れるような可能性を優先的に考える必要はありません。A*探索アルゴリズムでは「ゴールに向かう方向を優先的に深掘りしていった方が、より素早くゴールに到達する走行ラインが見つかるだろう」と考えます。この工夫により、無駄に広い範囲を探索することを防いでいるのです。

探索ツリーを事前に計算する

　Google CarはA*探索アルゴリズムをベースにしつつ、「探索ツリーを事前に計算する」という工夫を凝らしています。実は、障害物の存在を無視してしまえば、探索ツリーの形は走行中に変化することがありません。

　大量の探索ツリーを前もって計算しておけば、走行中は車の向きに合わせてツリーを回転するだけで瞬時に遠くまで走行ラインの先読みできるようになります。この事前計算を導入することで、走行ラインの探索時間を劇的に短縮しているそうです。