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

Authors

  • Frederico Messa Universidade Federal do Rio Grande do Sul
  • André Grahl Pereira Universidade Federal do Rio Grande do Sul

DOI:

https://doi.org/10.1609/aaai.v36i9.21270

Keywords:

Search And Optimization (SO), Planning, Routing, And Scheduling (PRS)

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 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.

Downloads

Published

2022-06-28

How to Cite

Messa, F., & Pereira, A. G. (2022). PEA*+IDA*: An Improved Hybrid Memory-Restricted Algorithm. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9), 10291-10298. https://doi.org/10.1609/aaai.v36i9.21270

Issue

Section

AAAI Technical Track on Search and Optimization