Fugu-MT 論文翻訳(概要): S$^*$: A Heuristic Information-Based Approximation Framework for Multi-Goal Path Finding

論文の概要: S$^*$: A Heuristic Information-Based Approximation Framework for Multi-Goal Path Finding

arxiv url: http://arxiv.org/abs/2103.08155v1
Date: Mon, 15 Mar 2021 06:27:37 GMT
ステータス: 処理完了
システム内更新日: 2021-03-17 00:31:17.953034
Title: S$^*$: A Heuristic Information-Based Approximation Framework for Multi-Goal Path Finding
Title（参考訳）: S$^*$:マルチゴール経路探索のためのヒューリスティック情報に基づく近似フレームワーク
Authors: Kenny Chour, Sivakumar Rathinam, Ramamoorthi Ravi
Abstract要約: 2近似保証を提供するマルチゴールパス探索(MGPF)問題のための新しいフレームワークを開発する。 MGPFは、特定の目標セット内の各ノードが少なくとも1回はパスに沿って訪問されるように、原点から目的地までの最小コストのパスを見つけることを目指しています。拡張ノード数と実行時間の観点から,従来の代替よりもフレームワークが優れていることを示す数値的結果を提示する。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We combine ideas from uni-directional and bi-directional heuristic search, and approximation algorithms for the Traveling Salesman Problem, to develop a novel framework for a Multi-Goal Path Finding (MGPF) problem that provides a 2-approximation guarantee. MGPF aims to find a least-cost path from an origin to a destination such that each node in a given set of goals is visited at least once along the path. We present numerical results to illustrate the advantages of our framework over conventional alternates in terms of the number of expanded nodes and run time.
Abstract（参考訳）: 移動セールスマン問題に対する一方向および双方向のヒューリスティック探索のアイデアと近似アルゴリズムを組み合わせて,2近似保証を提供する多方向経路探索(mgpf)問題の新たな枠組みを開発する。 MGPFは、特定の目標セット内の各ノードが少なくとも1回はパスに沿って訪問されるように、原点から目的地までの最小コストのパスを見つけることを目指しています。拡張ノード数と実行時間の観点から,従来の代替よりもフレームワークが優れていることを示す数値的結果を提示する。

関連論文リスト

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)
Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding [49.730902939565986]
マルチエージェントパスフィンディング問題は、グラフに閉じ込められたエージェントのグループに対するコンフリクトフリーパスのセットを見つけることである。本研究では、エージェントが他のエージェントをローカルにのみ観察できる分散MAPF設定に焦点を当てた。 MAPFタスクのための分散マルチエージェントモンテカルロ木探索法を提案する。
論文参考訳（メタデータ） (2023-12-26T06:57:22Z)
Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文参考訳（メタデータ） (2023-07-25T12:33:53Z)
Multi-Prompt Alignment for Multi-Source Unsupervised Domain Adaptation [86.02485817444216]
マルチプロンプトアライメント(MPA: Multi-Prompt Alignment)は,マルチソースUDAのためのシンプルかつ効率的なフレームワークである。 MPAは、学習したプロンプトを自動エンコードプロセスで認知し、再構築されたプロンプトの合意を最大化することでそれらを調整する。実験によると、MPAは3つの一般的なデータセットで最先端の結果を達成し、DomainNetの平均精度は54.1%である。
論文参考訳（メタデータ） (2022-09-30T03:40:10Z)
Informed Steiner Trees: Sampling and Pruning for Multi-Goal Path Finding in High Dimensions [6.291017032214274]
本研究では,高次元空間における多目的経路探索問題の解法を提案する。この手法は、探索空間内の選択された領域からのサンプリングポイントと、MGPFのよい解に導かないかもしれない非強調領域との交互に行われる。
論文参考訳（メタデータ） (2022-05-09T20:46:29Z)
A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文参考訳（メタデータ） (2022-03-28T21:34:16Z)
Enhanced Multi-Objective A* Using Balanced Binary Search Trees [35.63053398687847]
アルゴリズムのような多目的A* (MOA*) は、そのノードに到達した非支配パスを追跡するために、検索中に任意のノードに「フロンティア」セットを保持する。バランスの取れた二分探索木を利用して,これらのフロンティアを多目的に効率的に維持する手法を提案する。
論文参考訳（メタデータ） (2022-02-18T02:54:58Z)
Adaptive Multi-Goal Exploration [118.40427257364729]
我々は、AdaGoalが$epsilon$-optimal goal-conditioned policyを学習する目的を達成するためにどのように使えるかを示す。 AdaGoalは、ゴール条件の深い強化学習のための既存の手法の高レベルなアルゴリズム構造に固定されている。
論文参考訳（メタデータ） (2021-11-23T17:59:50Z)
Multi-objective Conflict-based Search Using Safe-interval Path Planning [10.354181009277623]
低レベル探索のための新しい多目的セーフインターバルパス計画法 (MO-SIPP) アルゴリズムを利用するMO-CBS(Multi-objective conflict-based search)を提案する。我々は, 平均低レベル探索時間において, 等級が大幅に改善されていることを示すために, 広範囲な数値計算結果を示す。また,建設現場計画における提案アルゴリズムの適用可能性を示すケーススタディも提示する。
論文参考訳（メタデータ） (2021-08-02T09:42:08Z)
Rethinking Counting and Localization in Crowds:A Purely Point-Based Framework [59.578339075658995]
そこで本稿では,共同クラウドカウントと個別ローカライゼーションのための純粋にポイントベースのフレームワークを提案する。我々は、P2PNet(Point to Point Network)と呼ばれる、このフレームワークの下で直感的なソリューションを設計する。
論文参考訳（メタデータ） (2021-07-27T11:41:50Z)
Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering [15.99072005190786]
本稿では,MAPF問題を一般化したマルチゴールマルチエージェントパス探索法(MAPF$MG$)を提案する。我々は,MAPF$MG$に対処するために,異なるパラダイムを用いた2つの新しいアルゴリズムを提案する。Hamiltonian-CBS (HCBS) と呼ばれる検索ベース検索アルゴリズムと,SMTパラダイムを用いたコンパイルベースアルゴリズムであるSMT-Hamiltonian-CBS (SMT-HCBS) を提案する。
論文参考訳（メタデータ） (2020-09-10T22:27:18Z)

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