比较两种逃出启发式陷阱的方法，发现随机重启更优。
Breadth-First Search vs. Restarting Random Walks for Escaping Uninformed Heuristic Regions
- 用广度优先搜索和随机重启两种方式逃离无信息启发区域
- 理论推导表明随机重启在期望时间上更快
- 适用于规划求解中避免陷入局部最优的场景
贪婪搜索方法如贪心最佳优先搜索（GBFS）和强制爬坡（EHC）在面对无信息启发区域（UHRs）如局部极小值或平坦区时常常失效。本文从理论和实证角度比较了广度优先搜索（BrFS）与随机重启游走（RRWs）在逃离UHRs中的表现。基于UHR特性与随机游走过程，推导出两种方法逃离UHR的期望运行时间，并据此判断何时RRWs在期望上优于BrFS。进一步将标准EHC（使用BrFS逃逸）与EHC-RRW（改用RRWs）进行对比，结果显示EHC-RRW在以往EHC有效的情况下仍具备强期望时间保证。最后在PDDL规划基准上进行实验，验证了两者在逃离UHRs方面的相对有效性。
原文摘要 · Abstract (English)
Greedy search methods like Greedy Best-First Search (GBFS) and Enforced Hill-Climbing (EHC) often struggle when faced with Uninformed Heuristic Regions (UHRs) like heuristic local minima or plateaus. In this work, we theoretically and empirically compare two popular methods for escaping UHRs in breadth-first search (BrFS) and restarting random walks (RRWs). We first derive the expected runtime of escaping a UHR using BrFS and RRWs, based on properties of the UHR and the random walk procedure, and then use these results to identify when RRWs will be faster in expectation than BrFS. We then evaluate these methods for escaping UHRs by comparing standard EHC, which uses BrFS to escape UHRs, to variants of EHC called EHC-RRW, which use RRWs for that purpose. EHC-RRW is shown to have strong expected runtime guarantees in cases where EHC has previously been shown to be effective. We also run experiments with these approaches on PDDL planning benchmarks to better understand their relative effectiveness for escaping UHRs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。