Next: Experimenting with MICRO-HILLARY Up: MICRO-HILLARY Previous: Using MICRO-HILLARY for a

## Correctness of MICRO-HILLARY

A problem solver is complete if it terminates with a solution when one exists [29, p. 75]. If, when starting from a solvable state, we never reach unsolvable states, and if the range of the heuristic function is finite, then a complete set of macros yields a complete problem solver.

Let S be a set of states and O a set of basic operators. Let be a set of solvable problems with the following property:

Let h be a well-behaved heuristic function with a finite range, Rh, over S ( ). Let M be a complete set of macros. Then, SolveProblem using M is a complete problem solver with respect to P. Furthermore, the number of operator applications is bounded by (|O|+Bm) Rh where Bm is the total length of macros in M.
Proof:
In every step of the hill-climbing procedure we are guaranteed (by the completeness of M) to find a state with a heuristic value which is lower than the value of the current state. Since h is well-behaved, and since it has a finite number of values, Rh, we can make at most Rh steps before reaching a goal state with h(s)=0. At every step, in the worst case, we try all the basic operators and all the macros before finding the one that makes progress. Therefore the total number of operator applications is bounded by (|O|+Bm) Rh.

Next: Experimenting with MICRO-HILLARY Up: MICRO-HILLARY Previous: Using MICRO-HILLARY for a
Shaul Markovitch
1998-07-21