Finding Acceptable Solutions Faster Using Inadmissible Information

Proceedings of the International Symposium on Combinatorial Search, 3

Volume

Vol. 3 No. 1 (2010): Third Annual Symposium on Combinatorial Search

Oral Presentations

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.

10.1609/socs.v1i1.18173