 |
Problem Difficulty and the Phase Transition in Heuristic Search
Members
J. Christopher Beck
Eldan Cohen
|
Project description
In the recent years, there has been significant work on the difficulty of heuristic search problems, identifying different problem instance characteristics that can have a significant impact on search effort. Phase transitions in the solubility of random problem instances have proved useful in the study of problem difficulty for other classes of computational problems, notably SAT and CSP, and it has been shown that the hardest problems typically occur during this rapid transition. In this work, we perform the first empirical investigation of the phase transition phenomena for heuristic search. We establish the existence of a rapid transition in the solubility of an abstract model of heuristic search problems and show that, for greedy best first search, the hardest instances are associated with the phase transition region. We then perform a novel investigation of the behavior of heuristics of different strength across the solubility spectrum. Finally, we demonstrate that the behavior of our abstract model carries over to commonly used benchmark problems including the Pan- cake Problem, Grid Navigation, TopSpin, and the Towers of Hanoi. An interesting deviation is observed and explained in the Sliding Puzzle.
As a major direction of our future work, we will investigate the application of the results above to other heuristic search algorithms such as cost-based GBFS and A*. Also, we intend to investigate "difficult" problem characteristics, such as a large operator cost ratio and the existence of UHRs, across the constrainedness range.
Start date
January 2016
Funding
University of Toronto Fellowship
TIDEL Research Assistantship
Publications
- Cohen, E. & Beck, J.C., "Problem Difficulty and the Phase Transition in Heuristic Search", Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, (AAAI2017), in press, 2017.
|
