Conference Proceedings

Traps, invariants, and dead-ends

N Lipovetzky, C Muise, H Geffner

Proceedings International Conference on Automated Planning and Scheduling, ICAPS | International Conference on Automated Planning and Scheduling (ICAPS) | Published : 2016


Copyright © 2016, Association for the Advancement of Artificial Intelligence ( All rights reserved. We consider the problem of deriving formulas that capture traps, invariants, and dead-ends in classical planning through polynomial forms of preprocessing. An invariant is a formula that is true in the initial state and in all reachable states. A trap is a conditional invariant: once a state is reached that makes the trap true, all the states that are reachable from it will satisfy the trap formula as well. Finally, dead-ends are formulas that are satisfied in states that make the goal unreachable. We introduce a preprocessing algorithm that computes traps in k-DNF form that is e..

View full abstract