Planowanie częściowe - Partial-order planning

Planowanie w częściowej kolejności to podejście do automatycznego planowania, które utrzymuje częściową kolejność między działaniami i zatwierdza kolejność między akcjami tylko wtedy, gdy jest do tego zmuszona, to znaczy, porzą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. W przeciwieństwie do tego, planowanie całkowitego zamówienia zachowuje całkowitą kolejność 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 zamówienia 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 podróżować od początku do końca toru z przeszkodami. Ten tor przeszkód składa się z mostu, huśtawki i huśtawki. Przez most należy przejść, zanim huśtawka i huśtawka będą osiągalne. Po osiągnięciu huśtawki i huśtawki można pokonywać w dowolnej kolejności, po czym można dotrzeć do końca. W planie częściowego zamówienia kolejność między tymi przeszkodami jest określana tylko wtedy, gdy jest to konieczne. Most należy przejechać jako pierwszy. Po drugie, można pokonywać huśtawkę lub huśtawkę. Po trzecie, pozostałą przeszkodę można pokonać. Wtedy można przejść przez koniec. Efektywność planowania częściowego opiera się na zasadzie najmniejszego zaangażowania .

Plan na częściowe zamówienie

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

• Zestaw działań (zwanych również operatorami ).
• Częściowy porządek na działania. Określa warunki dotyczące kolejności niektórych działań.
• Zestaw powiązań przyczynowych . Określa, które działania spełniają które 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 zamówienia częściowego.

Aby możliwe rozkazy działań były jak najbardziej otwarte, zestaw warunków zlecenia i powiązań przyczynowych musi być jak najmniejszy.

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

Linearyzacji częściowego programu kolejność jest całkowity projekt celu otrzymane z konkretnego programu częściowego porządku; innymi słowy, oba plany porządkowe składają się z tych samych działań, przy czym kolejność 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 się rozpocząć:

• 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 liście zakupów, aż lista będzie kompletna.

Planer częściowego zamówienia

Planowanie częściowy rzędu jest algorytm lub program, który będzie skonstruowanie planu częściowy rzędu i poszukiwania rozwiązania. Dane wejściowe to 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 porządku jest przestrzeń poszukiwań. Stan początkowy byłby planem z otwartymi warunkami wstępnymi równymi warunkom docelowym. Ostatnim stanem byłby jakikolwiek plan bez otwartych warunków wstępnych, czyli rozwiązanie.

Stan początkowy jest warunkami początkowymi i można go traktować jako warunki wstępne wykonania zadania. W przypadku zadania nakrycia stołu stan początkowy może być przejrzystą tabelą. Celem jest po prostu ostatnia czynność, którą należy wykonać, na przykład nakrycie do stołu. Operatorami algorytmu są działania, dzięki którym zadanie jest realizowane. W tym przykładzie może być dwóch operatorów: położyć (obrus) i umieścić (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 się, gdy wszystkie części celu zostaną osiągnięte. W przykładowym ustawianiu tabeli istnieją dwa typy działań, którymi należy się zająć - operatorzy wystawiania i układania. Istnieją również cztery nierozwiązane operatory: Akcja 1, rozkładanie obrusu, Akcja 2, Wyrzucanie (talerze), Akcja 3, Wyrzucanie (sztućce) i Działanie 4, Wygaszanie (szklanki). Jednakże istnieje zagrożenie, które pojawia się, jeśli Akcja 2, 3 lub 4 nastąpi przed Akcją 1. Zagrożeniem tym jest to, że warunek wstępny uruchomienia algorytmu będzie niezadowalający, ponieważ tabela nie będzie już czysta. W związku z tym istnieją ograniczenia, które należy dodać do algorytmu, które wymuszają wystąpienie akcji 2, 3 i 4 po akcji 1. Po wykonaniu tych kroków algorytm zakończy się, a cel zostanie osiągnięty.

Zagrożenia

Jak widać w algorytmie przedstawiony powyżej, planowanie częściowe zamówienie może napotkać pewne zagrożenia, czyli uporządkowania , które grożą przerwie związanej działania, a tym samym potencjalnie niszcząc cały plan. Istnieją dwa sposoby rozwiązywania zagrożeń:

• Awans
• Degradacja

Promocja porządkuje ewentualne zagrożenie po połączeniu, którym grozi. Degradacja zarządza potencjalne zagrożenie przed połączeniem, które zagraża.

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

Planowanie częściowego zamówienia a planowanie całkowitego zamówienia

Planowanie w częściowym porządku jest przeciwieństwem planowania w całkowitym porządku , w którym działania są sekwencjonowane jednocześnie i dla całości bieżącego zadania. Powstaje pytanie, kiedy mamy dwa konkurujące ze sobą procesy, 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ę, korzystając z taksonomii zbiorów podcelów Korfa , w której odkryli, że planowanie częściowego porządku działa lepiej, ponieważ daje bardziej trywialne serializowanie niż planowanie całkowitego porządku . Trywialna serializowalność ułatwia planistom szybkie działanie w przypadku celów, które zawierają cele podrzędne. Planiści działają wolniej, gdy mają do czynienia z celami podrzędnymi, które są mozolnie serializowane lub nieserializowane . Czynnikiem decydującym, który sprawia, że ​​podcel jest trywialnie lub pracochłonnie możliwy do serializacji, jest przestrzeń poszukiwań różnych planów. Okazało się, że planowanie według częściowego porządku jest bardziej skuteczne w znajdowaniu najszybszej ścieżki, a zatem jest bardziej wydajnym z tych dwóch głównych typów planowania.

Anomalia Sussmana

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

Wady planowania częściowego zamówienia

Wadą tego typu systemu planowania jest to, że wymaga on 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 ważne konsekwencje dla sztucznej inteligencji . Kodując 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 kosztu energii dla robota. Twórca musi zdawać sobie sprawę z tych dwóch opcji i rozważyć je, aby zbudować wydajnego robota.

Bibliografia

• Sztuczna inteligencja: nowoczesne podejście autorstwa Stuarta Russella, Petera Norviga
• Daniel Weld - wprowadzenie do planowania najmniejszych zobowiązań
• Kambhampati, S., Knoblock, CA, Yang, Q. (1994). Planowanie jako wyszukiwanie doprecyzowujące: ujednolicone ramy oceny kompromisów projektowych w planowaniu częściowego zamówienia. Elsevier Science.
• Poole, D., Mackworth, A. (2010). Planowanie częściowego porządku w podstawach sztucznej inteligencji agentów obliczeniowych. Cambridge University Press.
• Dyer, CR „Planowanie częściowego zamówienia (rozdział 11).” (2003) CS 540. University of Wisconsin-Madison. Madison w stanie Wisconsin.
• Barrett, A., and Weld, D. (1993). Planowanie częściowego zamówienia: ocena możliwych przyrostów wydajności. University of Washington: Wydział Informatyki i Inżynierii. Uwagi .
• Simmons, Reid. (2001). „Planowanie, realizacja i uczenie się 1. Planowanie częściowego zamówienia”. Carnegie Mellon University. Pittsburgh. Uwagi.
• http://pdf.aminer.org/000/744/302/partial_order_planning_evaluating_possible_efficiency_gains.pdf
• http://pdf.aminer.org/000/037/660/decomposition_and_causality_in_partial_order_planning.pdf
• http://dl.acm.org/citation.cfm?id=1867345
• http://arxiv.org/pdf/1106.0249.pdf
• http://www.grastien.net/ban/teaching/06-planning4.pdf