A non-admissible heuristic function based on synchronized abstract plans

Abstract

Classical Planning is a traditional Artificial Intelligence problem that consists of finding a sequence of actions, called a plan, to achieve some desired goal given an initial state. We say that the plan cost is the sum of the costs of performing each action that composes the plan. A classical planning task is a compact description of a planning problem. It induces a transition system: a graph where the vertices represent the possible states and the edges represent the actions that transform the states. To solve the planning problem, one has to determine a path from the initial state to a goal state in the transition system. Search algorithms combined with domain-independent heuristic functions are the most popular method for solving classical planning tasks. Heuristics estimate how far a state is from the goal, indicating which state should be evaluated next. An approach taken by some heuristics is to use abstractions: a mapping of the concrete states into abstract states that results in the so-called abstract transition system, which is typically smaller than the original transition system. The cost of a plan in the abstract transition system is an estimate for the concrete plan cost. This work introduces a new non-admissible heuristic for satisficing planning (where the goal is to find any plan, not necessarily the cheaper one). The main idea is: given an ordered list of abstract transition systems, compute the cheapest path from the source state to a goal state for each graph, considering the actions that compose previous paths as credit for the following ones. More precisely, an action can be used in a new path for free (with cost zero) up to the number of times it appears on the already determined path that uses it the most. In the end, the heuristic value is the sum of the cost of all paths found. We evaluate the proposed heuristic with the Fast Downward planning system. We com pare our heuristic with FF and Post-Hoc Optimization heuristics on the IPC11’s bench mark suite. The results show that the new heuristic increases the coverage by 12% com pared to the FF heuristic, while expanding fewer states on most domains.

Planejamento clássico é um tradicional problema de Inteligência Artificial que consiste em encontrar uma sequência de ações, denominada de plano, para atingir um desejado objetivo dado um estado inicial. Dizemos que o custo do plano é a soma dos custos de realizar cada ação que compõem o plano. Uma tarefa de planejamento clássico é uma descrição compacta de um problema de planejamento. Ela induz um sistema de transição: um grafo onde os vértices representam os possíveis estados e as arestas representam as ações que transformam os estados. Para resolver o problema de planejamento, é preciso determinar um caminho do estado inicial para um estado objetivo no sistema de transição. Algoritmos de busca combinados com funções heurísticas independentes de domínio são o método mais popular para resolução de tarefas de planejamento clássico. Heurísticas estimam quão longe um estado está do objetivo, indicando qual estado deve ser avaliado a seguir. Uma abordagem adotada por algumas heurísticas é utilizar uma abstração: um mapeamento dos estados concretos em estados abstratos que resulta no chamado sistema de transição abstrato, que é tipicamente menor que o sistema de transição original. O custo de um plano no sistema de transição abstrato é uma estimativa do custo do plano concreto. Este trabalho introduz uma nova heurística não admissível para "satisficing planning" (onde o objetivo é encontrar qualquer plano, não necessariamente o mais barato). A ideia principal é: dado uma lista ordenada de sistemas de transição abstratos, calcular o caminho mais barato do estado inicial até um estado objetivo para cada grafo, considerando as ações que compõem os caminhos anteriores como crédito para os seguintes. Mais precisamente, uma ação pode ser utilizada em um novo caminho gratuitamente (com custo zero) até a quantidade de vezes que aparece no caminho já encontrado que mais a utiliza. No final, o valor da heurística é a soma do custo de todos os caminhos encontrados. Nós avaliamos a heurística proposta com o sistema de planejamento Fast Downward. Comparamos nossa heurística com as heurísticas FF e Post-Hoc Optimization no con junto de benchmarks da IPC11. Os resultados mostram que a nova heurística aumenta a cobertura em 12% em comparação com a heurística FF, enquanto expande menos estados na maioria dos domínios.