マルチエージェント経路探索
グリッド環境でのマルチエージェントパス検索の例。

マルチエージェント経路探索（MAPF ）問題は、マルチエージェントプランニングの一例であり、複数のエージェントがそれぞれの位置から指定された目標地点まで、衝突のない経路を計算する問題です。これは最適化問題であり、与えられた目的関数（通常はすべてのエージェントが目標セルに到達するまでの時間ステップ数として定義されます）を最適化する経路を見つけることが目的です。MAPFは経路探索問題をマルチエージェントに一般化したものであり、グラフ理論における最短経路問題と密接に関連しています。

MAPF問題を解くためのアルゴリズムはいくつか提案されています。その複雑さのため、大規模な環境や多数のエージェントが存在する場合、最適なアプローチは実行不可能となることがあります。しかし、自動倉庫や空港管理など、MAPFが利用されるアプリケーションを考えると、ソリューションの効率性と有効性の間でトレードオフを見つけることが重要です。

問題の定式化

古典的なMAPF [ 1 ]問題の要素 は次のとおりです。

  • エージェントのセット。あ＝{1、2、。。。、け}{\displaystyle A=\{1,2,...,k\}}け{\displaystyle k}
  • 無向グラフ 、ここではノード集合、 はエッジ集合です。ノードはエージェントの可能な位置を表し、アークはその位置間の可能な接続を表します。G=(V,E){\displaystyle G=(V,E)}V{\displaystyle V}E{\displaystyle E}
  • 各エージェントをその開始点に関連付けるマップ。s:A→V{\displaystyle s:A\to V}
  • 各エージェントをそのターゲット ポイントに関連付けるマップ。t:A→V{\displaystyle t:A\to V}

