Discovering State Constraints in DISCOPLAN: Some New Results

Abstract

DISCOPLAN is an implemented set of efficient preplanning al-gorithms intended to enable faster domain-independent plan-ning. It includes algorithms for discovering state constraints (invariants) that have been shown to be very useful, for exam-ple, for speeding up SAT-based planning. DISCOPLAN origi-nally discovered only certain types of implicative constraints involving up to two fluent literals and any number of static lit-erals, where one of the fluent literals contains all of the vari-ables occurring in the other literals; only planning domains with STRIPS-like operators were handled. We have now ex-tended DISCOPLAN in several directions. We describe new techniques that handle operators with conditional effects, and enable discovery of several new types of constraints. More-over, discovered constraints can be fed back into the discov-ery process to obtain additional constraints. Finally, we out-line unimplemented (but provably correct) methods for dis-covering additional types of constraints, including constraints involving arbitrarily many fluent literals.