Planowanie częściowe

Planowanie z częściowym zamówieniem to podejście do automatycznego planowania , które utrzymuje częściowe uporządkowanie między działaniami i wprowadza uporządkowanie między działaniami tylko wtedy, gdy jest do tego zmuszone, to znaczy uporządkowanie działań jest częściowe. Również to planowanie nie określa, która akcja zostanie wykonana jako pierwsza, gdy przetwarzane są dwie akcje. Z drugiej strony, planowanie z całkowitym porządkiem utrzymuje całkowite uporządkowanie między wszystkimi działaniami na każdym etapie planowania. Biorąc pod uwagę problem, w którym do osiągnięcia celu wymagana jest pewna sekwencja działań, plan częściowego porządku określa wszystkie działania, które należy podjąć, ale określa kolejność działań tylko wtedy, gdy jest to konieczne.

Rozważ następującą sytuację: osoba musi przejść od początku do końca toru przeszkód. Ten tor przeszkód składa się z mostu, huśtawki i huśtawki. Most należy przejść, zanim huśtawka i huśtawka będą dostępne. Po dotarciu na huśtawkę i huśtawkę można przejechać w dowolnej kolejności, po czym koniec jest osiągalny. W planie częściowego zamówienia kolejność między tymi przeszkodami jest określona tylko wtedy, gdy jest to konieczne. Najpierw trzeba przejść przez most. Po drugie, można poruszać się po huśtawce lub huśtawce. Po trzecie, pozostałą przeszkodę można pokonać. Wtedy można przejść przez koniec. Planowanie częściowego zamówienia opiera się na zasadzie najmniejszego zaangażowania ze względu na swoją efektywność.

Plan częściowego zamówienia

Plan częściowego zamówienia lub plan częściowy to plan, który określa wszystkie działania, które należy podjąć, ale określa kolejność działań tylko wtedy, gdy jest to konieczne. Jest to wynikiem planowania częściowego zamówienia. Plan zamówienia częściowego składa się z czterech elementów:

Zestaw działań (znanych również jako operatory ).
Częściowy porządek działań. Określa warunki dotyczące kolejności niektórych działań.
Zestaw związków przyczynowych . Określa, które działania spełniają jakie warunki wstępne innych działań. Alternatywnie zestaw powiązań między zmiennymi w akcjach.
Zestaw otwartych warunków wstępnych . Określa, które warunki wstępne nie są spełnione przez żadne działanie w planie częściowego zamówienia.

Aby możliwe porządki działań były jak najbardziej otwarte, zbiór warunków porządku i związków przyczynowych musi być jak najmniejszy.

Plan jest rozwiązaniem, jeśli zbiór otwartych warunków wstępnych jest pusty.

Linearyzacja planu częściowego porządku jest całkowitym planem porządku wywodzącym się z konkretnego planu częściowego porządku ; innymi słowy, oba plany porządku składają się z tych samych działań, przy czym porządek w linearyzacji jest liniowym przedłużeniem porządku częściowego w pierwotnym planie porządku częściowego.

Przykład

Na przykład plan pieczenia ciasta może zaczynać się:

iść do sklepu
dostać jajka; dostać mąkę; dostać mleko
zapłacić za wszystkie towary
idź do kuchni

Jest to plan częściowy, ponieważ kolejność znajdowania jajek, mąki i mleka nie jest określona, agent może wędrować po sklepie, reaktywnie gromadząc wszystkie pozycje na swojej liście zakupów, aż lista się skompletuje.

Planer zamówień częściowych

Planer częściowego zamówienia to algorytm lub program , który konstruuje plan częściowego zamówienia i szuka rozwiązania. Wejściem jest opis problemu, składający się z opisów stanu początkowego , celu i możliwych działań .

Problem można interpretować jako problem wyszukiwania , w którym zbiorem możliwych planów częściowego rzędu jest przestrzeń poszukiwań. Stanem początkowym byłby plan z otwartymi warunkami wstępnymi równymi warunkom docelowym. Stanem końcowym byłby dowolny plan bez otwartych warunków wstępnych, tj. rozwiązanie.

Stan początkowy to warunki początkowe i można go traktować jako warunki wstępne dla danego zadania. W przypadku zadania ustawiania stołu stanem początkowym może być czysty stół. Celem jest po prostu ostateczna czynność, którą należy wykonać, na przykład nakrycie stołu. Operatorami algorytmu są akcje, dzięki którym zadanie jest realizowane. W tym przykładzie mogą istnieć dwa operatory: lay (obrus) i place (szklanki, talerze i sztućce).

