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

• Author / Creator

  Valenzano, Richard

• 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.

• Subjects / Keywords

  • WA*
  • Parallel search
  • WIDA*
  • Heuristic search
  • BULB
  • Dovetailing
  • Parameter tuning
  • Suboptimal single-agent search
  • WRBFS

• Graduation date

  Fall 2009

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/R37Q55

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.