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.