Depth-First Memory-Limited AND/OR Search and Unsolvability in Cyclic Search Spaces

Depth-First Memory-Limited AND/OR Search and Unsolvability in Cyclic Search Spaces

Akihiro Kishimoto, Adi Botea, Radu Marinescu

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 1280-1288. https://doi.org/10.24963/ijcai.2019/178

Computing cycle-free solutions in cyclic AND/OR search spaces is an important AI problem.  Previous work on optimal depth-first search strongly assumes the use of consistent heuristics, the need to keep all examined states in a transposition table, and the existence of solutions.  We give a new theoretical analysis under relaxed assumptions where previous results no longer hold.  We then present a generic approachto proving unsolvability, and apply it to RBFAOO and BLDFS, two state-of-the-art algorithms. We demonstrate the performance in domain-independent nondeterministic planning
Keywords:
Heuristic Search and Game Playing: Heuristic Search
Planning and Scheduling: Search in Planning and Scheduling