cs.DSSep 20, 2026

Smoothed Analysis of Inconsistent A*

Authors: Zhiyang Chen, Hailong Yao

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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 Ω(2n)Ω(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(n2mκ)O(n^2 m κ), where nn is the number of nodes, mm 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.

Figures & tables

Figure 1: (a) Direct updates; (b) Indirect updates. Blue paths denote original paths, and red paths denote updated paths.
Figure 2: Pareto-optimal conditions for node expansions.
Figure 3: Martelli’s instance for inconsistent A*. Blue integers are edge weights, and brown integers are heuristic values.
Figure 4: The iteration number of inconsistent A* on Martelli’s instance.
More in this topic

Graph-Based Planning

Graph-Based Planning represents states, tasks, or environments as nodes and edges to search for feasible, low-cost action sequences.

See all 99 papers

Explore similar work

CardsList
Sep 20, 2026

Expansion Counts under Standard A* Tie-Breaking Strategies on the Final Plateau

In the A* search algorithm, the tie-breaking strategies for nodes with the same ff-value determines which states A* expands on the final ff-layer. For nine standard tie-breaking strategies, we show that under a consistent heuristic, every pair has positive-cost instances favoring each strategy over the other by an arbitrarily large additive expansion gap. A parameterized unit-cost grid example also gives unbounded expansion-count ratios between low-hh with FIFO and LIFO. In unit-cost search with h>0h > 0 at non-goals, exact heuristic values near the goal lead to complementary extremal results: low-hh minimizes the number of remaining expansions from a common configuration within the perfect region, while high-hh maximizes the total number of expansions when every final-plateau state with h=1h=1 is a goal predecessor. Finally, with the evaluation function fα=g+αhf_α = g + αh, when h>0h>0 at non-goals, every heuristic weight 0≤α<10 \leq α<1 eliminates tie-breaking sensitivity, and all tie-breaking strategies expand the same set of states.

Alex Fukunaga

The University of Tokyo

Tree Search
AskPDF
Jul 25, 2026

Key-Interval A*: Accelerating Grid Pathfinding via Structural Abstraction

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.

Taiquan Sui

Department of Computer Science and Engineering, Chalmers University of Technology, Gothenburg, Sweden

Graph-Based Planning
AskPDF
Feb 27, 2026

UPath: Universal Planner Across Topological Heterogeneity For Grid-Based Pathfinding

The performance of search algorithms for grid-based pathfinding, e.g. A*, critically depends on the heuristic function that is used to focus the search. Recent studies have shown that informed heuristics that take the positions/shapes of the obstacles into account can be approximated with the deep neural networks. Unfortunately, the existing learning-based approaches mostly rely on the assumption that training and test grid maps are drawn from the same distribution (e.g., city maps, indoor maps, etc.) and perform poorly on out-of-distribution tasks. This naturally limits their application in practice when often a universal solver is needed that is capable of efficiently handling any problem instance. In this work, we close this gap by designing an universal heuristic predictor: a model trained once, but capable of generalizing across a full spectrum of unseen tasks. Our extensive empirical evaluation shows that the suggested approach halves the computational effort of A* by up to a factor of 2.2, while still providing solutions within 3% of the optimal cost on average altogether on the tasks that are completely different from the ones used for training \unicodex2013\unicode{x2013} a milestone reached for the first time by a learnable solver.

Aleksandr Ananikian, Daniil Drozdov, Konstantin Yakovlev

Saint-Petersburg University

Motion PlanningOOD GeneralizationGraph-Based Planning
AskPDF