arXiv preprint ·
Smoothed Analysis of Inconsistent A*
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
The Inverse Lyndon Array
High-Dimensional Ultra-Log-Concave Distributions
An Arboricity-Sensitive Algorithm for the $K_r-e$-Free Graph Sandwich Problem
Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata
Single-Pass Estimation of the Clustering Coefficient Distribution in Graph Streams
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.