2021/03/23 by Zhaoxing Bu, Richard E. Korf, Bu, Zhaoxing +1
Computer Science · #AI-based Problem Solving and Planning #Artificial Intelligence (cs.AI) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Formal Methods in Verification #I.2.8
paper · pdf · doi:10.48550/arxiv.2103.12701
openalex publication_date 2021/03/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a new algorithm A*+BFHS for solving problems with unit-cost operators where A* and IDA* fail due to memory limitations and/or the existence of many distinct paths between the same pair of nodes. A*+BFHS is based on A* and breadth-first heuristic search (BFHS). A*+BFHS combines advantages from both algorithms, namely A*'s node ordering, BFHS's memory savings, and both algorithms' duplicate detection. On easy problems, A*+BFHS behaves the same as A*. On hard problems, it is slower than A* but saves a large amount of memory. Compared to BFIDA*, A*+BFHS reduces the search time and/or memory requirement by several times on a variety of planning domains.