論文の概要: A Generalized A* Algorithm for Finding Globally Optimal Paths in
Weighted Colored Graphs
- arxiv url: http://arxiv.org/abs/2012.13057v1
- Date: Thu, 24 Dec 2020 01:27:31 GMT
- ステータス: 翻訳完了
- システム内更新日: 2021-04-25 08:09:32.894507
- Title: A Generalized A* Algorithm for Finding Globally Optimal Paths in
Weighted Colored Graphs
- Title（参考訳）: 重み付き有色グラフにおける大域的最適経路を求める一般化a*アルゴリズム
- Authors: Jaein Lim and Panagiotis Tsiotras
- Abstract要約: ここで定義される最適性の概念に関して、クラス順序A*(COA*)アルゴリズムの完全性と最適性を証明する。
coa* は不確かでない経路を見つけるという点で a* の解を支配する。
- 参考スコア（独自算出の注目度）: 14.175900236492922
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Both geometric and semantic information of the search space is imperative for
a good plan. We encode those properties in a weighted colored graph (geometric
information in terms of edge weight and semantic information in terms of edge
and vertex color), and propose a generalized A* to find the shortest path among
the set of paths with minimal inclusion of low-ranked color edges. We prove the
completeness and optimality of this Class-Ordered A* (COA*) algorithm with
respect to the hereto defined notion of optimality. The utility of COA* is
numerically validated in a ternary graph with feasible, infeasible, and unknown
vertices and edges for the cases of a 2D mobile robot, a 3D robotic arm, and a
5D robotic arm with limited sensing capabilities. We compare the results of
COA* to that of the regular A* algorithm, the latter of which finds the
shortest path regardless of uncertainty, and we show that the COA* dominates
the A* solution in terms of finding less uncertain paths.
- Abstract（参考訳）: 探索空間の幾何学的情報と意味的情報の両方が良い計画に不可欠である。
それらの特性を重み付き色グラフ(エッジ重みと頂点色で意味情報を表す幾何学的情報)にエンコードし、低ランク色エッジを最小に含む経路群の中で最短経路を求める一般化されたA*を提案する。
このクラス順序付きA*(COA*)アルゴリズムの完全性と最適性は、ここで定義された最適性の概念に対して証明する。
coa*の実用性は、2d移動ロボットや3dロボットアーム、センサー能力に乏しい5dロボットアームの場合には、実現可能で実現不可能で未知の頂点と縁を持つ3次グラフで数値的に検証される。
我々はCOA*の結果を通常のA*アルゴリズムと比較し、後者は不確実性に関係なく最短経路を見つけ、COA*がA*解を支配していることを示す。
関連論文リスト
- MATA*: Combining Learnable Node Matching with A* Algorithm for
Approximate Graph Edit Distance Computation [12.437507185260577]
正確なグラフ編集距離(GED)計算はNP完全であることが知られている。
グラフニューラルネットワーク(GNN)とA*アルゴリズムに基づく近似GED計算のためのデータ駆動型ハイブリッドアプローチMATA*を提案する。
論文 参考訳（メタデータ） (2023-11-04T09:33:08Z) - ELRA: Exponential learning rate adaption gradient descent optimization
method [83.88591755871734]
我々は, 高速(指数率), ab initio(超自由)勾配に基づく適応法を提案する。
本手法の主な考え方は,状況認識による$alphaの適応である。
これは任意の次元 n の問題に適用でき、線型にしかスケールできない。
論文 参考訳（メタデータ） (2023-09-12T14:36:13Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with
Feedback Graphs [21.563733343861713]
フィードバックグラフを用いたオンライン学習は、学習者のフィードバックが行動集合上の有向グラフによって決定されるシーケンシャルな意思決定フレームワークである。
本稿では,このフレームワークで学習するための計算効率のよいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-01T15:14:32Z) - GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation [93.60478281489243]
3次元曲面上の測地線経路を近似する学習可能なネットワークを提案する。
提案手法は,最短経路の効率的な近似と測地距離推定を提供する。
論文 参考訳（メタデータ） (2022-05-30T16:22:53Z) - Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm
and Application to 3D Multi-Shape Analysis [69.08838724594584]
グラフ内の最短経路を見つけることは、コンピュータビジョンやグラフィックスにおける多くの問題に関係している。
本稿では,行列値のエッジを持つグラフにおいて,最短経路のグラフ理論を新たに導入する。
論文 参考訳（メタデータ） (2021-12-08T08:23:37Z) - Robust and Accurate Superquadric Recovery: a Probabilistic Approach [29.7543198254021]
点雲から超四分儀を回収する最初の確率的手法を提案する。
提案手法は, 合成データセットと実世界のデータセットの精度, 効率, 堅牢性の観点から, 最先端の手法より優れている。
論文 参考訳（メタデータ） (2021-11-29T13:17:17Z) - Escaping Saddle Points in Nonconvex Minimax Optimization via
Cubic-Regularized Gradient Descent-Ascent [13.565010494569243]
勾配降下度アルゴリズム(GDA)は、非ミニマックス最適化問題の解法として広く応用されている。
我々は,非コンケーブ極小最適化における点のエスケープのための第一型GDAアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-10-14T00:36:44Z) - Generalized AdaGrad (G-AdaGrad) and Adam: A State-Space Perspective [0.0]
非機械学習問題の解法として,高速で一般化されたAdaGrad(G-AdaGrad)を提案する。
具体的には、G-AdaGradとAdamという収束加速アルゴリズムを解析するために状態空間の視点を採用する。
論文 参考訳（メタデータ） (2021-05-31T20:30:25Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。