グラフ上で多数のエージェントが衝突を避けながら各々の目的地へ到達する経路を求めるマルチエージェント経路探索（MAPF）を対象とする。自動倉庫のような実用的なシナリオでは、エージェントが目的地到着後に新たな目的地を受け取る、オンラインかつ継続的な解決が求められる。しかし、従来の探索ベースやコンパイルベースの最適解を求める手法は、エージェント数が数百規模に達すると計算量が爆発し、リアルタイムな更新が困難になるという課題がある。
動的な優先度継承とバックトラッキングを組み合わせることで、大規模かつ動的な環境への対応を実現した。隣接するノードのペアがすべて長さ3以上の単純サイクルに属するグラフ（二重連結グラフなど）においては、エージェントの数に関わらず、すべてのエージェントが有限時間内に目的地へ到達できることを理論的に証明している。
各タイムステップにおいて、エージェントは目的地までの距離に基づき更新される独自の優先度に従い、優先度の高い順に次の移動先を決定する。移動先の決定にあたっては、すでに高い優先度のエージェントによって要求されたノードや、衝突（頂点衝突およびスワップ衝突）を引き起こすノードを避ける。低優先度エージェントが占有するノードをより高い優先度のエージェントが要求する場合、低優先度エージェントが一時的にその高い優先度を継承することで、優先度逆転による停滞を解消する。もし有効な移動先が見つからない場合は、バックトラッキングを用いて、優先度継承を行ったエージェントに対して別の移動先を再帰的に要求し、衝突のない移動を試みる。
大規模なグリッドマップを用いた実験において、既存の最適解を求める手法が計算時間の制約により解けない条件下でも、PIBTは5秒以内という極めて短い実行時間で許容可能な解を出力した。エージェント数が1000に達するストレス・テストにおいても、1ステップあたりの実行時間は約10ミリ秒と、エージェント数に対して線形に近い増加に留まることを確認した。また、自動倉庫のタスクを模したマルチエージェント集荷配送（MAPD）の実験では、既存のToken Passing手法と比較して、実行時間の短縮および解の品質の両面で優れた性能を示した。
本手法は、エージェントの移動が同期していることを前提としている。実環境におけるエージェント間の非同期な動きへの対応は今後の課題である。
本研究では、自動倉庫のように数百台以上のエージェントが稼働する環境において、オンラインかつ継続的に動作するマルチエージェント経路計画（MAPF）のための新しい劣最適アルゴリズムであるPriority Inheritance with Backtracking（PIBT）を提案する。PIBTは、複数のエージェントの隣接する移動に焦点を当てる適応的な優先順位付けスキームに基づいており、スケーラブルで予測可能な計算時間での解の出力が可能である。理論面では、隣接するノードのペアがすべて単純なサイクルに属するグラフ（二重連結グラフなど）において、エージェントの数に関わらず、すべてのエージェントが有限時間内に目的地に到達することを証明している。実験では、実ロボットを用いたデモンストレーションを含む様々なシナリオにおいて、数百台のエージェントが存在する場合でも即座に許容可能な解を生成し、既存のMAPF手法では解決できない大規模なインスタンスも扱えることを示している。さらに、自動倉庫における荷物の搬送を模した反復的なシナリオにおいて、PIBTは既存手法と比較して実行時間と解の品質の両面で優れていることが確認された。
本研究では、多数のエージェントが衝突を避けながら目的地へ到達する経路を求めるマルチエージェント経路探索（MAPF）に対し、反復的かつオンラインで動作する新しい劣最適アルゴリズムであるPriority Inheritance with Backtracking（PIBT）を提案する。PIBTは、低優先度のエージェントがより高い優先度のエージェントの移動を妨げる際に、一時的にその高い優先度を継承させる仕組みと、エージェントの立ち往生を防ぐバックトラッキングプロトコルを組み合わせている。この手法は、グラフの隣接するすべてのノードが単純なサイクルに属する場合（二重連結グラフなど）において、すべてのエージェントが有限時間内に目的地へ到達できる到達性を理論的に保証する。各タイムステップの計算量は、エージェントの数をn、グラフの直径をD、目的地までの距離評価に要する時間をtとすると、O(n * D * t)となり、大規模な問題でも短時間での実行が可能である。実験では、数百台のエージェントが存在する大規模なグリッドマップにおいて、既存の優先度ベースや探索ベースの手法よりも数桁高速に動作し、平均的な劣最適性を一定以下に抑えつつ5秒以内に解を導出できることを示している。また、自動倉庫における荷物搬送のような反復的なマルチエージェント集荷配送（MAPD）のシナリオにおいても、既存手法を上回る実行速度と解の品質を達成しており、局所的な相互作用のみに依存するため分散実装への高い適性も有している。
マルチエージェント経路探索（MAPF）は、グラフ上の各エージェントに対して衝突のない経路を割り当てる問題であり、グラフの構造や最適化基準によってNP困難またはNP完全となる。既存手法は、探索ベース、コンパイルベース、優先度付き計画、ルールベース、学習ベースの5つの形式に分類される。探索やコンパイルベースの手法は完全かつ最適であるが、数百規模のエージェントを扱うオンラインやライフロングのシナリオでは、計算時間の面で課題がある。提案手法であるPIBTは、優先度付き計画とルールベースを組み合わせた手法であり、動的な優先度とバックトラッキングを用いることで、安全なプッシュ操作を組み合わせて実行する。PIBTは、全ての個体が最終的に目的地に到達することを保証するものの、全エージェントが同時に目的地に到達することを保証しないという意味で不完全（incomplete）とされるが、これはエージェントが継続的に活動するライフロングな状況を想定した設計である。また、PIBTは1ステップごとの計画を繰り返す性質を持つため、エージェントが動的に増減するオンラインMAPFへの適用も容易である。
本研究では、従来の単発的なマルチエージェント経路計画（MAPF）と、継続的かつオンラインなシナリオを扱うマルチエージェント集荷配送（MAPD）の2つの問題を定義している。MAPFは、自己ループや多重辺を持たず、任意のノード間が到達可能な強連結グラフにおいて、各エージェントが初期位置から目標位置へ移動する経路を求める問題である。経路計画においては、エージェントが同一時刻に同じノードを占有する頂点衝突と、エージェント同士が位置を入れ替えるスワップ衝突の両方を回避しなければならない。MAPFの解の質は、全エージェントが目標に到達するまでの各時刻の総和であるsum-of-costs、または全エージェントが目標に到達し終える時刻であるmakespanによって評価される。MAPDは、時間の経過とともにタスクが追加される動的な環境を想定しており、各タスクは集荷地点と配送地点のペアで構成され、エージェントはこれらを順番に訪問することでタスクを完了させる。MAPDの目的関数には、タスクの生成から完了までの時間であるサービスタイム、および全タスクが完了する時刻であるmakespanが用いられる。
PIBT（Priority Inheritance with Backtracking）は、反復的なマルチエージェント経路探索（MAPF）を解くための、優先度継承とバックトラッキングを組み合わせたアルゴリズムです。各タイムステップにおいて、エージェントは目的地への距離に基づき更新される独自の優先度に従い、高い優先度を持つエージェントが要求したノードを避けながら、優先度の高い順に次の移動先を決定します。低優先度エージェントが占有しているノードを、より高い優先度を持つエージェントが要求する場合、低優先度エージェントは一時的にその高い優先度を継承することで、優先度逆転によるデッドロックを回避します。もし優先度継承の結果として有効な移動先が見つからない場合は、バックトラッキングによって移動先の再計画を要求し、有効な結果が得られるまで再帰的に探索を繰り返すことで、衝突のない移動を保証します。グラフに適切な単純サイクルが存在する場合、すべてのエージェントが最終的に目的地に到達できる到達性が理論的に証明されています。1タイムステップあたりの計算量は、エージェントの数を n、各エージェントの候補ノード数を d とすると O(n * d log d) であり、大規模な問題や、迅速な初期解が求められるAnytime planningへの適用に適した非常に低コストな手法です。
PIBTは、マルチエージェント経路探索（MAPF）およびマルチエージェント集荷配送（MAPD）の両タスクにおいて、高いスケーラビリティと許容可能な解の品質を両立することが評価実験により示された。MAPFの実験では、1000エージェント規模の極めて高密度な環境においても、最適解を求める手法が計算量により解けない中で、PIBTは5秒以内という極めて短い実行時間で解を出力できる。解の品質については、疎な環境では他の手法と同等であるが、高密度な環境では完了時刻の制限により失敗する場合があるものの、補完的なソルバーを用いるPIBT+によって成功率を大幅に向上させることが可能である。MAPDの実験では、既存のToken Passing手法と比較して、PIBTは実行時間が大幅に短縮されるだけでなく、空きエージェントの優先順位付けによってタスク割り当て済みエージェントの経路が短縮されるため、サービス時間や完了時刻の面でも同等以上の性能を示す。さらに、スケーラビリティのストレス・テストでは、エージェント数が1000に達しても1ステップあたりの実行時間は約10ミリ秒と線形に近い増加に留まり、実機ロボットを用いたオンラインかつ継続的な運用シナリオでの動作も確認されている。
本研究では、エージェントの隣接する移動に焦点を当て、単純な優先順位付けに基づくスケーラブルな反復的マルチエージェント経路計画アルゴリズムであるPIBTを提案している。実験結果により、PIBTは大規模な問題に対して他のソルバーよりも迅速に解を導出できること、ピックアップおよびデリバリー問題において既存手法を上回る性能を示すこと、そして数千規模のエージェントが存在する場合でもリアルタイムでの計画が可能であることが示された。さらに、実ロボットを用いた実行実験も提示されている。今後の研究方向としては、エージェントの移動が同期していることを前提とする従来の設定から、実環境におけるエージェント間の非同期性を考慮した環境への適用が挙げられる。
PIBT+はPIBTとどう違う？どうやって成功率を向上した？
PIBT+とPIBTの違い、および成功率の向上方法については以下の通りです。
PIBTとPIBT+の違い
PIBT+は、PIBTに「補完的なソルバー（complement solver）」を追加したものです（Section 5.1.1）。PIBT単体では、グラフにサイクルが存在しない場合や、すべてのエージェントが同時にゴールに到達することを保証しない（reachabilityのみを保証する）性質があるため、失敗することがあります（Section 4.3.1, 5.1.2）。PIBT+は、このPIBTの欠点を補うために設計されています。
成功率の向上方法
PIBT+は、PIBTの解を補完するために別のソルバーを用いることで、成功率を劇的に向上させています（Section 5.1.2）。
補完ソルバーは具体的にどのような処理を行う？makespan制限とは何？
ご質問いただいた点について、論文の記述に基づき回答します。
補完ソルバーの具体的な処理について
論文内では、補完ソルバーが具体的にどのような計算アルゴリズムや内部処理を行うかについての詳細な記述はありません。
ただし、実験設定（Section 5.1.1）において、PIBT+は「PIBTの解を補完するために（to complement the solutions of PIBT）」別のソルバーを用いるとされており、実験では「PS+（Push and Swapの拡張版）」が使用されています。また、混雑した状況では、PIBTが解を見つけられず、補完ソルバーであるPS+が使用されることで解の質が低下する場合があることが述べられています（Section 5.1.2）。
makespan制限について
makespan制限とは、アルゴリズムが解を出す際に許容される「最大経過時間（タイムステップ数）」の閾値のことです。論文では、以下の文脈で使用されています。