Künstliche intelligente Agenten, die sich wie Menschen verhalten, sind in den letzten Jahren zu einem bestimmenden Thema und einem der Hauptziele geworden, die die rasante Entwicklung des Deep Learning, insbesondere des Reinforcement Learning (RL), vorantreiben. Monte-Carlo Tree Search (MCTS) ist eine Klasse von Methoden zur Lösung komplexer Entscheidungsprobleme durch die Synergie von Monte-Carlo-Planung und Reinforcement Learning (RL). MCTS hat beeindruckende Ergebnisse bei Go (AlphaGo), Schach (AlphaZero) oder Videospielen erzielt und wurde auch bei der Bewegungsplanung, dem autonomen Fahren von Autos und der autonomen Montage von Robotern erfolgreich eingesetzt. Viele der MCTS-Erfolge beruhen auf der Kopplung von MCTS mit neuronalen Netzen, die mit RL-Methoden wie Deep Q-Learning trainiert werden, um das Lernen von großen Problemen zu beschleunigen. Obwohl MCTS den neuesten Stand der Technik erreicht, erfordert die hochgradig kombinatorische Natur der Probleme, die üblicherweise mit MCTS behandelt werden, den Einsatz effizienter Strategien für die Navigation im Planungsbaum und schnell konvergierende Methoden für die Wertsicherung. Darüber hinaus erfordern große Probleme wie Go- und Schachspiele eine Sampling-Effizienz-Methode, um einen effektiven Planungsbaum zu erstellen, der für die fliegende Entscheidungsfindung entscheidend ist. Diese akuten Probleme sind besonders offensichtlich, vor allem bei den jüngsten Fortschritten, die MCTS mit tiefen neuronalen Netzen zur Funktionsannähe-rung kombinieren. Trotz der jüngsten Erfolge bei der Anwendung von MCTS zur Lösung verschiedener Aufgaben der autonomen Robotik sind die meisten Szenarien jedoch teilweise beobachtbar und erfordern eine fortschrittliche Planungsmethode in komplexen, unstrukturierten Umgebungen.

Diese Arbeit zielt darauf ab, die folgenden Fragen zu beantworten: Wie können Roboter unter hoch stochastischer Dynamik und partieller Beobachtbarkeit effizient planen? In den folgenden Abschnitten wird versucht, diese Frage zu beantworten: Zunächst schlagen wir eine neuartige Backup-Strategie vor, die den Power-Mittelwert-Operator verwendet, der einen Wert zwischen dem Durchschnitts- und dem Maximalwert berechnet. Wir nennen unseren neuen Ansatz Power-UCT. Wir analysieren unsere Methode theoretisch und geben Garantien für die Konvergenz zum Optimum. Schließlich demonstrieren wir empirisch die Effektivität unserer Methode in bekannten MDP- und POMDP-Benchmarks, die eine signifikante Verbesserung in Bezug auf die Stichprobeneffizienz und die Konvergenzge-schwindigkeit im Vergleich zu modernen Algorithmen zeigen.

Zweitens untersuchen wir eine effiziente Explorations-Ausnutzungs-Planungsstrategie, indem wir einen umfassenden theoretischen konvexen Regularisierungsrahmen in MCTS bereitstellen. Wir leiten die erste Regret-Analyse von regularisierten MCTS ab und zeigen, dass sie eine exponentielle Konvergenzrate garantiert. Anschließend nutzen wir unseren theoretischen Rahmen, um neuartige regularisierte Backup-Operatoren für MCTS einzu-führen, die auf der relativen Entropie der Politikaktualisierung und, was noch wichtiger ist, auf der Tsallis-Entropie der Politik basieren, für die wir überlegene theoretische Garantien beweisen. Anschließend verifizieren wir die Konsequenz unserer theoretischen Ergebnisse empirisch an einem Spielzeugproblem. Schließlich zeigen wir, wie unser Rahmenwerk leicht in AlphaGo integriert werden kann, und wir zeigen empirisch die Überlegenheit der konvexen Regularisierung im Vergleich zu repräsentativen Baselines bei bekannten RL-Problemen in mehreren Atari-Spielen.

In einem weiteren Schritt stellen wir die Verbindung zwischen den beiden Methoden, Power-UCT und der konvexen Regularisierung in MCTS, her und liefern eine rigorose theoretische Studie über die Effektivität der α-Divergenz in der Online Monte-Carlo Planung. Wir zeigen, wie die beiden Methoden durch die Verwendung der α-Divergenz miteinander verbunden werden können. Darüber hinaus bieten wir eine detaillierte Studie über den Bereich des α-Parameters, der dabei hilft, einen Kompromiss zwischen exploration-exploitation in MCTS zu finden, und zeigen somit, wie α-Divergenz in AlphaGo und AlphaZero integriert werden kann, um bei komplexen Aufgaben die besten Ergebnisse zu erzielen.

Schließlich untersuchen wir eine neuartige algorithmische Formulierung des beliebten MCTS-Algorithmus für die Roboterbahnplanung. Insbesondere untersuchen wir die Monte-Carlo-Pfadplanung (MCPP), indem wir zum einen ihre exponentielle Konvergenzrate zum optimalen Pfad in vollständig beobachtbaren MDPs analysieren und beweisen und zum anderen ihre probabilistische Vollständigkeit für das Finden machbarer Pfade in POMDPs (Beweisskizze) unter der Annahme begrenzter Beobachtbarkeit der Entfernung. Unser algorithmischer Beitrag ermöglicht es uns, kürzlich vorgeschlagene Varianten von MCTS mit verschiedenen Explorationsstrategien für die Roboterbahnplanung einzusetzen. Unsere experimentellen Auswertungen in simulierten 2D- und 3D-Umgebungen mit einem Manipulator mit 7 Freiheitsgraden (DOF) und in einer realen Roboter-Bahnplanungsaufgabe zeigen die Überlegenheit von MCPP in POMDP-Aufgaben.

Zusammenfassend lässt sich sagen, dass in dieser Arbeit neuartige Value-Backup-Operatoren und Policy-Selection-Strategien sowohl aus theoretischer als auch aus experimenteller Sicht vorgeschlagen und analysiert werden, um mit den Trade-Off-Problemen Stichproben-Effizienz und Exploration-Exploitation in MCTS zurechtzukommen und diese fortschrittlichen Methoden in die Roboterbahnplanung einzubringen.