Discovering State Invariants

Fangzhen Lin

We continue to advocate a methodology that we used earlier for pattern discovery through exhaustive search in selected small domains. This time we apply it to the problem of discovering state invariants in planning domains. State invariants are formulas that if true in a state, will be true in all successor states. In this paper, we consider the following four types of state invariants commonly found in AI planning domains: functional dependency constraints, constraints on mutual exclusiveness of categories, type information constraints, and domain closure axioms. As it turned out, for a class of action theories that include many planning benchmarks, for the first three types of constraints, whether they are state invariants can be verified by considering models whose domains are bounded by a small finite number. This forms the basis for a procedure that tries to discover state invariants by exhaustive search in small finite domains. An implementation of the procedure yields encouraging results in the blocks world and the logistics domain.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.