EUVIMEDEUVIMED entdecken
Crossref

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

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

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (43) · 37143-37151

DOI: 10.1609/aaai.v40i43.41044 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Daniel Platnick und 4 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Platnick, D., Tomasz, D., Earl, E., Khanzadeh, S., & Valenzano, R. (2026). Breadth-First Search vs. Restarting Random Walks for Escaping Uninformed Heuristic Regions. Proceedings of the AAAI Conference on Artificial Intelligence, 40(43), 37143-37151. https://doi.org/10.1609/aaai.v40i43.41044

Vancouver

Platnick D, Tomasz D, Earl E, Khanzadeh S, Valenzano R. Breadth-First Search vs. Restarting Random Walks for Escaping Uninformed Heuristic Regions. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(43):37143-37151. doi:10.1609/aaai.v40i43.41044

BibTeX
@article{Platnick2026,
  author = {Platnick, Daniel and Tomasz, Dawson and Earl, Eamon and Khanzadeh, Sourena and Valenzano, Richard},
  title = {Breadth-First Search vs. Restarting Random Walks for Escaping Uninformed Heuristic Regions},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {43},
  pages = {37143--37151},
  doi = {10.1609/aaai.v40i43.41044}
}
Kostenlos starten →