古典的な数学の問題が自動運転車に取り入れられる

ロボットが走り、車が自動運転できるようになるずっと以前、数学者たちは単純な数学の問題に思いを巡らせていました。彼らはそれを解き明かし、そしてそれを諦めました。彼らの数学的好奇心の対象が、遠い未来の機械に搭載されることなど、知る由もありませんでした。

未来は今ここに。プリンストン大学のアミール・アリ・アフマディとアニルダ・マジュムダールによる新たな研究の結果、純粋数学の古典的な問題が、ドローンや自動運転車が木に衝突したり、対向車線に逸れたりしないという確固たる証明を提供しようとしている。

「あなたのシステムが衝突を回避できるという100％完全な証明可能な保証が得られます」と、この研究でアフマディ氏と協力したプリンストン大学の最終学年の大学院生、ジョージナ・ホール氏は述べた。

この保証は、意外なところから来ています。それは、「平方和」として知られる数学の問題です。この問題は1900年に偉大な数学者ダヴィド・ヒルベルトによって提起されました。彼は、ある種の方程式が常に、それぞれ2乗された2つの項の和として表せるかどうかを問いました。

数学者たちは数十年以内にヒルベルトの問いに答えを出しました。それから約90年後、コンピュータ科学者やエンジニアたちは、この数学的性質、つまり方程式が平方和として表せるかどうかが、彼らが解決したい多くの現実世界の問題の答えに役立つことを発見しました。

「私がやっていることは、19世紀の古典数学と非常に新しい計算数学を多用している」とアフマディ氏は語った。

研究者たちは平方和が様々な疑問への答えを見つけるのに役立つことに気づきながらも、そのアプローチを実際に適用する上で課題に直面していました。アフマディ氏とマジュムダー氏による新たな研究は、そうした最大の課題の一つを解決しました。それは、古くからある数学の問題を、今日の最も重要な技術的課題のいくつかに正面から適用することです。

ポジティブさを保証

何かの平方和とはどういう意味でしょうか？13という数字を考えてみましょう。これは2つの平方和、2 ²と 3 ^{2の和です。34という数字は、3 2}と 5 ²の和です。

^{ヒルベルトの問いは、数ではなく、5x 2} + 16x + 13のような多項式に関するものでした。20世紀初頭に彼が提起した23の問いのうち17番目です。この種の多項式は、平方和で表すこともできます。例えば、5x ^{2 + 16x + 13 は、(x + 2) 2} + (2x + 3) ²と書き直すことができます。

式が平方和である場合、それは常に非負であることがわかります。（なぜなら、平方和は正またはゼロであり、正の数の和は正の数だからです。）ヒルベルトは、逆の場合、つまりすべての非負多項式が有理関数の平方和として表せるかどうかを知りたかったのです。1927年、数学者エミール・アルティンはヒルベルトの予想が正しいことを証明しました。

この関係は非常に有用であることが判明しました。数十もの変数を高べき乗した複雑な多項式を与えられた場合、それが常に非負かどうかをすぐに判断するのは容易ではありません。「明らかに非負である多項式もあれば、そうでない多項式もあります。常に非負であるかどうかをテストするのは難しいのです」とアフマディ氏は言います。

しかし、同じ多項式が平方和で表せることを示せば、結果として非負性が得られることがわかります。「平方和は、正性を証明する素晴らしい証明書になります」と、マサチューセッツ工科大学のコンピューター科学者兼エンジニアで、平方和の問題を応用分野に持ち込む上で影響力のあるパブロ・パリロ氏は述べています。

多項式が常に非負であるかどうかを知ることは、数学的には些細なことのように思えるかもしれません。しかし、ヒルベルトがこの疑問を提起してから1世紀が経ち、多項式の非負性は、私たち全員に影響を与える応用問題への答えとなることが証明されました。

最良の方法

二乗和は最適化の分野で現実世界に登場します。最適化理論は、制約の中で物事を行うための最善の方法を見つけることに関係しています。例えば、現在の交通状況と途中で立ち寄る必要がある場所を前提として、職場への最適なルートを見つけるなどです。このようなシナリオは、多くの場合、多項式方程式に要約できます。そのような場合、多項式が取る最小値を見つけることでシナリオを解く、つまり「最適化」します。

多くの変数を持つ多項式の最小値を見つけるのは困難です。複雑な多項式の最小値を計算するための高校のような簡単なアルゴリズムは存在せず、同じ多項式をグラフ化することも容易ではありません。

多項式の最小値を直接計算するのは難しいため、研究者は他の方法で推論します。そしてここで、非負性、そして多項式が平方和であるかどうかという問題が登場します。「非負性を証明することは、まさにあらゆる最適化問題の核心です」と、ワシントン大学の数学者レカ・トーマス氏は述べています。

最小値を見つける一つの方法は、自分自身に問いかけることです。「非負の多項式から、どこかで負になる前にどれだけの値を引けるだろうか？」この問いに答えるために、様々な値を試してみるかもしれません。多項式から3を引いても、依然として非負のままだろうか？4はどうだろうか？あるいは5はどうだろうか？この手順を繰り返す中で、各ステップで多項式が依然として非負であるかどうかを知りたいと思うでしょう。そして、それを確認するには、多項式が依然として平方和で表せるかどうかを確認する必要があります。

