論文の概要: Key-Interval A*: Accelerating Grid Pathfinding via Structural Abstraction
- arxiv url: http://arxiv.org/abs/2607.23393v1
- Date: Sat, 25 Jul 2026 23:41:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-28 22:34:15.090161
- Title: Key-Interval A*: Accelerating Grid Pathfinding via Structural Abstraction
- Title（参考訳）: Key-Interval A*: 構造的抽象化によるグリッドパスフィニングの高速化
- Authors: Taiquan Sui,
- Abstract要約: Key-Interval A* (KIA*) は、軽量な前処理を用いて、自由空間のコンパクトな間隔レベルの抽象化を構築し、探索する最適パスフィニングアルゴリズムである。
標準ベンチマークの実験では、KIA*は最短パス長を正確に保ち、8つのベンチマークグループのうち7つで最速のランタイムを達成する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Existing exact methods for 4-connected grid pathfinding reduce online search, but often either retain fine-grained search states or require substantial preprocessing. This paper presents Key-Interval A* (KIA*), an optimal pathfinding algorithm that uses lightweight preprocessing to construct and search over a compact interval-level abstraction of free space. KIA* represents free space using intervals: maximal contiguous runs of traversable cells. It extracts key intervals that capture structural boundary changes and connects them through contiguous non-key regions. KIA* then performs A*-style search on the resulting key-interval graph and constructively reconstructs grid paths from interval chains, without cell-level local search. We prove the completeness and optimality of KIA* on 4-connected grids. Experiments on standard benchmarks show that KIA* preserves exact shortest-path lengths and achieves the fastest runtime on seven of eight benchmark groups, with the largest gains on structured and game maps.
- Abstract（参考訳）: 既存の4連結グリッドパスフィニングの正確な手法は、オンライン検索を減少させるが、しばしばきめ細かい検索状態を保持するか、実質的な前処理を必要とする。
本稿では、軽量な前処理を用いて、自由空間のコンパクトなインターバルレベルの抽象化を構築し、探索する最適パスフィンディングアルゴリズムであるKey-Interval A*(KIA*)を提案する。
KIA*は、間隔を使って自由空間を表現している。
構造境界の変化を捉えた鍵区間を抽出し、連続した非鍵領域を通してそれらを接続する。
すると KIA* は、結果のキー-インターバルグラフ上で A* スタイルの探索を行い、セルレベルの局所探索なしでインターバルチェーンからグリッドパスを構築的に再構築する。
4 つの連結格子上での KIA* の完全性と最適性を証明する。
KIA*は8つのベンチマークグループのうち7つの最も短いパス長を保ち、最も高速な実行を実現している。
関連論文リスト
- GONDOR to the Rescue: Satisficing Planning with Low Memory [80.8869960059932]
GONDORはGreedy Best-First Search(GBFS)の拡張である
GONDORは、アンカー状態のスパースセットを保持しながら周期的に探索木を圧縮し、ゴールに達するとスパース状態間の再探索によって経路を再構築する。
実験により、GONDORは標準のGBFSと比較して、低メモリ予算下でのカバレッジを一貫して改善することが示された。
論文 参考訳（メタデータ） (2026-05-27T13:20:58Z) - InterLoc: LiDAR-based Intersection Localization using Road Segmentation with Automated Evaluation Method [10.561470037080177]
オンライン車両中心の交差点位置決めのための新しいLiDAR方式を提案する。
我々は,鳥の視線(BEV)表現における交叉候補を,意味的道路スキャンを連結して検出する。
セマンティックKITTITIデータセットの実験から,本手法は最新の学習ベースラインよりも精度と信頼性が優れていることが示された。
論文 参考訳（メタデータ） (2025-05-01T13:30:28Z) - ETS: Efficient Tree Search for Inference-Time Scaling [61.553681244572914]
テストタイムの計算スケーリングにおいて有望なアプローチのひとつは、プロセス報酬モデルに対する検索である。
木探索過程における軌跡の多様性は、多様性の増大がさらなる探索を促進するため、探索の精度に影響を与える。
本稿では,冗長なトラジェクトリを抽出し,必要な多様なトラジェクトリを維持しながら,KVの共有を促進する効率的なツリー探索(ETS)を提案する。
論文 参考訳（メタデータ） (2025-02-19T09:30:38Z) - Pathfinding with Lazy Successor Generation [12.02023514105999]
位置のみを付与し,エッジを暗黙的に定義するパスフィンディング問題について検討する。
単純な構造にもかかわらず、この問題は膨大な数の位置で非自明になる。
そこで我々は,LaCAS*アルゴリズムを提案する。これは,全ての後継を一度に生成するのではなく,探索が進むにつれて徐々に後継を生成できる。
論文 参考訳（メタデータ） (2024-08-27T23:25:25Z) - Kolmogorov Arnold Networks in Fraud Detection: Bridging the Gap Between Theory and Practice [3.692410936160711]
本研究では,コルモゴロフ・アルノルドネットワーク(KAN)の不正検出への適用性を検討した。
そこで本研究では,PCA(Principal Component Analysis, 主成分分析)を用いて,データをスプラインを用いて2次元に分割する手法を提案する。
論文 参考訳（メタデータ） (2024-08-15T18:58:21Z) - SLOPE: Search with Learned Optimal Pruning-based Expansion [2.0618817976970103]
SLOPE(Learned Optimal Pruning-based Expansion)を用いた探索手法を提案する。
ノードの距離を最適経路から学習し、その結果、オープンリストのサイズを小さくする。
これにより、探索は最適な経路に近い領域のみを探索し、メモリと計算コストを削減できる。
論文 参考訳（メタデータ） (2024-06-07T13:42:15Z) - Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
本稿では,長距離接続を伴う複雑な検索空間上に探索アルゴリズムを構築する。
我々はtextbfIF-NAS という単純なアルゴリズムを提案し、異なるサブネットワークを構築するために周期的なサンプリング戦略を実行する。
提案した探索空間において、IF-NASはランダムサンプリングと従来の重み付け検索のアルゴリズムを有意差で上回っている。
論文 参考訳（メタデータ） (2021-12-05T06:42:48Z) - Towards Improving the Consistency, Efficiency, and Flexibility of
Differentiable Neural Architecture Search [84.4140192638394]
最も微分可能なニューラルアーキテクチャ探索法は、探索用のスーパーネットを構築し、そのサブグラフとしてターゲットネットを導出する。
本稿では,エンジンセルとトランジットセルからなるEnTranNASを紹介する。
また,検索処理の高速化を図るため,メモリや計算コストの削減も図っている。
論文 参考訳（メタデータ） (2021-01-27T12:16:47Z) - Evaluating Online and Offline Accuracy Traversal Algorithms for
k-Complete Neural Network Architectures [6.123324869194195]
本稿では,バイナリ分類のためのコンパクトニューラルネットワークアーキテクチャについて検討する。
過完全なアーキテクチャ候補を好む場合、スピードと精度の向上を調査します。
論文 参考訳（メタデータ） (2021-01-16T20:37:29Z) - ISTA-NAS: Efficient and Consistent Neural Architecture Search by Sparse
Coding [86.40042104698792]
スパース符号問題としてニューラルアーキテクチャ探索を定式化する。
実験では、CIFAR-10の2段階法では、検索にわずか0.05GPUしか必要としない。
本手法は,CIFAR-10とImageNetの両方において,評価時間のみのコストで最先端のパフォーマンスを実現する。
論文 参考訳（メタデータ） (2020-10-13T04:34:24Z) - Real-Time Semantic Segmentation via Auto Depth, Downsampling Joint
Decision and Feature Aggregation [54.28963233377946]
本稿では,セグメンテーション戦略の自動化を目的として,AutoRTNetという共同検索フレームワークを提案する。
具体的には,ネットワーク深度とダウンサンプリング戦略を協調的に決定するハイパーセルと,自動マルチスケール機能アグリゲーションを実現するアグリゲーションセルを提案する。
論文 参考訳（メタデータ） (2020-03-31T14:02:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。