論文の概要: Multi-Objective Multi-Agent Path Finding with Lexicographic Cost Preferences
- arxiv url: http://arxiv.org/abs/2510.07276v1
- Date: Wed, 08 Oct 2025 17:40:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-09 16:41:20.668082
- Title: Multi-Objective Multi-Agent Path Finding with Lexicographic Cost Preferences
- Title（参考訳）: レキシコグラフィーによる多目的マルチエージェントパスの探索
- Authors: Pulkit Rustagi, Kyle Hollins Wray, Sandhya Saisubramanian,
- Abstract要約: 多目的経路探索(MO-MAPF)アルゴリズムは競合のない計画を生成する。
我々は,MO-MAPFをモデル化するためのレキシコグラフィーフレームワークと,アルゴリズムのテクスタイストLexicographic Conflict-Based Search (LCBS)を提案する。
LCBSは優先順位を意識した低レベルの$A*$検索とコンフリクトベースの検索を統合している。
私たちは最適性とスケーラビリティに関する洞察を提供し、LCBSが最大10の目的を持つインスタンスにスケーリングしながら最適なソリューションを計算していることを実証的に示しています。
- 参考スコア（独自算出の注目度）: 7.18523391773903
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Many real-world scenarios require multiple agents to coordinate in shared environments, while balancing trade-offs between multiple, potentially competing objectives. Current multi-objective multi-agent path finding (MO-MAPF) algorithms typically produce conflict-free plans by computing Pareto frontiers. They do not explicitly optimize for user-defined preferences, even when the preferences are available, and scale poorly with the number of objectives. We propose a lexicographic framework for modeling MO-MAPF, along with an algorithm \textit{Lexicographic Conflict-Based Search} (LCBS) that directly computes a single solution aligned with a lexicographic preference over objectives. LCBS integrates a priority-aware low-level $A^*$ search with conflict-based search, avoiding Pareto frontier construction and enabling efficient planning guided by preference over objectives. We provide insights into optimality and scalability, and empirically demonstrate that LCBS computes optimal solutions while scaling to instances with up to ten objectives -- far beyond the limits of existing MO-MAPF methods. Evaluations on standard and randomized MAPF benchmarks show consistently higher success rates against state-of-the-art baselines, especially with increasing number of objectives.
- Abstract（参考訳）: 多くの実世界のシナリオでは、複数のエージェントが共有環境で協調し、複数の競合する可能性のある目標間のトレードオフのバランスをとる必要がある。
現在の多目的マルチエージェントパス探索 (MO-MAPF) アルゴリズムは、パレートフロンティアの計算によって競合のない計画を生成するのが一般的である。
ユーザが定義した嗜好を明示的に最適化するわけではなく、たとえ好みが利用可能であったとしても、目的の数が不適切である。
そこで本研究では,MO-MAPF をモデル化するためのレキソグラフィーフレームワークと,目的物に対するレキソグラフィーの嗜好に適合した単一解を直接計算するアルゴリズムである textit{Lexicographic Conflict-Based Search} (LCBS) を提案する。
LCBSは、優先順位を意識した低レベルの$A^*$検索を競合ベースの検索と統合し、Paretoのフロンティア構築を回避し、目的よりも優先される効率的な計画を可能にする。
私たちは最適性とスケーラビリティに関する洞察を提供し、LCBSが最大10の目的を持つインスタンスにスケーリングしながら最適なソリューションを計算していることを実証的に示しています。
MAPFの標準およびランダム化ベンチマークの評価は、最先端のベースライン、特に目的数の増加に対して、一貫して高い成功率を示す。
関連論文リスト
- Decoding-Time Language Model Alignment with Multiple Objectives [116.42095026960598]
既存の手法は主に、1つの報酬関数に対してLMを最適化することに集中し、それらの適応性は様々な目的に制限される。
本稿では,予測の線形結合から次のトークンを出力する復号時間アルゴリズムである$textbfmulti-objective decoding (MOD)$を提案する。
提案手法は, 自然条件下であっても, 既存のアプローチが準最適であることを示すとともに, 提案手法の最適性を保証する。
論文 参考訳（メタデータ） (2024-06-27T02:46:30Z) - MAP: Low-compute Model Merging with Amortized Pareto Fronts via Quadratic Approximation [80.47072100963017]
Amortized Pareto Front (MAP) を用いた新しい低演算アルゴリズム Model Merging を導入する。
MAPは、複数のモデルをマージするためのスケーリング係数のセットを効率的に識別し、関連するトレードオフを反映する。
また,タスク数が比較的少ないシナリオではベイジアンMAP,タスク数の多い状況ではNested MAPを導入し,計算コストを削減した。
論文 参考訳（メタデータ） (2024-06-11T17:55:25Z) - BOtied: Multi-objective Bayesian optimization with tied multivariate ranks [33.414682601242006]
本稿では,非支配解と結合累積分布関数の極端量子化との自然な関係を示す。
このリンクにより、我々はPareto対応CDFインジケータと関連する取得関数BOtiedを提案する。
種々の合成および実世界の問題に対する実験により,BOtied は最先端MOBO 取得関数より優れていることが示された。
論文 参考訳（メタデータ） (2023-06-01T04:50:06Z) - PD-MORL: Preference-Driven Multi-Objective Reinforcement Learning
Algorithm [0.18416014644193063]
本稿では,連続ロボット作業にスケーラブルな選好空間全体をカバーするために,単一のユニバーサルネットワークをトレーニングする新しいMORLアルゴリズムを提案する。
PD-MORLは、連続制御タスクに挑戦するために最大25%大きなハイパーボリュームを達成する。
論文 参考訳（メタデータ） (2022-08-16T19:23:02Z) - Multi-objective Conflict-based Search Using Safe-interval Path Planning [10.354181009277623]
低レベル探索のための新しい多目的セーフインターバルパス計画法 (MO-SIPP) アルゴリズムを利用するMO-CBS(Multi-objective conflict-based search)を提案する。
我々は, 平均低レベル探索時間において, 等級が大幅に改善されていることを示すために, 広範囲な数値計算結果を示す。
また,建設現場計画における提案アルゴリズムの適用可能性を示すケーススタディも提示する。
論文 参考訳（メタデータ） (2021-08-02T09:42:08Z) - Exact Pareto Optimal Search for Multi-Task Learning and Multi-Criteria
Decision-Making [10.914300987810128]
EPO 探索は線形収束速度で EPO 解に収束することを示す。
我々は, PFを後部MCDMで近似するPESA-EPOと, 対話型MCDMで誘導するGP-EPOという新しいアルゴリズムを開発した。
EPO検索は変数数と線形にスケールし、ディープEコマースネットワークに使用することができる。
論文 参考訳（メタデータ） (2021-08-02T02:13:21Z) - Multi-objective Conflict-based Search for Multi-agent Path Finding [10.354181009277623]
マルチオブジェクトパスプランナーは通常、パスの長さなどの単一の目的を最適化しながら、パスのアンサンブルを計算します。
本稿では、マルチオブジェクトコンフリクトベース検索(MO-CBS)という、いわゆる次元の呪いをバイパスする手法を紹介します。
論文 参考訳（メタデータ） (2021-01-11T10:42:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。