## Definition **Heuristic planning** applies [[Heuristic Search]] (typically A*) to the state space of a [[Classical Planning]] problem, using *automatically derived* heuristics from the problem structure. The breakthrough that made classical planning practical at scale (~1998 onward). ## The Core Idea Manually designing heuristics for every planning domain is impractical. The insight: derive a heuristic *from the problem definition itself* by analysing a **relaxation** of the problem. ## Common Heuristics ### Delete-Relaxation ($h^+$) Drop the delete lists from every action — actions only *add* facts, never remove them. The resulting problem is solvable in polynomial time and gives an *admissible* lower bound on the original. The optimal cost of the relaxed problem is $h^+$. Computing $h^+$ exactly is still NP-hard, so practical heuristics approximate it. ### $h_{\text{add}}$ — Additive Estimate cost of achieving each goal fact independently; sum them. Cheap but inadmissible (overcounts when goals share prerequisites). ### $h_{\text{max}}$ — Maximum Estimate cost of each goal fact; take the maximum. Admissible; very weak. ### FF Heuristic (Hoffmann & Nebel, 2001) Extract an *explicit relaxed plan* from the planning graph; use its length as the heuristic. Inadmissible but powerful in practice. Forms the basis of the FF planner — once dominant on IPC benchmarks. ### Landmark Heuristics A **landmark** is a fact that *must* appear in every valid plan. Counting landmarks (or their action costs) yields strong heuristics. Powers **LAMA** and many modern planners. ### Pattern Databases Precompute optimal costs for sub-problems (projections of the state to subsets of variables). Use the maximum across pattern databases as the heuristic. Common in domain-independent planners. ### Causal-Graph and Merge-and-Shrink Heuristics Modern abstract-state methods that systematically aggregate states preserving solution structure. ## Algorithmic Stack Modern planners typically run: 1. Parse PDDL. 2. Ground the problem (instantiate action schemas). 3. Compute a planning graph (intermediate structure for heuristics). 4. Run weighted A* or greedy best-first with the chosen heuristic. 5. Postprocess (plan simplification). ## Why It Matters Pre-1998 planners struggled with toy problems. Post-heuristic-planning era, classical planners handle problems with thousands of objects and millions of states. The field went from "interesting curiosity" to "deployable in production." ## Limits - Heuristic computation itself can dominate runtime. - Domains with poor heuristic guidance (combinatorial optimisation flavoured) remain hard. - No advantage on uncertain/partial-observability problems — those need different paradigms. ## Related - [[Classical Planning]] - [[PDDL]] - [[GRAPHPLAN]] - [[A Star Algorithm]] - [[Heuristic Search]]