論文の概要: AMRA*: Anytime Multi-Resolution Multi-Heuristic A*
- arxiv url: http://arxiv.org/abs/2110.05328v2
- Date: Thu, 23 Mar 2023 15:36:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-24 19:05:27.457046
- Title: AMRA*: Anytime Multi-Resolution Multi-Heuristic A*
- Title（参考訳）: AMRA*: マルチリゾリューションマルチヒューリスティックA*
- Authors: Dhruv Mauria Saxena, Tushar Kusnur, Maxim Likhachev
- Abstract要約: MRA* (Multi-Resolution A*) は複数の解像度を探索する。
AMRA* は、粗い分解能をできるだけ早く利用して、解を見つけようとする。
そして、粗い解像度では得られなかったかもしれないより良い経路を見つけるために、微細な解像度に頼ることで、解を洗練する。
- 参考スコア（独自算出の注目度）: 21.927948636840682
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Heuristic search-based motion planning algorithms typically discretise the
search space in order to solve the shortest path problem. Their performance is
closely related to this discretisation. A fine discretisation allows for better
approximations of the continuous search space, but makes the search for a
solution more computationally costly. A coarser resolution might allow the
algorithms to find solutions quickly at the expense of quality. For large state
spaces, it can be beneficial to search for solutions across multiple
resolutions even though defining the discretisations is challenging. The
recently proposed algorithm Multi-Resolution A* (MRA*) searches over multiple
resolutions. It traverses large areas of obstacle-free space and escapes local
minima at a coarse resolution. It can also navigate so-called narrow
passageways at a finer resolution. In this work, we develop AMRA*, an anytime
version of MRA*. AMRA* tries to find a solution quickly using the coarse
resolution as much as possible. It then refines the solution by relying on the
fine resolution to discover better paths that may not have been available at
the coarse resolution. In addition to being anytime, AMRA* can also leverage
information sharing between multiple heuristics. We prove that AMRA* is
complete and optimal (in-the-limit of time) with respect to the finest
resolution. We show its performance on 2D grid navigation and 4D kinodynamic
planning problems.
- Abstract（参考訳）: ヒューリスティックな探索に基づく動き計画アルゴリズムは、最も短い経路問題を解決するために探索空間を区別する。
彼らの演技は、この離散化と密接に関連している。
細かい離散化は連続探索空間のより良い近似を可能にするが、解の探索はより計算コストがかかる。
粗い解決法により、アルゴリズムは品質を犠牲にして迅速に解を見つけることができる。
大きな状態空間の場合、離散化を定義することは難しいが、複数の解像度で解を探すことは有益である。
最近提案されたMulti-Resolution A* (MRA*) アルゴリズムは複数の解像度を探索する。
障害物のない空間の広い領域を横切り、粗い解像度で局所的なミニマを逃れる。
いわゆる狭い通路を、より細かい解像度でナビゲートすることもできる。
本研究では,MRA*の任意のバージョンであるAMRA*を開発する。
AMRA* は粗い分解能をできるだけ早く利用して解を見つけようとする。
そして、粗い解像度では利用できなかったより良い経路を見つけるために、細かい解像度に依存することで、ソリューションを洗練します。
いつでも、amra*は複数のヒューリスティック間での情報共有を利用することもできる。
我々は、amra* が最も細かい分解能に関して完全かつ最適である(時間の範囲内)ことを証明する。
2次元グリッドナビゲーションと4次元キノダイナミック計画問題にその性能を示す。
関連論文リスト
- Space Net Optimization [1.0323063834827415]
ほとんどのメタヒューリスティックアルゴリズムは、収束過程において後続の探索を導くためのいくつかの探索解に依存している。
スペースネット最適化(SNO)と呼ばれる新しいメタヒューリスティックアルゴリズムを提案する。
スペースネットと呼ばれる新しいメカニズムを備えており、メタヒューリスティックアルゴリズムは全ての探索された解から得られるほとんどの情報を使って、解空間の風景を描写することができる。
論文 参考訳（メタデータ） (2023-05-31T15:44:18Z) - Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids [0.190365714903665]
エージェントを2つのチームに分けた2色MAPFがNPハードのままであることを示す。
フロータイムの目的のために,エージェントの移動数に基づいてトラクタビリティフロンティアを確立する。
この結果は最適解の構造に新たな光を当て、一般的な問題のアルゴリズム設計を導くのに役立つかもしれない。
論文 参考訳（メタデータ） (2023-05-25T17:56:24Z) - Efficient Joint-Dimensional Search with Solution Space Regularization
for Real-Time Semantic Segmentation [27.94898516315886]
この問題に対して,リアルタイムに実行可能な最適ネットワーク構造を探索する。
新たな解空間規則化(SSR)損失は、スーパーネットが離散的に収束することを効果的に促すために最初に提案される。
より高効率な探索を実現するために,新しい階層的・プログレッシブ・ソリューション・スペース・スライキング法を提案する。
論文 参考訳（メタデータ） (2022-08-10T11:07:33Z) - Learning Resolution-Adaptive Representations for Cross-Resolution Person
Re-Identification [49.57112924976762]
低解像度(LR)クエリIDイメージと高解像度(HR)ギャラリーイメージとの整合性を実現する。
実際のカメラとの違いにより、クエリ画像が分解能の低下に悩まされることがしばしばあるため、これは困難かつ実用的な問題である。
本稿では,問合せ画像の解像度に適応する動的計量を用いて,HRとLRの画像を直接比較するためのSRフリーなパラダイムについて検討する。
論文 参考訳（メタデータ） (2022-07-09T03:49:51Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。
連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。
提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
論文 参考訳（メタデータ） (2021-11-01T21:06:35Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Scale-Localized Abstract Reasoning [79.00011351374869]
本稿では,インテリジェンステストとしてよく用いられる抽象的関係推論タスクについて考察する。
いくつかのパターンは空間的有理性を持っているが、他のパターンは意味論に過ぎないため、各クエリを複数の解像度で処理するマルチスケールアーキテクチャを提案する。
異なる解法によって実際に異なるルールが解かれることを示し、組み合わせたマルチスケールアプローチは、全てのベンチマークにおいて、このタスクにおける既存の技術の状態を5～54%上回っていることを示す。
論文 参考訳（メタデータ） (2020-09-20T10:37:29Z) - Learning What to Defer for Maximum Independent Sets [84.00112106334655]
本稿では,各段階における解の要素的決定を学習することにより,エージェントが適応的に段階数を縮小あるいは拡張する,新たなDRL方式を提案する。
提案手法を最大独立集合(MIS)問題に適用し、現状のDRL方式よりも大幅に改善したことを示す。
論文 参考訳（メタデータ） (2020-06-17T02:19:31Z) - Multi-Resolution A* [19.562565022582785]
ヒューリスティック検索に基づく計画手法は、離散化された空間上での運動計画に一般的に用いられる。
本稿では,複数の重み付きA*(WA*)探索を同時に行うマルチリゾリューションA*アルゴリズムを提案する。
MRA* はアンカー分解能探索空間と分解能完備性に関して有界な準最適であることを示す。
論文 参考訳（メタデータ） (2020-04-14T17:38:11Z) - sKPNSGA-II: Knee point based MOEA with self-adaptive angle for Mission
Planning Problems [2.191505742658975]
いくつかの問題には、多くの非支配的な解をもたらす多くの目的がある。
本稿では,最も重要な解を得るために設計された新しいアルゴリズムを提案する。
このアルゴリズムは無人航空機(UAV)ミッション計画問題における実世界の応用に応用されている。
論文 参考訳（メタデータ） (2020-02-20T17:07:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。