Landmark-basierte Monte-Carlo-Planung verbessert probabilistische MDPs

In der klassischen Planung haben Landmarke – Bedingungen, die in jedem Lösungsplan erfüllt sein müssen – bereits große Fortschritte ermöglicht. Neu ist die Anwendung dieser Idee in stochastischen Entscheidungsprozessen. Forscher haben probabilistische Landmarke definiert und den bekannten UCT‑Algorithmus so angepasst, dass er diese Landmarke als Zwischenschritte nutzt, um Markov‑Entscheidungsprozesse (MDPs) zu zerlegen.

Der Schlüssel zur Anpassung liegt in der Balance zwischen dem schnellen Erreichen von Landmarken („greedy“) und dem langfristigen Erreichen des eigentlichen Ziels. Durch diese Kombination kann der Algorithmus gezielt wichtige Zustände ansteuern, ohne dabei das Endziel aus den Augen zu verlieren.

In umfangreichen Benchmark‑Tests zeigte sich, dass gut gewählte Landmarke die Leistung von UCT in Online‑Planungsaufgaben deutlich steigern. Gleichzeitig hängt die optimale Mischung aus kurzfristigem und langfristigem Fokus stark vom jeweiligen Problem ab.

Die Ergebnisse deuten darauf hin, dass Landmarke wertvolle Leitfäden für Anytime‑Algorithmen darstellen, die MDPs lösen. Sie eröffnen damit neue Wege, probabilistische Planung effizienter und zielgerichteter zu gestalten.