Model Minimization, Regression, and Propositional STRIPS Planning

Abstract

Propositional STRIPS planning problems can be viewed as finite state automata (FSAs) represented in a factored form. Automaton minimization is a well-known technique for reducing the size of an explicit FSA. Recent work in computer-aided verification on model checking has extended this technique to provide automaton minimization algorithms for factored FSAs. In this paper, we consider the relationship between STRIPS problem-solving techniques such as regression and the recently developed automaton minimization techniques for factored FSAs. We show that regression computes a partial and approximate minimized form of the FSA corresponding to the STRIPS problem. We then define a systematic form of regression which computes a partial but exact minimized form of the associated FSA. We also relate minimization to methods for performing reachability analysis to detect irrelevant fluents. Finally, we show that exact computation of the minimized automaton is NP-complete under the assumption that this automaton is polynomial in size.