前提（優先）制約付きのマルチエージェントタスク割当と経路探索のための大規模近傍探索

arXiv cs.RO / 2026/4/1

📰 ニュースSignals & Early TrendsIdeas & Deep AnalysisModels & Research

共有:

要点

本論文は、TAPF-PC（優先関係付きのタスク割当と経路探索）を研究する。これは、MAPF-PCを一般化したものであり、各タスクを担当するエージェントの割当と、衝突回避されたエージェントの経路の両方を最適化しつつ、タスク間の順序関係を尊重する。
実行可能なMAPF-PCの初期解から開始し、各ローカル探索領域内で実行可能性を維持しながら、割当（再割当）に基づく近傍修復を反復して解を改善する、大規模近傍探索手法を提案する。
複数のベンチマーク系列と問題のスケーリング条件にわたる実験の結果、最適な構成は固定割当アプローチよりも大幅に優れており、89.1%のインスタンスで改善を達成した。
これらの結果は、前提（優先）制約が経路決定とタスクの役割割当を結び付ける場合、解の質のために柔軟な再割当を許可することが重要であることを示している。

Abstract

多くのマルチロボットアプリケーションでは、下流の処理が適切なタイミングで進められるように、タスクを効率的かつ正しい順序で完了する必要があります。先行関係制約付きマルチエージェント経路探索（MAPF-PC）は、タスク系列が事前に固定されているときに、順序関係を満たしつつ衝突のない計画を計算するための、よく研究された枠組みです。しかし多くの応用では、解の品質はエージェントの移動の仕方だけでなく、どのエージェントがどのタスクを担当するかにも依存します。そこで、本質的に持ち上げられた問題として、タスク割当てと先行関係制約付き経路探索（TAPF-PC）を考えます。TAPF-PCは、MAPF-PCを拡張し、割当て、先行関係の充足、そして経路コストを同時に最適化します。生じる結合されたTAPF-PCの探索空間に対処するために、我々は大規模近傍探索アプローチを開発します。これは、実行可能なMAPF-PCの初期解から開始し、割当て変更に基づく近傍修復により反復的に改善することで、選択した各近傍内で実行可能性を回復します。複数のベンチマークファミリとスケーリング条件にわたる実験の結果、最も性能の高い構成は、固定割当ての初期解による解に対して89.1%のインスタンスを改善し、先行関係制約のもとでの柔軟な再割当てによる利得を、大規模近傍探索が効果的に捉えていることを示しています。