Smoothed Analysis of Inconsistent A*

Zhiyang Chen, Hailong Yao

The A* search is a fundamental path-finding algorithm in artificial intelligence. While admissible and consistent heuristics guarantee efficient performance by expanding each state…