Publication

Echtzeitentscheidungen durch Trajektoriensimulation in Dual Reality

Christian Bürckert

Mastersthesis Universität des Saarlandes 6/2014.

Abstract

Bei der Monte-Carlo-Baumsuche werden, anstatt einer Heuristik, Monte-Carlo Simulationen verwendet, um die Suche zu leiten. Die Monte-Carlo-Baumsuche wird zur Entscheidungsfindung in diskreten Zustandsräumen wie zum Beispiel beim Schach oder der Wegsuche verwendet. Eine Dual Reality ist eine beidseitige Verknüpfung der Realität mit einem virtuellen Modell dieser Realität. Dabei nehmen Sensoren die Realität wahr und das virtuelle Modell wird entsprechend dieser wahrgenommenen Veränderungen angepasst. Änderungen am virtuellen Modell werden, sofern möglich, durch Aktuatoren in die Realität übertragen. Die Zukunft des Modells einer Dual Reality kann mit Suchbäumen jedoch nicht ausgedrückt werden, da die zeitliche Entwicklung eine unendliche Verzweigung eines kontinuierlichen Modells darstellt. Die in dieser Arbeit vorgestellte Trajektoriensimulation kann verwendet werden, um die Zukunft eines virtuellen Modells einer Realität einzuschätzen und ermöglicht dadurch das Fällen von Entscheidungen, die in Echtzeit durch Aktuatoren in die Wirklichkeit umgesetzt werden können. Trajektoriensimulationen sind diskrete Simulationen kontinuierlicher Trajektorien, die dazu verwendet werden, den Erwartungswert einer Bewertungsfunktion in der Zukunft zu approximieren. Basierend auf der Einschätzung des Erwartungswerts wird eine mathematische Relation eingeführt, die es ermöglicht, die Alternativen einer Entscheidung zu bewerten. Eine so gewonnene Entscheidung kann als rational bezeichnet werden, da sie versucht den größten Erwartungswert zu erzielen. Dabei sind Fehleinschätzungen, die durch Schwankungen bei der Erwartungswertapproximation entstehen, möglich. Die Trajektoriensimulation kann als kontinuierliche Erweiterung der Monte-Carlo-Baumsuche gesehen werden. Zur Umsetzung wird in dieser Arbeit die Trajektoriensimulation zuerst mathematisch definiert und dann ein Rahmenwerk eingeführt, in dem Trajektoriensimulationen genutzt werden, um Entscheidungen in Dual Reality zu fällen. Dieses Rahmenwerk wird zusätzlich in drei Szenarien umgesetzt: Das erste Szenario ist eine intelligente Ampelsteuerung, die den Verkehrsfluss optimieren und die Wartezeiten der Autos, verglichen mit einer Zeitschaltung, drastisch verringert. Das zweite Szenario ist ein Kundenleitsystem für große Supermärkte, dass durch Kassenempfehlungen auf Monitoren oder Smartphones die Wartezeit an den Kassen verringern und die Auslastung der Kassen besser verteilen kann. Das dritte Szenario unterstützt Filialleiter bei der Entscheidung, wann welche Kasse geöffnet oder geschlossen werden soll, um eine gewünschte Wartezeitauslastung zu erzielen und zeigt, wie schnell neue Entscheidungen auf ein vorhandenes Modell umgesetzt werden können. Der Vorteil, dass ein Computer dazu in der Lage ist viele Simulationen parallel durchzuführen, kann dazu genutzt werden, die Qualität der Entscheidungen zu verbessern und macht Trajektoriensimulation zu einer zukunftssicheren KI-Methode, deren Entscheidungsqualität mit zunehmender Anzahl der CPU-Kerne automatisch wächst.

Projekte

Weitere Links

Masterarbeit_(Printed).pdf (pdf, 2 MB)

German Research Center for Artificial Intelligence
Deutsches Forschungszentrum für Künstliche Intelligenz