論文の概要: Enhanced Multi-Objective A* with Partial Expansion
- arxiv url: http://arxiv.org/abs/2212.03712v2
- Date: Sat, 8 Jul 2023 15:48:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-11 22:36:58.194861
- Title: Enhanced Multi-Objective A* with Partial Expansion
- Title（参考訳）: 部分展開による拡張多目的A*
- Authors: Valmiki Kothare, Zhongqiang Ren, Sivakumar Rathinam, Howie Choset
- Abstract要約: グラフ上に現れる多目的短経路問題(MO-SPP)は、複数の目的を最適化しながら経路の集合を決定する。
この問題に対処するため,複数のMOA*アルゴリズムが最近開発された。
この作業は,MOA*の高メモリ消費を,実行時にほとんど増加せずに削減することを目的としている。
- 参考スコア（独自算出の注目度）: 22.45142249108214
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Multi-Objective Shortest Path Problem (MO-SPP), 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. By generalizing and unifying several
single- and multi-objective search algorithms, we develop the Runtime and
Memory Efficient MOA* (RME-MOA*) approach, which can balance between runtime
and memory efficiency by tuning two user-defined hyper-parameters.
- Abstract（参考訳）: 一般にグラフ上に置かれるMO-SPP(Multi-Objective Shortest Path Problem)は、複数の目的を最適化しながら開始頂点から目的地頂点への経路のセットを決定する。
一般に、全ての目的を同時に最適化できる単一の解経路は存在しないので、問題はいわゆるパレート最適解の集合を見つけようとする。
この問題に対処するため、複数の多目的a*(moa*)アルゴリズムが最近開発され、品質保証付きで素早く解を計算できるようになった。
しかし、これらのMOA*アルゴリズムは、特にグラフの分岐係数(すなわち、任意の頂点の隣人の数)が大きい場合、高いメモリ使用率に悩まされることが多い。
この作業は,MOA*の高メモリ消費を,実行時にほとんど増加せずに削減することを目的としている。
複数の単一目的および多目的探索アルゴリズムを一般化して統一することにより,2つのユーザ定義ハイパーパラメータをチューニングすることにより,実行時およびメモリ効率のバランスをとるランタイムとメモリ効率のmoa*(rme-moa*)アプローチを開発した。
関連論文リスト
- Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。
本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。
提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
論文 参考訳（メタデータ） (2024-11-04T15:17:19Z) - UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
マルチオブジェクト強化学習(MORL)エージェントでは、意思決定行動の最適化を行う。
重みベクトル w でパラメータ化される線型効用関数の場合に焦点を当てる。
学習過程の異なる段階で最も有望な重みベクトルを効率的に探索する上信頼境界に基づく手法を提案する。
論文 参考訳（メタデータ） (2024-05-01T09:34:42Z) - Real-Time Image Segmentation via Hybrid Convolutional-Transformer Architecture Search [49.81353382211113]
マルチヘッド自己認識を高分解能表現CNNに効率的に組み込むという課題に対処する。
本稿では,高解像度機能の利点をフル活用したマルチターゲットマルチブランチ・スーパーネット手法を提案する。
本稿では,Hybrid Convolutional-Transformer Architecture Search (HyCTAS)法を用いて,軽量畳み込み層とメモリ効率のよい自己保持層を最適に組み合わせたモデルを提案する。
論文 参考訳（メタデータ） (2024-03-15T15:47:54Z) - 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) - 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) - Follow the bisector: a simple method for multi-objective optimization [65.83318707752385]
複数の異なる損失を最小化しなければならない最適化問題を考える。
提案手法は、各イテレーションにおける降下方向を計算し、目的関数の相対的減少を等しく保証する。
論文 参考訳（メタデータ） (2020-07-14T09:50:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。