Miesiąc: luty 2022

Hierarchiczny algorytm wyszukiwania w poprzedniej sekcji doprecyzowuje HLA aż do pierwotnych sekwencji akcji, aby określić, czy plan jest wykonalny. Jest to sprzeczne ze zdrowym rozsądkiem: należy być w stanie określić, że plan wysokiego poziomu z dwoma HLA

dowozi go na lotnisko bez konieczności określania dokładnej trasy, wyboru miejsca parkingowego i tak dalej. Rozwiązaniem jest napisanie warunku wstępnego – opisów efektów HLA, tak jak robimy to dla prymitywnych działań. Z opisów powinno być łatwo wykazać, że plan wysokiego poziomu osiąga cel. To jest święty Graal, że tak powiem, planowania hierarchicznego, ponieważ jeśli wyprowadzimy plan wysokiego poziomu, który udowadnia, że ​​osiąga cel, pracując w małej przestrzeni wyszukiwania działań na wysokim poziomie, możemy zaangażować się w ten plan i pracować na problem dopracowania każdego etapu planu. To daje nam wykładniczą redukcję, której szukamy. Aby to zadziałało, musi być tak, że każdy wysokopoziomowy plan, który „zapowiada” osiągnięcie celu (na mocy opisów jego kroków), w rzeczywistości osiąga cel w zdefiniowanym wcześniej sensie: musi mieć co najmniej jedna implementacja, która osiąga cel. Ta właściwość została nazwana właściwością doprecyzowania w dół opisów HLA.

Pisanie opisów HLA, które spełniają właściwość doprecyzowania w dół, jest w zasadzie łatwe: tak długo, jak opisy są prawdziwe, każdy plan wysokiego poziomu, który twierdzi, że osiąga cel, musi w rzeczywistości to zrobić – w przeciwnym razie opisy są fałszywe twierdzenie o tym, co robią HLA. Widzieliśmy już, jak pisać prawdziwe opisy dla HLA, które mają dokładnie jedną implementację; problem pojawia się, gdy HLA ma wiele implementacji. Jak opisać efekty działania, które można wdrożyć na wiele różnych sposobów? Jedną bezpieczną odpowiedzią (przynajmniej w przypadku problemów, w których wszystkie warunki wstępne i cele są pozytywne) jest uwzględnienie tylko pozytywnych efektów, które są osiągane przez każde wdrożenie HLA oraz negatywnych skutków każdego wdrożenia. Wtedy własność uszlachetniania w dół byłaby spełniona. Niestety ta semantyka dla HLA jest zbyt konserwatywna. Rozważmy ponownie HLA Go (Home, SFO), który ma dwa udoskonalenia i przypuśćmy, dla celów argumentacji, prosty świat, w którym zawsze można dojechać na lotnisko i zaparkować, ale wzięcie taksówki wymaga gotówki jako warunku wstępnego. W takim przypadku Go(Home,SFO) nie zawsze zabierze Cię na lotnisko. W szczególności nie powiedzie się, jeśli Cash jest fałszywy, a zatem nie możemy dochodzić At(Agent,SFO) jako skutek HLA. Nie ma to jednak sensu; gdyby agent nie miał gotówki, sam by się kierował. Wymaganie wstrzymania efektu dla każdej implementacji jest równoznaczne z założeniem, że ktoś inny – przeciwnik – wybierze implementację. Traktuje wiele wyników HLA dokładnie tak, jakby HLA było działaniem niedeterministycznym, jak w Sekcji 4.3. W naszym przypadku to agent sam wybierze wdrożenie. Społeczność języków programowania ukuła termin demoniczny niedeterminizm w przypadku, gdy przeciwnik dokonuje wyborów, przeciwstawiając to anielskiemu niedeterminizmowi, w którym sam agent dokonuje wyborów. Zapożyczamy ten termin, aby zdefiniować anielską semantykę opisów HLA. Podstawowym pojęciem wymaganym do zrozumienia semantyki anielskiej jest osiągalny zbiór HLA: przy danym stanie osiągalny zbiór dla HLA h , zapisany jako REACH(s,h), jest zbiorem stanów osiągalnych przez dowolną implementację HLA.

Kluczową ideą jest to, że agent może wybrać, do którego elementu osiągalnego zestawu trafi, gdy wykonuje HLA; w ten sposób HLA z wieloma udoskonaleniami jest bardziej „potężny” niż ten sam HLA z mniejszą liczbą udoskonaleń. Możemy również zdefiniować osiągalny zestaw sekwencji HLA. Na przykład, osiągalny zbiór sekwencji [h₁,h₂] jest sumą wszystkich osiągalnych zbiorów uzyskanych przez zastosowanie h₂ w każdym stanie w osiągalnym zbiorze h₁ :

Biorąc pod uwagę te definicje, plan wysokiego poziomu — sekwencja HLA — osiąga cel, jeśli jego osiągalny zestaw przecina zestaw stanów celu. (Porównaj to ze znacznie silniejszym warunkiem semantyki demonicznej, gdzie każdy element osiągalnego zbioru musi być stanem celu). I odwrotnie, jeśli osiągalny zbiór nie przecina się z celem, to plan zdecydowanie nie działa. Rysunek ilustruje te pomysły.

