Invariant Synthesis for Conformant Planning

In order to compress the state space and accelerate the speed of conformant planning, invariants are introduced into conformant planning. Invariants of conformant planning are defined formally, and new knowledge representation “multi-valued conformant planning task” is given. The action model of multi-valued conformant planning is defined accordingly. An invariant synthesis method is proposed for conformant planning and a conformant invariant synthesis algorithm is specified. The synthesis method guesses candidates of invariants firstly. Then the synthesis method tests candidates among all initial world states and all actions according to the properties of conformant invariants. Some candidates are given up and some candidates are modified to form new candidates for testing again. Other candidates are proved to be invariants. Theoretical analysis and experimental results show that the algorithm can synthesize correct invariants and produce multi-value conformant planning tasks. For conformant planning, multi-valued conformant task can greatly compress the state space than Boolean codes used by conformant planning. In order to specify the application of the conformant invariants, the heuristics of reusing plan is combined with the multi-valued conformant tasks for solving the conformant tasks. The comparative experiments with planning system CFF are conducted for testing the efficiency and quality of the combination. Experimental results show that this combination is better than planning system CFF in some domains.