論文の概要: Enhanced Multi-Objective A* with Partial Expansion
- arxiv url: http://arxiv.org/abs/2212.03712v1
- Date: Tue, 6 Dec 2022 05:48:11 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-08 16:41:03.520355
- Title: Enhanced Multi-Objective A* with Partial Expansion
- Title(参考訳): 部分展開による拡張多目的A*
- Authors: Valmiki Kothare, Zhongqiang Ren, Sivakumar Rathinam, Howie Choset
- Abstract要約: 多目的短経路問題は通常、グラフ上に置かれる。
この問題は、いわゆるPareto-objective(英語版)ソリューションの集合を見つけることを目指している。
多目的A*アルゴリズム(MOA*)は、最近、品質保証付きソリューションを高速に計算するために開発された。
本稿では,まず単目的から多目的への「部分展開(partial expansion, PE)」の概念を拡張し,その上で,この新しいPE手法を最近の実行時効率のよいMOA*アルゴリズムであるEMOA*と融合する。
- 参考スコア(独自算出の注目度): 22.45142249108214
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Multi-Objective Shortest Path Problem, typically posed on a graph,
determines a set of paths from a start vertex to a destination vertex while
optimizing multiple objectives. In general, there does not exist a single
solution path that can simultaneously optimize all the objectives and the
problem thus seeks to find a set of so-called Pareto-optimal solutions. To
address this problem, several Multi-Objective A* (MOA*) algorithms were
recently developed to quickly compute solutions with quality guarantees.
However, these MOA* algorithms often suffer from high memory usage, especially
when the branching factor (i.e., the number of neighbors of any vertex) of the
graph is large. This work thus aims at reducing the high memory consumption of
MOA* with little increase in the runtime. In this paper, we first extend the
notion of "partial expansion" (PE) from single-objective to multi-objective and
then fuse this new PE technique with EMOA*, a recent runtime efficient MOA*
algorithm. Furthermore, the resulting algorithm PE-EMOA* can balance between
runtime and memory efficiency by tuning a user-defined hyper-parameter.
- Abstract(参考訳): グラフ上の多目的短経路問題(英語版)は、複数の目的を最適化しながら開始頂点から目的地頂点への経路の集合を決定する。
一般に、全ての目的を同時に最適化できる単一の解経路は存在しないので、問題はいわゆるパレート最適解の集合を見つけようとする。
この問題に対処するため、複数の多目的a*(moa*)アルゴリズムが最近開発され、品質保証付きで素早く解を計算できるようになった。
しかし、これらのMOA*アルゴリズムは、特にグラフの分岐係数(すなわち、任意の頂点の隣人の数)が大きい場合、高いメモリ使用率に悩まされることが多い。
この作業は,MOA*の高メモリ消費を,実行時にほとんど増加せずに削減することを目的としている。
本稿では,まず単一目的語から多目的語への「部分展開(partial expansion, PE)」の概念を拡張し,その上で,この新しいPE手法を最近の実行時効率的なMOA*アルゴリズムであるEMOA*と融合する。
さらに、PE-EMOA*は、ユーザが定義したハイパーパラメータをチューニングすることで、実行時とメモリ効率のバランスをとることができる。
関連論文リスト
- Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳(メタデータ) (2023-07-17T20:11:56Z) - Enhanced Multi-Objective A* Using Balanced Binary Search Trees [35.63053398687847]
アルゴリズムのような多目的A* (MOA*) は、そのノードに到達した非支配パスを追跡するために、検索中に任意のノードに「フロンティア」セットを保持する。
バランスの取れた二分探索木を利用して,これらのフロンティアを多目的に効率的に維持する手法を提案する。
論文 参考訳(メタデータ) (2022-02-18T02:54:58Z) - A Simple Evolutionary Algorithm for Multi-modal Multi-objective
Optimization [0.0]
マルチモーダル・多目的最適化問題(MMOP)を解くための定常進化アルゴリズムを提案する。
本報告では,1000関数評価の低計算予算を用いて,様々なテストスイートから得られた21個のMMOPの性能について報告する。
論文 参考訳(メタデータ) (2022-01-18T03:31:11Z) - A survey on multi-objective hyperparameter optimization algorithms for
Machine Learning [62.997667081978825]
本稿では,多目的HPOアルゴリズムに関する2014年から2020年にかけての文献を体系的に調査する。
メタヒューリスティック・ベース・アルゴリズムとメタモデル・ベース・アルゴリズム,および両者を混合したアプローチを区別する。
また,多目的HPO法と今後の研究方向性を比較するための品質指標についても論じる。
論文 参考訳(メタデータ) (2021-11-23T10:22:30Z) - Multi-Objective Path-Based D* Lite [10.354181009277623]
D* Liteのような増分グラフ探索アルゴリズムは、その後の同様の経路計画タスクを高速化するために、以前の探索作業を再利用する。
本稿では,Multi-Objective Path-Based D* Lite (MOPBD*) と呼ばれる多目的インクリメンタル検索アルゴリズムを提案する。
数値計算の結果,MOPBD*はスクラッチからの探索よりも効率的であり,経路計画における既存のインクリメンタル手法よりも桁違いに高速であることがわかった。
論文 参考訳(メタデータ) (2021-08-02T08:24:32Z) - Subdimensional Expansion for Multi-objective Multi-agent Path Finding [10.354181009277623]
マルチエージェントパスプランナーは通常、パスの長さなどの単一の目的を最適化するパスを決定する。
しかし、多くのアプリケーションは、計画プロセスにおいて同時に最適化されるために、例えば、時間から完了までの時間や燃料使用など、複数の目的を必要とするかもしれない。
本稿では,このいわゆる次元の呪いを回避し,従来のマルチエージェントワークをサブ次元展開という枠組みで活用するアプローチを提案する。
論文 参考訳(メタデータ) (2021-02-02T06:58:28Z) - Multi-objective Conflict-based Search for Multi-agent Path Finding [10.354181009277623]
マルチオブジェクトパスプランナーは通常、パスの長さなどの単一の目的を最適化しながら、パスのアンサンブルを計算します。
本稿では、マルチオブジェクトコンフリクトベース検索(MO-CBS)という、いわゆる次元の呪いをバイパスする手法を紹介します。
論文 参考訳(メタデータ) (2021-01-11T10:42:38Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Provable Multi-Objective Reinforcement Learning with Generative Models [98.19879408649848]
目的の選好から最適な政策を学習する単一政策 MORL の問題について検討する。
既存の方法は、多目的決定プロセスの正確な知識のような強い仮定を必要とする。
モデルベースエンベロップ値 (EVI) と呼ばれる新しいアルゴリズムを提案し, 包含された多目的$Q$学習アルゴリズムを一般化する。
論文 参考訳(メタデータ) (2020-11-19T22:35:31Z) - Follow the bisector: a simple method for multi-objective optimization [65.83318707752385]
複数の異なる損失を最小化しなければならない最適化問題を考える。
提案手法は、各イテレーションにおける降下方向を計算し、目的関数の相対的減少を等しく保証する。
論文 参考訳(メタデータ) (2020-07-14T09:50:33Z) - MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical
Models [96.1052289276254]
この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。
驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
論文 参考訳(メタデータ) (2020-04-16T16:20:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。