Neue Anytime-Variante von Multi-Heuristic A* liefert bessere Lösungen

Eine neue Variante des Multi-Heuristic A* (MHA*) namens A-MHA* wurde auf arXiv veröffentlicht und verspricht, die Suche nach suboptimalen Lösungen in Echtzeit zu revolutionieren. Durch die Kombination bewährter Ideen aus dem Anytime Repairing A* (ARA*) kann A-MHA* sofort eine brauchbare Lösung finden und diese kontinuierlich verbessern, solange Zeit zur Verfügung steht.

Der klassische MHA* nutzt mehrere inadmissible Heuristiken, um schneller als herkömmliche A* zu arbeiten, aber er liefert nur ein einmaliges Ergebnis. A-MHA* löst dieses Problem, indem es die Inflationsfaktoren dynamisch anpasst und die Lösungsschleife offen hält. Die Autoren zeigen, dass die Suboptimalitäts- und Vollständigkeitsgarantien des Originals erhalten bleiben, während die Anytime-Funktionalität hinzukommt.

In umfangreichen Tests wurde A-MHA* in einem 3‑D‑Pfadplanungs‑Domain sowie bei klassischen Schiebepuzzles eingesetzt. Die Ergebnisse zeigen, dass A-MHA* nicht nur schneller eine erste Lösung liefert, sondern diese auch schneller verbessert als der ursprüngliche MHA* und andere Anytime‑Algorithmen. Damit eröffnet die Methode neue Möglichkeiten für Echtzeit‑Planungsaufgaben in Robotik, Spieleentwicklung und Logistik.