時間は離散的であり、各エージェントは各タイムステップで1つのアクションを実行できると仮定します。アクションには2種類あります。エージェントが自身のノードに留まる待機アクションと、エージェントが隣接するノードに移動する移動アクションです。アクションは関数 として定式化されます。つまり、が に隣接し、かつ と異なる場合、は からに移動するアクションを表し、の場合、 はノードに留まるアクションを表します。 a:V→V{\displaystyle a:V\to V}a(v)=v′{\displaystyle a(v)=v'}v{\displaystyle v}v′{\displaystyle v'}v′{\displaystyle v'}v{\displaystyle v}v′{\displaystyle v'}v{\displaystyle v}v=v′{\displaystyle v=v'}

エージェントは、出発点から目的地まで移動するために一連の行動を実行する。エージェントが実行する一連の行動はで表され、プランと呼ばれる。エージェントが自身の位置から出発し、プラン を実行して目的地に到着した場合、 はエージェント のシングルエージェントプランと呼ばれる。[ 1 ] MAPF問題の有効な解は、プランが互いに衝突しないような、シングルエージェントプランの集合（エージェントごとに1つ）である。エージェントが目的地に到達すると、目的地に留まるか、消滅するかのいずれかを選択できる。[ 1 ]i{\displaystyle i}πi=(a1,a2,...,an){\displaystyle \pi _{i}=(a_{1},a_{2},...,a_{n})}i{\displaystyle i}s(i){\displaystyle s(i)}t(i){\displaystyle t(i)}πi{\displaystyle \pi _{i}}πi{\displaystyle \pi _{i}}i{\displaystyle i}k{\displaystyle k}

衝突の種類

MAPF問題に有効な解を与えるためには、エージェントの単独エージェントプランが互いに衝突しないことが必要である。プラン が与えられた場合、式 はプラン の各ステップを実行した後のエージェントの位置を表す。2つのプランとの間には、5つの異なる衝突の種類が考えられる。[ 1 ]k{\displaystyle k}πi{\displaystyle \pi _{i}}πi[x]{\displaystyle \pi _{i}[x]}i{\displaystyle i}x{\displaystyle x}πi{\displaystyle \pi _{i}}πi{\displaystyle \pi _{i}}πj{\displaystyle \pi _{j}}

競合の種類: (a) はエッジ競合、(b) は頂点競合、(c) は後続競合、(d) はサイクル競合、(e) はスワッピング競合です。
  • 頂点衝突： 2つのエージェントが同時に同じ場所を占有する場合、計画と計画の間に頂点衝突が発生します。正式には、頂点衝突は のときに発生します。πi{\displaystyle \pi _{i}}πj{\displaystyle \pi _{j}}πi[x]=πj[x]{\displaystyle \pi _{i}[x]=\pi _{j}[x]}
  • エッジ競合：2つのエージェントが同じエッジを同じ方向に同時に横切るたびに、エッジ競合が発生します。つまり、頂点競合が許可されていない場合、エッジ競合は存在できません。πi[x]=πj[x]{\displaystyle \pi _{i}[x]=\pi _{j}[x]}πi[x+1]=πj[x+1]{\displaystyle \pi _{i}[x+1]=\pi _{j}[x+1]}
  • 後続衝突：後続衝突は、あるタイムステップにおいて、あるエージェントが前のタイムステップで別のエージェントが占有していた場所を占有するときに発生します。数学的には、後続衝突は次のように記述されます。πi[x+1]=πj[x]{\displaystyle \pi _{i}[x+1]=\pi _{j}[x]}
  • サイクル衝突：サイクル衝突は、エージェントの集合（少なくとも3つ）がサイクルを回っているかのように動く場合に発生します。これは、各エージェントがサイクル内で、他のエージェントが1ステップ先に占めていた位置を占めることを意味します。以下の衝突が禁止されている場合、サイクル衝突は発生しません。
  • スワッピング競合：スワッピング競合とは、2つのエージェントが同時に同じエッジを異なる方向に通過し、位置を交換する状況を指します。これは および と表されます。πi[x+1]=πj[x]{\displaystyle \pi _{i}[x+1]=\pi _{j}[x]}πj[x+1]=πi[x]{\displaystyle \pi _{j}[x+1]=\pi _{i}[x]}

MAPF問題を形式化する際に、どの衝突が許容され、どの衝突が禁止されるかを決定することが可能です。許容される衝突と禁止される衝突に関する統一的な標準は存在しませんが、頂点と辺の衝突は通常許容されません。[ 1 ]

目的関数

単一エージェント計画を計算する際、目標はユーザー定義の目的関数を最大化することです。採用すべき標準的な目的関数はありませんが、最も一般的なものは以下のとおりです。[ 1 ]

  • フロー時間：この指標は、各エージェントが目標地点に到達するまでに要した時間ステップを合計することで得られる。正式には、これは に等しい。ここで、計画は衝突のない単一エージェント計画である。∑i∈A|πi|{\displaystyle \sum _{i\in A}|\pi _{i}|}πi,i∈A{\displaystyle \pi _{i},i\in A}
  • メイクスパン: すべてのエージェントがタスクを完了するために必要な時間ステップの数。 と定義され、は有効なソリューションの一部です。maxi∈A|πi|{\displaystyle \max _{i\in A}|\pi _{i}|}πi{\displaystyle \pi _{i}},i∈A{\displaystyle ,i\in A}
  • 期限内での目標到達数の最大化：期限内で目標に到達するエージェントの数を最大化する有効な解決策を見つけることが目的です。[ 2 ]

アルゴリズム

MAPF問題を解決するために、いくつかのアルゴリズムが提案されている。問題は、最適なメイクスパンまたはフロー時間のソリューションを見つけることがNP困難であるということであり、 [ 3 ]平面グラフ、[ 4 ]グリッドに類似したグラフ、[ 5 ]ツリーグラフ[ 6 ]ツリーの葉の数または内部頂点の数に制限がある場合でも困難である。[ 7 ]有界準最適ソリューションに関しては、準最適係数が より小さいメイクスパン最適ソリューションを見つけることがNP困難であることが示されている。[ 8 ]最適なMAPFソルバーは高品質のソリューションを返すが、その効率は低い。代わりに、有界準最適および準最適ソルバーはより効率的であるが、そのソリューションは効果的ではない。また、 MAPF問題を解決するための機械学習アプローチも提案されている。[ 9 ]43{\displaystyle {\tfrac {4}{3}}}

優先順位付けされた計画

計算の複雑さに対処するための1つの可能なアプローチは、優先順位付け計画です。[ 10 ]これは、MAPF問題を単一エージェントの経路探索問題に分離することから成ります。 k{\displaystyle k}

最初のステップは、各エージェントに、その優先度に対応する一意の番号を割り当てることです。次に、優先度に従って、各エージェントが目標地点に到達するための計画を計算します。計画を実行する際、エージェントは、既に計画を計算している、より優先度の高い他のエージェントの経路との衝突を回避する必要があります。 {1,2,...,k}{\displaystyle \{1,2,...,k\}}

このような設定でMAPF問題を解くことは、時間展開グラフにおける最短経路問題に対応する。 [ 11 ]時間展開グラフとは、時間の経過を考慮したグラフである。各ノードは2つのエントリ から構成され、はノード名、は時間ステップである。各ノードは、 が隣接し、時間ステップ において占有されていないノードにリンクされている。 (v,t){\displaystyle (v,t)}v{\displaystyle v}t{\displaystyle t}(v,t){\displaystyle (v,t)}(u,t+1){\displaystyle (u,t+1)}u{\displaystyle u}v{\displaystyle v}u{\displaystyle u}t+1{\displaystyle t+1}

優先順位付け計画の欠点は、たとえそれが健全なアプローチ（有効な解決策を返す）であったとしても、最適でも完全でもないということです。[ 12 ]これは、アルゴリズムが解決策を返すことが保証されておらず、その場合でも解決策が最適ではない可能性があることを意味します。

最適MAPFソルバー

最適MAPFソルバーは4つの異なるカテゴリーに分けられる：[ 12 ]

  • A*の拡張: このカテゴリのアルゴリズムは、A*アプローチの修正バージョンを採用します。
  • 増加コスト木探索：[ 13 ] MAPF問題の新たな形式化が提案されており、これは増加探索木とそれに対応するアルゴリズムを包含する。このアルゴリズムは2つのレベルで構成され、MAPF問題の有効な解は単一エージェントの解の集合から構成されるという仮定に基づいている。
  • 衝突ベースの探索：[ 14 ]このアルゴリズムは、単一エージェントの経路探索問題を解くときと同じように経路を計算し、衝突を避けるために漸進的に制約を追加します。
  • 制約プログラミング: [ 15 ]この種のアプローチでは、MAPFの問題は制約のセットに変換され、SATや混合整数計画法(MIP)ソルバーなどの特定の制約ソルバーを使用して解決されます。

有界準最適MAPFソルバー

有界準最適アルゴリズムは、最適性と解のコストの間でトレードオフを提供します。これらのアルゴリズムは、最適解のコストに係数を乗じた値以下のコストで解を返すため、ある係数によって有界であると言われています。MAPF有界準最適ソルバーは、最適MAPFソルバーと同じ分類に従って分類できます。[ 12 ]

バリエーション

MAPF問題の定義方法によって、例えばグリッド環境であるという事実や、時間が離散的であるという仮定など、様々な側面が変化する可能性があります。このセクションでは、古典的なMAPF問題のいくつかのバリエーションについて説明します。

匿名MAPF

これはMAPFのバージョンの一つで、目標地点は設定されているものの、エージェントには特定の目標が割り当てられていない。[ 16 ]エージェントが目標に到達するかどうかは重要ではなく、目標が達成されることが重要である。このバージョンに若干の修正を加えたバージョンでは、エージェントがグループに分けられ、各グループが目標セットを達成する必要がある。[ 17 ]

複数エージェントによる集荷と配達

MAPF問題は、現実世界のアプリケーションに関連するいくつかの側面を捉えることができません。例えば、自動倉庫では、ロボットが複数のタスクを次々に完了しなければならない場合があります。このため、MAPFの拡張版であるMulti-Agent Pick-up and Delivery (MAPD)​​が提案されています。[ 18 ] MAPD設定では、エージェントは一連のタスクを完了する必要があります。各タスクは、ピックアップ地点と配送地点で構成されます。タスクの完了を計画する際、経路はロボットの現在位置から始まり、ピックアップ地点を通過してタスクの配送地点で終了する必要があります。MAPDは、タスクが段階的に到着するMAPFの「生涯」バージョンと考えられています。[ 18 ]

古典的なMAPFを超えて

エージェントがグリッド環境にあり、速度が一定で時間が離散的であるという仮定は、仮説を単純化している。多くの研究では、速度や方向などのエージェントの運動学的制約[ 19 ]を考慮に入れたり、アークの重みがすべて 1 に等しいという仮定を超えたりしている。[ 20 ]他の研究では、離散時間の仮定を排除し、アクションの持続時間が 1 つの時間ステップに正確に等しいことに焦点を当てている。[ 21 ]現実を反映しない別の仮定は、エージェントが自分達がいる環境の正確に 1 つのセルを占有するというものである。この仮説を克服するための研究がいくつか行われている。[ 22 ]エージェントの形状と幾何学によって新しいタイプの衝突が発生する可能性があることは興味深い。完全に重なっていなくてもエージェント同士が衝突する可能性があるためである。

アプリケーション

MAPF は、いくつかの実際のケースのシナリオに適用できます。

  • 自動倉庫：倉庫物流はMAPFの主要な産業用途です。倉庫の自動化は生産性を向上させることが実証されています。[ 23 ]
  • 空港運営：MAPFアルゴリズムは混雑した空港で航空機を輸送する牽引車両を調整するために使用できます。[ 24 ]この種の問題を最適化できることは環境にも利益をもたらします。
  • 自律移動サービスロボット：サービスロボットは、非産業環境で人間に代わって危険で反復的な作業を実行する自動化エージェントです。[ 25 ]彼らの主な目的は人間を助けることです。
  • ビデオゲーム：このような設定でのMAPFの有用性は、プレイヤーが混雑したビデオゲーム環境でエージェントのチームを移動させる必要があるときに見ることができます。[ 26 ]

参照

参考文献

  1. ^ a b c d e fスターン、ロニ;スターテバント、ネイサン R.フェルナー、アリエル。ケーニッヒ、スヴェン。マ、ハング。ウォーカー、セイン。リー・ジャオヤン。アツモン、ドール。コーエン、リロン。クマール、TKサティシュ。エリ・ボヤルスキー。バルターク、ロマン（2019）。「マルチエージェント パスファインディング: 定義、バリアント、およびベンチマーク」(PDF)。arXiv : 1906.08291。{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
  2. ^ Ma, Hang; Wagner, Glenn; Felner, Ariel; Li, Jiaoyang; Kumar, TK Satish; Koenig, Sven (2018). 「期限付きマルチエージェントパスファインディング」. arXiv : 1806.04216 [ cs.AI ].
  3. ^ Yu, Jingjin; LaValle, Steven M. (2013). 「グラフ上での最適マルチロボット経路計画の構造と扱いにくさ」 . AAAI人工知能会議論文集. 第27巻. pp.  1443– 1449. doi : 10.1609/aaai.v27i1.8541 . S2CID 11655439 . 
  4. ^ Yu, Jingjin (2016年1月). 「平面グラフにおけるマルチロボット最適経路計画の困難性」. IEEE Robotics and Automation Letters . 1 (1): 33– 40. arXiv : 1504.02072 . Bibcode : 2016IRAL....1...33Y . doi : 10.1109/LRA.2015.2503143 . S2CID 10275469 . 
  5. ^ Banfi, Jacopo; Basilico, Nicola; Amigoni, Francesco (2017年10月). 「穴のある2Dグリッドグラフにおける時間最適マルチロボット経路計画の実現可能性」. IEEE Robotics and Automation Letters . 2 (4): 1941– 1947. Bibcode : 2017IRAL....2.1941B . doi : 10.1109/LRA.2017.2715406 . S2CID 36801258 . 
  6. ^ Fioravantes, Foivos; Knop, Dušan; Křištan, Jan Matyáš; Melissinos, Nikolaos; Opler, Michal (2024年3月24日). 「マルチエージェント経路探索のための正確なアルゴリズムと下限値：ツリー状トポロジーの威力」 . AAAI人工知能会議論文集. 38 (16): 17380– 17388. arXiv : 2312.09646 . doi : 10.1609/aaai.v38i16.29686 .
  7. ^フィオラバンテス、フォイヴォス;クノップ、ドゥシャン。クシシュシャン、ヤン・マティアシュ。メリシノス、ニコラオス。オプラー、ミハル。ヴー、トゥン・アイン（2024年12月12日）。 「高度に集中化されたネットワーク上でのマルチエージェント パス検索の解決」。arXiv : 2412.09433 [ cs.CC ]。
  8. ^ Ma, Hang; Tovey, Craig; Sharon, Guni; Kumar, TK; Koenig, Sven (2016年3月5日). 「ペイロード転送を伴うマルチエージェント経路探索と荷物交換ロボットルーティング問題」. AAAI人工知能会議論文集. 第30巻. doi : 10.1609/aaai.v30i1.10409 . S2CID 1585005 . 
  9. ^ Sartoretti, Guillaume; Kerr, Justin; Shi, Yunfei; Wagner, Glenn; Kumar, TK Satish; Koenig, Sven; Choset, Howie (2019年7月). 「PRIMAL: 強化学習と模倣マルチエージェント学習による経路探索」 . IEEE Robotics and Automation Letters . 4 (3): 2378– 2385. arXiv : 1809.03531 . Bibcode : 2019IRAL....4.2378S . doi : 10.1109/LRA.2019.2903261 . S2CID 52191178 . 
  10. ^ Cap, Michal; Novak, Peter; Kleiner, Alexander; Selecky, Martin (2015年7月). 「複数の移動ロボットの軌道調整のための優先順位付け計画アルゴリズム」 . IEEE Transactions on Automation Science and Engineering . 12 (3): 835– 849. arXiv : 1409.2399 . Bibcode : 2015ITASE..12..835C . doi : 10.1109/TASE.2015.2445780 . S2CID 347488 . 
  11. ^ Silver, David (2021). 「協調的パスファインディング」 . AAAI人工知能とインタラクティブデジタルエンターテイメント会議議事録. 第1巻. pp.  117– 122. doi : 10.1609/aiide.v1i1.18726 . S2CID 17714238 . 
  12. ^ a b c Stern, Roni (2019). 「マルチエージェントによる経路探索 – 概要」.人工知能. コンピュータサイエンス講義ノート. 第11866巻. pp.  96– 115. doi : 10.1007/978-3-030-33274-7_6 . ISBN 978-3-030-33273-0. S2CID  204832267 .
  13. ^シャロン・グニ、スターン・ロニ、ゴールデンバーグ・メイア、フェルナー・アリエル（2013年2月）「最適なマルチエージェント経路探索のためのコスト増加木探索」人工知能誌、195 : 470–495 . doi : 10.1016/j.artint.2012.11.006 .
  14. ^シャロン・グニ、スターン・ロニ、フェルナー・アリエル、スターテヴァント・ネイサン・R.（2015年2月）「衝突に基づく探索による最適なマルチエージェント経路探索」人工知能誌219 : 40–66 . doi : 10.1016 /j.artint.2014.11.006 . S2CID 3809045 . 
  15. ^ Bartak, Roman; Zhou, Neng-Fa; Stern, Roni; Boyarski, Eli; Surynek, Pavel (2017年11月). 「Picatにおけるマルチエージェント経路探索問題のモデル化と解決」. 2017 IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI) . pp.  959– 966. doi : 10.1109/ICTAI.2017.00147 . ISBN 978-1-5386-3876-7. S2CID  7819470 .
  16. ^ Kloder, S.; Hutchinson, S. (2006年8月). 「順列不変マルチロボットフォーメーションのための経路計画」. IEEE Transactions on Robotics . 22 (4): 650– 665. Bibcode : 2006ITRob..22..650K . doi : 10.1109/TRO.2006.878952 . S2CID 62805494 . 
  17. ^ Ma, Hang; Koenig, Sven (2016). 「エージェントチームのための最適なターゲット割り当てと経路探索」arXiv : 1612.05693 [ cs.AI ].
  18. ^ a b Ma, Hang; Li, Jiaoyang; Kumar, TK Satish; Koenig, Sven (2017年5月30日). 「オンライン集配タスクのための生涯マルチエージェント経路探索」. arXiv : 1705.10868 [ cs.AI ].
  19. ^ Hoenig, Wolfgang; Kumar, TK Satish; Cohen, Liron; Ma, Hang; Xu, Hong; Ayanian, Nora; Koenig, Sven (2016). 「運動学的制約を伴うマルチエージェント経路探索」第26回国際人工知能合同会議 (IJCAI-17) 議事録.
  20. ^ Barták, Roman; Švancara, Jiří; Vlk, Marek (2018). 「重み付けおよび容量制限付きアークを用いたマルチエージェント経路探索へのスケジューリングベースアプローチ」(PDF) .第17回自律エージェントおよびマルチエージェントシステム国際会議論文集. pp.  748– 756.
  21. ^ Andreychuk, Anton; Yakovlev, Konstantin; Surynek, Pavel; Atzmon, Dor; Stern, Roni (2022年4月). 「連続時間によるマルチエージェントパスファインディング」.人工知能. 305 103662. arXiv : 1901.05506 . doi : 10.1016/j.artint.2022.103662 . S2CID 207791641 . 
  22. ^ Li, Jiaoyang; Surynek, Pavel; Felner, Ariel; Ma, Hang; Kumar, TK Satish; Koenig, Sven (2019年7月17日). 「大規模エージェントのためのマルチエージェント経路探索」. AAAI人工知能会議論文集. 第33巻. pp.  7627– 7634. doi : 10.1609/aaai.v33i01.33017627 . S2CID 53687939 . 
  23. ^ Wurman, Peter R.; D'Andrea, Raffaello; Mountz, Mick (2008年3月20日). 「倉庫における数百台の協調型自律走行車両の連携」. AI Magazine . 29 (1): 9. doi : 10.1609/aimag.v29i1.2082 . S2CID 10475273 . 
  24. ^ Morris, Robert; Pasareanu, Corina S .; Luckow, Kasper; Malik, Waqar; Ma, Hang; Kumar, TK Satish; Koenig, Sven (2016). 「空港地上業務の計画、スケジュール、監視」 AAAIワークショップ：ハイブリッドシステムの計画.
  25. ^ Veloso, Manuela; Biswas, Joydeep; Coltin, Brian; Rosenthal, Stephanie (2015). 「CoBots: Robust Symbiotic Autonomous Mobile Service Robots」 . IJCAI'15: Proceedings of the 24th International Conference on Artificial Intelligence . AAAI Press. pp.  4423– 4429. ISBN 978-1-57735-738-4。
  26. ^ Ma, Hang; Yang, Jingxing; Cohen, Liron; Kumar, TK Satish; Koenig, Sven (2017). 「実現可能性調査：混雑したビデオゲーム環境における非均質チームの移動」 AAAI人工知能・インタラクティブデジタルエンターテイメント会議論文集13 ( 1): 270– 272. arXiv : 1710.01447 . doi : 10.1609/aiide.v13i1.12919 .
「 https://en.wikipedia.org/w/index.php?title=Multi-agent_pathfinding&oldid=1309856318」より取得