論文の概要: Reducing Redundant Work in Jump Point Search

• arxiv url: http://arxiv.org/abs/2306.15928v1
• Date: Wed, 28 Jun 2023 05:21:59 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-29 15:47:29.281020
• Title: Reducing Redundant Work in Jump Point Search
• Title（参考訳）: ジャンプポイント探索における冗長作業の削減
• Authors: Shizhe Zhao, Daniel Harabor, Peter J. Stuckey
• Abstract要約: JPS (Jump Point Search) は、オンライングリッドベースのパスフィンディングのための最先端のアルゴリズムである。 JPSは, 十分に研究されていない病的行動を示すことができる。 本稿では,CJPS (Constrained JPS) と呼ばれるオンライン手法を提案する。
• 参考スコア（独自算出の注目度）: 30.45272181563766
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: JPS (Jump Point Search) is a state-of-the-art optimal algorithm for online grid-based pathfinding. Widely used in games and other navigation scenarios, JPS nevertheless can exhibit pathological behaviours which are not well studied: (i) it may repeatedly scan the same area of the map to find successors; (ii) it may generate and expand suboptimal search nodes. In this work, we examine the source of these pathological behaviours, show how they can occur in practice, and propose a purely online approach, called Constrained JPS (CJPS), to tackle them efficiently. Experimental results show that CJPS has low overheads and is often faster than JPS in dynamically changing grid environments: by up to 7x in large game maps and up to 14x in pathological scenarios.
• Abstract（参考訳）: JPS (Jump Point Search) は、オンライングリッドベースのパスフィンディングのための最先端のアルゴリズムである。 ゲームやその他のナビゲーションシナリオで広く使われているが、JPSは研究されていない病理学的行動を示すことができる。 i) 地図の同じ領域を何度もスキャンして後継を見つけることができる。 (ii) 最適下探索ノードを生成して拡張する。 本研究では,これらの病的行動の源泉について検討し,実際にどのように起こるかを示し,より効率的に対処するためのオンラインアプローチであるConstrained JPS(CJPS)を提案する。 実験の結果、cjpsのオーバーヘッドは低く、動的に変化するグリッド環境ではjpsよりも高速であることが示され、大きなゲームマップでは最大7倍、病理シナリオでは最大14倍まで向上した。

関連論文リスト

• SLOPE: Search with Learned Optimal Pruning-based Expansion [2.0618817976970103]
  SLOPE(Learned Optimal Pruning-based Expansion)を用いた探索手法を提案する。 ノードの距離を最適経路から学習し、その結果、オープンリストのサイズを小さくする。 これにより、探索は最適な経路に近い領域のみを探索し、メモリと計算コストを削減できる。
  論文  参考訳（メタデータ） (2024-06-07T13:42:15Z)
• Path Planning in a dynamic environment using Spherical Particle Swarm Optimization [0.0]
  本研究では, 球面ベクトルを用いた粒子群最適化技術を用いたUAV用動的パスプランナ(DPP)を提案する。 経路は、チェックポイントを再計画する一組の経路として構築されている。経路長、安全、姿勢、経路平滑性はすべて、最適な経路がどうあるべきかを決定する上で考慮される。 実際のデジタル標高モデルを用いて4つのテストシナリオが実施される。それぞれのテストは、SPSO-DPPが安全で効率的な経路セグメントを生成することができるかを示すために、パスの長さと安全性に異なる優先順位を与える。
  論文  参考訳（メタデータ） (2024-03-19T13:56:34Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。 具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。 また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
  論文  参考訳（メタデータ） (2023-07-25T12:33:53Z)
• Enhanced Methods for the Weight Constrained Shortest Path Problem [18.567812400186092]
  WCSPP(Weight Constrained Shortest Path Problem)は、AIにおいてよく研究されているが、難しいトピックである。 本稿では, A* 探索に基づく WCSPP に対する2つの新しい解法を提案する。 我々は,大規模で現実的な問題事例の集合に対して,アルゴリズムの性能を実証的に評価した。
  論文  参考訳（メタデータ） (2022-07-29T15:32:45Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• GreedyNASv2: Greedier Search with a Greedy Path Filter [70.64311838369707]
  ワンショットNAS法では、検索スペースは通常かなり大きい(例えば1321ドル)。 本稿では,明示的な経路フィルタを用いて経路の特性を抽出し,弱い経路を直接フィルタする。 例えば、取得したGreedyNASv2-Lは、ImageNetデータセットで811.1%のTop-1精度を実現し、ResNet-50の強いベースラインを著しく上回っている。
  論文  参考訳（メタデータ） (2021-11-24T16:32:29Z)
• Waypoint Planning Networks [66.72790309889432]
  本稿では,ローカルカーネル(A*のような古典的アルゴリズム)と学習アルゴリズムを用いたグローバルカーネルを用いたLSTMに基づくハイブリッドアルゴリズムを提案する。 我々は、WPNとA*を比較し、動き計画ネットワーク(MPNet)やバリューネットワーク(VIN)を含む関連する作業と比較する。 WPN の探索空間は A* よりもかなり小さいが、ほぼ最適な結果が得られることが示されている。
  論文  参考訳（メタデータ） (2021-05-01T18:02:01Z)
• Theory-Inspired Path-Regularized Differential Network Architecture Search [206.93821077400733]
  差分アーキテクチャサーチ(DARTS)における高速ネットワーク最適化に対するスキップ接続の影響と,他のタイプの操作に対する競争上の優位性について検討する。 i)操作間の不当競争を避けるために各操作に導入された差分群構造スパース二乗ゲートと,(ii)浅部より収束する深部アーキテクチャの探索を誘導するために用いられる経路深度正規化の2つの主要なモジュールからなる理論に着想を得た経路規則化DARTSを提案する。
  論文  参考訳（メタデータ） (2020-06-30T05:28:23Z)

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

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