AAAI Publications, Twenty-Eighth International Conference on Automated Planning and Scheduling

Font Size: 
Compiling Optimal Numeric Planning to Mixed Integer Linear Programming
Chiara Piacentini, Margarita P. Castro, Andre A. Cire, J. Christopher Beck

Last modified: 2018-06-15

Abstract


Compilation techniques in planning reformulate a problem into an alternative encoding for which efficient, off-the-shelf solvers are available. In this work, we present a novel mixed-integer linear programming (MILP) compilation for cost-optimal numeric planning with instantaneous actions. While recent works on the problem are restricted to actions that modify variables present in simple numeric conditions, our MILP formulation, in addition, handles linear conditions and linear action effects on numeric state variables. Such problems are particularly challenging due to the state-dependency of the action effects. Experiments show that our approach, in addition to being the state of the art for the more general problem class, is competitive with heuristic search-based planners on domains with only simple numeric conditions.

Keywords


Optimal Numeric Planning; Integer Programming; State-dependent Action Effects

Full Text: PDF