A Propositional Planning Encoding Method by Reducing Action Variables

Action based encoding method is a novel propositional planning encoding method by reducing state variables adopted by SATPLAN2006, which is the state-of-the-art optimal planner of the International Planning Competition in 2006. In this paper, based on action based encoding method, another automated propositional planning encoding method by reducing action variables, called proposition based encoding method, is proposed. Firstly, the theoretical foundations to propose a new encoding method in planning as satisfiability framework are analyzed, and the theoretical composition of proposition based encoding method is proposed for automatically constructing a series of propositional encodings during planning processing. And then, the soundness and completeness of the proposed encoding method are justified and the feasible actual encodings for some axioms are described. Finally, the distinctions between the proposed encoding method and the existing excellent encoding methods are also compared. To analyze their specialties for different planning domains, the proposition based encoding method is implemented in SATPLAN2006 planner, and also is compared with action based encoding using several benchmarks adopted by the International Planning Competition. The experimental results validate that for sequential planning Blocks World problems, proposition based encoding is superior to action based encoding, and for parallel planning Logistics problems, the latter is superior to the former.