Simultaneously Searching with Multiple Settings: An Alternative to Parameter Tuning for Suboptimal Single-Agent Search Algorithms
Simultaneously Searching with Multiple Settings: An Alternative to Parameter Tuning for Suboptimal Single-Agent Search Algorithms
复制标题
同时使用多个设置进行搜索：次优单代理搜索算法参数调整的替代方案
DOI：
10.1609/socs.v1i1.18151
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Akihiro Kishimoto
中科院分区：
文献类型：
--
作者：
R. Valenzano;Nathan R Sturtevant;J. Schaeffer;K. Buro;Akihiro Kishimoto
许多搜索算法都有需要调整的参数，以获得最佳性能。通常，这些参数是离线调优的，从而产生一个应该对所有问题实例都有效的通用设置。对于次优单代理搜索，特定于问题实例的参数设置可以显著减少搜索工作量。我们认为使用对接是利用这一事实的一种方式。对接是使用多个参数设置同时执行搜索的过程。研究表明，采用对接可以将加权IDA*的搜索速度提高几个数量级，并且总体上提高了加权RBF的性能。这个过程是微不足道的并行化，并且被证明是一种有效的对WA*和BUB并行化的形式。特别是，使用具有平行燕尾的WA*在滑动瓷砖拼图领域产生良好的加速比，并增加了在自动规划系统中使用时解决的问题的数量。
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.