Pojęcie zestawów osiągalnych daje prosty algorytm: przeszukuj plany wysokopoziomowe, szukając takiego, którego zestaw osiągalny przecina cel; gdy to się stanie, algorytm może zobowiązać się do tego abstrakcyjnego planu, wiedząc, że to działa, i skupić się na dalszym udoskonalaniu planu. Do zagadnień algorytmicznych wrócimy później; na razie zastanów się, jak reprezentowane są efekty HLA – osiągalny zestaw dla każdego możliwego stanu początkowego. Prymitywne działanie może ustawić biegłość na prawdę lub fałsz lub pozostawić ją niezmienioną. (W przypadku efektów warunkowych  istnieje czwarta możliwość: odwrócenie zmiennej na jej przeciwieństwo). na którym wdrożenie jest wybrane. Oznacza to, że HLA może mieć dziewięć różnych wpływów na biegłość: jeśli zmienna zaczyna się jako prawda, zawsze może ją zachować, zamienić ją w fałsz lub mieć wybór; jeśli biegły zaczyna się od fałszu, zawsze może go fałszować, zawsze urzeczywistniać lub mieć wybór; a trzy wybory dla obu przypadków można dowolnie łączyć, co daje dziewięć. Notacyjnie jest to trochę trudne. Będziemy używać języka dodawania list i usuwania list (zamiast prawdziwej/fałszywej biegłości) wraz z symbolem oznaczającym „prawdopodobnie, jeśli agent tak zdecyduje”. Tak więc efekt oznacza „ewentualnie dodać A ”, czyli pozostawić A bez zmian lub sprawić, by było prawdziwe. Podobnie oznacza „ewentualnie usuń A ”  a oznacza „ewentualnie dodaj lub usuń A”. Na przykład HLA Go(Home,SFO) z dwoma udoskonaleniami prawdopodobnie usuwa Cash (jeśli agent zdecyduje się wziąć taksówkę), więc powinien mieć  . Widzimy zatem, że opisy HLA można wyprowadzić z opisów ich udoskonaleń. Załóżmy teraz, że mamy następujące schematy dla HLA h₁ i  h₂:

Oznacza to, że h1 dodaje A i prawdopodobnie usuwa B , podczas gdy h2 prawdopodobnie dodaje  A i ma pełną kontrolę nad C. . Teraz, jeśli tylko B jest prawdziwe w stanie początkowym, a celem jest AC, to ciąg [h1,h2] osiąga cel: wybieramy implementację h1, która sprawia, że ​​B jest fałszywe, następnie wybieramy implementację h2, która pozostawia A prawdziwe i sprawia, że ​​C jest prawdziwe.

W poprzedniej dyskusji założono, że efekty HLA — osiągalny zestaw dla dowolnego stanu początkowego — można dokładnie opisać, opisując wpływ na każdy płynny. Byłoby fajnie, gdyby tak było zawsze, ale w wielu przypadkach możemy jedynie przybliżyć efekty ponieważ HLA może mieć nieskończenie wiele implementacji i może generować arbitralnie osiągalne zbiory — podobnie jak problem z ruchomymi stanami przekonań. Powiedzieliśmy na przykład, że Go(Home,SFO) prawdopodobnie usuwa Cash; ewentualnie dodaje również At(Car,SFOlongTermParking); ale nie może zrobić obu — w rzeczywistości musi zrobić dokładnie jedno. Podobnie jak w przypadku stanów przekonań, być może będziemy musieli napisać przybliżone opisy. Użyjemy dwóch rodzajów przybliżeń: optymistyczny opis REACH⁺(s,h) HLA może zawyżać osiągalny zbiór, podczas gdy pesymistyczny opis REACH^–(s,h) może zaniżać osiągalny zbiór. Tak więc mamy

Na przykład optymistyczny opis Go(Home,SFO) mówi, że prawdopodobnie usuwa on Cash i prawdopodobnie dodaje At(Car,SFOlongTermParking). Inny dobry przykład pojawia się w łamigłówce 8, której połowa stanów jest nieosiągalna z dowolnego stanu: optymistyczny opis Act może równie dobrze obejmować całą przestrzeń stanów, ponieważ dokładny zbiór osiągalny jest dość chybotliwy.

Przy przybliżonych opisach test na to, czy plan osiąga cel, wymaga niewielkiej modyfikacji. Jeśli optymistyczny zestaw osiągalny dla planu nie przecina celu, plan nie działa; jeśli pesymistyczny zestaw osiągalny przecina cel, wtedy plan działa (rysunek (a) ). W przypadku dokładnych opisów plan albo działa, albo nie, ale w przypadku przybliżonych opisów istnieje środek pośredni: jeśli zestaw optymistyczny przecina cel, a zestaw pesymistyczny nie, wtedy nie możemy stwierdzić, czy plan działa (rysunek (b)). Kiedy ta okoliczność zaistnieje, niepewność można rozwiązać poprzez dopracowanie planu. To bardzo powszechna sytuacja w ludzkim rozumowaniu. Na przykład planując wspomniane dwutygodniowe wakacje na Hawajach, można by zaproponować spędzenie dwóch dni na każdej z siedmiu wysp. Roztropność wskazywałaby, że ten ambitny plan wymaga dopracowania poprzez dodanie szczegółów dotyczących transportu między wyspami.

Algorytm planowania hierarchicznego z przybliżonymi opisami anielskimi pokazano na rysunku wcześniejszym. Dla uproszczenia trzymaliśmy się tego samego ogólnego schematu, który zastosowano wcześniej na rysunku, to jest przeszukiwania wszerz w przestrzeni uściśleń. Jak właśnie wyjaśniono,

algorytm może wykryć plany, które zadziałają i nie będą działać, sprawdzając przecięcia optymistycznego i pesymistycznego osiągalnego zestawu z celem.

