Effective Bidirectional A* with Frontier Search and External-Memory Utilization

• Author(s) / Creator(s)

  • Niewiadomski, Robert
  • Amaral, Jose Nelson
  • Holte, Robert

• Technical report TR08-18. We present an advanced Bidirectional A* algorithm featuring an application of Frontier Search and a strategy for the performance-efficient utilization of External Memory. We present the results of an experimental evaluation demonstrating that this algorithm is capable of tackling exceptionally large state spaces while consuming significantly less time and space than its A* counterpart. For instance, in solving difficult instances of the 5-by-5 Sliding-Tile Puzzle and the 4-peg Towers-of-Hanoi problems, using additive pattern-database heuristics, the typical reductions in time- and space-consumption are in the range of one to two orders of magnitude. | TRID-ID TR08-18

• Date created

  2008

• Subjects / Keywords

  • Artificial Intelligence
  • Software Systems

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3J09WB0G

• License

  Attribution 3.0 International