Heuristic Search

Chapter 1. Introduction

This chapter introduces notational background, specific puzzles, and general problem formalisms. It recalls the success story of heuristic search and studies heuristics as efficiently computable lower bounds.

Keywords: computability theory, complexity theory, asymptotic resource consumption, symbolic logic, traveling salesman problem, sliding-tile problem, Sokoban, Rubik's Cube, route planning, STRIPS-type planning, production system, Markov decision process, consistent heuristic, admissible heuristic

In this book, we study the theory and the applications of heuristic search algorithms. The general model is the guided exploration in a space of states.

After providing some mathematical and notational background and ...