PEA*+IDA* : an improved hybrid memory-restricted algorithm

Abstract

It is well-known that the search algorithms A* and Iterative Deepening A* (IDA*) can fail to solve state-space tasks optimally due to time and memory limits. The former typically fails in memory-restricted scenarios and the latter in time-restricted scenarios. Therefore, several algorithms were proposed to solve state-space tasks optimally using less memory than A* and less time than IDA*, such as A*+IDA*, a hybrid memory-restricted algo rithm that combines A* and IDA*. In this work, we present a hybrid memory-restricted algorithm that combines Partial Expansion A* (PEA*) and IDA*. This new algorithm has two phases, the same structure as the A*+IDA* algorithm. The first phase of PEA*+IDA* runs PEA* until it reaches a memory limit, and the second phase runs IDA* without du plicate detection on each node of the Open of PEA*. First, we present a model that shows how PEA*+IDA* can perform better than A*+IDA* although pure PEA* usually makes more expansions than pure A*. Later, we perform an experimental evaluation using three memory limits and show that compared to A*+IDA* on classical planning domains, PEA*+IDA* has higher coverage and expands fewer nodes. Finally, we experimentally analyze both algorithms and show that having higher F-limits and better priority-queue composition given by PEA* have a considerable impact on the performance of the algo rithms.

É bem conhecido que os algoritmos de busca A* e Aprofundamento Iterativo A* (IDA* em inglês) podem falhar em resolver otimamente tarefas de busca em espaços de estado de vido a limites de tempo e memória. O primeiro tipicamente falha em cenários de memória limitada e o segundo em cenários de tempo limitado. Portanto, diversos algoritmos foram propostos para resolver otimamente tarefas de busca em espaços de estado usando menos memória que A* e menos tempo que IDA*, como por exemplo A*+IDA*, um algoritmo híbrido de memória limitada que combina A* e IDA*. Nesse artigo, nós apresentamos um algoritmo híbrido de memória limita que combina o A* de Expansões Parciais (PEA* em inglês) com IDA*. Este novo algoritmo possui duas fases, mesma estrutura que o algo ritmo A*+IDA*. A primeira fase do PEA*+IDA* roda PEA* até o limite de memória ser alcançado, e a segunda fase roda IDA*, sem detecção de duplicatas, em cada nó da Open do PEA*. Primeiramente nós apresentamos um modelo que mostra como PEA*+IDA* pode performar melhor que A*+IDA* apesar do PEA* puro normalmente fazer mais ex pansões que o A* puro. Depois nós apresentamos uma avaliação experimental usando três limites de memória e mostramos que comparado ao A*+IDA*, em domínios de planeja mento clássico, PEA*+IDA* tem uma cobertura maior e expande menos nós. Por fim nós analisamos experimentalmente ambos algoritmos e mostramos que ter um F-limite maior e ter a fila de prioridades com melhor composição por conta do PEA* causa um impacto considerável na performance dos algoritmos.