Abstract:
A search algorithm with an admissible heuristic function is the most common approach to optimally solve classical planning tasks. Recently Davies et al. (2015) introduced the solver OpSeq using Logic-Based Benders Decomposition to solve planning tasks optimally. In this approach, the master problem is an integer program derived from the operator-counting framework that generates operator counts, i.e. an assignment of integer counts for each task operator. Then, the operator sequencing subproblem verifies if a plan satisfying these operator counts exist, or generates a necessary violated constraint to strengthen the master problem. In OpSeq the subproblem is solved by a SAT solver.
In this paper we show that operator sequencing can be better solved by state-space search. We introduce OpSearch, an A*-based algorithm to solve the operator sequencing subproblem: it either finds an optimal plan, or uses the frontier of the search to derive a violated constraint. We show that using standard search framework has two advantages: i) search scales better than a SAT-based approach for solving the operator sequencing, ii) explicit information in the search frontier can be used to derive stronger constraints.
We present results on the IPC 2011 benchmark showing that this approach solves more planning tasks, using less memory. On tasks solved by both methods OpSearch requires to solve fewer operator sequencing problems than OpSeq, evidencing the stronger constraints generated by OpSearch.
