...MICRO-HILLARY¹

MICRO-HILLARY is a simplified version of a system called Hillary [5]. The program was named after Sir Edmund Hillary. We did not notice that the name Hillary had already been used by Iba, Wogulis and Langley [11].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... state.²

The formalization could have used a goal predicate that returns true for states that are goal states. For simplicity we assumed a single specified goal state.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... hill-climbing³

Simple hill-climbing means that the problem solver steps forward as soon as an improvement is detected without waiting for the best improvement.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...minimum-to-minimum⁴

The original name given by Iba is peak-to-peak. To make the name of the filter more appropriate for heuristic functions that consider lower values as better, we call Iba's method minimum-to-minimum.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... limit⁵

D is a predefined upper limit (D=100 was used for the experiments described here) on the maximal radius. If, for some reason, the escape route is longer than D, we can iterate the algorithm with a larger D.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... row.⁶

Table 19 specifies the exact definition of this function for the general NxN case.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... hardware⁷

For example, all the CPU time figures reported here were achieved running a Common Lisp program on an outdated Sun. Recent experiments on an UltraSparc yield times which are about 4.4 times faster than those reported here.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... search⁸

Best-first search has several meanings in the AI literature. Here we mean a heuristic search method that keeps the whole front of the search, expands the node with the best heuristic value and replaces it with its children. When two nodes have equivalent heuristic value, the one with the shorter distance from the initial state is prefered.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...MICRO-HILLARY's.⁹

We used a fast implementation of best-first search with efficient data structures: a heap and a hash table for the OPEN list, a hash table for the CLOSED list.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.