Trial based Heuristic Tree Search for Finite Horizon MDPs

Ansätze zur Generierung von Lösungen für Markov Decision Processes (MDPs) sind beispielsweise Real-Time Dynamic Programming (RTDP), Monte-Carlo Tree Search (MCTS) und auch AO*. Alle diese Ansätze können im Framework Trial-Based Heuristic Search dargestellt werden. Dieses Framework betrachtet die jeweiligen Ansätze als spezifische Kombination von fünf elementaren Zutaten. Dadurch ermöglicht das Framework es auch, die einzelnen Zutaten gezielt neu zu kombinieren. Inhalt des Themas ist die Erarbeitung der einzelnen Ansätze mit ihren jeweiligen Vor- und Nachteilen als Instanzen des Frameworks.

Behandlung qualitativer Unsicherheit durch heuristische Suche

In dieser Arbeit wird ein bestimmter Ansatz zum Lösen
nicht-deterministischer Planungsprobleme untersucht. Ein solches Problem
beschreibt die Anforderung, bestimmte Ziele ausgehend von einem aktuellen
Zustand zu erfüllen. Während die Umgebung als voll observierbar
angenommen wird, können Aktionen potentiell mehrere Ausgänge haben.
Lösungen entsprechen Strategien, die das Erfüllen aller Ziele
garantieren, unabhängig davon, welche Aktions-Ausgänge bei der Ausführung der
Strategie eintreten.
Der hierzu verfolgte Ansatz erfordert die Verwendung einer bestimmten
Heuristik (Ziel-Distanz-Schätzung), die im Detail erörtert wird.

Point-Based Value Iteration

Value Iteration (VI) ist ein naiver Algorithmus zur Generierung von Lösungen, sogenannten Policies, für POMDPs, der allerdings nur sehr schlecht skaliert. Point-Based Value Iteration (PBVI) begrenzt die Komplexität der Berechnung durch eine gezielte Approximation des Vorgehens von VI. PBVI ist deshalb in der Lage interessantere Probleme zu lösen. Inhalt des Themas ist die Erarbeitung der Funktionsweise der Algorithmen Value Iteration und Point-Based Value Iteration.

Monte-Carlo Planning in large POMDPs

Monte-Carlo Tree Search (MCTS) bezeichnet eine Familie von Algorithmen, die Suchprobleme durch probabilistische Erforschung des Suchraums lösen. Als solche eignen sie sich auch für die Anwendung auf POMDPs. Hier ergeben sich sogar Synergien, die die Verwebung von Policy-Generierung und Policy-Ausführung vereinfachen und beim POMCP-Algorithmus ausgenutzt werden. Inhalt des Themas ist die Erarbeitung der Funktionsweise von MCTS und speziell des POMCP-Algorithmus.