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.
Blogger's Review: The KIA* algorithm successfully reduces search state complexity and enhances pathfinding efficiency by introducing the concept of key intervals. This structural abstraction not only optimizes runtime but also maintains path accuracy, providing new insights for future pathfinding research.