Heuristic Function

An admissible heuristic is one that never overestimates the true cost to reach the goal from any given node. This is the most critical property for guaranteeing solution optimality. If a heuristic is admissible, the A* search algorithm is guaranteed to return an optimal (least-cost) path, provided one exists.

• Formal Definition: For all nodes n, h(n) ≤ h*(n), where h*(n) is the true optimal cost from n to the goal.
• Example: In pathfinding on a grid, the straight-line Euclidean distance is an admissible heuristic for the actual travel distance, as the 'crow flies' is always the shortest possible path.

A consistent (or monotonic) heuristic satisfies the triangle inequality. For every node n and its successor n' generated by action a with cost c(n, a, n'), the heuristic estimate must obey: h(n) ≤ c(n, a, n') + h(n'). This implies that the estimated cost to the goal from n is no greater than the step cost to its successor plus the estimated cost from there.

• Key Implication: Consistency implies admissibility. If a heuristic is consistent, A* never needs to re-expand a node after it is placed in the closed set, making it more efficient.
• Visualization: The heuristic's estimate decreases smoothly and consistently as you move closer to the goal.

The informedness of a heuristic refers to how closely it approximates the true cost h*(n). A more informed heuristic (one that gives a higher value while still being admissible) prunes the search space more aggressively, leading to faster discovery of the optimal path.

• Trade-off: There is often a balance between the computational cost of calculating a highly informed heuristic and the search time it saves. The perfect heuristic h(n) = h*(n) would lead directly to the goal with no search.
• Example: For the 8-puzzle, the Manhattan distance heuristic (sum of tile displacements) is more informed—and therefore more effective—than the simpler number of misplaced tiles heuristic.

A heuristic h2 dominates another heuristic h1 if, for all nodes n in the state space, h2(n) ≥ h1(n), and for at least one node, h2(n) > h1(n). Both must be admissible. A dominating heuristic is more informed and will never expand more nodes than the dominated heuristic when used with A*.

• Practical Use: When you have multiple admissible heuristics for a problem, you can safely use their maximum: h(n) = max(h1(n), h2(n), ...). This composite heuristic dominates each individual one, yielding better performance.
• Application: In planning with multiple subgoals, taking the maximum cost of several relaxed-problem heuristics creates a more powerful, dominant heuristic.

A heuristic must be computationally efficient to evaluate. The overhead of calculating h(n) for every explored node must be outweighed by the reduction in the number of nodes expanded. An ideal heuristic provides a strong guiding estimate with minimal computational cost.

• Common Sources: Effective heuristics are often derived from simplified relaxed models of the original problem (e.g., ignoring delete effects in planning) or from pattern databases that store precomputed costs for subproblems.
• Engineering Consideration: In real-time systems, a fast, slightly less informed heuristic may be preferable to a slow, perfect one.

Effective heuristics are not generic; they are engineered using deep knowledge of the planning domain. Common design methodologies include:

• Relaxation: Create a simpler version of the problem by removing constraints (e.g., allowing tiles to move through each other in a puzzle). The optimal cost in the relaxed problem is an admissible heuristic for the original.
• Abstraction: Map the original state space to a smaller abstract space, solve the problem there, and use that cost as an estimate.
• Landmark Heuristics: Use landmarks—facts that must be true at some point in any solution—to estimate the minimum number of actions remaining.
• Subgoal Decomposition: Estimate cost as the sum of costs to achieve independent subgoals.

An admissible heuristic is a heuristic function, denoted h(n), that never overestimates the true cost to reach the goal from node n. This property is critical for optimality guarantees in algorithms like A* search. If a heuristic is admissible, A* is guaranteed to return an optimal (least-cost) solution, provided one exists.

• Key Property: For all nodes n, h(n) ≤ h*(n), where h*(n) is the true optimal cost to the goal.
• Example: In pathfinding on a grid, the straight-line Euclidean distance is an admissible heuristic for the shortest path, as it is the shortest possible distance (a straight line) and never overestimates the actual travel cost.

A search* is a best-first graph traversal and pathfinding algorithm that finds a least-cost path from a start node to a goal node. It combines the actual cost from the start (g(n)) with a heuristic estimate to the goal (h(n)) to prioritize the most promising nodes. The evaluation function is f(n) = g(n) + h(n).

• Optimality: A* is optimal if the heuristic h(n) is admissible (never overestimates) and consistent (satisfies the triangle inequality).
• Primary Use: It is the foundational algorithm for efficient, optimal planning in domains with a computable heuristic, such as robotics navigation, game AI, and logistics scheduling.

Monte Carlo Tree Search is a heuristic search algorithm for optimal decision-making in sequential decision processes, particularly in environments with vast state spaces (like games). Instead of a static heuristic function, MCTS uses random simulation (rollouts) to estimate the value of states, building a search tree that balances exploration of uncertain paths with exploitation of known high-reward paths.

• Four Steps: Selection, Expansion, Simulation, Backpropagation.
• Contrast with A*: MCTS does not require a domain-specific heuristic function; it learns value estimates through sampling. It excels in domains where constructing a reliable heuristic is difficult.

In automated planning, the state space is the set of all possible configurations or situations that the world can be in. It forms a graph where nodes are states and edges are actions that transition between states. The planner's task is to find a path through this graph from an initial state to a goal state.

• Search Challenge: The state space is often astronomically large (the "combinatorial explosion").
• Role of Heuristics: A heuristic function provides an estimate of the distance from any given state in this space to the goal, guiding the search to avoid exploring irrelevant regions.

A cost function assigns a numerical cost to each action in a planning domain. The total cost of a plan is the sum of the costs of its constituent actions. The planner's objective is typically to find a plan that achieves the goal while minimizing this total cost.

• Relationship to Heuristic: The heuristic function h(n) estimates the remaining cost from state n to the goal. The actual incurred cost from the start to n is g(n). The sum, f(n)=g(n)+h(n), estimates the total cost of a path going through n.
• Optimization: In cost-sensitive planning, an admissible heuristic allows algorithms like A* to find the minimum-cost plan.

A landmark is a fact (a logical proposition) that must be true at some point in every valid plan that solves a given planning problem. Landmarks represent necessary subgoals. They are used to derive more informed heuristic functions and impose ordering constraints on actions.

• Heuristic Derivation: The number of unachieved landmarks remaining is often used as a heuristic estimate (landmark heuristic). For example, if reaching the goal requires having a key, opening a door, and being in a room, each is a landmark.
• Informed Guidance: Landmark-based heuristics are often more accurate than simpler relaxations, leading to faster search and fewer expanded states.