Zaplanuj przestrzeń

Przestrzeń planu algorytmu jest ograniczona między jego początkiem a końcem. Algorytm rozpoczyna się, tworząc stan początkowy i kończy, gdy wszystkie części celu zostaną osiągnięte. W przykładzie ustawiania stołu należy uwzględnić dwa rodzaje działań — operatory put-out i lay. Istnieją również cztery nierozwiązane operatory: Akcja 1, nakrycie obrusu, Akcja 2, Wydanie (talerze), Akcja 3, Wydanie (sztućce) i Akcja 4, Wydanie (szklanki). Istnieje jednak zagrożenie, które pojawia się, jeśli Akcja 2, 3 lub 4 nastąpi przed Akcją 1. Zagrożenie to polega na tym, że warunek wstępny do rozpoczęcia algorytmu nie będzie spełniony, ponieważ tabela nie będzie już czysta. W związku z tym istnieją ograniczenia, które należy dodać do algorytmu, aby działania 2, 3 i 4 następowały po działaniu 1. Po wykonaniu tych kroków algorytm zakończy się, a cel zostanie osiągnięty.

Groźby

Jak widać na przedstawionym powyżej algorytmie, planowanie częściowego zamówienia może napotkać pewne zagrożenia, czyli zamówienia, które grożą przerwaniem połączonych działań, a tym samym potencjalnie zniszczeniem całego planu. Istnieją dwa sposoby rozwiązania zagrożeń:

Promocja nakazuje możliwe zagrożenie po połączeniu, które zagraża. Degradacja porządkuje możliwe zagrożenie przed połączeniem, któremu zagraża.

Algorytmy planowania częściowego rzędu są znane z tego, że są zarówno solidne, jak i kompletne, przy czym dźwięk jest definiowany jako całkowite uporządkowanie algorytmu, a kompletność jest definiowana jako zdolność do znalezienia rozwiązania, biorąc pod uwagę, że rozwiązanie faktycznie istnieje.

Planowanie częściowe a planowanie całościowe

Planowanie częściowe jest przeciwieństwem planowania całościowego, w którym działania są sekwencjonowane jednocześnie i dla całości zadania. Kiedy mamy do czynienia z dwoma konkurencyjnymi procesami, pojawia się pytanie, który z nich jest lepszy? Anthony Barret i Daniel Weld argumentowali w swojej książce z 1993 roku, że planowanie częściowego zamówienia jest lepsze od planowania całkowitego zamówienia, ponieważ jest szybsze, a przez to bardziej wydajne. Przetestowali tę teorię za pomocą taksonomii zbiorów podcelowych Korfa, w której odkryli, że planowanie częściowego rzędu działa lepiej, ponieważ zapewnia bardziej trywialną serializowalność niż planowanie całkowitego rzędu. Trywialna serializowalność ułatwia planistom szybkie działanie w przypadku celów zawierających cele podrzędne. Planiści działają wolniej, gdy mają do czynienia z mozolnie serializowalnymi lub nieseriowalnymi celami podrzędnymi. Decydującym czynnikiem, który sprawia, że podcel jest trywialnie lub mozolnie serializowany, jest przestrzeń poszukiwań różnych planów. Odkryli, że planowanie częściowego zamówienia jest bardziej biegłe w znajdowaniu najszybszej ścieżki, a zatem jest bardziej wydajne z tych dwóch głównych typów planowania.

Anomalia Sussmana

Wiadomo, że plany częściowego porządku łatwo i optymalnie rozwiązują anomalię Sussmana . Korzystanie z tego typu przyrostowego systemu planowania rozwiązuje ten problem szybko i skutecznie. Było to wynikiem planowania częściowego zamówienia, które ugruntowało swoją pozycję jako wydajnego systemu planowania.

Wady planowania częściowego zamówienia

Wadą tego typu systemu planowania jest to, że wymaga znacznie większej mocy obliczeniowej dla każdego węzła. Ten wyższy koszt na węzeł występuje, ponieważ algorytm planowania częściowego zamówienia jest bardziej złożony niż inne. Ma to istotne dla sztucznej inteligencji . Podczas kodowania robota do wykonania określonego zadania twórca musi wziąć pod uwagę, ile energii potrzebuje. Chociaż plan częściowego zamówienia może być szybszy, może nie być wart kosztów energii dla robota. Twórca musi być świadomy i rozważyć te dwie opcje, aby zbudować wydajnego robota.