Participants:
Alfonso Gerevini
Dipartimento di Elettronica per l'Automazione
Universita` di Brescia, 25123 Brescia, Italy
Web home page: http://www.ing.unibs.it/~gerevini/
E-mail: gerevini@bsing.ing.unibs.it
Len Schubert
Department of Computer Science
Room 733, Computer Studies Building
University of Rochester
E-mail: schubert@cs.rochester.edu
Summary
State invariants (or state constraints) in planning are properties of objects or relationships among objects that hold in all states reachable from the initial state. For example, familiar invariants in the blocks world are the properties that if one block is on another, the former is on no other block, and the latter is not clear. The importance of state invariants for efficient planning is that they can be used to radically restrict the search space. In addition, rapid determination of state invariants can be very helpful in planning domain design, quickly revealing implicit properties that the designer may or may not have intended.
The DISCOPLAN System, available on-line via this link, is an efficient system for discovering state invariants in planning domains, represented in terms of a set of initial conditions and a set of STRIPS-like operators expressed in UCPOP or PDDL syntax, allowing for conditional effects, negated preconditions, and typed and untyped parameters. Among the types of invariants found are implicative constraints relating a fluent predication to a fluent or static predication (with allowance for static supplementary conditions), single-valuedness constraints, exclusiveness constraints, and several others. The algorithms used are polynomial-time for any fixed bound on the number of literals in an invariant. Some combinations of constraints are found by simultaneous induction, and the methods can be iterated by expanding operators using previously found invariants. The invariants found by DISCOPLAN have been shown to enable large performance gains in SAT planners.
Some relevant publications