City Research Online

Abstract

When input a model of a planning domain and a problem to be solved, generative planning systems endeavour to generate a plan that is a solution to the input problem. There is a trade-off between the generality and efficiency of these systems which means that general planners tend to be inefficient. Our research has focussed on improving the efficiency of general planners. A popular approach to tackling this “efficiency versus generality” problem has been to embed systems with on-line and post-event learning components that use current and previous planning experience to increase subsequent performance. However, in this thesis we argue for a move away from this approach towards what we call off-line compilation, where all processing is independent of on-line planning. In support of this we have created two novel complementary techniques for off-line compilation, which we call PRECEDE and PROPOSE. In the course of our work they have been precisely defined, implemented and evaluated, and all aspects of this work are described in the thesis.

PRECEDE is a method for generating goal orders that are based on necessary interactions between goals. PROPOSE is a method for generating iterative macro operators for all sorts of objects in a modelled planning domain, ft also generates sequences of constants that can be used to unwind the iterative parts of the macros. The PRE-CEDE goal orders can be used to select goals to achieve next and the PROPOSE iterative macros and enumerated sequences can be used to select ground operators for goal achievement during plan generation. These methods are off-line in the sense that all processing is performed a priori direct from the model of a planning domain.

The compilation methods were evaluated statically, empirically and in comparison with established methods of on-line and post-event learning. For the empirical testing of off-line compilation an example planner was selected and extended so that it could use domain models that had been compiled by PRECEDE and PROPOSE. This planner was then used in a series of empirical tests which revealed that the techniques, both individually and in combination, consistently improve the performance of the planner (a speed-up of between 2 and 5 times faster across a sample of planning domains). Also, the results of static and dynamic comparison with established methods show that off-line compilation with PRECEDE and PROPOSE compares favourably with existing post-event and on-line learning methods.

Publication Type:	Thesis (Doctoral)
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments:	School of Science & Technology > Computer Science School of Science & Technology > School of Science & Technology Doctoral Theses Doctoral Theses

Export

Downloads