A*探索アルゴリズムを発展させた「微分可能 A*探索」を世界に提案 オムロンのサイニックエックス研究論文が「ICML2021」に採択

オムロン株式会社の子会社として近未来デザインの創出を目指すオムロン サイニックエックス株式会社の主任研究者 米谷竜氏、シニアリサーチャー谷合竜典氏らの研究グループは、自動走行ロボットなどが移動経路を計画するアルゴリズムにAIの技術領域の一つである機械学習を用いることで、飛躍的に経路計画性能を向上させる経路探索アルゴリズムを開発したことを発表した。

同アルゴリズムでは過去の経路計画から学習により経路を導き出すことで、経路計画に必要な移動環境の認識や経路探索の効率を向上させることができる。研究の詳細は7月18日より開催される機械学習分野における国際会議「International Conferenceon Machine Learning 2021」(以下、ICML)にて発表される。「ICML」は世界中の研究者が参加し議論が行われる国際会議で、「NeurIPS」「ICLR」とならび、機械学習分野において国際的に権威のあるトップカンファレンスの一つ。2021年は5,000件を超える投稿の中から、およそ22%の論文が採択されている。

<採択された論文情報>
論文タイトル:「Path Planning using Neural A Search」
著者:米谷 竜(OSX)、谷合 竜典(OSX)、Mohammadamin Barekatain(2019年から2020年の間OSX インターン)、西村 真衣(OSX)、金崎 朝子(東京工業大学、OSX 技術アドバイザ)


A*探索アルゴリズムを発展させた「微分可能 A*探索」を世界に提案

近年、新型コロナウイルス感染症の拡大などで人々の生活様式が大きく変化し、人と人との接触や密を回避するために、自律移動ロボットによる配達や消毒など、さまざまな検証が行われている。また、人手不足の深刻化によりモノの搬送などにおいても、最終拠点からエンドユーザーまでのラストワンマイルを自動で搬送する研究が多く行われている。そのような場面で、自律移動ロボットは目的地に到達するために多様な環境において移動経路を導き出し、ロボット自らが意思決定を行って走行する必要がある。周囲の障害物などに接触することなく、安定して最短経路で目的地へ到達するためには、この移動経路を正確かつ効率的に見つける経路計画が重要。

これまでに様々な経路計画アルゴリズムの研究が行われているが、その中でもA-Star(読み:エースター、以下、A*探索)探索アルゴリズムを用いたアプローチは、スタート地点から目的地までの最短ルートを確実かつ効率的に探索できることから、活用、改良が進められてきた。さらに近年では深層学習の技術を活用し、過去の経路計画の事例をロボットに学習させ、経路計画をさらに効率化する取り組みが進められている。しかしながら、このような深層学習を用いた手法は、経路計画により得られる経路の最適性、経路計画の効率性などの性能に課題があった。

このような課題に対して、米谷・谷合氏らの研究グループではA*探索のアルゴリズムを発展させ、深層ニューラルネットワークの一部として利用可能な「微分可能 A*探索」を世界に先駆けて提案し、経路計画の性能を飛躍的に向上させることに成功した。

深層ニューラルネットワークとは
ヒトの脳の仕組みを模した数理モデル(ニューラルネットワーク)を多層に重ねたもの。


「微分可能 A*探索」の特徴

今回採択された論文では経路計画において用いられる「A*探索アルゴリズム」を深層学習で広く用いられる誤差逆伝播法が利用できる形式「微分可能 A*探索」として新たに定式化。これにより、ニューラルネットワークを構成する一つのモジュールとしてA*探索アルゴリズムを利用し、与えられた問題に対して期待される経路を効率よく導き出すネットワークとして学習できるようになった。

誤差逆伝播法とは
機械学習において、ニューラルネットワークの出力と教師データとの誤差を最小化するように、ニューラルネットワークを学習させるアルゴリズム。


経路計画における最適性と効率のトレードオフを大幅に改善

経路計画において与えられた環境での最適な経路を導出するためには、その環境で進むことが可能な経路を広範囲に探索する必要性が発生し、両者のトレードオフが課題となる。提案した「微分可能 A*探索」を用いた深層ニューラルネットワークでは、経路計画における問題とその解法の関係性を学習できるようになる。これにより、経路計画におけるベンチマークテストにおいて、最短経路探索にかかる探索効率を従来手法から大幅に改善させることに成功した。

ベンチマークによる性能検証結果

・黒色が障害物を表し、灰色の中でスタート地点からゴール地点までの経路探索を行う。
・赤が経路探索結果を示しており、従来手法に比べ最適な経路で探索できていることが分かる。
・緑が探索をおこなった領域を示しており、緑の範囲が少ないほど、探索効率が高いことを表すため、A探索および従来手法よりも探索効率が高いことが分かる。

従来手法1:最良優先探索法
従来手法2:Choudhury, S., Bhardwaj, M., Arora, S., Kapoor, A., Ranade, G., Scherer, S., and Dey, D. Data-driven planning via imitation learning. The International Journal of Robotics Research (IJRR), 37(13-14):1632–1672, 2018.


実画像を用いた経路計画の実現

通常のA*探索アルゴリズムでは環境中のどこが走行可能でどこが走行不可能であるかを認識し、あらかじめロボットに知らせる必要があった。これに対して提案手法ではカメラ等で撮影した実画像とその中を歩く人間の移動経路のデータを学習することにより、実画像における道路や建物の領域といった詳細な環境情報を与えることなく、人間の歩行軌跡と同等の経路を計画できるようになった。

実画像での検証結果(スタート地点から道路に沿って緑色の樹木を迂回し、ゴール地点へ到達することが正解の移動軌跡)

今回開発した技術は、ロボットがカメラを通した環境の観察に基づいて人や障害物などを自ら判断し、それらを回避しながら移動するために有効な技術。今後は実際の自律移動型ロボットでの検証を進めていくとともに、さらなる精度向上を目指していく。また、さまざまな研究機関とのオープンイノベーションによる共創を引き続き行いながら、研究を通じて社会的課題を解決しソーシャルニーズの創造を目指していくとしている。

ロボスタFacebookで最新ニュースが届く【フォロワー2万5千人突破!!】
ロボット、AI、スマートスピーカー、ビッグデータ、自動運転、xR、ドローンなど最新情報が満載
ロボットスタート「ロボスタ」 Facebbok公式ページ

ABOUT THE AUTHOR / 

山田 航也
山田 航也

横浜出身の1998年生まれ。現在はロボットスタートでアルバイトをしながらプログラムを学んでいる。好きなロボットは、AnkiやCOZMO、Sotaなどのコミュニケーションロボット。

PR

連載・コラム