Local Minima, Heavy Tails, and Search Effort for GBFS

Local Minima, Heavy Tails, and Search Effort for GBFS

Eldan Cohen, J. Christopher Beck

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 4708-4714. https://doi.org/10.24963/ijcai.2018/654

Problem difficulty for greedy best first search (GBFS) is not entirely understood, though existing work points to deep local minima and poor correlation between the h-values and the distance to goal as factors that have significant negative effect on the search effort. In this work, we show that there is a very strong exponential correlation between the depth of the single deepest local minima encountered in a search and the overall search effort. Furthermore, we find that the distribution of local minima depth changes dramatically based on the constrainedness of problems, suggesting an explanation for the previously observed heavy-tailed behavior in GBFS. In combinatorial search, a similar result led to the use of randomized restarts to escape deep subtrees with no solution and corresponding significant speed-ups. We adapt this method and propose a randomized restarting GBFS variant that improves GBFS performance by escaping deep local minima, and does so even in the presence of other, randomization-based, search enhancements.
Keywords:
Planning and Scheduling: Planning Algorithms
Heuristic Search and Game Playing: Heuristic Search
Planning and Scheduling: Search in Planning and Scheduling