Optimal Planning as Constraint Optimization

We consider the problem of optimal planning in determinis- tic domains and reduce it to the problem of finding an optimal solution of a corresponding constraint optimization problem incorporating a bound n on the maximum length of the plan. By solving the latter, we can conclude whether (i) the plan found is optimal even for bounds greater than n; or (ii) we need to increase n; or (iii) it is useless to increase n since the planning problem has no solution. Our approach (i) sub- stantially generalizes previous approaches for optimal sym- bolic deterministic planning; (ii) allows to compute non triv- ial lower bounds on the cost and length of optimal plans; and (iii) produces an encoding linear in the size of the planning problem and the bound