「問いたいのは、『多項式は非負か？』ということです。問題は、変数が増えると非負かどうかを答えるのが難しくなることです」とアフマディ氏は言います。「だからこそ、非負性の代替として平方和を使うのです。」

研究者は、多項式の最小値（つまり、多項式の最適値）が分かれば、他の手法を用いてその値に至る入力を特定することができます。しかし、非負性を利用して最適化問題を解くためには、多項式が平方和に等しいかどうかを迅速に計算する方法が必要です。そして、研究者たちがこの問いを解明するまでには、ヒルベルトの問いから100年もかかりました。

問題を分解する

ヒルベルトの17番目の問いは、2000年頃に純粋数学から実社会​​への応用へと移行しました。この時、複数の研究者が、多項式が平方和であるかどうかを判定するアルゴリズム的手法を考案しました。彼らは、平方和の問題を「半正定値計画問題」、つまりコンピュータが処理可能な問題へと変換することでこれを実現しました。これにより、コンピュータサイエンスやエンジニアリングなどの分野の研究者は、非負値の力を利用して、最適な問題解決方法の探索を行うことができるようになりました。

しかし、半正定値計画法には大きな限界があります。大規模な問題では速度が遅く、研究者が真に関心を持つ最も複雑な多項式の多くを扱うことができません。半正定値計画法は、少数から12個程度の変数を6以下のべき乗で累乗した多項式を平方和分解するのに使用できます。複雑な工学的問題（例えば、ヒューマノイドロボットが確実に立ち上がれるようにする方法など）を特徴付ける多項式は、50個以上の変数を含むことがあります。半正定値計画法は、そのような多項式を永遠に計算しても、平方和の答えを返さない可能性があります。

昨年6月にオンラインに投稿された論文で、アフマディ氏とマジュムダー氏は、半正定値計画法の遅さを回避する方法を説明しています。彼らは、単一の遅い半正定値計画法を解いて平方和分解を求めるのではなく、より単純な一連の問題を用いて、はるかに高速に計算する方法を示しています。

こうした種類の問題は「線形計画法」と呼ばれ、1940年代に戦争関連の最適化問題を解くために開発されました。線形計画法は現在では広く理解されており、迅速に解くことができます。アフマディ氏とマジュムダー氏は、新たな研究で、多数の連結線形計画法（あるいは場合によっては二次錐計画法と呼ばれる別の種類の問題）を解き、その結果を組み合わせることで、半正定値計画法で得られる解とほぼ同等の解が得られることを示しています。つまり、エンジニアは非負性の有無を検証し、平方和分解を迅速に求めることができる、新しい実用的なツールを手に入れたということです。

「私たちはロボット工学と制御理論の多くの問題を検討し、得られた解決策の品質が実践でも有用であり、計算がはるかに高速であることを実証しました」とマジュムダール氏は語った。

安全性の証明

自動運転車に乗っているとき、解のスピードは何よりも重要です。そして、そのような状況では、多項式は、衝突したくない障害物を囲む一種の数学的な障壁として機能する可能性があります。ただし、十分な速さで多項式を見つけることができればの話ですが。

簡単な例を想像してみてください。巨大な駐車場に自動運転車が停まっているとします。駐車場には、奥の警備ブース以外何も置いてありません。あなたの目標は、車が警備ブースに決して突っ込まないようにプログラムすることです。

この場合、まず駐車場に座標グリッドを配置します。次に、グリッド上の点を入力として受け取る多項式を作成します。この多項式において、自分の車の位置での値は負、警備ブースの位置での値は正となるようにしてください。

あなたの車とブースの間のいくつかの点において、多項式は負から正へと交差します。あなたの車は多項式が負となる点にのみ存在することが許されるため、これらの点は壁のような形を形成します。

「特定の場所からスタートした場合、障害物があるラインの反対側には行きません。これにより、衝突回避の安全性が正式に証明されます」とアフマディ氏は述べた。

さて、この壁が車とブースの中間にあるのは良くありません。多項式は、壁が障害物にできるだけ密着するように設計する必要があります。こうすることで、ガードブースを囲いながら、車が動き回るのに十分なスペースを確保できます。

実際には、壁とブースの間の距離という値を最小化したいので、多項式のグラフをずらして、非負値でなくなるまでどれだけ移動できるかを調べます。そして、ずらした多項式が平方和のままであるかどうかをテストすることで、その直線を探ります。

駐車場がほぼ空いているのは良いことです。しかし、現実の運転シナリオでは、車のセンサーは車、自転車、子供など、常に新たな、そして変化する障害物を検知します。新たな障害物が現れたり、既存の障害物が動いたりするたびに、車はそれらを遮断するために複雑な多項式を新たに考案しなければなりません。つまり、膨大な量の二乗和チェックをリアルタイムで実行しなければならないのです。

7年前、別の研究者2人が、このような多項式技術を用いて自動運転車を行き来すべきでない場所から隔離できるかもしれないと考えました。しかし、当時の計算速度では、このアイデアは夢物語でした。

アフマディ氏とマジュムダール氏の新しいアプローチは、このような高速計算を実行する方法を提供します。ですから、自動運転車が安全に世界を走行できるようになるとしたら、私たちはGoogleとTesla、そしてDavid Hilbertに感謝することになるでしょう。

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。