論文の概要: Multi-objective Conflict-based Search for Multi-agent Path Finding
- arxiv url: http://arxiv.org/abs/2101.03805v2
- Date: Tue, 23 Mar 2021 06:19:25 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-04 14:34:00.109664
- Title: Multi-objective Conflict-based Search for Multi-agent Path Finding
- Title（参考訳）: 多目的コンフリクトに基づくマルチエージェント経路探索
- Authors: Zhongqiang Ren, Sivakumar Rathinam and Howie Choset
- Abstract要約: マルチオブジェクトパスプランナーは通常、パスの長さなどの単一の目的を最適化しながら、パスのアンサンブルを計算します。
本稿では、マルチオブジェクトコンフリクトベース検索(MO-CBS)という、いわゆる次元の呪いをバイパスする手法を紹介します。
- 参考スコア（独自算出の注目度）: 10.354181009277623
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Conventional multi-agent path planners typically compute an ensemble of paths
while optimizing a single objective, such as path length. However, many
applications may require multiple objectives, say fuel consumption and
completion time, to be simultaneously optimized during planning and these
criteria may not be readily compared and sometimes lie in competition with each
other. Naively applying existing multi-objective search algorithms to
multi-agent path finding may prove to be inefficient as the size of the space
of possible solutions, i.e., the Pareto-optimal set, can grow exponentially
with the number of agents (the dimension of the search space). This article
presents an approach named Multi-objective Conflict-based Search (MO-CBS) that
bypasses this so-called curse of dimensionality by leveraging prior
Conflict-based Search (CBS), a well-known algorithm for single-objective
multi-agent path finding, and principles of dominance from multi-objective
optimization literature. We prove that MO-CBS is able to compute the entire
Pareto-optimal set. Our results show that MO-CBS can solve problem instances
with hundreds of Pareto-optimal solutions which the standard multi-objective A*
algorithms could not find within a bounded time.
- Abstract（参考訳）: 従来のマルチエージェントパスプランナーは通常、経路長のような単一の目的を最適化しながら経路のアンサンブルを計算する。
しかし、多くのアプリケーションでは、燃料消費や完了時間といった複数の目的を計画中に同時に最適化する必要があり、これらの基準は容易に比較されず、時には互いに競合することもある。
既存の多目的探索アルゴリズムをマルチエージェントパス探索に適用することは、可能解の空間のサイズ、すなわちパレート最適集合がエージェントの数(探索空間の次元)とともに指数関数的に増加するため、非効率であることが証明される。
本稿では,多目的コンフリクトベースサーチ(mo-cbs)という手法を提案する。これは,先行的コンフリクトベースサーチ(cbs),単一目的マルチエージェントパス探索のためのよく知られたアルゴリズム,多目的最適化文献からの優位性の原則を利用して,このいわゆる次元の呪いを回避している。
我々はMO-CBSがパレート最適集合全体を計算できることを証明する。
以上の結果から,MO-CBS は標準多目的 A* アルゴリズムが有界時間内に見つからない数百のパレート最適解の問題を解くことができることがわかった。
関連論文リスト
- 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 [75.11267478778295]
マルチオブジェクト強化学習(MORL)エージェントでは、意思決定行動の最適化を行う。
重みベクトル w でパラメータ化される線型効用関数の場合に焦点を当てる。
学習過程の異なる段階で最も有望な重みベクトルを効率的に探索する上信頼境界に基づく手法を提案する。
論文 参考訳（メタデータ） (2024-05-01T09:34:42Z) - MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem [5.580214316179672]
MG-MAPF問題は、各エージェントが少なくとも1回は衝突することなく、予め割り当てられた複数のゴールポイントを訪問する必要がある。
そこで本研究では,単一エージェントパスフィンディング(Single-Adnt pathfinding)とセーフ区間探索(Single-Adnt pathfinding)の分離に基づくMulti-Goal Conflict-Based Search (MGCBS)を提案する。
提案手法は, 常に最適な結果を得ることができ, 評価において最先端の手法よりも最大7倍高速に実行することができる。
論文 参考訳（メタデータ） (2024-04-30T12:49:54Z) - Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。
標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。
我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。
本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
論文 参考訳（メタデータ） (2023-04-01T15:50:18Z) - A Scale-Independent Multi-Objective Reinforcement Learning with
Convergence Analysis [0.6091702876917281]
多くのシーケンシャルな意思決定問題は、対立する可能性のある異なる目的の最適化を必要とする。
本稿では,Advantage Actor-Critic (A2C)アルゴリズムに基づいて,単エージェントスケール非依存型多目的強化学習を開発する。
次に、収束保証を提供する考案された多目的アルゴリズムに対して収束解析を行う。
論文 参考訳（メタデータ） (2023-02-08T16:38:55Z) - Multi-Objective Quality Diversity Optimization [2.4608515808275455]
MOME(Multi-Objective MAP-Elites)の多目的設定におけるMAP-Elitesアルゴリズムの拡張を提案する。
すなわち、MAP-Elitesグリッドアルゴリズムから受け継いだ多様性と、多目的最適化の強みを組み合わせる。
本手法は,標準的な最適化問題からロボットシミュレーションまで,いくつかのタスクで評価する。
論文 参考訳（メタデータ） (2022-02-07T10:48:28Z) - 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) - Subdimensional Expansion for Multi-objective Multi-agent Path Finding [10.354181009277623]
マルチエージェントパスプランナーは通常、パスの長さなどの単一の目的を最適化するパスを決定する。
しかし、多くのアプリケーションは、計画プロセスにおいて同時に最適化されるために、例えば、時間から完了までの時間や燃料使用など、複数の目的を必要とするかもしれない。
本稿では,このいわゆる次元の呪いを回避し,従来のマルチエージェントワークをサブ次元展開という枠組みで活用するアプローチを提案する。
論文 参考訳（メタデータ） (2021-02-02T06:58:28Z) - Provable Multi-Objective Reinforcement Learning with Generative Models [98.19879408649848]
目的の選好から最適な政策を学習する単一政策 MORL の問題について検討する。
既存の方法は、多目的決定プロセスの正確な知識のような強い仮定を必要とする。
モデルベースエンベロップ値 (EVI) と呼ばれる新しいアルゴリズムを提案し, 包含された多目的$Q$学習アルゴリズムを一般化する。
論文 参考訳（メタデータ） (2020-11-19T22:35:31Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z) - Pareto Multi-Task Learning [53.90732663046125]
マルチタスク学習は複数の相関タスクを同時に解くための強力な方法である。
異なるタスクが互いに衝突する可能性があるため、すべてのタスクを最適化するひとつのソリューションを見つけることは、しばしば不可能である。
近年,マルチタスク学習を多目的最適化として活用することにより,タスク間のトレードオフが良好である1つのパレート最適解を求める方法が提案されている。
論文 参考訳（メタデータ） (2019-12-30T08:58:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。