9.3 Heuristics for State-Space Planning 201
as the iterative-deepening scheme, are usually able to guarantee an optimal solution
when guided with an admissible node-selection heuristic. But quite often, one may
have to trade admissibility for informativeness.
9.3 Heuristics for State-Space Planning
This section presents several node-selection heuristics for state-space planning. We
start with a simple heuristic function and present its use in guiding a forward-search
backtracking algorithm, then a backward-search procedure. We then develop sev-
eral more elaborate heuristics and discuss their properties. Finally, the relationship
between these heuristics and the planning-graph techniques is discussed.
9.3.1 State Reachability Relaxation
Let us consider ...