Po znalezieniu wykonalnego planu abstrakcyjnego algorytm rozkłada pierwotny problem na podproblemy, po jednym dla każdego etapu planu. Stan początkowy i cel dla każdego podproblemu uzyskuje się poprzez regresję stanu celu gwarantowanego do osiągnięcia poprzez schematy działania dla każdego etapu planu. Rysunek (b) ilustruje podstawową ideę: stan zakreślony po prawej stronie jest stanem gwarantowanym stan celu, a stan zakreślony po lewej stronie jest celem pośrednim uzyskanym przez cofnięcie celu poprzez ostatnią akcję. Zdolność do angażowania się lub odrzucania planów wysokiego poziomu może dać ANGELIC-SEARCH znaczną przewagę obliczeniową nad HIERARCHICZNYM WYSZUKIWANIEM, które z kolei może mieć dużą przewagę nad zwykłym starym PRZESZUKIWANIEM OD SZEROKOŚCI. Rozważmy na przykład posprzątanie wielkiego świata próżni składającego się z układu pomieszczeń połączonych wąskimi korytarzami, gdzie każdy pokój to prostokąt o szer. x wys. kwadratów. Rozsądne jest posiadanie HLA dla Navigate  i jednego dla CleanWholeRoom. (Sprzątanie pomieszczenia może być realizowane z wielokrotnym zastosowaniem innego HLA w celu oczyszczenia każdego rzędu.) Ponieważ istnieje pięć podstawowych czynności, koszt PRZESZUKANIA-PIERWSZEGO-SZUKANIA wzrasta do 5d , gdzie d jest długością najkrótszego rozwiązania (w przybliżeniu dwukrotność całkowitej liczby kwadratów); algorytm nie potrafi zarządzać nawet dwoma pokojami 3×3. WYSZUKIWANIE HIERARCHICZNE jest bardziej wydajne, ale nadal cierpi na wzrost wykładniczy, ponieważ próbuje wszystkich sposobów czyszczenia zgodnych z hierarchią. ANGELIC-SEARCH skaluje się w przybliżeniu liniowo pod względem liczby kwadratów – zobowiązuje do dobrej sekwencji etapów sprzątania i nawigacji na wysokim poziomie oraz odcina inne opcje. Sprzątanie zestawu pomieszczeń przez sprzątanie każdego pokoju po kolei nie jest nauką o rakietach: jest łatwe dla ludzi ze względu na hierarchiczną strukturę zadania. Kiedy rozważymy, jak trudno ludziom rozwiązać małe łamigłówki, takie jak 8-puzzle, wydaje się prawdopodobne, że ludzka zdolność rozwiązywania złożonych problemów nie wynika z rozważania kombinatoryki, ale raczej z umiejętności abstrahowania i rozkładania problemów w celu wyeliminowania kombinatoryki.

Podejście anielskie można rozszerzyć, aby znaleźć najtańsze rozwiązania poprzez uogólnienie pojęcia osiągalnego zbioru. Zamiast stanu osiągalnego lub nie, każdy stan będzie miał koszt najskuteczniejszego sposobu dotarcia do niego. (W przypadku stanów nieosiągalnych koszt jest nieskończony). Optymistyczne i pesymistyczne opisy wiązały te koszty. W ten sposób wyszukiwanie anielskie może znaleźć optymalne do udowodnienia plany abstrakcyjne bez konieczności rozważania ich realizacji. To samo podejście można zastosować do uzyskania skutecznych algorytmów hierarchicznego wyprzedzenia wyszukiwania online, w stylu LRTA* .

Pod pewnymi względami takie algorytmy odzwierciedlają aspekty ludzkich rozważań w zadaniach, takich jak planowanie wakacji na Hawajach — rozważanie alternatyw odbywa się początkowo na abstrakcyjnym poziomie w długich skalach czasowych; niektóre części planu pozostają dość abstrakcyjne do czasu wykonania, takie jak spędzenie dwóch leniwych dni na Moloka’i, podczas gdy inne części są szczegółowo zaplanowane, takie jak loty do odbycia i zakwaterowanie do zarezerwowania – bez tych ostatnich udoskonaleń, nie ma gwarancji, że plan będzie wykonalny.

Planowanie HTN jest często formułowane za pomocą pojedynczej akcji „na najwyższym poziomie” zwanej Ustawą, której celem jest znalezienie wdrożenia Ustawy, które osiąga cel. To podejście jest całkowicie ogólne. Na przykład, klasyczne problemy planowania można zdefiniować w następujący sposób: dla każdego działania prymitywnego podaj jedno udoskonalenie Działaj z krokami [ai Działaj] . Tworzy to rekurencyjną definicję Aktu, która pozwala nam dodawać działania. Ale potrzebujemy jakiegoś sposobu, aby zatrzymać rekurencję; robimy to, wprowadzając jeszcze jedno udoskonalenie dla Act, jedno z pustą listą kroków i warunkiem wstępnym równym celowi problemu. To mówi, że jeśli cel został już osiągnięty, to właściwą implementacją jest nic nie robić. Podejście prowadzi do prostego algorytmu: wielokrotnie wybieraj HLA w bieżącym planie i zastępuj go jednym z jego udoskonaleń, aż plan osiągnie cel. Jedną z możliwych implementacji opartych na przeszukiwaniu drzewa wszerz pokazano .Plany są rozpatrywane w kolejności głębokości zagnieżdżenia udoskonaleń, a nie liczby kroków pierwotnych. Łatwo jest zaprojektować wersję algorytmu do przeszukiwania wykresów, a także wersje pogłębiania w głąb i iteracyjne.

Zasadniczo ta forma wyszukiwania hierarchicznego bada przestrzeń sekwencji, które są zgodne z wiedzą zawartą w bibliotece HLA o tym, jak należy coś zrobić. Wiele wiedzy można zakodować, nie tylko w sekwencjach czynności określonych w każdym uściśleniu, ale także w warunkach wstępnych uszczegółowienia. W przypadku niektórych domen planiści HTN byli w stanie wygenerować ogromne plany przy bardzo niewielkim wyszukiwaniu. Na przykład O-PLAN (Bell and Tate, 1985), który łączy planowanie HTN z harmonogramowaniem, został wykorzystany do opracowania planów produkcyjnych dla Hitachi. Typowy problem dotyczy linii produktów składającej się z 350 różnych produktów, 35 maszyn montażowych i ponad 2000 różnych operacji. Planista generuje 30-dniowy harmonogram z trzema ośmiogodzinnymi zmianami dziennie, obejmujący dziesiątki milionów kroków. Innym ważnym aspektem planów HTN jest to, że z definicji mają strukturę hierarchiczną; zazwyczaj ułatwia to ludziom zrozumienie. Korzyści obliczeniowe wyszukiwania hierarchicznego można zobaczyć, analizując wyidealizowany przypadek. Załóżmy, że problem planowania ma rozwiązanie za pomocą prymitywnych działań. Dla niehierarchicznego planisty w przód w przestrzeni stanów z dopuszczalnymi działaniami w każdym stanie, koszt wynosi O(b^d) , jak wyjaśniono w rozdziale 3 . Dla planisty HTN załóżmy bardzo regularną strukturę udoskonalania: każde nieprymitywne działanie ma możliwe udoskonalenia, każde w działania na następnym niższym poziomie. Chcemy wiedzieć, ile jest różnych drzew udoskonaleń z tą strukturą. Teraz, jeśli istnieją działania na poziomie pierwotnym, to liczba poziomów poniżej korzenia wynosi logkd , więc liczba wewnętrznych węzłów doprecyzowania wynosi

