Heuristic Function

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.

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.