Hierarchiczna sieć zadań - Hierarchical task network
W sztucznej inteligencji , hierarchiczna sieć zadanie (HTN) planowanie to podejście do zautomatyzowanego planowania , w którym zależność między działaniami może być podana w formie sieci hierarchicznie uporządkowanych.
Problemy planowania są określane w hierarchicznym podejściu sieciowym zadań poprzez dostarczenie zestawu zadań, którymi mogą być:
- prymitywne (stan początkowy) zadania, które z grubsza odpowiadają działaniom STRIPS ;
- zadania złożone (stan pośredni), które można postrzegać jako złożone z zestawu prostszych zadań;
- Zadania celu (stan celu), które z grubsza odpowiadają celom STRIPS , ale są bardziej ogólne.
Rozwiązaniem problemu HTN jest zatem wykonywalna sekwencja prymitywnych zadań, które można uzyskać z początkowej sieci zadań, rozkładając złożone zadania na ich zestaw prostszych zadań i wstawiając ograniczenia porządkowe.
Prymitywne zadanie to czynność, która może zostać wykonana bezpośrednio, biorąc pod uwagę stan, w jakim jest wykonywana, zgodnie z jego warunkiem wstępnym. Zadanie złożone to złożone zadanie składające się z częściowo uporządkowanego zestawu dalszych zadań, które mogą być prymitywne lub abstrakcyjne. Zadanie celu to zadanie spełnienia warunku. Różnica między zadaniami prymitywnymi a innymi polega na tym, że czynności pierwotne mogą być wykonywane bezpośrednio. Zadania złożone i celowe wymagają wykonania sekwencji prymitywnych czynności; jednak zadania celu są określane na podstawie warunków, które muszą zostać spełnione, podczas gdy zadania złożone można określić tylko w kategoriach innych zadań za pośrednictwem sieci zadań opisanej poniżej.
Ograniczenia między zadaniami są wyrażane w postaci sieci zwanych (hierarchicznymi) sieciami zadaniowymi. Sieć zadań to zbiór zadań i ograniczeń między nimi. Taka sieć może służyć jako warunek wstępny wykonania innego zadania złożonego lub celu. W ten sposób można wyrazić, że dane zadanie jest wykonalne tylko wtedy, gdy zostanie wykonany zestaw innych działań (wymienionych w sieci) i są one wykonane w taki sposób, aby spełnione były zawarte w nich ograniczenia (określone przez sieć) . Szczególnym formalizmem do reprezentowania hierarchicznych sieci zadań, który był dość szeroko stosowany, jest TAEMS .
Niektóre z najbardziej znanych niezależnych od domeny systemów planowania HTN to:
- Nonlin, jeden z pierwszych systemów planowania HTN.
- SIPE-2
- O-Plan, otwarta architektura planowania
- UMCP, pierwszy sprawdzony i kompletny system planowania HTN.
- IX / I-Plan
- SHOP2, planista HTN opracowany na University of Maryland w College Park .
- PANDA, system przeznaczony do planowania hybrydowego, rozszerzenie planowania HTN opracowanego na Uniwersytecie Ulm w Niemczech.
- HTNPlan-P, planowanie HTN oparte na preferencjach .
Planowanie HTN jest ściśle bardziej wyraziste niż STRIPS , do tego stopnia, że w ogólnym przypadku jest nierozstrzygalne. Jednak wiele ograniczeń składniowych planowania HTN jest rozstrzygalnych, ze znanymi złożonościami od NP-complete do 2-EXPSPACE-complete , a niektóre problemy HTN można skutecznie wkompilować w PDDL , język podobny do STRIPS.
Zobacz też
- PASKI
- Hierarchiczny system sterowania - system kontroli ze sprzężeniem zwrotnym dobrze dostosowany do planowania HTN