Depth-bounded Discrepancy Search

Walsh, Toby

Depth-bounded Discrepancy Search

Download BibTeX Cite

Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Search. Pages 1388-1394.

Abstract

Many search trees are impractically large to explore exhaustivel y. Recently, techniques like limited discrepancy search have been proposed for improving the chance of finding a goal in a limited amount of search. Depth-bound ed discrepancy search offers such a hop e. The motivation behind depth-bounded discrepancy search is that branching heuristics are more likely to be wrong at the top of the tree than at the bottom . We therefore combine one of the best features of limited discrepancy search - the ability to undo early mistakes - with the completeness of iterative deepening search. We show theoretically and experimentally that this novel combination outperforms existing techniques.

Toby Walsh. 1997. Depth-bounded Discrepancy Search. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97. IJCAI, 1388–1394. https://ijcai.org/proceedings/1997/200

@inproceedings{ijcai1997p200,
  title     = {Depth-bounded Discrepancy Search},
  author    = {Walsh, Toby},
  booktitle = {Proceedings of the Fifteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-97}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Martha E. Pollack},
  pages     = {1388--1394},
  year      = {1997},
  note      = {Search},
  url       = {https://ijcai.org/proceedings/1997/200},
}

TY  - CPAPER
TI  - Depth-bounded Discrepancy Search
AU  - Walsh, Toby
T2  - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1997
SP  - 1388
EP  - 1394
UR  - https://ijcai.org/proceedings/1997/200
ER  -