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

Akihiro Kishimoto, Adi Botea, Radu Marinescu

IJCAI 2019 pp. 1280-1288

doi:10.24963/IJCAI.2019/178 /ijcai/2019/kishimoto2019ijcai-depth/

Abstract

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

PDF IJCAI Semantic Scholar

Cite

Text

Kishimoto et al. "Depth-First Memory-Limited AND/OR Search and Unsolvability in Cyclic Search Spaces." International Joint Conference on Artificial Intelligence, 2019. doi:10.24963/IJCAI.2019/178

Markdown

[Kishimoto et al. "Depth-First Memory-Limited AND/OR Search and Unsolvability in Cyclic Search Spaces." International Joint Conference on Artificial Intelligence, 2019.](https://mlanthology.org/ijcai/2019/kishimoto2019ijcai-depth/) doi:10.24963/IJCAI.2019/178

BibTeX

@inproceedings{kishimoto2019ijcai-depth,
  title     = {{Depth-First Memory-Limited AND/OR Search and Unsolvability in Cyclic Search Spaces}},
  author    = {Kishimoto, Akihiro and Botea, Adi and Marinescu, Radu},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {1280-1288},
  doi       = {10.24963/IJCAI.2019/178},
  url       = {https://mlanthology.org/ijcai/2019/kishimoto2019ijcai-depth/}
}