The generation of pre-interpretations for detecting unsolvable planning problems

Abstract

In deductive planning, there exists a· particular class of planning problems, called unsolvable planning problems, which although successfully treated theoretically, turns out to be undetectable using ordinary resolution methods as infinite sequences of useless actions have to be considered. These problems are exacerbated when we extend our problem domains to infinite domains of resources, e.g. a blocks world with a ("theoretically") unlimited number of blocks or an electric circuit with an unlimited number of switches. Furthermore, the introduction of new objects, by means of "generating" actions (see Section 4), poses huge problems to most if not all existing planning approaches. This "discrepancy" between theory and practise is annoying and prevents us from deciding interesting unsolvable planning problems. Our aim in this paper is therefore to develop an analysis method specifically for the detection of such problems.