マルチエージェント経路計画（MAPF）では、通信遅延や物理的制約により、エージェントが計画された時刻に目的地へ到着できない不確実性が存在する。従来のTemporal Plan Graph (TPG)は、エージェント間の通過順序を固定された依存関係として定義するため、あるエージェントの遅延が他のエージェントの不要な待機を招き、全体の実行時間を増大させる。本研究は、MAPF-DPモデルにおける実行時の不確実性を対象とし、固定的な順序制約による効率低下を解決することを目的とする。
従来のTPGがエージェント間の通過順序を固定していたのに対し、実行時に「先着順」で順序を切り替えられる双方向の依存関係を導入した点が新規である。これにより、先行者が退出するのと同時に後続者が進入できる柔軟な実行が可能になる。また、計算資源に応じて性能を向上させられるanytimeアルゴリズムとして、BTPG-naïveとBTPG-optimizedの2種類を提案している。
BTPGは、衝突が発生する地点において、どちらのエージェントが先に進入するかを選択できる双方向のタイプ2エッジのペアを持つグラフ構造である。実行時には、ペアとなるエージェントのうち先に衝突地点に到着した方を優先し、もう一方のエッジを破棄する。構築アルゴリズムとして、深さ優先探索を用いてエッジを双方向ペアへ変換するBTPG-naïveと、特定の頂点を含むサイクルがデッドロックを招かないという性質を利用して、より広範な変換を許容するBTPG-optimizedがある。BTPG-optimizedは、探索パスに特定の頂点が含まれる場合にエッジをスキップする処理を行い、新しいペアが見つからなくなるまで変換プロセスを繰り返す。
6種類のベンチマークマップと複数のエージェント数を用いた計3,900回のシミュレーションにより、エージェントが確率的に遅延する条件下での性能を評価した。比較対象は従来のTPGおよびBTPG-naïveであり、評価指標は平均実行タイムステップ数である。結果として、BTPG-optimizedはTPGと比較して実行タイムステップ数を8%から20%削減し、一貫して優れた性能を示した。BTPG-optimizedは、単独のタイプ2エッジの約50%を双方向ペアに変換しており、計算時間はBTPG-naïveより長いものの、制限時間内ではより多くのペアを発見し高い改善率を実現する。
BTPGは、特定の遅延が発生する意図的な敵対的条件下においては、従来のTPGよりも実行時間が長くなるケースが存在するというトレードオフがある。また、BTPG-optimizedはBTPG-naïveよりも構築に多くの計算時間を要する。
従来のマルチエージェント経路計画（MAPF）では、エージェントが特定の時刻に特定の地点へ到着することを前提とするが、現実の実行における不確実性は衝突やデッドロックを招く要因となる。既存手法であるTemporal Plan Graph（TPG）は、各地点での通過順序を固定することで整合性を保つが、この固定された順序が不要な待機時間を生じさせ、実行効率を低下させる課題がある。本研究では、実行中に通過順序を切り替えることを可能にするBidirectional Temporal Plan Graph（BTPG）という新しいグラフ表現を提案する。BTPGを構築するために、BTPG-naïveとBTPG-optimizedという2つのanytimeアルゴリズムを設計した。実験の結果、BTPGを用いることで、従来のTPGと比較して不要な待機時間を8%から20%削減できることが示された。
マルチエージェント経路計画（MAPF）では、通信遅延や物理的制約によってエージェントが計画通りの時刻に目的地へ到着できない場合、衝突やデッドロックが発生する可能性がある。従来のTemporal Plan Graph（TPG）は、エージェント間の依存関係をグラフで定義することで、遅延が発生しても計画された通過順序を維持し、衝突やデッドロックを回避する手法である。しかし、TPGに基づく厳格な順序遵守は、あるエージェントが遅延した際に、他のエージェントが不要に待機することを強いる課題がある。本研究では、衝突やデッドロックを回避しつつ、通過順序を切り替え可能な依存関係として捉える新しいグラフ表現であるBidirectional Temporal Planning Graph（BTPG）を提案する。BTPGを用いることで、エージェントが実行時に「先着順」で場所を通過することを可能にし、不要な待機時間を最小化する。BTPGを構築する2つのanytimeアルゴリズム、BTPG-naïveおよびBTPG-optimizedを用いた実験では、BTPGに従うことが従来のTPGに従う場合よりも一貫して優れた性能を示し、不要な待機時間を8%から20%削減できることが示されている。
本セクションでは、マルチエージェント経路計画（MAPF）の定義と、その実行における依存関係を管理するTemporal Plan Graph（TPG）について述べている。MAPFは、無向グラフ上で各エージェントが衝突を避けながら始点から終点へ移動する経路の集合を求める問題であり、本研究では実行時の遅延を考慮したMAPF-DPモデルを扱う。従来のTPGは、エージェントの各状態を頂点とし、エージェント内の連続する移動を規定する型1エッジと、エージェント間の先行関係を規定する型2エッジを持つ有向非巡回グラフである。TPGの実行において、グラフに閉路が存在しないことは、衝突やデッドロックなしに全エージェントが目的地に到達できるための必要十分条件である。既存手法には、調整を最小化する計画生成や、遅延を考慮した保守的な計画、あるいは実行時の再計画などが存在するが、これらは計算コストや遅延の事前知識を必要とする。これに対し、提案手法は既存のMAPFプランナーで生成した計画に対し、計画段階で切り替え可能な依存関係を探索・後処理することで、実行時の追加計算を排除する。
従来のTPGでは、後続のエージェントが先行するエージェントの目的地到達を待たなければならないという制約があったため、先行者が退出するのと同時に後続者が進入することが不可能であった。本研究では、後続による追従を許可するために、タイプ2エッジの定義を「後続のエージェントは、先行するエージェントが特定の地点に進入した時刻よりも前には進入できない」という形式に修正する。この修正により、3つ以上のエージェントが互いの位置を循環的に入れ替える「回転サイクル」が発生し得る。回転サイクルは、タイプ2エッジのみで構成され、エッジの数が2つを超えるサイクルとして定義され、デッドロックを引き起こさない。一方で、2つのエージェントのみによる循環はエッジの衝突を招きデッドロックとなるため、有効なTPGであるための条件として、回転サイクル以外のサイクルを含まないことを規定している。
Bidirectional TPG（BTPG）は、衝突が発生する地点において、どちらのエージェントが先に進入するかを切り替えられるように設計された、双方向のタイプ2エッジのペアを持つ時間計画グラフである。従来のTPGではエージェントの通過順序が固定されていたが、BTPGでは「先着順」の実行ポリシーを採用しており、ペアとなるエージェントのうち先に衝突地点に到着した方のエージェントが優先的に通過できるエッジを選択し、もう一方のエッジは破棄する。この手法は、TPGにおける特定のタイプ2エッジに起因する不要な待機時間を削減することを目的としている。3,900回のシミュレーション実験では、BTPGの実行性能がTPGを下回ることはなかったが、特定の遅延が発生する意図的な敵対的条件下では、BTPGの方が実行時間が長くなるケースが存在することが示されている。
BTPGの構築には、MAPFプランナーから得られた有効なTPGを基に、タイプ2エッジを双方向ペアへと変換するBTPG-n（naïve）とBTPG-o（optimized）の2つのアルゴリズムが提案されている。BTPG-nは、深さ優先探索を用いて、回転サイクルや自己サイクル以外の「NRNSサイクル」が含まれないことを確認しながら、エッジを一つずつ双方向ペアに変換する。一方、BTPG-oは、特定の頂点とエッジの組み合わせを含むサイクルはデッドロックを招かないという定理に基づき、BTPG-nではNRNSサイクルと判定されるケースも許容することで、より広範な変換を可能にしている。BTPG-oの深さ優先探索では、現在の探索パスに特定の頂点が含まれている場合にエッジをスキップする処理が追加されており、さらに双方向ペアが増えることで有効性の判定条件が緩和される性質を利用して、新しいペアが見つからなくなるまで変換プロセスを繰り返す。実験の結果、BTPG-oはBTPG-nよりも構築に時間を要するものの、約2倍の双方向ペアを見つけることができ、実行効率の面でより優れていることが示されている。
本実験では、最適解を得るためのMAPFソルバーを用いて生成した計画を基に、提案手法であるBTPG-naiveおよびBTPG-optimizedの性能を、6種類のベンチマークマップと複数のエージェント数を用いた計3,900回のシミュレーションを通じて評価しています。エージェントの一部が確率的に遅延する条件下での評価において、BTPG-optimizedはBTPG-naiveおよび従来のTPGよりも一貫して平均実行タイムステップ数を短縮しており、TPGに対する改善率の中央値は8%から20%の範囲にあります。BTPG-optimizedは、単独のタイプ2エッジの約50%を双方向ペアへと変換しており、実際に使用されるペアの割合は全体の約10%と限定的ですが、これらが実行時間の短縮に大きく寄与しています。計算時間に関しては、BTPG-optimizedはBTPG-naiveよりも長い時間を要しますが、これはより多くの双方向ペアを見つけ出すことによるものであり、任意の制限時間内においてBTPG-optimizedはBTPG-naiveよりも多くの双方向ペアを発見し、より高い改善率を実現する特性を示しています。
本研究では、双方向ペアという概念を導入し、マルチエージェント経路計画における通過順序を表現する新しいグラフ構造であるBTPGを提案した。従来のTPGとは異なり、BTPGは実行中にエージェントが特定の地点での通過順序を切り替えることを可能にする。BTPGを構築する手法としてBTPG-nとBTPG-oの2つのアルゴリズムを提案しており、これらは与えられた計算時間内で解を更新できるanytimeアルゴリズムの特性を持つ。実験の結果、エージェントに遅延が生じた際、BTPGを用いることでTPGを用いる場合と比較して実行効率が8%から20%向上することが示された。また、限られた計算時間内ではBTPG-oがBTPG-nよりも優れた性能を発揮する。以上のことから、計画における依存関係の切り替えを許容することで、再計画を行うことなく実行時間を改善できることが示された。