A new greedy algorithm to estimate the Post-hoc method

Abstract

Heuristic functions estimate how far each state is from the goal condition and have been widely used to guide state-space search to solve planning tasks. Effective heuristic func tions find a good compromise between computation speed and quality in their estimates. Several heuristics have been proposed in the literature, and a technique called Post-hoc Optimization (PhO) has gathered attention since its proposal. PhO is an effective tech nique to combine abstraction heuristics in an integer program (IP) where the objective function is the sum of the costs applied from the operators into an optimal plan. As PhO bases it on IPs, we usually calculate it using general IP solvers, which can make it relatively slow to compute if we compare it to other heuristics. Estimating the PhO solution can be faster than actually solving it. Local Search Heuristic (LSH) computes these estimations by making greedy decisions on each step towards satis fying the constraints of the IP. In this work, we introduce a novel greedy algorithm called Improved Local Search Heuristic (ILSH) that leverages concepts from LSH. Inspired by the approximation algorithms for set cover (Johnson, 1974; Lovász, 1975; Chvatal, 1979), our algorithm aims to estimate PhO sufficiently well and, at the same time, compute it faster than PhO does such that we can apply it in larger contexts.To evaluate the efficacy of our approach, we conduct experiments comparing our algo rithm ILSH with existing methods such as Post-hoc itself, a relaxed version utilizing Linear Programming instead of IP, and LSH. In conclusion, we show that our heuristic can perform well and, at the same time, main tain closer estimates of the actual IP solution when compared to LSH. Regarding time to compute, ILSH takes less time than PhO (and still computes as good plans as Post-hoc), but on average, it costs up to one order of magnitude more time than LSH does to compute its estimate. Despite not being the fastest algorithm tested in this work, its superiority in plan quality and its reasonable total execution time make it an interesting alternative to the existing methods in the literature.

Funções heurísticas estimam o quão longe cada estado está da condição objetivo e têm sido amplamente utilizadas para guiar a busca no espaço de estados para resolver tare fas de planejamento. Funções heurísticas efetivas encontram um bom meio-termo entre velocidade computacional e qualidade nas suas estimativas. Diversas heurísticas foram propostas na literatura e uma técnica chamada Post-hoc Optimization (PhO) tem atraído certa atenção desde a sua ideação. PhO é uma técnica efetiva para combinar heurísticas de abstração em um programa inteiro (IP) onde a função objetivo é a soma dos custos aplicados pelos operadores em um plano ótimo. Como PhO se baseia em IPs, nós geral mente o calculamos usando resolvedores IP genéricos, o que pode torná-lo relativamente lento para computar se compararmos com outras heurísticas. Estimar a solução do PhO pode ser mais rápido que resolvê-lo. Local Search Heuristic (LSH) computa essas estimativas tomando decisões gulosas em cada passo visando sa tisfazer as restrições do IP. Neste trabalho, nós introduzimos um novo algoritmo guloso chamado Improved Local Search Heuristic (ILSH) que combina conceitos do LSH. Inspirado nos algoritmos de aproximação para o problema de cobertura de conjuntos (Johnson, 1974; Lovász, 1975; Chvatal, 1979), nosso algoritmo visa estimar PhO suficientemente bem e, ao mesmo tempo, computá-lo mais rapidamente que o próprio PhO de tal forma que possamos aplicá-lo em contextos maiores. Para avaliar a eficácia da nossa abodagem, conduzimos experimentos comparando nosso algoritmo ILSH com métodos já existentes como o próprio Post-hoc, uma versão relaxada usando programação linear ao invés de IP, e o LSH. Por fim, nós mostramos como nossa heurística pode performar bem e, ao mesmo tempo, manter estimativas mais próximas a solução do IP quando comparado ao LSH. Em relação a tempo de computação, ILSH toma menos tempo que PhO (mesmo computando planos tão bons quanto ele), mas, em média, custa até uma ordem de magnitude mais tempo do que LSH custa para computar a estimativa. Apesar de não ser o algoritmo mais rápido testado neste trabalho, sua superioridade em qualidade do plano e seu tempo de execução razoável faz com que ele seja uma alternativa interessante para os métodos existentes na literatura.