AGVロボットマルチエージェント経路探索の4つの主要な研究方向

マルチエージェント経路探索 (MAPF) は、人工知能、ロボット工学、理論計算機科学、実践的オペレーションズリサーチの分野で広く研究されてきました。この論文では、MAPF メソッドを実際のシナリオに拡張する際に発生する問題と、これらの問題を解決するための 4 つの研究方向について説明します。我々は、MAPF 問題の標準モデルのためのより高速な方法を開発するよりも、これらの問題を解決することの重要性を強調します。

1 はじめに

マルチエージェント パス検索 (MAPF、マルチエージェント ルーティングとも呼ばれる) は、人工知能、ロボット工学、理論計算機科学、実践的オペレーションズ リサーチの分野で広く研究されてきました。 (標準) MAPF のタスクは、コスト関数を最適化しながら、他のエージェントと衝突することなく、指定されたグラフ内の現在の頂点から目標までの複数のエージェントのパスを見つけることです。 MAPF で使用される既存の方法には、充足可能性からの問題への還元、整数線形計画法、回答セット計画法 [Yu and LaValle, 2013b; Erdem et al., 2013; Surynek, 2015]、最適、有界準最適または準最適検索法 [Silver, 2005; Sturtevant and Buro, 2006; Ryan, 2008; Wang and Botea, 2008; Standley, 2010; Standley and Korf, 2011; Wang and Botea, 2011; Luna and Bekris, 2011; Sharon et al., 2013; de Wilde et al., 2013; Barer et al., 2014; Goldenberg et al., [2014年; WagnerとChoset、2015年; Boyarskiら、2015年; Sharonら、2015年]。

私たちは最近、Kiva（Amazon Robotics）倉庫システム[Wurman et al., 2008]（図1）や自律型空中タグ[Morris et al., 2016]など、MAPFを現実世界のシナリオに一般化する際に生じるさまざまな問題を研究しました。これらの質問は、次の 2 つの一般的な問題に分けられます。

1. 多くの実際のケースでは、新しい構造を利用したり、新しい問題モデルが必要になったりするため、MAPF 問題の標準モデルに対してより高速な方法を開発するだけでは不十分です。

2. MAPF またはその新しいモデルを組み合わせ最適化問題として研究するだけでは不十分です。結果として得られる MAPF ソリューションも実装する必要があるためです。

これら 2 つの問題をさまざまな観点から解決するための 4 つの研究方向について説明します。

1. 多くの実用的なマルチエージェント システムでは、すべてのエージェントにとって最適なパスを見つける前に、まずエージェントをチームに分け、次に各チームに特定の目標を割り当てます。各エージェントには、そのチームから目標を割り当てる必要があります。この困難に対処するために、私たちはさまざまなエージェント グループに対してターゲット割り当てとパス検索 (TAPF) を組み合わせた問題を定式化しました。また、数十のグループと数百のエージェントに拡張できる最適なTAPFメソッドも開発しました[Ma and Koenig、2016]。

[[188185]]

2. 多くの実用的なマルチエージェント システムでは、エージェントは匿名 (交換可能) ですが、そのペイロードは非匿名 (交換不可能) であり、特定のターゲットに配信する必要があります。多くの場合、エージェントはこのようなシステムでペイロードを交換できます。最初の試みとして、より一般的な輸送問題（ペイロードの転送を可能にする）を解決するために、パッケージ交換ロボットルーティング（PERR）問題を定式化します[Ma et al.、2016]。本論文では、近似最適MAPFソリューションの難しさ（複雑さ）も証明します。

3. 多くの実用的なマルチエージェントシステムでは、エージェントの動作の一貫性とエージェントの動作の結果の予測可能性が重要ですが（特に人間とエージェントが共有するワークスペースの場合）、既存のMAPF手法ではこれが考慮されていません。我々は、与えられたMAPFの例の問題構造を2段階で調査しました。第1段階では、ユーザーが提供するエッジを持つ多数の高速道路で構成されるエージェントのパスを見つけるソリューションを開発し、一貫性があり予測可能なエージェントの動きを実現しました[Cohen et al., 2015]。第2段階では、高速道路を自動的に生成する方法を開発しました[Cohen et al., 2016]。

4.MAPF は、主にマルチロボット システムのナビゲーション モジュールまたは動作計画モジュールからヒントを得ています。ただし、特に実際のロボットの不完全な計画実行機能を考慮すると、MAPF ソリューションの最適性または制限された準最適性は、必ずしもその堅牢性を意味するものではありません。 MAPF メソッドの出力を効率的に後処理して、実用的なマルチロボット システムで実行できる計画実行スケジュールを作成するフレームワークを開発します。

図 1: (左) 自律走行ユニットと自律ユニットで移動できる製品を保管する保管ポッド。(右) 典型的な Kiva 倉庫システムのレイアウト (Wurman 他、2008)

MAPF アプローチを実際のシナリオに一般化するために、これらの研究方向の実用性を実証し、これら 2 つの問題を解決することが、MAPF 問題に対するより高速な標準モデル手法の開発と同じくらい重要 (またはそれ以上に重要) であることを示します。

2 エージェントグループに対するターゲット割り当てと経路探索の組み合わせ (TAPF)

一般的に、ターゲットはエージェントが属する各グループに割り当てられます。エージェントは最初にグループに分割され、次に各エージェントにグループからターゲットを割り当てて、現在の頂点からターゲットまでのエージェントのパスを取得し、コスト関数を最適化する必要があります。たとえば、Kiva 倉庫システムでは、倉庫から新しい保管場所に保管コンパートメントを移動する駆動ユニットは、それぞれに使用可能な保管場所を割り当てる必要があるため、グループを形成します。従来の MAPF 手法では、各エージェントに事前に目標が割り当てられる目標割り当て手順の存在を前提としていましたが、最適性を実現するために、目標割り当てと経路検索の問題を統合し、それらの共通の目標を定義する TAPF モデルを構築しました。 TAPF では、エージェントはグループに分割され、各グループ内のターゲットの数はグループ内のエージェントの数と同じになります。 TAPF のタスクは、エージェントに目標を割り当て、エージェントの現在の頂点から目標までの衝突のないパスを計画することです。これにより、各エージェントはグループの目標の 1 つだけに移動し、グループ内のすべての目標が訪問され、最大完了時間 (すべてのエージェントが目標に到達して移動を停止する最も早い時間ステップ) が最小化されます。グループ内の各エージェントは、そのグループのターゲットに割り当てることができるため、同じグループ内のエージェントは交換可能です。ただし、異なるグループのエージェントは互換性がありません。 TAPF は、(標準) MAPF と MAPF の匿名バリアントの一般化として考えることができます。

• (標準の) MAPF は、各グループが 1 つのエージェントのみで構成されている場合、グループの数がエージェントの数と等しくなるという TAPF の結果です。エージェントへのターゲットの割り当ては事前に決定されているため、エージェントは匿名ではありません（交換できません）。
• グループが 1 つだけ (すべてのエージェントを含む) の場合、MAPF の匿名バリアント (ターゲット不変 MAPF とも呼ばれる) は TAPF から取得されます。エージェントは任意のターゲットに割り当てることができるため、交換可能です。これは、フローベースのMAPF法[Yu and LaValle, 2013a; Turpin et al., 2014]を使用して多項式時間で最適に解くことができます。

現在の最先端の最適 TAPF 法は、Conflict-Based Min-Cost Flow [Ma and Koenig、2016] と呼ばれ、検索ベースとフローベースの MAPF 法を組み合わせたものです。数十のグループと数百のエージェントに一般化できます。

3 MAPFの小包交換ロボットルーティング（PERR）と新しい複雑度計算結果

プロキシは通常は匿名ですが、割り当てられたターゲットにペイロード (パッケージ) を運ぶため、匿名ではありません。たとえば、Kiva 倉庫システムでは、運転ユニットは匿名ですが、それらが運ぶ保管ポッドには保管場所が割り当てられているため、匿名ではありません。各エージェントがパッケージを運ぶ場合、問題は（標準の）MAPF と同等になります。実際には、荷物はエージェント間で配達されることが多く、乗り換えによる乗客間のライドシェア [Coltin and Veloso、2014] やオフィスでのロボットを使用した荷物配達 [Veloso et al.、2015] など、より一般的な輸送問題につながります。私たちはこれらの問題を理解するための第一歩としてPERRを使用しました[Ma et al., 2016]。 PERR では、各エージェントが 1 つのパッケージを運び、隣接する頂点の任意の 2 つのエージェントがパッケージを交換でき、各パッケージは指定された宛先に配達される必要があります。したがって、PERR は (標準の) MAPF の修正版として見ることができます。

• PERR 内のパッケージは、(標準の) MAPF 内で自身を移動するエージェントとして見ることができます。
• PERR では、隣接する頂点にある 2 つの区画は頂点を交換できますが、(標準の) MAPF では、隣接する頂点にある 2 つの区画は頂点を交換できません。

K-PERR は PERR を一般化したものであり、パッケージは K 種類に分割され、同じ種類のパッケージは交換可能です。 TAPF ではエージェントがグループに分割され、同じチーム内のエージェントは交換可能であるため、K-PERR は K グループ用の TAPF の修正版と見なすことができます。同様に、PERR は (標準の) MAPF の修正版と見なすことができます。最適な PERR および K-PERR ソリューション (K ≥ 2) を近似することが難しいことを実証しました。私たちの研究の結果、4/3 未満の係数内で最大メイクスパンの最小化のために MAPF と TAPF を近似することは、2 チームのみの TAPF の場合でも NP 困難であることがわかりました。また、MAPF にスワップ操作を追加しても理論的には複雑さは軽減されないが、PERR は MAPF よりも簡単に解決できることも示します。さまざまな実際のシナリオで生じる問題の連続体: 「1 人のエージェントが多数の荷物を扱う」は、典型的な田舎の郵便配達員の問題を生み出し、「荷物と同じ数のエージェント」は、MAPF、TAPF、または PERR を生み出します。これら 2 つの極端な状況を理解することは、他の多くの現実世界のタスクの要件と同様に、一般的な問題を解決するのに役立ちます。

図2: シミュレーションされたKiva倉庫システムにおけるユーザー提供の高速道路

4. 問題の構造とその動きの予測可能性を探る

エージェントは人間と作業スペースを共有し、その動作の一貫性と動作結果の予測可能性は人間の安全にとって重要であるため、既存の MAPF 方法は考慮されません。これにより、与えられたMAPFの例の問題構造を調査し、エージェントがユーザーが提供するハイウェイと呼ばれるエッジのセットに沿って移動するようにインセンティブを与えるスキームを設計する動機が生まれました[Cohen et al.、2015]。我々は、経験グラフに基づく高速道路のアイデア[Phillips et al., 2012]を単純なインフレーションスキームのコンテキストで使用して、高速道路の端を含むパスを返し、エージェント間の直接衝突を回避し、エージェントの動きの一貫性と予測可能性を実現するようにMAPFメソッドを動機付ける新しいヒューリスティック値を導き出します。たとえば、Kiva 倉庫システムでは、図 2 の矢印で示すように、保管場所間の狭い通路に沿って高速道路を設計できます。私たちは、シミュレートされた Kiva 倉庫システムで、このような高速道路により、望ましい MAPF ソリューション コストの制限された準最適性を維持しながら、MAPF アプローチを大幅に高速化できることを実証しました。同じアプローチを使用して、TAPF および PERR の例の質問を構成することもできます。実現可能性調査では、ユーザーが提供する道路と同等の道路を自動的に生成する方法も開発しました。

5. 不完全な計画と実行能力を解決する

最先端の MAPF または TAPF メソッドは、ユーザーが提供する準最適性保証の下で、妥当な計算時間内に数百のエージェントの最適パスまたは衝突のないパスを見つけることができます。 Kiva 倉庫システムのような雑然としたコンパクトな環境でもうまく機能します。しかし、エージェントの計画実行能力は不完全であることが多く、動きを完全に同期できないため、頻繁に再計画が必要になり、時間が無駄になる可能性があります。そこで我々は、シンプルな時間的ネットワークを使用してMAPFソリューションを効率的に後処理し、非ホロノミックロボットに適用可能な計画実行スケジュールを作成するフレームワークを提案する。この計画実行スケジュールでは、ロボットの最大並進速度と回転速度を考慮し、ロボット間の安全距離と余裕度（最も遅い進入時刻と最も早い進入時刻の位置の差として定義）を保証して、不完全な計画実行を軽減し、多くの場合時間のかかる再計画を回避する。[Honig ¨ et al., 2016]このフレームワークは、シミュレーションと実際のロボットで評価されています。 TAPF メソッドと PERR メソッドも同じフレームワークに適用できます。今後の作業で対処すべき問題としては、ユーザーが提供する安全距離の拡大、動作制約の追加、不確実性計画、再計画などがあります。

6 結論

MAPF アプローチを現実のシナリオに一般化し、問題の構造や既存の MAPF アプローチを調査する際に生じる問題に対処するための 4 つの研究方向について説明します。私たちの目標は、MAPF の分野で研究する研究者にとって興味深い研究の方向性を指摘することです。