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.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:AEU.10048/732 |
| Date | 11 1900 |
| Creators | Valenzano, Richard |
| Contributors | Schaeffer, 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 Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 760491 bytes, application/pdf |
Page generated in 0.0018 seconds