Relaxation heuristics for numeric planning

Abstract

Abstract: Ein wichtiges Merkmal von intelligenten Agenten ist, das sie denken bevor sie handeln. Handlungsplanung ist das Teilgebiet der Künstlichen Intelligenz, welches sich mit dieser Art von Denken beschäftigt. Das Ergebnis eines solchen Denkprozesses ist eine Handlungsanweisung für die Schritte des Agenten. Gegeben ein durch Zustände und Aktionen beschriebenes Modell der Welt, ist ein Plan eine Sequenz von Aktionen, welche einen initialen Weltzustand in einen Zustand überführt, in welchem eine gewünschte Zielbedingung erfüllt ist.Im klassischen Planen werden die Zustände der Welt durch Variablen mit beschränktem Wertebereich beschrieben. Allerdings ist dieser Formalismus für viele reale Anwendungsbereiche nicht ausdrucksstark genug. Um etwa Ressourcen (z.B. die verbleibende Menge Benzin im Tank) oder physikalsiche Größen (z.B. die aktuelle Geschwindigkeit eines Autos) zu modellieren, werden numerische Variablen benötigt. In dieser Arbeit beschäftigen wir uns mit numerischer Handlungsplanung bei welcher Variablen auch kontinuierliche Werte zugewiesen werden können.Im Allgemeinen ist die Existenz einer Lösung eines numerischen Planungsproblems unentscheidbar. Daher untersuchen wir Näherungslösungen für numerische Planungsprobleme, welche die Kosten von bestimmten numerischen Fakten abschätzen, insbesondere solche, die zum erreichen eines Ziels benötigt werden. Im Fokus dieser Arbeit stehen hierbei Intervall-basierte Relaxiserungsheuristiken, da diese auf viele numerische Probleme angewendet werden können, insbesondere auch auf Probleme mit nicht-linearen Änderungen. Bei einigen Problemen bieten die vorgestellten Relaxierungsheuristiken eine gute Orientierungshilfe, aber selbst in Fällen bei denen die Informationsqualität schwach ist, ermöglichen Relaxierungsheuristiken eine grundlegende Orientierung für Probleme in welchen spezialisierte Lösungen nicht verfügbar sind