提出新启发式方法F2A,高效降低双向搜索的计算开销。
Front-to-Attractors: Modifying the Front-to-Front Heuristic in Bidirectional Search

- 用动态维护的吸引子替代完整前段,减少配对计算
- 相比F2F节省11.2倍评估次数,比F2E少4.8倍节点扩展
- 适合需要高效路径搜索的应用场景
启发式在双向搜索算法中起核心作用,常见两类:前向到终点(F2E)估计状态到目标的距离;前向到前段(F2F)则通过成对函数h(s, s')估算到对向搜索前段中各状态的距离。尽管F2F更有效且减少节点扩展,但其依赖大量成对计算带来显著开销。为此,我们提出新启发式类——前向到吸引子(F2A),在保留F2F高信息量的同时大幅降低计算成本。F2A不评估到所有对向前段状态的距离,而是估算到一组动态维护的吸引子的距离。这些吸引子作为前段的代理,实现丰富启发式引导,同时仅需极少计算资源,并保持与F2F相同的最优性保证。我们在多个领域验证F2A,结果表明其相比F2F减少最多11.2倍的成对评估,平均比F2E少4.8倍节点扩展。
原文摘要 · Abstract (English)
Heuristics play a central role in the performance of bidirectional search algorithms, which commonly rely on two main classes. Front-to-end (F2E) heuristics estimate the distance from a state s to the target of the search (the goal for forward search or the start for backward search). In contrast, front-to-front (F2F) heuristics estimate the distance from s to the opposite search frontier using a pairwise function h(s, s'), where s' ranges over frontier states. Although F2F heuristics are typically more informative and therefore reduce the number of node expansions, their reliance on extensive pairwise evaluations incurs substantial computational overhead. To address this limitation, we introduce a new heuristic class, front-to-attractors (F2A), that preserves much of the informativeness of F2F while dramatically reducing its computational cost. Rather than evaluating distances to all states on the opposite frontier, F2A estimates the distance from s to a small, dynamically maintained set of attractors in the opposite search direction. These attractors serve as a surrogate for the full frontier, enabling rich heuristic guidance at a fraction of the computational expense while maintaining the optimality guarantees offered by F2F. We evaluate F2A across multiple domains and show that it reduces the number of pairwise evaluations by up to 11.2x compared to F2F, while achieving 4.8x fewer node expansions than F2E on average.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。