The use of a lower bound estimate in the search has a tremendous impact on the size of the resulting search trees, whereas OBDDs can be used to efficiently describe sets of states based on their binary encoding. This paper combines these two ideas into a new algorithm BDDA. It challenges both the breadth-first search using OBDDs and the traditional A algorithm. The problem with A is that in many application areas the set of states is too huge to be kept in main memory. In contrast, brute-force breadth-first search using OBDDs unnecessarily expands several nodes. Therefore, we exhibit a new trade-off between time and space requirements and tackle the most important problem in heuristic search, the overcoming of space limitations while avoiding a strong penalty in time. We evaluate our approach in the (n~2 - 1)-Puzzle and within Sokoban.
展开▼
