Abstract:
DISCOPLAN is an implemented set of efficient preplanning algorithms intended to enable faster domain-independent planning. It includes algorithms for discovering state constraints (invariants) that have been shown to be very useful, for example, for speeding up SAT-based planning. DISCOPLAN originally discovered only certain types of implicative constraints involving up to two fluent literals and any number of static literals, where one of the fluent literals contains all of the variables occurring in the other literals; only planning domains with strips-like operators were handled. We have now extended discoplan in several directions. We describe new techniques that handle operators with conditional effects, and enable discovery of several new types of constraints. Moreover, discovered constraints can be fed back into the discovery process to obtain additional constraints. Finally, we outline unimplemented (but provably correct) methods for discovering additional types of constraints, including XOR constraints, and constraints involving arbitrarily many fluent literals.