Heuristic search is a problem-solving technique in artificial intelligence and computer science that uses heuristic functions—rules of thumb or estimates—to guide the exploration of a search space toward a goal. Unlike exhaustive search methods, heuristic search prioritizes promising paths, reducing computational cost and enabling efficient solutions for complex problems such as pathfinding, game playing, and automated planning. The quality of the heuristic critically influences performance, with properties like admissibility and consistency ensuring optimality in algorithms like A*.

1 Foundations

The theoretical basis of heuristic search rests on the formal definition of search spaces, the construction and evaluation of heuristic functions, and the criteria used to assess algorithm performance.

1.1 Search Spaces

A search space consists of states, transitions (actions), an initial state, and one or more goal states. In graph search, states correspond to nodes, transitions to edges, and the problem is to find a path from the initial node to any goal node. The size of a search space is often exponential in the problem's dimensions, making exhaustive methods impractical.

1.2 Heuristic Functions

A heuristic function \(h(n)\) estimates the cost from a given state \(n\) to a goal. It is typically derived from domain knowledge or problem relaxations. Heuristics guide search by ranking states according to their estimated promise.

1.2.1 Admissibility

A heuristic is admissible if it never overestimates the true minimal cost to a goal: \(h(n) \leq h^*(n)\), where \(h^*(n)\) is the true optimal cost. Admissibility is essential for algorithms like A* to guarantee that the first solution found is optimal.

1.2.2 Consistency

A heuristic is consistent (or monotone) if it satisfies the triangle inequality: \(h(n) \leq c(n, n') + h(n')\) for every state \(n\) and its successor \(n'\), where \(c\) is the step cost. Consistency implies admissibility and ensures that A* can reuse expanded states without re-expanding them.

1.3 Evaluation Criteria

Heuristic search algorithms are evaluated on completeness, optimality, time complexity, and space complexity. Completeness guarantees finding a solution if one exists; optimality ensures the solution is of minimal cost. Time and space complexity depend on the heuristic's accuracy and the branching factor of the search space.

2 Algorithms

Heuristic search algorithms vary in how they select states for expansion and how they manage memory.

Best-first search maintains a priority queue of states ordered by an evaluation function \(f(n)\). It repeatedly expands the state with the smallest \(f(n)\) until a goal is found.

Greedy best-first search uses \(f(n) = h(n)\) (the heuristic cost to the goal). It expands the state that appears closest to the goal. This approach is fast but not optimal and may get stuck in dead ends or local optima.

2.1.2 A* Algorithm

A* combines the cost already incurred (\(g(n)\)) with the heuristic estimate: \(f(n) = g(n) + h(n)\). It expands states in order of estimated total path cost. A* is complete and optimal when \(h\) is admissible.

2.1.2.1 Properties of A*

A* is optimally efficient among optimal algorithms: no optimal algorithm expands fewer states in the worst case. It has exponential worst-case time and memory usage, but good heuristics can make it practical.

To reduce memory usage, algorithms limit the number of stored states.

2.2.1 Iterative Deepening A* (IDA*)

IDA* performs depth-first search with a cutoff based on \(f\)-cost. It repeatedly increases the cutoff until a solution is found. IDA* uses linear memory but may re-explore states; it is optimal with admissible heuristics.

2.2.2 Simplified Memory-Bounded A* (SMA*)

SMA* maintains a fixed-size memory for expanded states. When memory is full, it drops the worst-ranked state (highest \(f\)-cost) and continues. SMA* is complete and optimal if the memory is sufficient to hold a solution path.

Bidirectional heuristic search runs two simultaneous searches: one from the start, one from the goal. The searches meet in the middle, potentially reducing the explored space. It uses heuristics for both directions and must ensure consistency to guarantee optimality.

3 Heuristic Construction

Designing effective heuristics is central to heuristic search performance. Several methods exist.

3.1 Domain-Specific Heuristics

Domain-specific heuristics are hand-crafted using expert knowledge of the problem. For example, in the 15-puzzle, the Manhattan distance heuristic sums the horizontal and vertical distances of each tile to its goal position. Such heuristics are often admissible and informative.

3.2 Relaxed Problem Heuristics

Relaxed problem heuristics drop constraints from the original problem to create a simpler version whose optimal cost is a lower bound. For example, in the sliding-tile puzzle, ignoring tile blocking yields Manhattan distance; ignoring order yields a simpler heuristic.

3.3 Pattern Databases

A pattern database stores the exact optimal cost for a subset of states (a pattern) to the goal. It is precomputed by abstracting the problem. When expanded, the heuristic is the maximum or sum of costs from several pattern databases.

3.3.1 Disjoint Pattern Databases

Disjoint pattern databases partition the problem elements (e.g., tiles in a puzzle) into groups that do not interact. Their costs can be summed without overcounting, producing a strong admissible heuristic.

3.3.2 Compressing Pattern Databases

To reduce memory usage, pattern databases can be compressed by hashing or storing only a representative set of entries. Compression may lose information but can fit larger problems into available memory.

4 Applications

Heuristic search is widely used in practical systems that require efficient planning and decision-making.

4.1 Pathfinding

Pathfinding finds the shortest route between two points in a graph. Heuristic search (especially A*) is the standard method for grid-based and road-network pathfinding.

4.1.1 Navigation Systems

Global positioning system (GPS) navigation uses A* or variants with heuristics like Euclidean or Manhattan distance to compute driving routes. Real-time traffic data can be integrated as dynamic edge costs.

4.2 Game Playing

In deterministic turn-based games (e.g., chess, checkers, Go), heuristic search algorithms such as minimax with alpha-beta pruning use evaluation functions as heuristics to estimate the value of board positions. A* is also used for puzzle solving and resource management games.

4.3 Planning

Automated planning systems generate sequences of actions to achieve goals. Heuristic search planners (e.g., FF, Fast Downward) use domain-independent heuristics (e.g., the relaxed plan heuristic) to guide the search through state spaces.

4.4 Robotics

Robots use heuristic search for motion planning and manipulation. A* and its variants plan collision-free paths in configuration spaces, often with heuristics based on Euclidean distance or task-specific costs.

5 Limitations and Challenges

Despite its power, heuristic search faces inherent limitations.

5.1 Overestimation and Underestimation

An overestimating heuristic (violating admissibility) can cause A* to return a suboptimal solution. Underestimation (too low) increases search time but preserves optimality. Balancing informativeness and admissibility is a key challenge.

5.2 Memory Constraints

A*'s memory usage grows with the number of visited states, which can be exponential. Memory-bounded variants (IDA*, SMA*) mitigate this but may sacrifice speed or completeness when memory is very tight.

5.3 Local Optima

Greedy algorithms and non-admissible heuristics may lead to local optima where no further progress seems possible. Techniques like random restarts, simulated annealing, or using a weighted evaluation function can help escape local optima.