Return to search

Simultaneously searching with multiple algorithm settings: an alternative to parameter tuning for suboptimal single-agent search

Many single-agent search algorithms have parameters that need to be tuned. Although settings found by offline tuning will exhibit strong average performance, properly selecting parameter settings for each problem can result in substantially reduced search effort. We consider the use of dovetailing as a way to deal with this issue. This procedure performs search with multiple parameter settings simultaneously. We present results testing the use of dovetailing with the weighted A*, weighted IDA*, weighted RBFS, and BULB algorithms on the sliding tile and pancake puzzle domains. Dovetailing will be shown to significantly improve weighted IDA*, often by several orders of magnitude, and generally enhance weighted RBFS. In the case of weighted A* and BULB, dovetailing will be shown to be an ineffective addition to these algorithms. A trivial parallelization of dovetailing will also be shown to decrease the search time in all considered domains.

Identiferoai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:AEU.10048/732
Date11 1900
CreatorsValenzano, Richard
ContributorsSchaeffer, Jonathan (Computing Science), Sturtevant, Nathan (Computing Science), Schaeffer, Jonathan (Computing Science), Sturtevant, Nathan (Computing Science), Liu, Andy (Mathematical and Statistical Sciences), Bulitko, Vadim (Computing Science)
Source SetsLibrary and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada
LanguageEnglish
Detected LanguageEnglish
TypeThesis
Format760491 bytes, application/pdf

Page generated in 0.0019 seconds