Smoothed analysis explains efficient A star with imperfect heuristics
Smoothed Analysis of Inconsistent A*
Data Structures and AlgorithmsArtificial Intelligence
Summary
Sometimes computers find paths by guessing which direction is best, but their guesses can be inconsistent and cause repeated work, making them very slow in theory. The authors explain why in real life, these imperfect guesses still lead to fast results by showing that small random changes in the problem make worst-case slowdowns unlikely. They prove that with these small tweaks, the pathfinding method runs in time that grows reasonably with problem size. This understanding also applies to similar algorithms used when negative path costs occur.
What this means in practice
- •For ai system developers: Design AI search systems that use machine-learned heuristics confidently without fearing exponential slowdowns under slight problem noise.
- •For network routing engineers: Improve routing algorithms on networks with fluctuating edge weights by applying insights into run-time behavior under small random changes.
A theory result. No direct application yet.
Authors
Zhiyang Chen, Hailong Yao
Abstract
The A* search is a fundamental path-finding algorithm in artificial intelligence. While admissible and consistent heuristics guarantee efficient performance by expanding each state at most once, modern search applications frequently employ powerful but inconsistent heuristics derived from machine learning, randomized evaluations, etc. A long-standing theoretical barrier to using these inconsistent heuristics is the risk of catastrophic node re-expansion, which yields a worst-case exponential time complexity of $Ω(2^n)$. However, empirical observations contradict this pessimistic bound, demonstrating that inconsistent A* operates highly efficiently in practice. To bridge this significant gap between theory and practice, this paper presents the first smoothed analysis of the A* algorithm using inconsistent heuristics. We model typical real-world noise by applying slight random perturbations to the edge weights of worst-case search graphs. Our main result proves that the expected smoothed time complexity of inconsistent A* is bounded by a polynomial, specifically a total iteration number of $O(n^2 m κ)$, where $n$ is the number of nodes, $m$ is the number of edges, and $κ$ controls the scale of random perturbations. Furthermore, we also show that this result naturally extends to the functionally equivalent problem of Dijkstra's algorithm on negative-weight graphs.