対象は、障害物を含む4近傍グリッド上で、各エージェントが位置と向きを持ちながら、逐次的に与えられる目標へ移動する多エージェント経路計画である。エージェントは現在の目標に到達すると、外部のタスク割当モジュールから次の目標を受け取るが、将来の目標は事前には利用できない。オンラインLMAPF-Tでは回転にも行動を要するため、次の1時刻だけを選ぶPIBTは、回転を伴わない場合より性能が低下しうる。本文抜粋では、タスク割当そのものは研究対象外であり、主にエージェントの効率的な経路生成を扱う。
中心的な提案は、PIBTにマルチアクション操作を導入したEPIBTである。別の経路計画器を呼び出さず、限定長の操作候補を直接扱うことで、複数時刻を考慮しつつPIBTの高速なルールベース処理を保とうとする。さらに、1ステップ中のエージェント再訪問と操作継承を加え、既に選んだ行動を状況に応じて変更したり、他のエージェントから継承された操作を再利用したりする。EPIBTをLNSとグラフ誘導に接続した構成について、著者らはオンラインLMAPF-Tで既存の最先端手法を上回ると報告する。
通常のPIBTは、目標までの距離などに基づく優先順位でエージェントを順に処理し、衝突しない次の行動を選ぶ。あるエージェントの行動が別のエージェントを押し出す必要を生じさせた場合、優先度を継承して再帰的に処理し、失敗時にはバックトラックして別の行動を試す。EPIBTでは、長さ3から5程度の限定された操作を候補として扱い、操作が失敗すれば取り消して次を試す。エージェントは衝突回避行動を見つけた後でも同じステップ内で再訪問されうるが、再訪問は計算量を抑えるため制限される。自身の候補が失敗した場合には、他のエージェントから継承した操作が割り当てられる。さらに、残った計算時間でLNSを実行し、目標への近さを表す指標が改善する解を受理し、グラフ誘導も組み合わせる。
評価は、League of Robot Runnersで使われた5マップ、random-32-32-20、brc202d、Paris-1-256、sortation、warehouseを対象に行われた。エージェント数を変えた複数インスタンスで、公開アーカイブの目標系列を用い、エージェント間の目標割当による影響を避けるため、タスクプールを循環的に割り当てた。実験は単一スレッドのIntel Xeon Gold 6338上で、各時刻1秒の計算予算を使い、通常は5000時刻、random-32-32-20では1000時刻を実行した。アブレーションではマルチアクション操作、再訪問、操作継承、操作長3・4・5を比較し、PIBT、Causal PIBT、LNSやグラフ誘導を含む構成とスループットを比較した。抜粋には全インスタンスの正確な数値、各ベースラインの実装条件、統計的検定の詳細は示されていない。
再訪問は結果を大きく改善する一方、無制限に許すと時間予算を使い切って性能を悪化させるため、制限がスループットと実行時間を安定させる。操作を長くすると実行時間が増え、複数エージェントの衝突が増えて現在の解消機構で処理できない場合があるため、全体として長さ3が有利だと説明される。ただし、sortationやwarehouseのような大規模マップで5000エージェントを扱う場合には、長い操作が時にスループットを改善する。理論的性質は、隣接ノードが単純サイクルを形成するという元のPIBTの仮定を引き継ぐため、任意のグラフでの保証ではない。著者らは将来課題として、多エージェント衝突処理の改善とLNS・グラフ誘導との統合最適化を挙げている。
古典的MAPFでは、複数エージェントが開始位置から指定目標へ衝突なく到達する必要があり、エージェント数や密度が増えると最適解探索は難しくなる。CBSやICTSなどの最適性を保証する手法は、大規模問題で実行時間と拡張性に課題があるため、高速な初期解生成器、ウィンドウ探索、anytime最適化が研究されてきた。PIBTは、次の1時刻だけを考慮しながら多数のエージェントの衝突回避行動をミリ秒単位で選べるため、低レベルプランナや行動サンプラとして広く利用されている。
各エージェントの状態はグリッド上の位置と向きで表され、利用可能なのは現在の目標だけである。移動に加えて回転を行う行動モデルでは、向きを変えるために複数の行動を消費することがある。研究対象のオンラインLMAPF-Tは、限られた時間予算の下で、外部から継続的に与えられる目標を処理する。抜粋では、厳密な行動集合の全定義や衝突規則の全詳細は完全には提示されていない。
EPIBTの操作候補は、通常の1ステップ行動ではなく、限定長の行動列として扱われる。抜粋では、回転モデルで全方向移動を模倣するために、FWW、RFW、CFW、RRF、WWWという5種類の操作を用いたと説明される。操作長が1から5へ増えると、到達可能なセル、状態、占有セル列の候補が増え、探索負荷も高くなる。PIBTの性質を保つ理論分析は、元のPIBTと同じグラフ上の仮定に依存する。
アブレーションでは、マルチアクション操作だけでなく、再訪問と操作継承を個別に評価した。操作長3、4、5を比較し、実行時間とスループットへの影響を調べた。総合評価では、EPIBT単体と、LNSおよびグラフ誘導を組み合わせた構成を既存のPIBT系手法や他の最先端手法と比較した。抜粋からは、各マップのエージェント数の全リストや再現用コードの詳細までは確認できない。
EPIBTは、抜粋で示された5マップすべてにおいてPIBTとCausal PIBTを一貫して上回ったと報告される。再訪問の導入は大きな改善をもたらしたが、無制限の再訪問は時間予算超過につながり、制限付き再訪問がより安定した。エージェント数が10000の場合でも、次の行動の計算は100ミリ秒未満だったとされる。EPIBTにLNSとグラフ誘導を加えた構成は、5マップ中3マップでスコア1.0を達成し、残りの2マップでも多くの場合に他手法を上回ったが、低エージェント数では他手法が上回る場合もあった。
本研究は、回転行動モデル向けにPIBTを拡張するEPIBTを提案した。マルチアクション操作によって、別個の経路計画アルゴリズムを使わずに短い複数時刻の依存関係を扱う。再訪問と操作継承は性能と効率をさらに改善し、LNSとグラフ誘導を組み合わせた構成は、提示されたオンラインLMAPF-T評価で既存手法を上回る性能を示したと結論づけられる。
評価は5つの競技由来マップと、固定された目標系列・タスク割当方式に基づいており、他の環境や割当器への一般化は抜粋だけでは確立されない。理論的性質は単純サイクルに関する仮定を必要とし、長い操作で生じる多エージェント衝突は現在の方法で十分に解消できないことがある。LNSとグラフ誘導を使う総合構成の厳密な数値比較や、個別コンポーネントの詳細な寄与は、提示された抜粋には完全には含まれていない。
PIBTの魅力であるミリ秒級の局所的な行動選択を維持しながら、回転に時間がかかるロボット群へ適用範囲を広げようとする点が重要である。倉庫物流や輸送など、オンラインに目標が到着し、大規模なエージェント数を扱う用途に対して、軽量な低レベル計画器と解品質改善を組み合わせる設計上の示唆を与える。
回転行動を含むMAPF、LMAPF、MAPDや、PIBTを低レベルプランナとして利用する研究者に適している。高速なオンライン経路生成と、LNS・グラフ誘導による解品質改善の統合に関心がある読者にも有用である。最適性保証や一般グラフでの理論保証を主目的とする読者は、提示された仮定と抜粋の数値的限界を確認したうえで読むべきである。