本研究は、エージェントの集合 $\mathcal{A}$、タスクの集合 $\mathcal{T}$、およびタスク間の先行制約 $\mathcal{P}$ が定義された環境において、タスクの割り当て、実行順序、および衝突のない経路を決定するTAPF-PC問題を扱う。従来のMAPF-PCは各エージェントに固定されたタスク順序が与えられるが、TAPF-PCではどのエージェントがどのタスクを実行するかという割り当ての柔軟性が解の品質に大きく影響する。目的関数は、各エージェントが最後に割り当てられたタスクを完了する時刻の総和（sum of costs）を最小化することである。
先行制約によってタスク間の依存関係が複雑に絡み合う条件下において、タスクの所有権を固定せず、再割り当てを伴う大規模近傍探索（LNS）を導入した点が新規である。従来の固定割り当てに基づく手法では解空間が制限されるが、提案手法はタスクの依存関係（推移的閉包）を考慮した破壊と修復を行うことで、先行制約のボトルネック解消とルーティング効率の向上を同時に実現する。
提案手法は、外層のタスク再割り当て探索と内層のMAPF-PC修復層からなる二段階のLNSフレームワークである。破壊フェーズでは、選択したタスクとその後続タスクの推移的閉包を抽出して破壊集合 $\mathcal{D}$ を構成し、待機時間 $w_{i}$ や先行条件の実行間隔 $s_{i,j}$ に基づく演算子を用いて対象を選択する。修復フェーズでは、挿入コストの差に基づくRegret-Based Repairや、先行条件のリリース境界 $r_{i}$ を考慮したMAPF-PC Neighborhood Repairを用いる。低レベルプランナーには、時間制約を考慮しつつ境界の衝突を許容するrelaxed modeのSIPPSを採用している。
empty、random、warehouseの4種類のマップを用いた実験において、最大でエージェント数 $n=100$、タスク数 $m=100$ の規模で評価を行った。比較対象としてRegret、Local–PBS、Global–PBS、Global–CBSの4手法を用い、コスト合計（SoC）の減少量や改善頻度を指標とした。結果として、提案手法は固定割り当てのシード解と比較してインスタンスの $89.1\%$ で解の品質を向上させ、特にGlobal–PBSが多くの設定で最大のコスト削減率を達成した。
先行制約の密度が非常に高い「high-precedence regime」においては、グローバルな修復が困難になるため、Global–PBSの成功率が急落しLocal–PBSの方が安定するというトレードオフが存在する。また、本手法は実行可能な初期解を前提としている。今後の課題として、制約が密な領域に対応する強力な修復ポリシーの設計や、タスクが動的に到着する生涯学習（lifelong）設定への拡張が挙げられる。
本研究では、タスクの割り当て、先行制約の充足、および経路コストを同時に最適化する、タスク割り当てと経路探索を伴う先行制約付き問題（TAPF-PC）を提案している。この問題は、タスクの順序が固定されている従来のMAPF-PCを拡張したものであり、どのエージェントがどのタスクを実行するかという割り当ての柔軟性が解の品質に大きく影響する。提案手法は、実行可能解となるMAPF-PCのシード解から開始し、再割り当てに基づく近傍修復を繰り返すことで、選択された近傍内で実行可能性を維持しながら解を逐次的に改善する大規模近傍探索（LNS）アプローチである。複数のベンチマークを用いた実験の結果、最適な設定では、タスク割り当てを固定したシード解と比較して、インスタンスの $89.1\%$ において解の品質が向上することが示された。これにより、先行制約が存在する条件下においても、LNSが柔軟な再割り当てによる利得を効果的に捉えられることが実証されている。
本研究では、タスクの割り当て、先行制約の遵守、および衝突回避を同時に最適化する必要があるTask Assignment and Path Finding with Precedence Constraints (TAPF-PC) を扱う。従来のMAPF-PCは各エージェントに固定された目標シーケンスが与えられる設定であるが、TAPF-PCはどのエージェントがどのタスクを実行するかという割り当ての選択肢まで含めて探索する必要があり、固定割り当てにおける最適解がTAPF-PCにおける最適解になるとは限らない。提案手法は、大規模な探索空間に対応するためにLarge Neighborhood Search (LNS) フレームワークを採用しており、実行可能なMAPF-PCの解を初期解として、先行制約を考慮したタスクの近傍を選択して再割り当てを行う。この手法は、外側の探索層でタスクの再割り当てを行い、内側の修復層でMAPF-PCの手法を用いて、近傍境界で生じるタイミングや経路の制約を満たすように領域を修復する二段階の構造を持つ。実験の結果、柔軟な再割り当てを行うことで、テストしたインスタンスの89.1%において解の品質が向上することが示された。
本研究では、環境を無向グラフ $G = (V, E)$ としてモデル化し、エージェントの集合 $\mathcal{A}$ とタスクの集合 $\mathcal{T}$、およびタスク間の先行制約の集合 $\mathcal{P}$ を定義する。各タスク $t \in \mathcal{T}$ には目標頂点 $g_t \in V$ が割り当てられており、先行制約 $(t_i, t_j) \in \mathcal{P}$ はタスク $t_i$ が完了した後にのみ $t_j$ が完了可能であることを示す。問題設定は、エージェントごとに固定されたタスク順序の集合 $\mathcal{S}$ が入力として与えられる MAPF-PC と、タスクの割り当ておよび順序自体を解として決定する TAPF-PC の2種類に分けられる。MAPF-PC において、タスク $t$ の完了時刻を $C(t)$ とすると、解は衝突を回避しつつ、各エージェント内の連続するタスクの順序および全域的な先行制約 $C(t_i) < C(t_j)$ をすべて満たす必要がある。TAPF-PC では、エージェントごとのタスク順序の集合 $\mathcal{S}$ を決定することを含め、オフライン設定において各エージェントが最後に割り当てられたタスクを完了する時刻の総和（sum of costs）を最小化することを目指す。
本研究では、先行順序制約（Precedence Constraints）を持つマルチエージェント・タスク割り当ておよび経路計画（TAPF-PC）を解くために、実行可能な完全解を対象とした大規模近傍探索（LNS）フレームワークを提案している。探索は、既存のMAPF-PCソルバーを用いて得られた、エージェントごとのタスク順序と衝突のない経路が確定している初期解から開始される。本手法の核となる特徴は、近傍の定義をエージェントや経路ではなくタスクに対して行う点にあり、あるタスクを削除した際に依存関係にある後続タスクの再検討や、タスクを修復する際に先行順序グラフの整合性を保つための先行タスクの復元を考慮する。アルゴリズムは二層構造となっており、外層のLNSがタスクの再割り当てと局所的な順序決定を探索し、内層では、現在のグローバルな解に埋め込まれた制約付きMAPF-PCの部分問題として、誘導された局所的な修復問題を解く。各反復では、タスク近傍の選択、破壊、再割り当てと順序の提案、修復問題の解決、そして修復された経路を既存の解に結合するプロセスを経て、受容ルールに基づき現在の最良解を更新する。
本手法は、先行条件付きマルチエージェント・タスク割り当ておよび経路計画（TAPF-PC）を解くためのLarge Neighborhood Search（LNS）フレームワークを提案している。探索は、先行条件を考慮した貪欲法とMAPF-PCソルバー（PBS-PCやCBS-PCなど）を用いて生成された、タスクの割り当て、エージェント内の実行順序、および衝突のない経路を含む初期解から開始される。破壊フェーズでは、タスクをシードとして選択し、先行グラフにおける後続タスクの推移的閉包をとることで、依存関係のあるタスク群を破壊集合 $\mathcal{D}$ として抽出する。破壊演算子には、従来のコストや衝突に基づくものに加え、先行条件のボトルネックを特定するPrecedence-Wait（待機時間 $w_{i}$ が大きいタスクを対象）やLow-Slack（先行条件の実行間隔 $s_{i,j}$ が小さいエッジを対象）といった先行条件を考慮した手法が導入されている。修復フェーズには、挿入コストの差 $c_{i,2} - c_{i,1}$ に基づくRegret-Based Repairと、先行条件のリリース境界 $r_{i}$ を考慮してトポロジカル順序でタスクを再挿入するMAPF-PC Neighborhood Repairの2種類がある。経路計画の高速化のため、修復段階ではSIPPS（Safe Interval Path Planning with Soft constraints）を低レベルプランナーとして採用しており、先行条件による時間制約を考慮しつつ、境界における衝突を許容するrelaxed modeでの修復も可能である。最終的に、LNSループ終了後に、得られた割り当てと順序を固定した状態でインスタンス全体に対してフルスケールのMAPF-PCソルバーを適用する後処理を行うことで、解の品質を向上させている。
本実験では、先行制約付きマルチエージェント・タスク割り当ておよび経路計画（TAPF-PC）における、修復戦略や再割り当て範囲、チーム規模、先行制約密度が性能に与える影響を評価する。ベンチマークは、empty、random、warehouseの4種類のマップファミリーから構成され、規模に応じてsmall、medium、largeの3つのティアに分類され、最大でエージェント数 $n=100$、タスク数 $m=100$ の大規模インスタンスまで扱う。比較対象の手法は、Regret、Local–PBS、Global–PBS、Global–CBSの4種類であり、これらは貪欲な再挿入、再割り当て範囲（Local vs Global）、およびMAPF-PCソルバーの種類（PBS vs CBS）の影響を分離して検証するために選定されている。LNSの構成として、破壊サイズ $d=5$、ALNSによる適応的な破壊選択、および閾値受理（Threshold Acceptance）を採用しており、受理ルールには冷却係数 $\alpha=0.95$、初期温度 $T_0$ を初期コスト合計の $10\%$ と設定している。評価指標には、コスト合計（SoC）の絶対減少量 $\Delta \text{SoC}$、相対減少量、および改善頻度（$\Delta \text{SoC} > 0$ となるインスタンスの割合）を用い、先行制約による待機時間の減少についても追跡する。実行時間はティアごとに制限されており、smallでは 300秒、mediumでは 600秒、largeでは 1200秒の壁時計時間予算がLNSのメインループに割り当てられている。
提案手法の修復戦略を比較した結果、Regret、Local–PBS、Global–PBS、Global–CBSのすべてがRegretベースラインを大幅に上回り、特にGlobal–PBSが最も優れた性能を示した。Global–PBSは、多くの小規模および中規模設定において最大のコスト削減率（median relative reduction）を達成し、大規模なPBSシードの倉庫環境においても、75.0%のインスタンスで改善が見られる唯一の手法であった。探索の挙動に関しては、Global–PBSは実行開始直後に急速に改善が進むものの、十分な実行時間がある場合には、初期に先行するLocal–PBSを追い抜き、より高い改善率に到達する傾向がある。スケーラビリティの観点では、エージェント数が増加してもGlobal–PBSの優位性は維持されるが、先行制約の密度が高まる「high-precedence regime」においては、Global–PBSの修復成功率が急落するため、Local–PBSの方が安定して高い性能を示す。コスト削減の要因については、先行制約に起因する待機時間の削減が寄与しているものの、Global–PBSがLocal–PBSよりも高い最終的なコスト削減を実現していることから、先行制約のボトルネック解消だけでなく、経路コストの低いエージェントへのタスク再割り当てによるルーティング効率の向上も重要な役割を果たしている。
本研究では、タスクの割り当て、順序付け、および衝突のない経路計画を先行制約の下で同時に決定する必要がある TAPF-PC 問題を検討し、タスクの所有権を固定する手法では解空間が制限され、改善の機会を逃すことを示した。提案手法は、外側の再割り当て探索と内側の MAPF-PC 修復サブ問題を分離した LNS フレームワークであり、低レベルプランナーとして SIPPS を統合している。実験の結果、固定割り当ての初期解と比較して 89.1% のインスタンスで性能が向上し、特に閾値受理型の Global–PBS 変種が最も優れた性能を示した。一方で、先行制約が非常に密な設定では、グローバルな修復が困難になるため、Local–PBS の方が効果的になるという限界も明らかになった。今後の課題として、制約が密な領域に向けたより強力な修復ポリシーの設計や、タスクがオンラインで到着し先行関係が時間とともに変化する生涯学習（lifelong）設定への拡張が挙げられる。