Sequencing operator counts with state-space search

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. In this approach to planning, 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 counts sequencing subproblem verifies if a plan satisfying these operator counts exists, or generates a violated constraint to strengthen the master problem. In OpSeq, the subproblem is solved by a SAT solver. In this thesis, we show that this subproblem can be better solved by state-space search. We introduce OpSearch, an A -based algorithm to solve the operator counts sequencing problem: it either finds an optimal plan, or uses the frontier of the search, i.e., the set of generated but yet unexpanded states, to derive a violated constraint. We show that using a standard search framework has three advantages: i) the search scales better than a SAT-based approach for solving the operator counts sequencing, ii) explicit information in the search frontier can be used to derive stronger constraints, and iii) stronger heuristics generate more informed constraints. We present results using the benchmark of the International Planning Competition, showing that this approach solves more planning tasks, using less memory. On tasks solved by both methods, OpSearch usually requires solving fewer operator counts sequencing problems than OpSeq, evidencing the stronger constraints generated by OpSearch.

Um algoritmo de busca com uma função heurística admissível é a abordagem mais comum para resolver otimamente tarefas de planejamento. Recentemente DAVIES et al. (2015) introduziram o resolvedor OpSeq usando uma Decomposição de Benders Baseada em Lógica. Nesta abordagem para planejamento, o problema principal é um programa inteiro derivado da estrutura de operator-counting que gera contagens de operadores, isto é, uma atribuição de contagens inteiras para cada operador da tarefa. Em seguida, o problema de sequenciamento de contagens de operadores verifica se um plano satisfazendo estas contagens de operadores existe, ou gera uma restrição violada para fortificar o problema principal. Em OpSeq, o subproblema é resolvido por um resolvedor SAT. Nesta dissertação, mostramos que este subproblema pode ser melhor resolvido por busca em espaço de estados. Introduzimos OpSearch, um algoritmo baseado em A para resolver o problema de sequenciamento de contagens de operadores: ele encontra um plano ótimo, ou usa a fronteira da busca, isto é, o conjunto de estados gerados mas ainda não expandidos, para derivar uma restrição violada. Mostramos que utilizar uma estrutura de busca padrão tem três vantagens: i) a busca escala melhor que uma abordagem baseada em SAT para resolver o sequenciamento de contagens de operadores, ii) informação explícita na fronteira de busca pode ser usada para derivar restrições mais fortes, e iii) heurísticas mais fortes geram restrições mais informadas. Apresentamos resultados utilizando o conjunto de instâncias da Competição Internacional de Planejamento, mostrando que esta abordagem resolve mais tarefas de planejamento, usando menos memória. Nas tarefas resolvidas por ambos os métodos, OpSearch geralmente requer resolver menos problemas de sequenciamento de contagens de operadores que OpSeq, evidenciando as restrições mais fortes geradas por OpSearch.