用区间抽象加速网格路径搜索，比传统方法更快更准。
Key-Interval A*: Accelerating Grid Pathfinding via Structural Abstraction
- 将可通行区域抽象为连续区段，只关注关键边界变化
- 在8个测试组中7组最快，结构化地图提速最明显
- 适合游戏、机器人路径规划等需要精确最短路的场景
现有4连通网格路径规划的精确方法要么保留细粒度状态，要么需大量预处理。本文提出关键区间A*（KIA*），通过轻量预处理构建自由空间的紧凑区间级抽象。KIA*将可通行区域表示为最大连续可通行单元段，提取反映结构边界的关键词汇区间，并通过非关键词汇区域连接。在生成的关键区间图上执行A*搜索，并直接从区间链重构网格路径，无需细胞级局部搜索。证明了KIA*在4连通网格上的完备性和最优性。标准基准测试显示，KIA*保持精确最短路径长度，在8个基准组中7组运行时间最快，尤其在结构化和游戏地图上提升显著。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。