論文の概要: Large Neighborhood Search for Multi-Agent Task Assignment and Path Finding with Precedence Constraints

• arxiv url: http://arxiv.org/abs/2603.28968v1
• Date: Mon, 30 Mar 2026 20:12:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-01 15:25:02.768585
• Title: Large Neighborhood Search for Multi-Agent Task Assignment and Path Finding with Precedence Constraints
• Title（参考訳）: 先行制約を考慮したタスク割り当てと経路探索のための大規模近傍探索
• Authors: Viraj Parimi, Brian C. Williams,
• Abstract要約: 先行制約付きマルチエージェントパス探索(MAPF-PC)は衝突のない計画計算のためのよく研究されたフレームワークである。 本研究では,MAPF-PCシードから始まる大規模な地域探索手法を開発し,再割り当てによる地区修復を反復的に改善する。 実験により、最も優れた構成は、固定割り当てシードソリューションよりも89.1%のインスタンスを改善していることが示された。
• 参考スコア（独自算出の注目度）: 3.7347677698423536
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many multi-robot applications require tasks to be completed efficiently and in the correct order, so that downstream operations can proceed at the right time. Multi-agent path finding with precedence constraints (MAPF-PC) is a well-studied framework for computing collision-free plans that satisfy ordering relations when task sequences are fixed in advance. In many applications, however, solution quality depends not only on how agents move, but also on which agent performs which task. This motivates the lifted problem of task assignment and path finding with precedence constraints (TAPF-PC), which extends MAPF-PC by jointly optimizing assignment, precedence satisfaction, and routing cost. To address the resulting coupled TAPF-PC search space, we develop a large neighborhood search approach that starts from a feasible MAPF-PC seed and iteratively improves it through reassignment-based neighborhood repair, restoring feasibility within each selected neighborhood. Experiments across multiple benchmark families and scaling regimes show that the best-performing configuration improves 89.1% of instances over fixed-assignment seed solutions, demonstrating that large neighborhood search effectively captures the gains from flexible reassignment under precedence constraints.
• Abstract（参考訳）: 多くのマルチロボットアプリケーションはタスクを効率的に正しい順序で完了させ、ダウンストリーム操作を正しいタイミングで進行させる必要がある。 先行制約付きマルチエージェントパス探索(MAPF-PC)は、タスクシーケンスが事前に固定されたときの順序関係を満たす衝突のない計画を計算するためのよく研究されたフレームワークである。 しかし、多くのアプリケーションでは、ソリューションの品質はエージェントの動作だけでなく、どのエージェントがどのタスクを実行するかにも依存する。 これにより、タスク割り当てと経路探索の優先順位制約(TAPF-PC)が解け、MAPF-PCを最適化し、タスク割り当て、優先満足度、ルーティングコストを最適化する。 そこで本研究では,提案手法を適用可能なMAPF-PCシードから始まり,再割り当てによる地区修復を行い,各地区で実現可能性の回復を図るため,大規模な地域探索手法を開発した。 複数のベンチマークファミリとスケーリングレジームでの実験では、最も優れた構成は固定配置のシードソリューションよりも89.1%のインスタンスを改善することが示され、大きな近傍探索が優先制約の下での柔軟な再割り当てによる利得を効果的に捉えることが示されている。

関連論文リスト

• Beyond Monolithic Architectures: A Multi-Agent Search and Knowledge Optimization Framework for Agentic Search [56.78490647843876]
  エージェント検索は、大規模言語モデル(LLM)が推論とツールの使用をインターリーブできるようにすることによって、複雑な情報を探すための有望なパラダイムとして登場した。 本稿では,bfM-ASKを提案する。bfM-ASK,bfM-ASK,bfM-ASK,bfM-ASK,bfM-ASK,bfM-ASK,bfM-ASK,bfM-ASK。
  論文  参考訳（メタデータ） (2026-01-08T08:13:27Z)
• PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving [89.60370366013142]
  制約,検証,選択という3つの重要な要素を持つモデルに依存しない,スケーラブルなエージェントフレームワークであるPlanGENを提案する。 具体的には、推論時間アルゴリズムの性能を向上させるために、制約誘導反復検証を提案する。
  論文  参考訳（メタデータ） (2025-02-22T06:21:56Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [51.00436121587591]
  マルチオブジェクト強化学習(MORL)エージェントでは、意思決定行動の最適化を行う。 重みベクトル w でパラメトリした線型効用関数の場合に焦点を当てる。 学習過程の異なる段階で最も有望な重みベクトルを効率的に探索する上信頼境界に基づく手法を提案する。
  論文  参考訳（メタデータ） (2024-05-01T09:34:42Z)
• Optimal Task Assignment and Path Planning using Conflict-Based Search with Precedence and Temporal Constraints [5.265273282482319]
  本稿では,TAPF-PTC問題におけるタスク割り当てと経路探索について検討する。 我々は、競合ベースの検索(CBS)を拡張して、優先度と時間的制約に従うタスク割り当てと衝突のない経路を同時に生成する。 実験により,我々のアルゴリズムであるCBS-TA-PTCは,優先度と時間的制約を効果的に解決できることを示した。
  論文  参考訳（メタデータ） (2024-02-13T20:07:58Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。 具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。 また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
  論文  参考訳（メタデータ） (2023-07-25T12:33:53Z)
• Optimal Multi-Agent Path Finding for Precedence Constrained Planning Tasks [0.7742297876120561]
  我々は,PC-MAPF (Precedence Constrained Multi-Agent Path Finding) 問題の拡張について検討する。 そこで我々は,PC-CBS (Precedence Constrained Conflict Based Search) という新しいアルゴリズムを提案する。 本アルゴリズムは, 各種倉庫集合体, マルチエージェントピックアップ, 配送タスクに対して性能をベンチマークし, 最近提案された効率的なベースラインのサブ最適性を評価する。
  論文  参考訳（メタデータ） (2022-02-08T07:26:45Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。