. Każdy węzeł wewnętrzny ma możliwe udoskonalenia, więc można skonstruować r^(d-1)/(k-1) możliwych drzew dekompozycji.

Analizując ten wzór, widzimy, że utrzymywanie r małych i lk dużych może skutkować ogromnymi oszczędnościami: bierzemy k-ty pierwiastek z kosztu niehierarchicznego, jeśli b i r są porównywalne. Małe r i duże k oznaczają bibliotekę HLA z niewielką liczbą udoskonaleń, z których każde daje długą sekwencję działań. Nie zawsze jest to możliwe: długie sekwencje akcji, które można wykorzystać w szerokim zakresie problemów, są niezwykle rzadkie. Kluczem do planowania HTN jest biblioteka planów zawierająca znane metody realizacji złożonych działań na wysokim poziomie. Jednym ze sposobów budowania biblioteki jest poznanie metod na podstawie doświadczenia w rozwiązywaniu problemów. Po wyczerpującym doświadczeniu konstruowania planu od podstaw agent może zapisać plan w bibliotece jako metodę realizacji akcji wysokiego poziomu zdefiniowanej przez zadanie. W ten sposób agent może z czasem stać się coraz bardziej kompetentny, ponieważ nowe metody są budowane na bazie starych metod. Jednym z ważnych aspektów tego procesu uczenia się jest umiejętność uogólniania konstruowanych metod, eliminowania szczegółów charakterystycznych dla danego problemu (np. nazwa budowniczego lub adres działki) i zachowanie tylko kluczowych elementów planu. Wydaje nam się nie do pomyślenia, że ​​ludzie mogliby być tak kompetentni, jak oni, bez takiego mechanizmu.

Podstawowy formalizm, jaki przyjmujemy, aby zrozumieć dekompozycję hierarchiczną, pochodzi z obszaru hierarchicznych sieci zadań lub planowania HTN. Na razie zakładamy pełną obserwowalność i determinizm oraz zbiór działań, obecnie nazywanych działaniami prymitywnymi, ze standardowymi schematami warunku wstępnego – efektu. Kluczową koncepcją dodatkową jest akcja wysokiego poziomu lub HLA – na przykład akcja „Jedź na lotnisko w San Francisco”. Każdy HLA ma jedno lub więcej możliwych udoskonaleń w sekwencję działań, z których każde może być HLA lub działaniem pierwotnym. Na przykład akcja „Jedź na lotnisko w San Francisco”, reprezentowana formalnie jako Go(Home,SFO), może mieć dwa możliwe udoskonalenia, jak pokazano. Ten sam rysunek przedstawia rekurencyjne udoskonalenie nawigacji w świecie próżni: aby dotrzeć do celu, zrobić krok, a następnie udać się do celu.

Te przykłady pokazują, że działania na wysokim poziomie i ich udoskonalenia ucieleśniają wiedzę o tym, jak robić rzeczy. Na przykład udoskonalenia dla Go(Home,SFO) mówią, że aby dostać się na lotnisko, możesz jeździć samochodem lub skorzystać z usługi zamawiania przejazdu; kupowanie mleka, siadanie i przesuwanie skoczka na e4 nie są brane pod uwagę. Udoskonalenie HLA, które zawiera tylko prymitywne działania, nazywa się implementacją HLA. W świecie siatki sekwencje [Right,Right,Down] i [Down,Right,Right] implementują funkcję HLA Navigate([1,3],[3,2]). Implementacja planu wysokiego poziomu (sekwencja HLA) to połączenie implementacji każdego HLA w sekwencji. Biorąc pod uwagę definicję warunku wstępnego i skutku każdego prymitywnego działania, łatwo jest określić, czy jakakolwiek dana implementacja planu wysokiego poziomu osiąga cel. Można więc powiedzieć, że plan wysokopoziomowy osiąga cel z danego stanu, jeśli przynajmniej jedna z jego implementacji osiąga cel z tego stanu. „Przynajmniej jedna” w tej definicji jest kluczowa – nie wszystkie implementacje muszą osiągnąć cel, ponieważ agent decyduje, którą implementację wykona. Zatem zbiór możliwych wdrożeń w planowaniu HTN – z których każda może mieć inny wynik – nie jest tym samym, co zbiór możliwych wyników w planowaniu niedeterministycznym. Tam wymagaliśmy, aby plan działał dla wszystkich wyników, ponieważ agent nie może wybrać wyniku; natura to robi. Najprostszym przypadkiem jest HLA, który ma dokładnie jedną implementację. W takim przypadku możemy obliczyć warunki wstępne i efekty HLA na podstawie warunków implementacji (patrz Ćwiczenie 11.HLAU), a następnie potraktować HLA dokładnie tak, jakby było samo działaniem pierwotnym. Można wykazać, że odpowiedni zbiór HLA może skutkować spadkiem złożoności czasowej ślepego wyszukiwania z wykładniczego w głębokości rozwiązania do liniowego w głębokości rozwiązania, chociaż opracowanie takiego zbioru HLA może być samo w sobie nietrywialnym zadaniem. Gdy HLA mają wiele możliwych implementacji, istnieją dwie opcje: jedną jest wyszukiwanie wśród implementacji  dla jednego, który działa; drugim jest bezpośrednie rozumowanie na temat HLA – pomimo mnogości implementacji .Ta ostatnia metoda umożliwia wyprowadzenie poprawnych do udowodnienia planów abstrakcyjnych, bez konieczności rozważania ich realizacji.

