Planungsverfahren für das Allgemeine Spiel
Final Report Abstract
Die automatische Synthese von Robotik-Kontrollern aus GDL-Spezifikationen der Robotik-Umgebung unter Einbeziehung unvollständiger Information ist unser Ansatz, die am Lehrstuhl existierende Expertise in der Robotik mit der des Allgemeinen Spiels zu verbinden. Eine der ältesten Visionen der Künstlichen Intelligenz ist die Konstruktion von autonomen Robotern, deren Problemlösefähigkeit vergleichbar zu der von Menschen ist. Anfang der 70er Jahre entstand das Stanford Research Institute Planning System STRIPS (Fikes & Nilsson, 1971), dessen Formalismus zur Beschreibung von Handlungsplanungsfragestellungen bis in die heutige Zeit grundlegend ist. STRIPS ist durch die Ausführung von Plänen auf Robotern motiviert, und SHAKEY (Nilsson 1984) einer der ersten Roboter, der Service-Dienste auf Basis von STRIPS anbieten sollte. STRIPS unterteilt Planungsoperatoren in Vorbedingungen und Effekte und bietet einen Schlussfolgerungsmechanismus an, der aus einer logischen Beschreibung von Start- und Zielzustand einen Plan als Sequenz von Aktionen generiert. STRIPS wurde über die Jahre auf Beschreibungssprachen, wie die Planning Domain Definition Language PDDL, erweitert. Parallel dazu entstand GDL (für Game Description Language), die sich zur Beschreibung von Spielen eignet. Untersuchungen (z.B. mit unserem System GAMER) zeigen: Viele Planungsprobleme lassen sich in GDL sowie viele Spiele in PDDL überführen. Ungeachtet der Vision für die Planungs-basierte Robotik, ist es Forschern über die Jahre nur bedingt gelungen, "klassische" Ansätze auf einen Service-Roboter zum Beispiel für die Haushaltsarbeit zu portieren. Die Gründe dafür sind vielfältig: Die Diskrepanz von Weltzustand und seiner interner Repräsentation; der Unterschied des Arbeits- und (mit vielen Freiheitsgraden behafteten) Konfigurationsraumes; der Umgang mit der fehlerbehafteten Ausführung von Plänen; viele Pläne sind "paranoid": alle Unwägbarkeiten werden ausgeschlossen; das Fehlen von Lernverfahren zur stetigen Verbesserung von Plänen; die Notwendigkeit von reaktiver, d.h. sich der Umgebung anpassender Pläne; die Anforderung an eine Planung in Realzeit; die Diskrepanz zwischen diskreter und kontinuierlicher Darstellung; die Ungenauigkeit von und die Vielfältigkeit der verschiedenen Sensoren; die inhärente Unvollständigkeit von Informationen; die festen Ausführungseinheiten in der Roboterkontrolle; die Komplexität der Inferenzaufgabe auf Basis von Trajektorien, u.v.a.m. Dabei wird ein Plan bzw. eine Strategie als ausführbares Programm angesehen. Die Erzeugung (Synthese) von Plänen basierend auf ausführbaren Einheiten und Rückkopplung mit dem Sensorsystem ist somit vielschichtig. Unser Ansatz trägt die folgenden drei Kernideen: 1. Nutzung von GDL als Repräsentationssprache zur Modellierung von Robotik- Domänen. Diese etablierte Sprachklasse ist sowohl expressiv als auch als deskriptiv. 2. Betrachtung der Umgebung als modellierbarer Gegenspieler. Dies erlaubt eine Strategiesynthese als ausführbares Programm, wobei besondere Aufmerksamkeit der Gegenspielermodellierung gebührt, da die Umgebung nicht immer als "paranoid" angesehen werden kann. 3. Synthese von Plänen, die temporal-logischen Bedingungen (z.B. LTL) genügen. Hier sollen zusätzliche Anforderungen an den auszuführenden Plan geltend gemacht werden. Dazu gesellen sich die Adaption von Teilplänen, sowie die Verfeinerung von Plansuchverfahren. Eine Überraschung in diesem Projekt bildeten die durchwegs schlechten Ergebnisse aller GDL-II Planer in den Test-Wettbewerben.
Publications
- Symbolic A* Search with Pattern Databases and the Merge-and-Shrink Abstraction, 20th European Conference on Artificial Intelligence (ECAI), 2012, 306-311
Stefan Edelkamp, Peter Kissmann, and Álvaro Torralba
- Action Planning & General Game Playing for Robots. RSS- Workshop Combined Robot Motion Planning and AI Planning for Practical Applications, 2013, Berlin
Stefan Edelkamp
- Transition Trees for Cost- Optimal Symbolic Planning, 23rd International Conference on Automated Planning and Scheduling (ICAPS), 2013, 206-214
Álvaro Torralba, Stefan Edelkamp, and Peter Kissmann
- Symbolic and Explicit Search Hybrid through Perfect Hash Functions - A Case Study in Connect Four. International Conference on Automated Planning and Scheduling (ICAPS) 2014, New Hampshire
Stefan Edelkamp, Peter Kissmann, Martha Rohte
