- NewOn the Hardness of Optimal Motion on Trees
Tzvika Geft
採択先: 未取得
新着論文キーワード一致 2被引用 0関連度 2本文(arXiv)読む価値 5/5
Multi-Agent Path FindingMAPF
2026-06-04 ・ 本論文は、木構造におけるマルチエージェント経路探索（MAPF）およびPebble Motion on Trees (PMT) の計算複雑性を解明した研究である。Stack Rearrangement (SR) 問題からの帰着を用いる新しいフレームワークを提案し、距離、makespan、flowtimeの各目的関数において、labeledおよび2-coloredのバリエーションが、極めて単純な「subdivided stars」や最大次数3の木においてもNP困難であることを証明した。これにより、数十年にわたるPMTの複雑性に関する未解決問題を解決し、計算の困難性が生じる境界（tractability threshold）を特定した。
- NewMulti-Agent Cooperative Transportation: Optimal and Efficient Task Allocation and Path Finding
Ning Zhou, Nikolai W. F. Bode, Edmund R. Hunt
採択先: 未取得
補充候補キーワード一致 2被引用 0関連度 2本文(arXiv)読む価値 4/5
Multi-Agent Path FindingMAPF
2026-05-15 ・ 複数のエージェントが協力して大型物品を運搬する「Cooperative Transportation Task Allocation and Path Finding (CT-TAPF)」問題を新たに定式化し、最適解を得るためのCT-TCBSと、計算効率に優れた劣最適解ソルバーを提案する。
- Lifelong LaCAM with Local Guidance for Lifelong MAPF
Tomoki Arita, Keisuke Okumura
採択先: 未取得
補充候補キーワード一致 1被引用 0関連度 4本文(arXiv)読む価値 4/5
MAPF
2026-05-16 ・ Lifelong Multi-Agent Pathfinding (LMAPF) において、構成ベースのソルバー LaCAM に局所的なガイダンス（Local Guidance）を導入し、再帰的ホライゾン（receding-horizon）フレームワークへと拡張した手法 LLLG を提案する。本手法は、前回の計画結果をウォームスタートとして利用することで、高密度な環境下での混雑緩和とスループットの向上を、リアルタイムな計算コストを維持しつつ実現する。
- Should I Replan? Learning to Spot the Right Time in Robust MAPF Execution
David Zahrádka, David Woller, Denisa Mužíková, Miroslav Kulich, Libor Přeučil
採択先: 未取得
新着論文キーワード一致 2被引用 0関連度 5本文(arXiv)読む価値 4/5
Multi-Agent Path FindingMAPF
2026-04-28 ・ エージェントの遅延が発生する実環境下のマルチエージェント経路計画（MAPF）において、Action Dependency Graph (ADG) の統計量に基づき、再計画（Replanning）によるコスト削減の期待値を予測する回帰モデルを提案する。提案手法は、動的障害物による遅延が発生した際に、再計画によって得られる潜在的な利益を高い精度で推定し、実行コストの増大を最大 $50\%$ まで低減できることを示した。
- Unassigned Agents in Compilation-based Multi-agent Path Finding
Pavel Surynek
採択先: 未取得
新着論文キーワード一致 2被引用 0関連度 5本文(arXiv)読む価値 3/5
Multi-Agent Path FindingMAPF
2026-06-14 ・ 目的地を持つエージェント $\mathcal{A}$ と、目的地を持たない未割り当てエージェント $\mathcal{U}$ が混在するUA-MAPF問題を、コンパイルベースのSAT/SMTソルバーを用いて解く手法を提案している。未割り当てエージェントは、目的地への到達義務はないものの、他のエージェントの経路を妨げないよう移動させる必要がある。本研究は、MDD（Multi-valued Decision Diagram）をUA用に拡張したUA-MDDを用いることで、既存のSMT-CBSやNRF-SATといった高度なソルバーをUA-MAPFへ容易に適応できることを示した。
- Many-to-Many Multi-Agent Pickup and Delivery
Ethan Schneider, Jingkai Chen, Tianyi Gu, Kunlei Lian, Seth Hutchinson, Sonia Chernova
採択先: 未取得
補充候補キーワード一致 2被引用 0関連度 5本文(arXiv)読む価値 4/5
Multi-Agent Pickup and DeliveryMAPD
2026-05-08 ・ 従来の1対1のタスク割り当て制約を打破し、アイテムの保管場所が複数存在する「Many-to-Many Multi-Agent Pickup and Delivery (M2M-MAPD)」問題を定義・解決する研究。提案手法のM2Mは、Large Neighborhood Search (LNS) と Priority Based Search (PBS) を組み合わせることで、高密度な在庫環境下でも既存のSOTA手法（LNS-PBS）を凌駕する高いタスクスループットを達成した。
- Robust Multi-Agent Path Finding under Observation Attacks: A Principled Adversarial-Plus-Smoothing Training Recipe
Riad Ahmed
採択先: 未取得
新着論文キーワード一致 2被引用 0関連度 5本文(arXiv)読む価値 4/5
Multi-Agent Path FindingMAPF
2026-05-12 ・ 分散型マルチエージェント経路探索（MAPF）において、観測値への微小な摂動がチーム全体の停滞を招く脆弱性を克服するため、ネットワーク構造やデプロイメント・パイプラインを変更せずに頑健性を向上させる2段階の学習レシピ「Adv-PPO」および「Adv-PPO+MACER」を提案する。
- Optimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schrödinger Bridges
Usman A. Khan, Joseph W. Durham
採択先: 未取得
補充候補キーワード一致 2被引用 0関連度 5本文(arXiv)読む価値 5/5
Multi-Agent Path FindingMAPF
2026-05-11 ・ 匿名マルチエージェント経路探索（MAPF）をマルコフ構造を持つマルチ・マージナル最適輸送（MMOT）として定式化し、完全単模性（TU）を利用して整数解を多項式時間で得る手法と、シュレディンガー・ブリッジ（SBP）を用いたエントロピー正則化によるスケーラブルな近似手法を提案している。
- Discrete Diffusion for Complex and Congested Multi-Agent Path Finding with Sparse Social Attention
Yuanzhe Wang, Tian Zhi, Zihang Wei, Hongguang Wang, Jiaming Guo, Yang Zhao, Zisheng Liu, Shiyu Quan, Xing Hu, Zidong Du, Yunji Chen
採択先: 未取得
キーワード一致 2被引用 0関連度 5本文(arXiv)読む価値 4/5
Multi-Agent Path FindingMAPF
2026-05-13 ・ 離散的なデノイジング拡散確率モデル（D3PM）を初期解生成器として統合し、Large Neighborhood Search 2（LNS2）による修復プロセスを強化するハイブリッドフレームワーク「DiffLNS」を提案する。Sparse Social Attentionを用いることで、混雑した環境下でも計算効率を維持しながら協調的な行動軌跡を学習し、最大312エージェントのシナリオにおいても高い成功率を実現する。
- Anytime Multi-Task Multi-Agent Pickup and Delivery Under Energy Constraint
Fumiya Kudo, Kai Cai
採択先: IEEE Robotics and Automation Letters
キーワード一致 4被引用 13関連度 7アブストラクト読む価値 4/5
Multi-Agent Path FindingMAPFMulti-Agent Pickup and DeliveryMAPD
2024-11-01 ・ 本論文は、エージェントのエネルギー制約と、エージェントの現在位置に関わらずタスクを割り当て可能な「Anytime Task Allocation」を導入した、新しいマルチタスクMAPD（Multi-Agent Pickup and Delivery）問題を提案しています。提案手法は、従来のマルチタスクMAPDと比較して、幅広いエージェント数においてメイクスパンを $5 - 19 \%$ 短縮することに成功しています。
- Integrated Task Assignment and Path Planning for Capacitated Multi-Agent Pickup and Delivery
Zhe Chen, Javier Alonso–Mora, Xiaoshan Bai, Daniel Harabor, Peter J. Stuckey
採択先: IEEE Robotics and Automation Letters
キーワード一致 4被引用 185関連度 7本文(OA-PDF)読む価値 5/5
Multi-Agent Path FindingMAPFMulti-Agent Pickup and DeliveryMAPD
2021-04-22 ・ 容量制限付きマルチエージェント・ピックアップ＆デリバリー（Capacitated MAPD）問題に対し、タスク割り当て（TA）と経路計画（MAPF）を統合して解く手法を提案する。優先度付き計画（Prioritised Planning）を用いて実際の衝突回避コストを評価に用いることで、従来の逐次的な手法におけるコスト予測の乖離を解消し、特に容量制限がある環境において既存の最良の準最適手法であるTPTSを大幅に上回る性能を実現している。
- Dynamic Multi-Agent Pickup and Delivery in Robotic Cellular Warehousing Systems
Cheng Ren, Ming Li, Xinping Guan, George Q. Huang
採択先: 未取得
キーワード一致 2被引用 0関連度 5本文(arXiv)読む価値 4/5
Multi-Agent Pickup and DeliveryMAPD
2026-06-04 ・ ロボット細胞型倉庫システム（RCWS）において、実行中の注文に新たなSKUが追加される「内部的な注文の進化」を考慮した、初のDynamic-MAPD問題を定式化し、イベント駆動型のトークン・パッシングに基づく2つの再計画アルゴリズム（Dynamic-TPおよびCooperative-TP）を提案する。
- CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs
Abhishek S, Badrikanath Praharaj, Sreeram MV
採択先: 未取得
キーワード一致 2被引用 0関連度 5本文(arXiv)読む価値 4/5
Multi-Agent Path FindingMAPF
2026-06-03 ・ MAPF（Multi-Agent Path Finding）において、従来のSum of Costs (SoC) では予測困難な実機実行時間（wall-clock completion time）を予測するため、CADENCE手法を提案する。本研究は、計画段階から取得可能な「primitive motion burden（旋回数や停止・再始動回数など）」と「interaction-aware coordination structure（依存関係の深さなど）」を特徴量として導入し、7台の差動駆動ロボットを用いた実機実験を通じて、SoCのみを用いるよりも大幅に予測精度が向上することを実証した。
- STEAM: A Training-Free Congestion-Aware Enhancement Framework for Decentralized Multi-Agent Path Finding
Mingyang Feng, Mengnuo Zhang, Shaoyuan Li, Xiang Yin
採択先: 未取得
キーワード一致 2被引用 0関連度 5本文(arXiv)読む価値 4/5
Multi-Agent Path FindingMAPF
2026-05-20 ・ STEAMは、学習済みの分散型MAPF（Multi-Agent Path Finding）ポリシーを一切再学習・変更することなく、テスト時の実行プロセスに軽量な混雑回避ガイダンスを注入する、学習不要（training-free）かつ方策に依存しない（policy-agnostic）強化フレームワークである。
- Graph Attention-Guided Search for Dense Multi-Agent Pathfinding
Rishabh Jain, Keisuke Okumura, Michael Amir, Amanda Prorok
採択先: 未取得
キーワード一致 1被引用 0関連度 1本文(arXiv)読む価値 4/5
MAPF
2025-10-20 ・ 高密度なマルチエージェント経路探索（MAPF）において、グラフアテンションを用いたニューラル方策 $\text{MAGAT}^+$ を探索アルゴリズム $\text{LaCAM}$ に統合したハイブリッドフレームワーク $\text{LaGAT}$ を提案する。事前学習とマップ特化型の微調整、およびデッドロック検出メカニズムを組み合わせることで、既存の探索ベース手法や学習ベース手法のパレート境界を突破し、高密度環境における解の質とリアルタイム性能を向上させている。
- LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding
Keisuke Okumura
採択先: 未取得
キーワード一致 1被引用 0関連度 1本文(arXiv PDF)読む価値 5/5
MAPF
2022-11-24 ・ LaCAM (lazy constraints addition search for MAPF) は、完全性を備えつつ、数百から10,000エージェント規模の大規模・高密度なマルチエージェント経路探索（MAPF）を高速に解決する2レベル探索アルゴリズムである。
- Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding
Keisuke Okumura, Manao Machida, X. Défago, Yasumasa Tamura
採択先: International Joint Conference on Artificial Intelligence
キーワード一致 2被引用 195関連度 5本文(arXiv PDF)読む価値 5/5
Multi-Agent Path FindingMAPF
2019-01-31 ・ Lifelong MAPF/MAPDにおいて、数百から数千規模のエージェントをリアルタイムに制御可能な、優先度継承とバックトラッキングを用いた新しい劣最適アルゴリズムPIBTを提案する。