Wszystkie metody rozwiązywania problemów i planowania opisane w poprzednich rozdziałach opierają się na ustalonym zestawie działań atomowych. Akcje można łączyć ze sobą, a najnowocześniejsze algorytmy mogą generować rozwiązania zawierające tysiące akcji. To dobrze, jeśli planujemy wakacje i działania są na poziomie „lotu z San Francisco do Honolulu”, ale na poziomie kontroli motorycznej „zegnij lewe kolano o 5 stopni” musielibyśmy połączyć miliony lub miliardy działań, a nie tysiące. Wypełnienie tej luki wymaga planowania na wyższych poziomach abstrakcji. Ogólnym planem na wakacje na Hawajach może być „Jedź na lotnisko w San Francisco; lotem HA 11 do Honolulu; robić wakacje przez dwa tygodnie; zabierz HA 12 z powrotem do San Francisco; idź do domu.” Biorąc pod uwagę taki plan, akcja „Jedź na lotnisko w San Francisco” może być postrzegana jako zadanie samo w sobie, z rozwiązaniem takim jak „Wybierz usługę wezwania na przejażdżkę; zamówić samochód; jedź na lotnisko.” Każdą z tych czynności można z kolei rozkładać dalej, aż dojdziemy do czynności sterowania motoryką niskiego poziomu, jak naciśnięcie przycisku. W tym przykładzie planowanie i działanie przeplatają się; na przykład, problem z zaplanowaniem przejścia od krawężnika do bramy zostałby odłożony do czasu porzucenia. W ten sposób ta konkretna akcja pozostanie na abstrakcyjnym poziomie przed fazą wykonania. Koncentrujemy się na idei dekompozycji hierarchicznej, idei, która przenika prawie wszystkie próby radzenia sobie ze złożonością. Na przykład złożone oprogramowanie jest tworzone z hierarchii podprogramów i klas; armie, rządy i korporacje mają hierarchię organizacyjną. Kluczową zaletą struktury hierarchicznej jest to, że na każdym poziomie hierarchii zadanie obliczeniowe, misja wojskowa lub funkcja administracyjna są zredukowane do niewielkiej liczby czynności na kolejnym niższym poziomie, więc koszt obliczeniowy znalezienia prawidłowego sposobu organizacji te działania dla obecnego problemu są niewielkie.

Zrelaksowany problem pozostawia nam uproszczony problem planowania tylko po to, aby obliczyć wartość funkcji heurystycznej. Wiele problemów z planowaniem ma 10100 stanów lub więcej, a rozluźnienie działań nie zmniejsza liczby stanów, co oznacza, że ​​obliczenie heurystyki może być nadal kosztowne. Dlatego teraz przyjrzymy się relaksacjom, które zmniejszają liczbę stanów, tworząc abstrakcję stanów – odwzorowanie wielu do jednego ze stanów w podstawowej reprezentacji problemu do abstrakcyjnej reprezentacji. Najłatwiejszą formą abstrakcji stanu jest zignorowanie niektórych biegłości. Rozważmy na przykład problem z ładunkiem lotniczym z 10 lotniskami, 50 samolotami i 200 ładunkami. Każdy samolot może znajdować się na jednym z 10 lotnisk, a każda paczka może być w jednym z samolotów lub wyładowana na jednym z lotnisk. Zatem jest 10⁵⁰ x (50 + 10)²⁰⁰ ≈ 10⁴⁰⁵ stanów. Rozważmy teraz konkretny problem w tej dziedzinie, w którym zdarza się, że wszystkie paczki znajdują się na zaledwie 5 lotniskach, a wszystkie paczki na danym lotnisku mają to samo miejsce docelowe. W takim razie przydatną abstrakcją problemu jest porzucenie wszystkich biegłych w At, z wyjątkiem tych dotyczących jednego samolotu i jednej paczki na każdym z 5 lotnisk. Teraz jest tylko 10⁵ x (5 + 10)⁵ ≈ 10¹¹ stanów.  Rozwiązanie w tej abstrakcyjnej przestrzeni stanów będzie krótsze niż rozwiązanie w oryginalnej przestrzeni (a tym samym będzie dopuszczalną heurystyką), a rozwiązanie abstrakcyjne można łatwo rozszerzyć do rozwiązania pierwotnego problemu (poprzez dodanie dodatkowych akcji Load i Unload) . Kluczową ideą definiowania heurystyk jest dekompozycja: podzielenie problemu na części, rozwiązywanie każdej części niezależnie, a następnie połączenie części. Założenie niezależności podcelu jest takie, że koszt rozwiązania koniunkcji podcelów jest aproksymowany przez sumę kosztów rozwiązania każdego podcelu niezależnie. Założenie niezależności pobocznego celu może być optymistyczne lub pesymistyczne. Optymizmem jest, gdy między planami podrzędnymi występują negatywne interakcje dla każdego celu podrzędnego – na przykład, gdy działanie w jednym planie podrzędnym usuwa cel osiągnięty w innym planie podrzędnym. Jest to pesymistyczne, a zatem niedopuszczalne, gdy podplany zawierają zbędne działania – na przykład dwa działania, które można zastąpić jednym działaniem w połączonym planie.

Reprezentacje rozkładane na czynniki pokazują, że wiele stanów to tylko warianty innych stanów. Załóżmy na przykład, że mamy tuzin bloków na stole, a celem jest umieszczenie bloku A na szczycie wieży składającej się z trzech bloków. Pierwszym krokiem do rozwiązania problemu jest umieszczenie bloku x na bloku y (gdzie x, y i A są różne). Następnie umieść A nad x i gotowe.

