BrFS vs. RRW: Neue Erkenntnisse zum Durchbrechen von Heuristik-Plateaus

In der Welt der Suchalgorithmen stoßen Greedy-Methoden wie Greedy Best‑First Search (GBFS) und Enforced Hill‑Climbing (EHC) häufig an die Grenzen von Uninformed Heuristic Regions (UHRs) – lokalen Minima und Plateaus, die die Suche ins Stocken bringen. Ein neues arXiv‑Veröffentlichung (arXiv:2511.09549v1) untersucht nun, wie man diese Hindernisse überwinden kann, indem man zwei populäre Techniken vergleicht: die klassische Breitensuche (BrFS) und das wiederholte Starten von Random Walks (RRWs).

Die Autoren leiten zunächst analytisch die erwartete Laufzeit für das Verlassen einer UHR mit BrFS und RRWs ab. Dabei berücksichtigen sie die Eigenschaften der UHR und die Dynamik der Random‑Walk‑Prozedur. Auf Basis dieser Resultate bestimmen sie, unter welchen Bedingungen RRWs im Erwartungswert schneller sind als BrFS.

Im praktischen Teil wird die Theorie auf die Enforced Hill‑Climbing‑Strategie angewendet. Während die Standard‑EHC die UHR‑Escape‑Phase mit BrFS realisiert, wird die Variante EHC‑RRW vorgestellt, die stattdessen RRWs nutzt. Die Experimente zeigen, dass EHC‑RRW robuste Laufzeitgarantien bietet – besonders in Szenarien, in denen die herkömmliche EHC bereits erfolgreich war.

Schließlich werden die beiden Ansätze auf einer Reihe von PDDL‑Planungsbenchmarks getestet. Die Resultate liefern wertvolle Einblicke in die relative Effektivität von BrFS und RRWs beim Durchbrechen von Heuristik‑Plateaus und geben Planern ein neues Werkzeug an die Hand, um schwierige Suchräume effizienter zu durchdringen.