When the Worst Case Won’t Stay Put: What Small Perturbations Do to Inconsistent A*
TL;DR for operators Chen and Yao’s Smoothed Analysis of Inconsistent A*1 studies a familiar problem in search systems: an inconsistent heuristic can cause A* to reopen previously processed nodes, and classical constructions allow the resulting work to grow exponentially. The paper shows that this failure mode can be surprisingly fragile. Under independent random perturbations of edge weights whose probability densities are bounded by $\kappa$, the expected number of A* iterations is ...