Model Minimization, Regression, and Propositional STRIPS Planning

摘要

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 techniqeu to provide automaton minimization algorithms for factored FSAs. in this paper, we consider the relationship between STRIPS problem-solving techniques such as regressing and the recnetly developed automaton minimization techniques for factored FSAs. We show that regression computes a partial and approxiamte minimized form of the FSA corresponding to the STRIPS problem. We then define a systematic form of regressio nwhic hcomputes a partial but exact minimzied form of the associated FSA. We also relate minimization to methods for performing reachability analysis to detect irrelevant fluents. Finally, we show that exact comptuation of the minimized automaton is NP-complete under the assumption that this automaton is polynomial in size.