論文の概要: Enhanced Multi-Objective A* Using Balanced Binary Search Trees

• arxiv url: http://arxiv.org/abs/2202.08992v1
• Date: Fri, 18 Feb 2022 02:54:58 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-21 14:30:01.470203
• Title: Enhanced Multi-Objective A* Using Balanced Binary Search Trees
• Title（参考訳）: balanced binary search treeを用いた多目的a*の拡張
• Authors: Zhongqiang Ren, Sivakumar Rathinam, Maxim Likhachev and Howie Choset
• Abstract要約: アルゴリズムのような多目的A* (MOA*) は、そのノードに到達した非支配パスを追跡するために、検索中に任意のノードに「フロンティア」セットを保持する。 バランスの取れた二分探索木を利用して,これらのフロンティアを多目的に効率的に維持する手法を提案する。
• 参考スコア（独自算出の注目度）: 35.63053398687847
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work addresses the Multi-Objective Shortest Path Problem (MO-SPP): Given a graph where each edge is associated with a non-negative cost vector, MO-SPP aims to find all the Pareto-optimal paths connecting the given start and goal nodes. To solve MO-SPP, the popular multi-objective A* (MOA*) like algorithms maintain a "frontier" set at any node during the search to keep track of the non-dominated paths that reach that node. The computational efficiency of MOA* algorithms directly depend on how efficiently one can maintain the frontier sets. Recently, several techniques have been developed in the literature to address this issue mainly for two objectives. In this work, we introduce a new method to efficiently maintain these frontiers for multiple objectives by leveraging balanced binary search trees. We provide extensive simulation results for problems with three, four and five objectives to show that our method outperforms existing techniques by an order of magnitude in general.
• Abstract（参考訳）: この研究は、MO-SPP (Multi-Objective Shortest Path Problem) に対処する: 各エッジが非負のコストベクトルに関連付けられているグラフが与えられたら、MO-SPPは、与えられた開始ノードとゴールノードを接続するパレート最適化パスの全てを見つけることを目的としている。 mo-sppを解決するために、アルゴリズムのような一般的なマルチ目的a*(moa*)は、検索中に任意のノードに"frontier"セットを保持し、そのノードに到達する非支配的なパスを追跡する。 moa*アルゴリズムの計算効率は、フロンティア集合をいかに効率的に維持できるかに直接依存する。 近年,主に2つの目的のために,この問題に対処する技術が文献で開発されている。 本研究では,バランスの取れた二分探索木を利用して,これらのフロンティアを多目的に効率的に維持する手法を提案する。 3,4,5の課題に対して広範なシミュレーション結果を提供し,提案手法が既存の手法を1桁上回ることを示した。

関連論文リスト

• OPMOS: Ordered Parallel Multi-Objective Shortest-Path [0.7864304771129751]
  MOS(Multi-Objective Shortest-Path)問題は、スタートノードからマルチ属性グラフの宛先ノードへのパレート最適解の集合を見つける。 一般化されたMOSアルゴリズムは、各ノードで部分経路の「フロンティア」を維持し、順序付けられた処理を実行する。 ここで提案されているOPMOSフレームワークは、順序付けられた並列性を解放し、MOS内の複数のパスの同時実行を効率的に活用する。
  論文  参考訳（メタデータ） (2024-11-25T18:53:49Z)
• 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)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。 具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。 また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
  論文  参考訳（メタデータ） (2023-07-25T12:33:53Z)
• SparseTrack: Multi-Object Tracking by Performing Scene Decomposition based on Pseudo-Depth [84.64121608109087]
  2次元画像から目標の相対的な深さを求めるための擬似深度推定法を提案する。 次に,得られた深度情報を用いて,高密度なターゲットセットを複数のスパースなターゲットサブセットに変換するディープカスケードマッチング(DCM)アルゴリズムを設計する。 擬似深度法とDCM戦略をデータアソシエーションプロセスに統合することにより、SparseTrackと呼ばれる新しいトラッカーを提案する。
  論文  参考訳（メタデータ） (2023-06-08T14:36:10Z)
• Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids [0.190365714903665]
  エージェントを2つのチームに分けた2色MAPFがNPハードのままであることを示す。 フロータイムの目的のために,エージェントの移動数に基づいてトラクタビリティフロンティアを確立する。 この結果は最適解の構造に新たな光を当て、一般的な問題のアルゴリズム設計を導くのに役立つかもしれない。
  論文  参考訳（メタデータ） (2023-05-25T17:56:24Z)
• Enhanced Multi-Objective A* with Partial Expansion [22.45142249108214]
  グラフ上に現れる多目的短経路問題(MO-SPP)は、複数の目的を最適化しながら経路の集合を決定する。 この問題に対処するため,複数のMOA*アルゴリズムが最近開発された。 この作業は,MOA*の高メモリ消費を,実行時にほとんど増加せずに削減することを目的としている。
  論文  参考訳（メタデータ） (2022-12-06T05:48:11Z)
• Multi-Robot Active Mapping via Neural Bipartite Graph Matching [49.72892929603187]
  本稿では,最小時間ステップにおけるシーンマップ構築の完全化を目的としたマルチロボットアクティブマッピングの問題点について検討する。 この問題の鍵は、より効率的なロボットの動きを可能にするゴール位置推定にある。 本稿では,ニューラルコマッピング(NeuralCoMapping)という新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-03-30T14:03:17Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• S$^*$: A Heuristic Information-Based Approximation Framework for Multi-Goal Path Finding [0.0]
  2近似保証を提供するマルチゴールパス探索(MGPF)問題のための新しいフレームワークを開発する。 MGPFは、特定の目標セット内の各ノードが少なくとも1回はパスに沿って訪問されるように、原点から目的地までの最小コストのパスを見つけることを目指しています。 拡張ノード数と実行時間の観点から,従来の代替よりもフレームワークが優れていることを示す数値的結果を提示する。
  論文  参考訳（メタデータ） (2021-03-15T06:27:37Z)

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

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