Limited Discrepancy Beam Search
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 125-130.
Abstract
Beam search reduces the memory consumption of bestfirst search at the cost of finding longer paths but its memory consumption can still exceed the given memory capacity quickly. We therefore develop BULB (Beam search Using Limited discrepancy Backtracking), a complete memory-bounded search method that is able to solve more problem instances of large search problems than beam search and does so with a reasonable runtime. At the same time, BULB tends to find shorter paths than beam search because it is able to use larger beam widths without running out of memory. We demonstrate these properties of BULB experimentally for three standard benchmark domains.
@inproceedings{ijcai2005p50,
title = {Limited Discrepancy Beam Search},
author = {Furcy, David and Koenig, Sven},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {125--130},
year = {2005},
url = {https://ijcai.org/proceedings/2005/50},
}
TY - CPAPER TI - Limited Discrepancy Beam Search AU - Furcy, David AU - Koenig, Sven T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 125 EP - 130 UR - https://ijcai.org/proceedings/2005/50 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
