# Key-Interval A*: Accelerating Grid Pathfinding via Structural Abstraction

arXiv: https://arxiv.org/abs/2607.23393 · HTML: https://mlsanity.com/paper/2607.23393/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 7 references that are in the map.
- First posted on arXiv 25 Jul 2026.

## Abstract (arXiv)

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.