Jest 11 możliwości forx , a biorąc pod uwagę x , 10 wyborów dla y , a więc 110 stanów do rozważenia. Ale wszystkie te stany są symetryczne: wybór jednego z drugim nie ma znaczenia, a zatem planista powinien brać pod uwagę tylko jeden z nich. Jest to proces redukcji symetrii: wycinamy wszystkie symetryczne gałęzie drzewa poszukiwań z wyjątkiem jednej. W wielu dziedzinach stanowi to różnicę między trudnym do rozwiązania i wydajnym rozwiązywaniem. Inną możliwością jest przycinanie w przód, akceptując ryzyko, że możemy przyciąć optymalne rozwiązanie, aby skoncentrować poszukiwania na obiecujących gałęziach. Możemy zdefiniować preferowane działanie w następujący sposób: Najpierw zdefiniuj rozluźnioną wersję problemu i rozwiąż go, aby uzyskać zrelaksowany plan. Wtedy preferowane działanie jest albo etapem zrelaksowanego planu, albo spełnia pewien warunek zrelaksowanego planu. Czasami można skutecznie rozwiązać problem, uznając, że można wykluczyć negatywne interakcje. Mówimy, że problem ma szeregowalne cele cząstkowe, jeśli istnieje kolejność celów cząstkowych, w której planista może je osiągnąć w tej kolejności bez konieczności cofania któregokolwiek z wcześniej osiągniętych celów cząstkowych. Na przykład w świecie klocków, jeśli celem jest zbudowanie wieży (np. A na B , która z kolei jest na C , która z kolei jest na Stole), wtedy cele podrzędne można serializować od dołu do góry: jeśli najpierw osiągniemy C on Table, nigdy nie będziemy musieli tego cofać, gdy osiągamy inne cele podrzędne. Planista, który używa sztuczki od dołu do góry, może rozwiązać każdy problem w świecie klocków bez cofania się (chociaż nie zawsze może znaleźć najkrótszy plan). Jako inny przykład, jeśli jest pokój z n włącznikami światła, z których każdy steruje oddzielnym światłem, a celem jest włączenie ich wszystkich, to nie musimy rozważać permutacji kolejności; moglibyśmy arbitralnie ograniczyć się do planów, które przełączają przełączniki, powiedzmy, w porządku rosnącym. Dla planisty Remote Agent, który dowodził statkiem kosmicznym Deep Space One NASA, ustalono, że propozycje związane z dowodzeniem statkiem kosmicznym są serializowane. Być może nie jest to zbyt zaskakujące, ponieważ statek kosmiczny został zaprojektowany przez jego inżynierów tak, aby był jak najłatwiejszy w sterowaniu (z zastrzeżeniem innych ograniczeń). Korzystając z serializowanej kolejności celów, planista zdalnego agenta był w stanie wyeliminować większość wyszukiwań. Oznaczało to, że był wystarczająco szybki, aby kontrolować statek kosmiczny w czasie rzeczywistym, co wcześniej uważano za niemożliwe.

Ani przeszukiwanie do przodu, ani do tyłu nie jest efektywne bez dobrej funkcji heurystycznej h(s). Przypomnijmy , że funkcja heurystyczna szacuje odległość od stanu do celu i że jeśli możemy wyprowadzić dopuszczalną heurystykę dla tej odległości – taką, która nie przeszacowuje – wtedy możemy użyć wyszukiwania A* do znalezienia optymalnych rozwiązań. Z definicji nie ma sposobu na analizę stanu atomowego, a zatem wymaga pewnej pomysłowości analityka (zwykle człowieka), aby zdefiniować dobre heurystyki specyficzne dla domeny dla problemów wyszukiwania ze stanami atomowymi. Jednak planowanie wykorzystuje czynnikową reprezentację stanów i działań, co umożliwia zdefiniowanie dobrej heurystyki niezależnej od domeny. Przypomnij sobie, że dopuszczalną heurystykę można wyprowadzić definiując zrelaksowany problem, który jest łatwiejszy do rozwiązania. Dokładny koszt rozwiązania tego łatwiejszego problemu staje się wówczas heurystyką pierwotnego problemu. Problemem wyszukiwania jest graf, w którym węzły to stany, a krawędzie to działania. Problem polega na znalezieniu ścieżki łączącej stan początkowy ze stanem docelowym. Istnieją dwa główne sposoby na złagodzenie tego problemu: dodanie większej liczby krawędzi do grafu, co znacznie ułatwia znalezienie ścieżki lub grupowanie wielu węzłów razem, tworząc abstrakcję przestrzeni stanów, która ma mniej stanów , a co za tym idzie jest łatwiejsze do wyszukiwania. Najpierw przyjrzymy się heurystyce, która dodaje krawędzie do wykresu. Być może najprostsza jest heurystyka ignorowania warunków wstępnych, która usuwa wszystkie warunki wstępne z działań. Każde działanie ma zastosowanie w każdym stanie, a każdy płynny cel można osiągnąć w jednym kroku (jeśli są jakieś odpowiednie działania – jeśli nie, problem jest niemożliwy). To prawie sugeruje, że liczba kroków wymaganych do rozwiązania zrelaksowanego problemu to liczba niezaspokojonych celów – prawie, ale nie do końca, ponieważ (1) niektóre działania mogą osiągnąć wiele celów i (2) niektóre działania mogą cofnąć skutki innych. W przypadku wielu problemów dokładną heurystykę uzyskuje się poprzez rozważenie (1) i zignorowanie (2). Najpierw rozluźniamy działania, usuwając wszystkie warunki wstępne i wszystkie efekty z wyjątkiem tych, które są dosłowne w celu. Następnie liczymy minimalną liczbę wymaganych działań, aby połączenie efektów tych działań spełniało cel. To jest przykład problemu z okładką. Jest jedna drobna irytacja: problem z okładką jest NP-trudny. Na szczęście prosty algorytm zachłanny gwarantuje zwrócenie zestawu pokrycia, którego rozmiar mieści się w zakresie log n prawdziwego minimalnego pokrycia, gdzie jest liczbą literałów w celu. Niestety zachłanny algorytm traci gwarancję dopuszczalności. Możliwe jest również zignorowanie tylko wybranych warunków wstępnych akcji. Rozważ układankę z przesuwanymi płytkami (8-puzzle lub 15-puzzle) z sekcji 3.2 . Moglibyśmy zakodować to jako problem planowania dotyczący kafelków z jednym schematem Slide:

