論文の概要: Optimal Any-Angle Pathfinding on a Sphere
- arxiv url: http://arxiv.org/abs/2004.12781v2
- Date: Mon, 2 Nov 2020 09:50:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-10 04:12:09.417536
- Title: Optimal Any-Angle Pathfinding on a Sphere
- Title(参考訳): 球面上の最適任意の角度パスフィニング
- Authors: Volodymyr Rospotniuk and Rupert Small
- Abstract要約: 本稿では球面上の点対間の最短経路を計算するための任意の角度パスフィンディングアルゴリズムについて述べる。
ユークリッド空間の Anya は (Harabor & Grastien, 2013) によって説明され、球面幾何学に拡張可能であることが示されている。
パフォーマンスベンチマークはStarcraftやWarcraft IIIなどいくつかのゲームマップに提供されている。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Pathfinding in Euclidean space is a common problem faced in robotics and
computer games. For long-distance navigation on the surface of the earth or in
outer space however, approximating the geometry as Euclidean can be
insufficient for real-world applications such as the navigation of spacecraft,
aeroplanes, drones and ships. This article describes an any-angle pathfinding
algorithm for calculating the shortest path between point pairs over the
surface of a sphere. Introducing several novel adaptations, it is shown that
Anya as described by (Harabor & Grastien, 2013) for Euclidean space can be
extended to Spherical geometry. There, where the shortest-distance line between
coordinates is defined instead by a great-circle path, the optimal solution is
typically a curved line in Euclidean space. In addition the turning points for
optimal paths in Spherical geometry are not necessarily corner points as they
are in Euclidean space, as will be shown, making further substantial
adaptations to Anya necessary. Spherical Anya returns the optimal path on the
sphere, given these different properties of world maps defined in Spherical
geometry. It preserves all primary benefits of Anya in Euclidean geometry,
namely the Spherical Anya algorithm always returns an optimal path on a sphere
and does so entirely on-line, without any preprocessing or large memory
overheads. Performance benchmarks are provided for several game maps including
Starcraft and Warcraft III as well as for sea navigation on Earth using the
NOAA bathymetric dataset. Always returning the shorter path compared with the
Euclidean approximation yielded by Anya, Spherical Anya is shown to be faster
than Anya for the majority of sea routes and slower for Game Maps and Random
Maps.
- Abstract(参考訳): ユークリッド空間における経路探索はロボット工学やコンピュータゲームでよく見られる問題である。
しかし、地球表面や宇宙空間での長距離航法では、ユークリッドとして幾何学を近似することは、宇宙船、飛行機、ドローン、船などの現実の用途には不十分である。
本稿では球面上の点対間の最短経路を計算するための任意の角度パスフィンディングアルゴリズムについて述べる。
いくつかの新しい適応を導入し、ユークリッド空間に対して (Harabor & Grastien, 2013) で記述されたアニヤが球面幾何学に拡張できることが示されている。
ここで、座標間の最短距離線が大円の経路で定義されるとき、最適解は通常ユークリッド空間の曲線である。
加えて、球面幾何学における最適経路のターニングポイントは、ユークリッド空間にあるから必ずしもコーナーポイントではない。
球面 Anya は、球面幾何学で定義された世界地図のこれらの異なる性質を考えると、球面上の最適経路を返す。
ユークリッド幾何学におけるAnyaの主な利点、すなわち球状Anyaアルゴリズムは、常に球面上の最適経路を返却し、前処理や大きなメモリオーバーヘッドなしに完全にオンライン化する。
パフォーマンスベンチマークは、StarcraftやWarcraft IIIなどいくつかのゲームマップや、NOAAの観測データを用いた地球上の海上航行に提供されている。
Anyaによるユークリッド近似よりも短い経路を返す場合、Spherical Anyaは航路の大部分でAnyaよりも高速で、Game MapsやRandom Mapsでは遅いことが示されている。
関連論文リスト
- Online Vectorized HD Map Construction using Geometry [18.602869210526848]
本稿では,地図インスタンスのユークリッド形状と関係を基本的な知覚を超えて学習するGeMapを提案する。
提案手法は,NuScenesおよびArgoverse 2データセット上での最先端性能を実現する。
論文 参考訳(メタデータ) (2023-12-06T08:26:26Z) - Neural Latent Geometry Search: Product Manifold Inference via
Gromov-Hausdorff-Informed Bayesian Optimization [21.97865037637575]
我々は、この新しい定式化を数学的に定義し、ニューラル潜在幾何探索(NLGS)として作成する。
計量幾何学からのグロモフ・ハウスドルフ距離に基づいて、候補潜在測地間の距離の新たな概念を提案する。
次に、潜在測地間の滑らかさの概念に基づいてグラフ探索空間を設計し、その計算を帰納バイアスとして利用する。
論文 参考訳(メタデータ) (2023-09-09T14:29:22Z) - Sphere2Vec: A General-Purpose Location Representation Learning over a
Spherical Surface for Large-Scale Geospatial Predictions [73.60788465154572]
現在の2Dおよび3D位置エンコーダはユークリッド空間における点距離をモデル化するために設計されている。
本研究では,球面上の点座標を符号化する場合に,球面距離を保存できるSphere2Vecというマルチスケール位置エンコーダを提案する。
論文 参考訳(メタデータ) (2023-06-30T12:55:02Z) - GeoUDF: Surface Reconstruction from 3D Point Clouds via Geometry-guided
Distance Representation [73.77505964222632]
スパース点雲から離散曲面を再構成する問題に対処する学習ベース手法であるGeoUDFを提案する。
具体的には、UDFのための幾何誘導学習法とその勾配推定を提案する。
予測されたUDFから三角形メッシュを抽出するために,カスタマイズされたエッジベースマーチングキューブモジュールを提案する。
論文 参考訳(メタデータ) (2022-11-30T06:02:01Z) - GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation [93.60478281489243]
3次元曲面上の測地線経路を近似する学習可能なネットワークを提案する。
提案手法は,最短経路の効率的な近似と測地距離推定を提供する。
論文 参考訳(メタデータ) (2022-05-30T16:22:53Z) - Absolute Triangulation Algorithms for Space Exploration [0.0]
この研究は三角測量の歴史と理論的基礎の包括的なレビューを提供する。
ハートレーやストゥルムと同じ解を提供する2つの新しい最適非定性三角法アルゴリズムが導入された。
様々な三角法アルゴリズムは、惑星の相対的な航法を含むいくつかの数値的な例で評価される。
論文 参考訳(メタデータ) (2022-05-24T16:54:07Z) - Neural Convolutional Surfaces [59.172308741945336]
この研究は、大域的、粗い構造から、微細で局所的で、おそらく繰り返される幾何学を歪める形状の表現に関係している。
このアプローチは, 最先端技術よりも優れたニューラル形状圧縮を実現するとともに, 形状詳細の操作と伝達を可能にする。
論文 参考訳(メタデータ) (2022-04-05T15:40:11Z) - Geometric decomposition of geodesics and null phase curves using
Majorana star representation [0.0]
ヒルベルト空間の測地線をブロッホ球面上の$n-1$曲線に分解するためにマヨラナ星表現を用いる。
また、$(n>2)$-次元ヒルベルト空間に対して任意の2つの任意の状態間で無限に多くのNPCを構成する方法を提案する。
論文 参考訳(メタデータ) (2022-02-24T17:21:17Z) - SPIN Road Mapper: Extracting Roads from Aerial Images via Spatial and
Interaction Space Graph Reasoning for Autonomous Driving [64.10636296274168]
道路抽出は、自律航法システムを構築するための重要なステップである。
この問題に対して単に畳み込みニューラルネットワーク(ConvNets)を使用することは、画像内の道路セグメント間の遠い依存関係をキャプチャする非効率であるため、効果がない。
本研究では,ConvNetに接続した時,特徴写像から投影された空間空間および相互作用空間上に構築されたグラフの推論を行う空間空間グラフ推論(SPIN)モジュールを提案する。
論文 参考訳(メタデータ) (2021-09-16T03:52:17Z) - PUGeo-Net: A Geometry-centric Network for 3D Point Cloud Upsampling [103.09504572409449]
PUGeo-Netと呼ばれる新しいディープニューラルネットワークを用いた一様高密度点雲を生成する手法を提案する。
その幾何学中心の性質のおかげで、PUGeo-Netはシャープな特徴を持つCADモデルとリッチな幾何学的詳細を持つスキャンされたモデルの両方でうまく機能する。
論文 参考訳(メタデータ) (2020-02-24T14:13:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。