Mechanical generation of admissible heuristics

摘要: This chapter takes its title from Section 4.2 of Judea Pearl’s landmark book Heuristics [Pearl 1984], and explores how the vision outlined there has unfolded in the quarter-century since its appearance. As the book’s title suggests, it is an in-depth summary of classical artificial intelligence (AI) heuristic search, a subject to which Pearl and his colleagues contributed substantially in the early 1980s. The purpose of heuristic search is to find a least-cost path in a state space from a given start state to a goal state. In principle, such problems can be solved by classical shortest path algorithms, such as Dijkstra’s algorithm [Dijkstra 1959], but in practice the state spaces of interest in AI are far too large to be solved in this way. One of the seminal insights in AI was recognizing that even extremely large search problems can be solved quickly if the search algorithm is provided with additional information in the form of a heuristic function h (s) that estimates the distance from any given state s to the nearest goal state [Doran and Michie 1966; Hart, Nilsson, and Raphael 1968]. A heuristic function h (s) is said to be admissible if, for every state s, h (s) is a lower bound on the true cost of reaching the nearest goal from state s. Admissibility is desirable because it guarantees the optimality of the solution found by the most widely-used heuristic search algorithms. Most of the chapters in Heuristics contain mathematically rigorous definitions and analysis. In contrast, Chapter 4 offers a conceptual account of where heuristic functions come from, and a vision of how one might create algorithms for automatically generating effective heuristics from a problem description. An …