Reproduce “Breadth-First Search vs. Restarting Random Walks for Escaping Uninformed Heuristic Regions” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

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

A comparative study establishes theoretical runtimes and empirical performance for Breadth-First Search (BrFS) and Restarting Random Walks (RRWs) in escaping uninformed heuristic regions (UHRs) in AI planning. The research identifies theoretical conditions favoring each method and demonstrates that RRW variants offer memory efficiency and improved coverage in certain unbounded-UHR domains.

Key insights

  • BrFS runtime is fundamentally tied to the number of states shallower than the goal depth, which it must explore exhaustively, while RRW runtime is inversely proportional to the success probability of a single walk.
  • RRWs are theoretically faster than BrFS when the success probability is sufficiently high, particularly in broad, deeper search spaces with a high density of escape states.
  • The number of goals required for RRWs to outperform BrFS increases linearly with goal depth, but the density of goals needed actually decreases with increasing depth, suggesting RRWs are more competitive in deeper state space parts.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.