Hierarchische Netzwerkplanung

Zusammenfassung

In vielen Bereichen der Informatik, wie Roboter-Navigation, Workflow Managenment, Mission Scheduling und Konstruktion ist Planung ein zentrales Problem. Als Planung wird der Vorgang bezeichnet, eine Aktionsfolge zu suchen, die von einem gegebenen Start- zu einem Zielzustand führt. Zur Strukturierung des Such-Raumes kann von Details abstrahiert werden, die Plan-Suche kann so gerichtet und damit effizienter erfolgen. Ein besonders ausdrucksmächtiger Ansatz zur Planung mit Abstraktion sind hierarchische Task-Netzwerke (HTN). Dabei wird ein grober, abstrakter Plan dadurch verfeinert, dass enthaltene Plan-Schritte (Tasks) durch konkretere Teil- Pläne (Task-Netzwerke) ersetzt werden. Dieser Vorgang wird als Expansion bezeichnet.

In dieser Implementierung eines HTN-Planers wurde ein neuer modifizierter Ansatz der Abstraktion verfolgt. Dabei werden nicht nur die Plan-Schritte abstrahiert, sondern auch deren Vor-und Nachbedingungen. Der Anwender hat damit mehr Freiheit bei der Beschreibung eines Planungs-Problems.

Bei der Umsetzung dieser Konzepte wurde auf besondere Flexibilität des resultierenden Systems geachtet. Dies wir u.a. durch die Verwendung verschieden starker Ordnungs-Semantiken erreicht, die bei der Anordnung der Tasks die größtmögliche Modellierungs-Freiheit lassen. Außerdem besteht die Möglichkeit, einfach alternative Planungs-Strategien umzusetzen.