論文の概要: OPMOS: Ordered Parallel Multi-Objective Shortest-Path

• arxiv url: http://arxiv.org/abs/2411.16667v1
• Date: Mon, 25 Nov 2024 18:53:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-26 14:18:23.192097
• Title: OPMOS: Ordered Parallel Multi-Objective Shortest-Path
• Title（参考訳）: OPMOS: 並列多目的ショートパス
• Authors: Leo Gold, Adam Bienkowski, David Sidoti, Krishna Pattipati, Omer Khan,
• Abstract要約: MOS(Multi-Objective Shortest-Path)問題は、スタートノードからマルチ属性グラフの宛先ノードへのパレート最適解の集合を見つける。 一般化されたMOSアルゴリズムは、各ノードで部分経路の「フロンティア」を維持し、順序付けられた処理を実行する。 ここで提案されているOPMOSフレームワークは、順序付けられた並列性を解放し、MOS内の複数のパスの同時実行を効率的に活用する。
• 参考スコア（独自算出の注目度）: 0.7864304771129751
• License:
• Abstract: The Multi-Objective Shortest-Path (MOS) problem finds a set of Pareto-optimal solutions from a start node to a destination node in a multi-attribute graph. To solve the NP-hard MOS problem, the literature explores heuristic multi-objective A*-style algorithmic approaches. A generalized MOS algorithm maintains a "frontier" of partial paths at each node and performs ordered processing to ensure that Pareto-optimal paths are generated to reach the goal node. The algorithm becomes computationally intractable as the number of objectives increases due to a rapid increase in the non-dominated paths, and the concomitantly large increase in Pareto-optimal solutions. While prior works have focused on algorithmic methods to reduce the complexity, we tackle this challenge by exploiting parallelism using an algorithm-architecture approach. The key insight is that MOS algorithms rely on the ordered execution of partial paths to maintain high work efficiency. The OPMOS framework, proposed herein, unlocks ordered parallelism and efficiently exploits the concurrent execution of multiple paths in MOS. Experimental evaluation using the NVIDIA GH200 Superchip shows the performance scaling potential of OPMOS on work efficiency and parallelism using a real-world application to ship routing.
• Abstract（参考訳）: MOS(Multi-Objective Shortest-Path)問題は、スタートノードからマルチ属性グラフの宛先ノードへのパレート最適解の集合を見つける。 NP-hard MOSの問題を解決するために、本論文はヒューリスティックな多目的A*スタイルのアルゴリズムアプローチを探求する。 一般化されたMOSアルゴリズムは各ノードにおける部分経路の「フロンティア」を維持し、目標ノードに到達するためにパレート最適経路を生成するように順序付き処理を実行する。 このアルゴリズムは、非支配パスの急速な増加とパレート最適解の同時増加により、目的の数が増加するにつれて、計算的に難解になる。 従来の研究は複雑性を減らすためにアルゴリズム手法に重点を置いてきたが、アルゴリズムアーキテクチャアプローチを用いて並列性を活用することでこの問題に取り組む。 鍵となる洞察は、MOSアルゴリズムが高い作業効率を維持するために部分経路の順序付き実行に依存していることである。 ここで提案されているOPMOSフレームワークは、順序付けられた並列性を解放し、MOS内の複数のパスの同時実行を効率的に活用する。 NVIDIA GH200 Superchip を用いた実験評価では,OPMOS の作業効率と並列性における性能スケーリングの可能性を示す。

関連論文リスト

• LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning [91.95362946266577]
  経路計画はロボット工学と自律航法における基本的な科学的問題である。 A*やその変種のような伝統的なアルゴリズムは、パスの妥当性を保証することができるが、状態空間が大きくなるにつれて、計算とメモリの非効率が著しく低下する。 本稿では, A* の正確なパスフィニング能力と LLM のグローバルな推論能力とを相乗的に組み合わせた LLM ベースの経路計画法を提案する。 このハイブリッドアプローチは、特に大規模シナリオにおいて、パス妥当性の完全性を維持しながら、時間と空間の複雑さの観点からパスフィニング効率を向上させることを目的としている。
  論文  参考訳（メタデータ） (2024-06-20T01:24:30Z)
• Optimizing Tensor Contraction Paths: A Greedy Algorithm Approach With Improved Cost Functions [1.3812010983144802]
  より少ない時間で効率的な収縮経路を計算できる opt_einsum による欲求アルゴリズムに基づく新しい手法を提案する。 我々のアプローチでは、現代のアルゴリズムが失敗する大きな問題に対するパスを計算できる。
  論文  参考訳（メタデータ） (2024-05-08T09:25:39Z)
• A Conflict-Aware Optimal Goal Assignment Algorithm for Multi-Robot Systems [6.853165736531941]
  マルチロボットアプリケーションは、衝突のない経路を確保しながら、各ロボットにユニークな目標を割り当てることを目的としている。 そこで本研究では,次の最適な割り当てを計算するための効率的な競合誘導手法を提案する。 複数のベンチマークワークスペース上で,最大100個のロボットに対して,我々のアルゴリズムを広範囲に評価した。
  論文  参考訳（メタデータ） (2024-02-19T19:04:19Z)
• Enhanced Multi-Objective A* with Partial Expansion [22.45142249108214]
  グラフ上に現れる多目的短経路問題(MO-SPP)は、複数の目的を最適化しながら経路の集合を決定する。 この問題に対処するため,複数のMOA*アルゴリズムが最近開発された。 この作業は,MOA*の高メモリ消費を,実行時にほとんど増加せずに削減することを目的としている。
  論文  参考訳（メタデータ） (2022-12-06T05:48:11Z)
• Entropic Neural Optimal Transport via Diffusion Processes [105.34822201378763]
  本稿では,連続確率分布間のエントロピー最適輸送(EOT)計画を計算するための新しいアルゴリズムを提案する。 提案アルゴリズムは,シュリンガーブリッジ問題(Schr"odinger Bridge problem)として知られるEOTの動的バージョンのサドル点再構成に基づく。 大規模EOTの従来の手法とは対照的に,我々のアルゴリズムはエンドツーエンドであり,単一の学習ステップで構成されている。
  論文  参考訳（メタデータ） (2022-11-02T14:35:13Z)
• Arch-Graph: Acyclic Architecture Relation Predictor for Task-Transferable Neural Architecture Search [96.31315520244605]
  Arch-Graphはタスク固有の最適アーキテクチャを予測するトランスファー可能なNASメソッドである。 Arch-Graphの転送性と,多数のタスクにわたる高いサンプル効率を示す。 わずか50モデルの予算の下で、2つの検索スペースで平均して0.16%と0.29%のアーキテクチャを見つけることができる。
  論文  参考訳（メタデータ） (2022-04-12T16:46:06Z)
• Multi-Robot Active Mapping via Neural Bipartite Graph Matching [49.72892929603187]
  本稿では,最小時間ステップにおけるシーンマップ構築の完全化を目的としたマルチロボットアクティブマッピングの問題点について検討する。 この問題の鍵は、より効率的なロボットの動きを可能にするゴール位置推定にある。 本稿では,ニューラルコマッピング(NeuralCoMapping)という新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-03-30T14:03:17Z)
• 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)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。 古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。 提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
  論文  参考訳（メタデータ） (2020-06-15T02:57:57Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。