Lune

AAAI2026Top-tier venue

Breadth-First Search vs. Restarting Random Walks for Escaping Uninformed Heuristic Regions

Daniel Platnick, Dawson Tomasz, Eamon Earl, Sourena Khanzadeh, Richard Valenzano

Abstract

Greedy search methods such as 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: breadth-first search (BrFS) and restarting random walks (RRWs). First, we 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. Next, we 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. Finally, we run experiments with these approaches on PDDL planning benchmarks to better understand their relative effectiveness for escaping UHRs.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. How the Duration of the Learning Period Affects the Performance of Random Gradient Selection Hyper-HeuristicsAndrei Lissovoi, Pietro S. Oliveto, John Alasdair WarwickerAAAI 2020 · 14 citations
  2. Optimize Planning Heuristics to Rank, not to Estimate Cost-to-GoalLeah Chrestien, Stefan Edelkamp, Antonín Komenda, Tomás PevnýNeurIPS 2023 · 17 citations
  3. New Results in Bounded-Suboptimal SearchMaximilian Fickert, Tianyi Gu, Wheeler RumlAAAI 2022 · 9 citations
  4. Rectangle Search: An Anytime Beam SearchSofia Lemons, Wheeler Ruml, Robert C. Holte, Carlos Linares LópezAAAI 2024
  5. What Are the Rules? Discovering Constraints from DataBoris Wiegand, Dietrich Klakow, Jilles VreekenAAAI 2024 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines