SOURCE-LINKED INTELLIGENCE

Smoothed Analysis of Inconsistent A*

arXiv · AI, language, vision and robotics · article · Sep 20, 2026 · UTC

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, demonst

Read original source ↗ Open in workspace

recordType

paper

region

Global