AAAI Publications, Third Annual Symposium on Combinatorial Search

Font Size: 
Finding Acceptable Solutions Faster Using Inadmissible Information
Jordan Tyler Thayer, Wheeler Ruml

Last modified: 2010-08-25


Bounded suboptimal search algorithms attempt to find a solution quickly while guaranteeing that the cost does not exceed optimal by more than a desired factor. These algorithms generally use a single admissible heuristic both for guidance and guaranteeing solution quality. We present a new approach to bounded suboptimal search that separates these roles, consulting multiple sources of potentially inadmissible information to determine search order and using admissible information to guarantee quality. An empirical evaluation across six benchmark domains shows the new approach has better overall performance.


bounded suboptimality; search; heuristics

Full Text: PDF