AAAI Publications, Third Annual Symposium on Combinatorial Search

Font Size: 
Simultaneously Searching with Multiple Settings: An Alternative to Parameter Tuning for Suboptimal Single-Agent Search Algorithms
Richard Anthony Valenzano, Nathan Sturtevant, Jonathan Schaeffer, Karen Buro, Akihiro Kishimoto

Last modified: 2010-08-25


Many search algorithms have parameters that need to be tuned to get the best performance. Typically, the parameters are tuned offline, resulting in a generic setting that is supposed to be effective on all problem instances. For suboptimal single-agent search, problem-instance-specific parameter settings can result in substantially reduced search effort. We consider the use of dovetailing as a way to take advantage of this fact. Dovetailing is a procedure that performs search with multiple parameter settings simultaneously. Dovetailing is shown to improve the search speed of weighted IDA* by several orders of magnitude and to generally enhance the performance of weighted RBFS. This procedure is trivially parallelizable and is shown to be an effective form of parallelization for WA* and BULB. In particular, using WA* with parallel dovetailing yields good speedups in the sliding-tile puzzle domain, and increases the number of problems solved when used in an automated planning system.


single-agent search; dovetailing; wida*; wrbfs; bulb; parallel wa*; parallel planning; parallel search; configuration selection

Full Text: PDF