オムロンサイニックエックス株式会社（本社：東京都文京区、代表取締役社長：諏訪正樹、以下OSX）は、複数の自動走行ロボット（以下エージェント）が衝突することなく目的地に移動するための経路計画（以下、マルチエージェント経路計画）において、経路導出の効率を大幅に改善することが可能な新しい経路計画手法を開発しました。

マルチエージェント経路計画に対する従来手法の多くは、エージェントが移動可能な範囲全体を対象とした経路の探索が必要でした。これに対して本手法では、経路計画の成功率や解として経路長の短さを従来手法と同程度に維持しつつ、それぞれのエージェントに対する経路の探索範囲を10分の1程度に削減することができます。

本成果の詳細は、5月9日より開催される国際会議「International Conference on Autonomous Agents and Multiagent Systems (以下、AAMAS) 2022」にて発表を行います。

「AAMAS」は世界中の研究者が参加し議論が行われる国際会議で、自律ロボットに関する国際的に権威のある主要国際会議の一つです。2022年は600件を超える投稿の中から、およそ26%の論文が採択されています。OSXからの発表は、5月12日０時および18時（日本時刻）を予定しています。

＜採択された論文情報＞
論文タイトル：「CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces」
著者：奥村圭祐（東京工業大学、2021年4月から10月の間OSXインターン）、米谷竜（OSX）、西村真衣（OSX）、金崎朝子（東京工業大学、OSX技術アドバイザ）

開発した技術の特長は、以下の通りです。

■研究の背景
近年、製造現場だけでなく医療やサービス業など様々なシーンでの労働力不足により、人の作業を機械で代替し自動化を進める動きが加速しています。特に、モノの搬送などの分野においては、複数の目的地へ物品を届ける要望があり、作業の効率化を図るために複数台の自動走行ロボットを活用する研究開発が活発に行われています。

このような場面では、複数台のエージェントをそれぞれの目的地に効率的に到達させるため、障害物を避け、エージェント同士が衝突すること無く、より短い移動経路を導き出す経路計画（マルチエージェント経路計画）技術が重要です。マルチエージェント経路計画では、エージェントが移動可能な全範囲を碁盤目(以下グリッド)のように表現し、そのうえで経路を探索する手法が一般的です（図1(a)^※1）。また、移動可能な範囲をグリッドに分割せずに連続的な空間として扱う手法も提案されています。この手法では、エージェントが移動可能なランダムな位置（頂点）から構成されたロードマップと呼ばれるグラフを活用します（図1(b)^※2）。しかしいずれの場合においても、短い移動経路を得るためには、グリッドの目の細かさやロードマップにおける頂点数を増加させる必要があり、それにともなって経路計画の計算コストが膨大になるという課題がありました。

※1 たとえば、David Silver. 2005. Cooperative Pathfinding. Proceedings of the Artificial Intelligence for Interactive Digital Entertainment Conference (AIIDE) (2005), 117–122

※2 たとえば、Wolfgang Hönig, James A Preiss, TK Satish Kumar, Gaurav S Sukhatme, and Nora Ayanian. 2018. Trajectory Planning for Quadrotor Swarms. IEEE Transactions on Robotics (T-RO) 34, 4 (2018), 856–869.

■研究の概要
このような課題に対して、OSXの研究グループでは、経路を導出するためのロードマップとしてCTRM（cooperative timed roadmap）を提案いたしました。CTRMはそれぞれのエージェントに対して、障害物や他のエージェントを避けつつ自身のゴールに向かうために考慮すべき探索範囲を効率的に限定することができます（図1(c)）。

CTRMの構築には、AIの一分野である機械学習を活用しています。提案するアプローチではマルチエージェント経路計画の問題とその解となる経路をあらかじめ大量に用意し、各エージェントが障害物や他のエージェントの位置を考慮しつつ、衝突を避け協調的に目的地に向かうための移動先を、確率分布として学習します。この学習結果を用いることで、新たな経路計画の問題においても、ゴールへの移動や衝突の回避と関係のない冗長な移動先を排除した効率的なCTRMを構築することができるようになります（図2）。たとえば、いくつかの障害物がある環境下で30~40台のエージェントが移動するという条件下では、エージェントが移動な全範囲を探索する従来手法と比較して、探索範囲を10分の1程度、計算時間を2分の1程度に削減しつつ、同等の経路を導出することができます。
経路計画の一例として、同一のエージェントが10個の時の各手法での経路計算の結果のイメージを図3に示しています。本手法により、滑らかで効率的な経路の解を短時間で求めることが可能となります。

図1 経路計算手法の比較

(a)従来手法(グリッド方式)

(b)従来手法(ロードマップ方式)

(c)提案手法(CTRM)

図1 経路計算手法の比較

【凡例】黒丸印：障害物、青丸印：エージェントのスタート地点、青四角印：エージェントのゴール地点、灰色線：エージェントの移動経路候補

図2 提案手法の概要

【凡例】黒丸印：障害物、各色丸印：各エージェントのスタート地点、各色四角印：各エージェントのゴール地点

図3 10個の同一のエージェントに対する移動経路の計算結果の例

(a)従来手法(グリッド方式)

(b)従来手法(ロードマップ方式)

(c)提案手法(CTRM)

図3 10個の同一のエージェントに対する移動経路の計算結果の例

今回開発した手法は、物流倉庫の自動化やドローン等移動体の協調的な制御など、マルチエージェント経路計画に関連する様々なケースへの応用が期待されます。今後は、実際の自動搬送ロボットでの検証を進めていくとともに、さらなる精度・計算効率の向上を目指していきます。また、さまざまな研究機関とのオープンイノベーションによる共創を引き続き行いながら、研究を通じて社会的課題を解決しソーシャルニーズの創造を目指してまいります。

本成果はオープンソースソフトウェアとして公開されており、以下のリンクから利用することができます。
https://github.com/omron-sinicx/ctrm
https://github.com/omron-sinicx/jaxmapp

詳細は、以下の記事をご参照ください。
データ駆動型マルチエージェント経路計画に関する研究がAAMAS 2022に採択されました

オムロンサイニックエックス株式会社について
オムロンサイニックエックス株式会社は、オムロンの考える"近未来デザイン"を創出する戦略拠点です。「AI」「ロボティクス」「IoT」「センシング」など、幅広い領域の最先端技術のトップ人財が研究員として在籍し、社会的課題を解決するために、技術革新をベースに「ビジネスモデル」「技術戦略」「知財戦略」を統合し具体的な事業アーキテクチャに落とし込んだ"近未来デザイン"を創り出します。また、大学や社外研究機関との共同研究を通じて「近未来デザイン」の創出を加速していきます。詳細については、https://www.omron.com/sinicx/をご参照ください。

本件に関する報道関係からのお問い合わせ先: オムロン株式会社　イノベーション推進本部
エンゲージメント・コミュニケーション部
TEL: 0774-74-2010

オムロン サイニックエックス、自律ロボットに関する主要国際会議「AAMAS2022」に研究論文が採択

オムロンサイニックエックス、自律ロボットに関する主要国際会議「AAMAS2022」に研究論文が採択