Jak widzieliśmy, jeśli usuniemy warunki wstępne  wtedy dowolny kafelek może przesunąć się w jednej akcji na dowolne pole i otrzymujemy heurystykę liczby zgubionych kafelków. Jeśli usuniemy tylko warunek wstępny Blank(s2), otrzymamy heurystykę odległości Manhattan. Łatwo zobaczyć, jak te heurystyki można wyprowadzić automatycznie z opisu schematu działania. Łatwość manipulowania schematami działania jest wielką zaletą faktoryzacji reprezentacji problemów planowania w porównaniu z atomową reprezentacją problemów wyszukiwania. Inną możliwością jest heurystyka ignorowania-usuwania-list. Załóżmy na chwilę, że wszystkie cele i warunki wstępne zawierają tylko pozytywne literały. Chcemy stworzyć rozluźnioną wersję oryginalnego problemu, która będzie łatwiejsza do rozwiązania i w której długość rozwiązania posłuży jako dobra heurystyka. Możemy to zrobić, usuwając listy usuwania ze wszystkich działań (tj. usunięcie wszystkich negatywnych literałów z efektów). Dzięki temu możliwy jest monotonny postęp w kierunku celu – żadne działanie nigdy nie cofnie postępu dokonanego przez inne działanie. Okazuje się, że nadal trudno jest znaleźć optymalne rozwiązanie tego zrelaksowanego problemu, ale przybliżone rozwiązanie można znaleźć w czasie wielomianowym poprzez wspinaczkę pod górę.

Rysunek przedstawia część przestrzeni stanów dla dwóch problemów planowania przy użyciu heurystyki ignoredelete-lists. Kropki reprezentują stany i działania krawędzi, a wysokość każdej kropki nad dolną płaszczyzną reprezentuje wartość heurystyczną. Stany na dole są rozwiązaniami. W obu tych problemach droga do celu jest szeroka. Nie ma ślepych uliczek, więc nie ma potrzeby cofania się; proste wyszukiwanie wspinaczki z łatwością znajdzie rozwiązanie tych problemów (chociaż może nie być rozwiązaniem optymalnym).

Trzy podejścia, które omówiliśmy powyżej, nie są jedynymi wypróbowanymi w 50-letniej historii zautomatyzowanego planowania. Poniżej pokrótce opiszemy kilka innych. Podejście zwane Graphplan wykorzystuje wyspecjalizowaną strukturę danych, graf planowania, do kodowania ograniczeń dotyczących tego, w jaki sposób działania są powiązane z ich warunkami wstępnymi i skutkami oraz które elementy wzajemnie się wykluczają. Rachunek sytuacyjny to metoda opisu problemów planowania w logice pierwszego rzędu. Wykorzystuje aksjomaty stanu następcy, tak jak robi to SATPLAN, ale logika pierwszego rzędu pozwala na większą elastyczność i bardziej zwięzłe aksjomaty. Ogólnie rzecz biorąc, podejście to przyczyniło się do naszego teoretycznego zrozumienia planowania, ale nie wywarło dużego wpływu na zastosowania praktyczne, być może dlatego, że programy udowadniające pierwszego rzędu nie są tak dobrze rozwinięte, jak programy spełniania propozycji. Możliwe jest zakodowanie ograniczonego problemu planowania (tj. problemu znalezienia planu długości) jako problemu spełnienia ograniczeń (CSP). Kodowanie jest podobne do kodowania problemu SAT, z jednym ważnym uproszczeniem: w każdym kroku czasowym potrzebujemy tylko jednej zmiennej Actiont, której domeną jest zbiór możliwych akcji. Nie potrzebujemy już jednej zmiennej dla każdej akcji i nie potrzebujemy aksjomatów wykluczania akcji. Wszystkie dotychczasowe podejścia konstruują całkowicie uporządkowane plany, składające się z ściśle liniowych sekwencji działań. Ale jeśli problem z ładunkiem lotniczym polega na załadowaniu 30 paczek na jeden samolot i 50 paczek na inny, wydaje się, że nie ma sensu zadekretowanie określonej liniowej kolejności 80 operacji załadunku. Alternatywa zwana planowaniem częściowego rzędu reprezentuje plan jako graf, a nie sekwencję liniową: każde działanie jest węzłem na grafie, a dla każdego warunku wstępnego działania istnieje krawędź z innego działania (lub ze stanu początkowego), która wskazuje, że poprzednie działanie ustanawia warunek wstępny. Moglibyśmy więc mieć plan kolejności częściowej, który mówi, że akcje Remove(Spare,Trunk) i Remove(Flat,Axle) muszą pojawić się przed PutOn(Spare,Axle), ale bez mówienia, która z dwóch akcji Remove powinna być pierwsza.

Poszukujemy raczej w przestrzeni planów niż państw-światów, wkładając działania, by spełnić warunki. W latach 80. i 90. planowanie częściowego porządku było postrzegane jako najlepszy sposób radzenia sobie z problemami planowania z niezależnymi podproblemami. Do 2000 roku planiści wyszukiwania w przód opracowali doskonałe heurystyki, które pozwoliły im skutecznie odkrywać niezależne podproblemy, dla których zaprojektowano planowanie częściowego rzędu. Co więcej, SATPLAN był w stanie wykorzystać prawo Moore’a: beznadziejnie duża propozycja w 1980 roku wygląda teraz na małą, ponieważ komputery mają dziś 10 000 razy więcej pamięci. W rezultacie planiści częściowych zamówień nie są konkurencyjni w przypadku w pełni zautomatyzowanych, klasycznych problemów planowania. Niemniej jednak planowanie częściowe pozostaje ważną częścią tej dziedziny. W przypadku niektórych konkretnych zadań, takich jak planowanie operacji, wybieraną technologią jest planowanie częściowego zamówienia z heurystyką specyficzną dla domeny. Wiele z tych systemów korzysta z bibliotek planów wysokiego poziomu. Planowanie częściowego porządku jest również często stosowane w dziedzinach, w których zrozumienie planów jest ważne dla ludzi. Na przykład plany operacyjne dla statków kosmicznych i łazików marsjańskich są generowane przez planistów częściowych zamówień, a następnie są sprawdzane przez operatorów przed przesłaniem ich do pojazdów w celu wykonania. Podejście do udoskonalania planu ułatwia ludziom zrozumienie, co robią algorytmy planowania i weryfikację poprawności planów przed ich wykonaniem.

