Learning action strategies for planning domains

This paper reports on experiments where techniques of supervised machine le arning are applied to the problem of planning. The input to the learning al gorithm is composed of a description of a planning domain, planning problem s in this domain, and solutions for them. The output is an efficient algori thm-a strategy-for solving problems in that domain. We test the strategy on an independent set of planning problems from the same domain, so that succ ess is measured by its ability to solve complete problems. A system, L2ACT, has been developed in order to perform these experiments. We have experimented with the blocks world domain and the logistics transpo rtation domain, using strategies in the form of a generalisation of decisio n lists. The condition of a rule in the decision list is an existentially q uantified first order expression, and each such rule indicates which action to take when the condition is satisfied. The learning algorithm is a varia nt of Rivest's (1987) algorithm, improved with several techniques that redu ce its time complexity. The experiments demonstrate that the approach is fe asible, and generalisation is achieved set that unseen problems can be solv ed by the learned strategies. Moreover, the learned strategies are efficien t, the solutions found by them are competitive with those of known heuristi cs for the domains, and transfer from small planning problems in the exampl es to larger ones in the test set is exhibited. (C) 1999 Elsevier Science B .V. All rights reserved.