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ć:

  1. prymitywne (stan początkowy) zadania, które z grubsza odpowiadają działaniom STRIPS ;
  2. zadania złożone (stan pośredni), które można postrzegać jako złożone z zestawu prostszych zadań;
  3. 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ż

Bibliografia