SMT-based Nonlinear PDDL+ Planning

PDDL+ planning involves reasoning about mixed discretecontinuous change over time. Nearly all PDDL+ planners assume that continuous change is linear. We present a new technique that accommodates nonlinear change by encoding problems as nonlinear hybrid systems. Using this encoding, we apply a Satisfiability Modulo Theories (SMT) solver to find plans. We show that it is important to use a novel planning-specific heuristic for variable selection for SMT solving, which is inspired by recent advances in planning as SAT. We show the promising performance of the resulting solver on challenging nonlinear problems.

Daniel Bryce, David Musliner, and Robert Goldman. SMT-Based Nonlinear PDDL+ Planning. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI-15), 2015. - [PDF]