Finding Mutual Exclusion Invariants in Temporal Planning Domains

We present a technique for automatically extracting temporal mutual exclusion invariants from PDDL2.2 planning instances. We first identify a set of invariant candidates by inspecting the domain and then check these candidates against properties that assure invariance. If these properties are violated, we show that it is sometimes possible to refine a candidate by adding additional propositions and turn it into a real invariant. Our technique builds on other approaches to invariant synthesis presented in the literature, but departs from their limited focus on instantaneous discrete actions by addressing temporal and numeric domains. To deal with time, we formulate invariance conditions that account for both the entire structure of the operators (including the conditions, rather than just the effects) and the possible interactions between operators. As a result, we construct a technique that is not only capable of identifying invariants for temporal domains, but is also able to find a broader set of invariants for non-temporal domains than the previous techniques.