Hierarchische Aufgabennetzwerk-Planung

Die hierarchische Aufgabennetzwerk-Planung (HTN-Planung) löst Probleme, indem sie übergeordnete Aufgaben rekursiv in Unteraufgaben zerlegt, wobei eine Methodenbibliothek verwendet wird, anstatt direkt über primitive Aktionen zu suchen, um einen Zielzustand zu erreichen.

Definition

Die HTN-Planung stellt ein Problem als ein anfängliches Netzwerk von auszuführenden Aufgaben und eine Reihe von Methoden zur Zerlegung zusammengesetzter Aufgaben in Unteraufgaben dar; eine Lösung ist eine Zerlegung in primitive, ausführbare Aktionen, die die Einschränkungen der Methoden berücksichtigt.

Scope

Dieses Thema behandelt das HTN-Planungsparadigma: Aufgaben (primitiv und zusammengesetzt), Methoden, die festlegen, wie eine zusammengesetzte Aufgabe in Unteraufgaben zerlegt wird, und den Planungsprozess, der ein anfängliches Aufgabennetzwerk verfeinert, bis nur noch ausführbare primitive Aktionen übrig bleiben. Es befasst sich mit der Ausdrucksstärke und Komplexität der HTN-Planung im Vergleich zur klassischen Planung und mit bemerkenswerten HTN-Planern. Das klassische, zielzustandsbasierte Planungsmodell wird in den verwandten Themen behandelt; die HTN-Planung kodiert stattdessen prozedurales Domänenwissen.

Core questions

• Wie kodieren Methoden Domänenwissen darüber, wie zusammengesetzte Aufgaben zu erledigen sind?
• Wie unterscheidet sich die Aufgabenzerlegung von der Suche nach einem Zielzustand in der klassischen Planung?
• Was ist die Ausdrucksstärke und rechnerische Komplexität der HTN-Planung im Vergleich zur klassischen Planung?
• Wie werden Ordnungs- und Vorbedingungsbeschränkungen zwischen Unteraufgaben während der Zerlegung gehandhabt?

Key concepts

• primitive und zusammengesetzte Aufgaben
• Methoden und Zerlegung
• Aufgabennetzwerke
• Ordnungsbeschränkungen
• prozedurales Domänenwissen
• HTN-Ausdrucksstärke
• geordnete Aufgabenzerlegung
• SHOP2

Key theories

Aufgabenzerlegung mit Methoden

Die HTN-Planung ersetzt die zielgerichtete Suche durch rekursive Zerlegung: Zusammengesetzte Aufgaben werden über Methoden in Netzwerke von Unteraufgaben erweitert, bis alle Aufgaben primitiv sind, wodurch menschliches Fachwissen über die Ausführung von Aufgaben direkt kodiert werden kann.

Ausdrucksstärke und Komplexität der HTN-Planung

Die HTN-Planung ist streng ausdrucksstärker als die klassische STRIPS-Planung; in ihrer allgemeinen Form kann die Existenz eines Plans unentscheidbar sein, und eingeschränkte Formen gehören höheren Komplexitätsklassen an, was die Leistungsfähigkeit der methodenbasierten Zerlegung widerspiegelt.

Planer für geordnete Aufgabenzerlegung

Praktische HTN-Planer wie SHOP2 planen, indem sie Aufgaben in der Reihenfolge zerlegen, in der sie ausgeführt werden, was es ihnen ermöglicht, Vorbedingungen gegen vollständig bestimmte Zustände zu bewerten und reichhaltiges Domänenwissen effizient zu integrieren.

Clinical relevance

Die HTN-Planung wird häufig dort eingesetzt, wo Expertenverfahren bekannt sind und befolgt werden müssen, wie z z.B. bei der Planung von Fertigungsprozessen, militärischen und logistischen Operationen, der Komposition von Webdiensten sowie der Generierung von Spielen und Geschichten, da Methoden es Domänenexperten ermöglichen, Standardwege zur Erledigung von Aufgaben zu kodieren.

History

Die hierarchische Planung geht auf Sacerdotis NOAH und Abstraktionshierarchien in den 1970er Jahren zurück. Erol, Hendler und Nau formalisierten die HTN-Planung und analysierten ihre Komplexität in den frühen 1990er Jahren, und die Planer SHOP und SHOP2 (um 2000-2003) machten die geordnete HTN-Planung zu einer praktischen und weit verbreiteten Technologie.

Key figures

• Dana Nau
• Kutluhan Erol
• James Hendler
• Earl D. Sacerdoti
• Austin Tate

Seminal works

• erol1994
• nau2003

Frequently asked questions

Wie unterscheidet sich die HTN-Planung von der klassischen Planung?

Die klassische Planung sucht nach einer beliebigen Aktionssequenz, die einen Zielzustand erreicht, wobei nur die Vorbedingungen und Effekte der Aktionen verwendet werden. Die HTN-Planung beginnt stattdessen mit zu erledigenden Aufgaben und zerlegt diese mithilfe von Methoden, die kodieren, wie diese Aufgaben prozedural normalerweise ausgeführt werden, sodass sie auf reichhaltigerem Domänenwissen beruht.

Warum kann die HTN-Planung unentscheidbar sein?

Da Methoden eine zusammengesetzte Aufgabe in Netzwerke zerlegen können, die weitere zusammengesetzte Aufgaben enthalten, kann der Zerlegungsprozess unbegrenzt rekursiv sein, ähnlich wie eine Grammatik beliebig lange Ableitungen erzeugt. In ihrer allgemeinen Form ist die Entscheidung, ob eine gültige Zerlegung existiert, daher unentscheidbar.