Plan generation using a method of deductive program synthesis

Abstract

In this paper we introduce a planning approach based on a method of deductive program synthesis. The program synthesis system we rely upon takes first-order specifications and from these derives recursive programs automatically. It uses a set of transformation rules whose applications are guided by an overall strategy. Additionally several heuristics are involved which considerably reduce the search space. We show by means of an example taken from the blocks world how even recursive plans can be obtained with this method. Some modifications of the synthesis strategy and heuristics are discussed, which are necessary to obtain a powerful and automatic planning system. Finally it is shown how subplans can be introduced and generated separately.