Wcześniej pokazaliśmy, jak sprytne przepisanie aksjomatów może zmienić problem wumpusowego świata w problem spełnialności logiki zdań, który można by przekazać efektywnemu rozwiązywaniu spełnialności. Planery oparte na SAT, takie jak SATPLAN, działają poprzez tłumaczenie opisu problemu PDDL na formę propozycji. Tłumaczenie obejmuje szereg kroków:

* Propozycjonalizuj akcje: dla każdego schematu akcji stwórz podstawowe propozycje, podstawiając stałe dla każdej ze zmiennych. Czyli zamiast pojedynczego schematu Unload(c,p,a) mielibyśmy osobne propozycje działań dla każdej kombinacji cargo, samolotu i lotniska (tutaj zapisane z indeksami dolnymi) i dla każdego kroku czasowego (tutaj zapisanego jako indeks górny) .

* Dodaj aksjomaty wykluczenia akcji mówiące, że żadne dwie akcje nie mogą wystąpić w tym samym czasie, np.

* Dodaj aksjomaty warunków wstępnych: dla każdej akcji podstawowej A^t , dodaj aksjomat A^t => PRE(A^t) , to znaczy, jeśli akcja zostanie podjęta w czasie t , to warunki wstępne muszą być spełnione. Na przykład,  

* Zdefiniuj stan początkowy: potwierdź F⁰ dla każdego płynnego F w stanie początkowym problemu, a ¬F⁰ dla każdego płynnego nie wymienionego w stanie początkowym.

* Propositionalize celu: cel staje się alternatywą dla wszystkich jego podstawowych instancji, gdzie zmienne są zastępowane przez stałe. Na przykład cel posiadania bloku A na innym bloku, On(A,x) Ʌ   Block(x) w świecie z obiektami A,B i C zostałby zastąpiony przez cel

* Dodaj aksjomaty stanu następcy: dla każdego płynnego F dodaj aksjomat postaci

gdzie ActionCausesF oznacza alternatywę wszystkich akcji naziemnych, które dodają F , a ActionCausesNotF oznacza alternatywę wszystkich akcji naziemnych, które usuwają F. Wynikowe tłumaczenie jest zwykle znacznie większe niż oryginalne PDDL, ale jest nowoczesne pod względem wydajności nowoczesnych solwerów SAT często z nawiązką nadrabia to.

W wyszukiwaniu wstecznym (zwanym również wyszukiwaniem regresyjnym) zaczynamy od celu i stosujemy działania wstecz, aż znajdziemy sekwencję kroków, która osiągnie stan początkowy. Na każdym kroku rozważamy odpowiednie działania (w przeciwieństwie do wyszukiwania do przodu, które uwzględnia działania, które mają zastosowanie). To znacznie zmniejsza współczynnik rozgałęzień, szczególnie w domenach z wieloma możliwymi działaniami.

Odpowiednie działanie to takie, którego efekt łączy się z jednym z literałów celu, ale nie ma żadnego efektu, który neguje jakąkolwiek część celu. Na przykład dla celu ¬Poor Ʌ Famous , akcja mająca wyłącznie efekt Famous byłaby istotna, ale taka z efektem Poor Ʌ Famous nie jest uważana za istotną: nawet jeśli ta akcja może być użyta w pewnym momencie planu (w celu ustanowienia Sławy ), nie może pojawić się w tym momencie planu, ponieważ wtedy Biedny pojawiłby się w stanie końcowym. Co to znaczy zastosować akcję wstecz? Mając dany cel i działanie , regresja od początku daje nam opis stanu g’ , którego literały dodatni i ujemny są podane przez

Oznacza to, że warunki wstępne musiały być spełnione wcześniej, w przeciwnym razie akcja nie mogła zostać wykonana, ale literały dodatnie/ujemne, które zostały dodane/usunięte przez akcję, nie musiały być wcześniej prawdziwe. Te równania są proste dla literałów podstawowych, ale należy zachować ostrożność, gdy zmienne g występują w a i . Załóżmy na przykład, że celem jest dostarczenie określonej części ładunku do SFO: At(C2, SFO) . Schemat akcji Unload ma skutek At(c,a). Kiedy połączymy to z celem, otrzymujemy podstawienie ; zastosowanie tego podstawienia {c/C2 , a/SFO} do schematu daje nam nowy schemat, który oddaje ideę użycia dowolnej płaszczyzny, która jest w SFO:

Tutaj zastąpiliśmy p nową zmienną o nazwie p’ . Jest to przykład standaryzacji oddzielnych nazw zmiennych, dzięki czemu nie będzie konfliktu między różnymi zmiennymi, które mają tę samą nazwę. Opis stanu regresji daje nam nowy cel:

Jako inny przykład rozważ cel posiadania książki o określonym numerze ISBN: . Biorąc pod uwagę bilion 13-cyfrowych numerów ISBN i schemat pojedynczego działania

wyszukiwanie do przodu bez heurystyki musiałoby rozpocząć wyliczanie 10 miliardów akcji kupna gruntu. Ale przy wyszukiwaniu wstecznym ujednolicilibyśmy cel za pomocą efekt Own(i’) , dając podstawienie . Potem cofamy się nad działaniem SUBST(θ,A), aby uzyskać opis stanu poprzednika

Jest to część stanu początkowego, więc mamy rozwiązanie i gotowe, biorąc pod uwagę tylko jedno działanie, a nie bilion. Bardziej formalnie załóżmy opis celu, który zawiera literał celu g_i i schemat działania A . Jeśli A ma wpływ e^‘j literał gdzie Unify(g_i, e^‘_j) = θ i gdzie definiujemy A’ =  SUBST(θ,A). a jeśli nie ma żadnego efektu w A’, który jest negacją dosłownego in g , to A’ jest odpowiednim działaniem względem g . W przypadku większości problematycznych domen wyszukiwanie wsteczne utrzymuje współczynnik rozgałęzienia na niższym poziomie niż wyszukiwanie do przodu. Jednak fakt, że wyszukiwanie wstecz wykorzystuje stany ze zmiennymi, a nie stany podstawowe, utrudnia wymyślenie dobrej heurystyki. Jest to główny powód, dla którego większość obecnych systemów preferuje wyszukiwanie do przodu.