論文の概要: Subdimensional Expansion for Multi-objective Multi-agent Path Finding
- arxiv url: http://arxiv.org/abs/2102.01353v1
- Date: Tue, 2 Feb 2021 06:58:28 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-03 16:38:55.522157
- Title: Subdimensional Expansion for Multi-objective Multi-agent Path Finding
- Title（参考訳）: 多目的マルチエージェントパス探索のための部分次元拡張
- Authors: Zhongqiang Ren, Sivakumar Rathinam and Howie Choset
- Abstract要約: マルチエージェントパスプランナーは通常、パスの長さなどの単一の目的を最適化するパスを決定する。
しかし、多くのアプリケーションは、計画プロセスにおいて同時に最適化されるために、例えば、時間から完了までの時間や燃料使用など、複数の目的を必要とするかもしれない。
本稿では,このいわゆる次元の呪いを回避し,従来のマルチエージェントワークをサブ次元展開という枠組みで活用するアプローチを提案する。
- 参考スコア（独自算出の注目度）: 10.354181009277623
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Conventional multi-agent path planners typically determine a path that
optimizes a single objective, such as path length. Many applications, however,
may require multiple objectives, say time-to-completion and fuel use, to be
simultaneously optimized in the planning process. Often, these criteria may not
be readily compared and sometimes lie in competition with each other. Simply
applying standard multi-objective search algorithms to multi-agent path finding
may prove to be inefficient because 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 paper presents an approach
that bypasses this so-called curse of dimensionality by leveraging our prior
multi-agent work with a framework called subdimensional expansion. One example
of subdimensional expansion, when applied to A*, is called M* and M* was
limited to a single objective function. We combine principles of dominance and
subdimensional expansion to create a new algorithm named multi-objective M*
(MOM*), which dynamically couples agents for planning only when those agents
have to "interact" with each other. MOM* computes the complete Pareto-optimal
set for multiple agents efficiently and naturally trades off sub-optimal
approximations of the Pareto-optimal set and computational efficiency. Our
approach is able to find the complete Pareto-optimal set for problem instances
with hundreds of solutions which the standard multi-objective A* algorithms
could not find within a bounded time.
- Abstract（参考訳）: 従来のマルチエージェントパスプランナーは、通常、経路長のような単一の目的を最適化する経路を決定する。
しかし、多くのアプリケーションでは、計画プロセスで同時に最適化されるために、完成までの時間と燃料の使用など、複数の目的が必要です。
しばしば、これらの基準は容易に比較されず、しばしば互いに競合している。
標準的な多目的探索アルゴリズムをマルチエージェントパス探索に適用するだけで、可能解の空間、すなわちパレート最適集合のサイズがエージェントの数(探索空間の次元)とともに指数関数的に増加するため、非効率であることが証明できる。
本稿では,このいわゆる次元の呪いを回避し,従来のマルチエージェントワークをサブ次元展開という枠組みで活用するアプローチを提案する。
A* に適用された部分次元展開の例は M* と呼ばれ、M* は単目的函数に制限された。
支配と部分次元拡大の原則を組み合わせて、マルチオブジェクトM*(MOM*)と呼ばれる新しいアルゴリズムを作成し、エージェントが互いに「相互作用」しなければならない場合にのみ、計画のためのエージェントを動的に結合します。
MOM*は、複数のエージェントに対する完全なパレート最適集合を効率的に計算し、パレート最適集合の最適部分近似と計算効率を自然に交換する。
我々の手法は、標準多目的A*アルゴリズムでは有界時間内に見つからない数百の解を持つ問題インスタンスに対する完全なパレート最適集合を見つけることができる。
関連論文リスト
- UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
マルチオブジェクト強化学習(MORL)エージェントでは、意思決定行動の最適化を行う。
重みベクトル w でパラメータ化される線型効用関数の場合に焦点を当てる。
学習過程の異なる段階で最も有望な重みベクトルを効率的に探索する上信頼境界に基づく手法を提案する。
論文 参考訳（メタデータ） (2024-05-01T09:34:42Z) - Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。
最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。
本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
論文 参考訳（メタデータ） (2024-01-30T14:26:04Z) - Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。
標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。
我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。
本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
論文 参考訳（メタデータ） (2023-04-01T15:50:18Z) - Enhanced Multi-Objective A* with Partial Expansion [22.45142249108214]
グラフ上に現れる多目的短経路問題(MO-SPP)は、複数の目的を最適化しながら経路の集合を決定する。
この問題に対処するため,複数のMOA*アルゴリズムが最近開発された。
この作業は,MOA*の高メモリ消費を,実行時にほとんど増加せずに削減することを目的としている。
論文 参考訳（メタデータ） (2022-12-06T05:48:11Z) - Multi-Objective Quality Diversity Optimization [2.4608515808275455]
MOME(Multi-Objective MAP-Elites)の多目的設定におけるMAP-Elitesアルゴリズムの拡張を提案する。
すなわち、MAP-Elitesグリッドアルゴリズムから受け継いだ多様性と、多目的最適化の強みを組み合わせる。
本手法は,標準的な最適化問題からロボットシミュレーションまで,いくつかのタスクで評価する。
論文 参考訳（メタデータ） (2022-02-07T10:48:28Z) - Pareto Navigation Gradient Descent: a First-Order Algorithm for
Optimization in Pareto Set [17.617944390196286]
マルチタスク学習のような現代の機械学習アプリケーションは、複数の目的関数をトレードオフするために最適なモデルパラメータを見つける必要がある。
勾配情報のみを用いてOPT-in-Paretoを近似的に解く1次アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-10-17T04:07:04Z) - Multi-objective Conflict-based Search for Multi-agent Path Finding [10.354181009277623]
マルチオブジェクトパスプランナーは通常、パスの長さなどの単一の目的を最適化しながら、パスのアンサンブルを計算します。
本稿では、マルチオブジェクトコンフリクトベース検索(MO-CBS)という、いわゆる次元の呪いをバイパスする手法を紹介します。
論文 参考訳（メタデータ） (2021-01-11T10:42:38Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Decomposition in Decision and Objective Space for Multi-Modal
Multi-Objective Optimization [15.681236469530397]
多モード多目的最適化問題(MMMOP)はパレート最適集合内に複数の部分集合を持つ。
一般的な多目的進化的アルゴリズムは、複数の解部分集合を探索するために純粋に設計されていないが、MMMOP向けに設計されたアルゴリズムは、目的空間における劣化した性能を示す。
これは、MMMOPに対処するためのより良いアルゴリズムの設計を動機付けている。
論文 参考訳（メタデータ） (2020-06-04T03:18:47Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。