PEA*+IDA*: An Improved Hybrid Memory-Restricted Algorithm

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 timerestricted 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 algorithm that combines A∗ and IDA∗. In this paper, 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 duplicate detection on each node of PEA∗ ’s Open. 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 algorithms.

Authors

• Frederico Messa
• André Grahl Pereira

Keywords

No keywords are indexed for this paper.