Experimental Methodology

Most of the experiments described here consist of a learning phase and a testing phase. The training problems are generated by MICRO-HILLARY. We let every learning phase run until MICRO-HILLARY reaches quiescence and halts. Since the training problems are generated by random sequences, we repeat each learning session 100 times. We test each resulting macro set by allowing the problem solver to use the macros for solving a set of 100 test problems. A random test-problem is generated in the same manner as a training problem. The only difference is the length of the random sequence of operators applied to the goal state. For testing we used random sequences of length 1,000,000 to ensure that the problems will be sufficiently difficult (or sufficiently random). For the sliding-tile domains, the test problems were generated using a known domain-dependent method for creating random solvable problems. The generator continuously creates random permutations of the goal state and returns the first even permutation. The domain-specific method does not harm the generality of MICRO-HILLARY since it is used only by the experimenter. This method allows us to compare the results obtained by MICRO-HILLARY to the results obtained by other researchers. When in testing mode, we allow MICRO-HILLARY to escape from local minima but we do not allow it to acquire new macros (see the SolveProblem procedure in Figure 2). For all the experiments described in this paper, MICRO-HILLARY was able to solve all the problems while in testing mode; therefore, no special handling of ``censored data'' [3,36] was necessary. Recall that the quiescence test lets MICRO-HILLARY stop only after it is able to solve 50 problems without getting stuck in any local minima. This significantly reduces the likelihood that it will encounter a local minimum after learning.