Planowanie

Każde zadanie znalezienia planu można teoretycznie rozwi _{}azać posługuj _{}ac si_{}e jedn _{}a z metod przeszukiwania przestrzeni stanów. Jest to jednak cz_{}esto niewykonalne w praktyce, ze wzgl_{}edu na skomplikowany opis stanów i wysoki współczynnik rozgał_{}ezienia.

Przykład Skonstruować plan, gwarantuj _{}acy posiadanie szklanki mleka, kilku bananów i wiertarki.

Mały fragment przestrzeni stanów dla tego zadania:

Systemy planuj _{}ace s _{}a znacznie bardziej wyrafinowane od systemów realizuj _{}acych przeszukiwanie przestrzeni stanów.

Podstawowe cechy systemów planuj _{}acych

• Wykorzystanie j_{}ezyka formalnego (na ogół logiki) do opisu przestrzeni stanów, celu i akcji. (Zwi_{}ekszenie ekspresji.)

• Konstruowanie planu metod _{}a zst_{}epuj _{}ac _{}a. Zaczynamy od planu przybliżonego, który później ulepszamy. (Zwi_{}ekszenie efektywności.)

• Wykorzystanie metody “dziel i zwyci_{}eżaj” przy konstruowaniu planu. Typowe systemy planuj _{}ace dziel _{}a cel na podcele, które próbuj _{}a kolejno zrealizować. (Zwi_{}ekszenie efektywności.)

Rachunek sytuacyjny jest bardzo eleganckim i ekspresyjnym formalizmem planuj _{}acym. Niestety, z praktycznego punktu widzenia, jest nieefektywny.

Planowanie efektywne wymaga:

(1) Użycia podzbioru logiki pierwszego rz_{}edu jako j_{}ezyka formalizacji.

(2) Użycia wyspecjalizowanych algorytmów do planowania zamiast udowadniacza twierdzeń ogólnego przeznaczenia typu metody rezolucji.

Wi_{}ekszość systemów planuj _{}acych wywodzi si_{}e z systemu STRIPS (STanford Research Institute Problem Solver, 1970).

Reprezentacja stanów, celu i akcji w systemach typu STRIPS

Stany reprezentowane s _{}a jako koniunkcja literałów nie zawieraj _{}acych zmiennych:

At(Home) ∧ ¬Have(Milk) ∧ ⋯

Cel jest dowoln _{}a koniunkcj _{}a literałów:

At(home) ∧ Have(Milk) ∧ ⋯

Formuła celu może zawierać zmienne:

At(x) ∧ Sells(x, Milk).

Zakłada si_{}e, że zmienne wyst_{}epuj _{}ace w formule celu s _{}a egzystencjalnie kwantyfikowane.

Opis akcji

• Nazwa akcji.

• Warunek wst_{}epny (precondition) – koniunkcja literałów dodatnich, które musz _{}a zachodzić, aby akcja była wykonywalna.

• Efekty akcji – Koniunkcja literałów opisuj _{}acych zmiany stanu w wyniku wykonania akcji.

Op(ACT ION : Go(there), P RECOND : At(here)∧P ath(here, there), EF F ECT : At(there) ∧ ¬At(here)).

Uwaga: Powyższy opis definiuje cał _{}a klas_{}e akcji.

Stany b_{}edziemy cz_{}esto zapisywali jako zbiory literałów.

Akcja jest stosowalna w stanie s jeśli wszystkie warunki wst_{}epne tej akcji s _{}a zawarte w s. W wyniku wykonania akcji A w stanie s otrzymujemy stan, który: (1) Zawiera wszystkie literały wyst_{}epuj _{}ace w koniunkcji efektów akcji.

(2) Zawiera wszystkie literały wyst_{}epuj _{}ace w s, za wyj _{}atkiem tych, których negacje wyst_{}epuj _{}a w koniunkcji efektów akcji.

Jeśli stan s zawiera

At(Home), P ath(Home, Supermarket), …

to akcja Go(Supermarket) jest stosowalna i w wyniku wykonania tej akcji otrzymamy:

¬At(Home), At(Supermarket), P ath(Home, Supermarket), … System planuj _{}acy może być oparty na przeszukiwaniu przestrzeni stanów lub przeszukiwaniu przestrzeni planów. To drugie rozwi _{}azanie jest efektywniejsze.

Jak reprezentować plany?

Cel: RightShoeOn ∧ LeftShoeOn.

Stan pocz _{}atkowy: T rue.

Akcje:

Op(ACTION: RightShoe, PRECOND: RightSockOn,

EFFECT: RightShoeOn).

Op(ACTION: LeftShoe, PRECOND: LeftSockOn,

EFFECT: LeftShoeOn).

Op(ACTION: RightSock, PRECOND: T rue,

EFFECT: RightSockOn).

Op(ACTION: LeftSock, PRECOND: T rue,

EFFECT: LeftSockOn).

Plan cz_{}eściowy— cz_{}eściowo uporz _{}adkowany zbiór schematów akcji.

Plan liniowy — liniowo uporz _{}adkowany zbiór schematów akcji.

Plan ukonkretniony (cz_{}eściowy, liniowy) — cz_{}eściowo (liniowo) uporz _{}adkowany zbiór akcji.

Linearyzacja planu cz_{}eściowego P — każdy plan liniowy zawieraj _{}acy dokładnie akcje (schematy akcji) planu P, zgodny z cz_{}eściowym porz _{}adkiem określonym na P.

Plan reprezentujemy jako struktur_{}e danych zawieraj _{}ac _{}a:

• Zbiór operatorów (plan steps): akcje i (lub) schematy akcji.

• Zbiór w_{}ezłów porz _{}adkuj _{}acych (ordering constraints): wyrażenia postaci S_{i} ≺ S_{j}, gdzie S_{i}, S_{j} s _{}a operatorami.

• Zbiór ograniczeń zmiennych (variable constraints): wyrażenia postaci v = x, gdzie v jest zmienn _{}a, natomiast x jest inn _{}a zmienn _{}a lub stał _{}a.

• Zbiór powi _{}azań przyczynowych (causal links): wyrażenia postaci S_{i} →^{c} S_{j}, interpretowane: operator S_{i} zapewnia warunek wst_{}epny c dla operatora S_{j}.

Plan pocz _{}atkowy: składa si_{}e z pary operatorów, Start i F inish, powi _{}azanych w_{}ezłem Start ≺ F inish. Operator Start nie posiada warunków wst_{}epnych. Efektem jego działania jest realizacja stanu pocz _{}atkowego. Warunkiem wst_{}epnym operatora F inish jest formuła celu. Efektem jego działania jest akcja pusta. Plan pocz _{}atkowy nazywany jest też planem minimalnym.

Poniżej: (a) Ogólna struktura planu pocz _{}atkowego. (b) Plan pocz _{}atkowy dla problemu zakładania butów.

Poniżej: cz_{}eściowy plan (b_{}ed _{}acy rozwi _{}azaniem problemu zakładania butów) i jego sześć linearyzacji.

Co to jest rozwi _{}azanie problemu planowania (plan końcowy)?

Plan końcowy powinien być ukonkretniony.

Dopuszczamy natomiast plany cz_{}eściowe jako rozwi _{}azanie zadania planowania, ponieważ:

1. Plan cz_{}eściowy może posiadać wiele linearyzacji. Nie widać powodu, dlaczego system planuj _{}acy miałby wybrać jedn _{}a z nich jako rozwi _{}azanie.

2. Plan cz_{}eściowy może być wykonany w trybie równoległym.

3. Plan cz_{}eściowy można w naturalny sposób wykorzystać jako “podplan” przy rozwi _{}azywaniu wi_{}ekszego zadania.

Plan pełny – plan, w którym warunek wst_{}epny każdego operatora jest zapewniony w wyniku realizacji innego operatora. Dokładniej, dla dowolnego warunku wst_{}epnego c dowolnego operatora S_{i}, istnieje operator S_{j} taki, że:

1. S_{j} ≺ S_{i}.

2. c ∈EFFECTS (S_{j}).

3. Plan nie zawiera operatora S_{k} takiego, że ¬c∈EFFECTS (S_{k}) i S_{j} ≺ S_{k} ≺ S_{i}.

Plan poprawny – plan, w którym zarówno zbiór w_{}ezłów porz _{}adkuj _{}acych, jak i zbiór ograniczeń zmiennych s _{}a niesprzeczne.

Każdy plan pełny i poprawny jest planem końcowym, czyli rozwi _{}azaniem zadania planowania.

Konstruowanie planu

Ogólny pomysł:

(1) Zaczynamy od planu pocz _{}atkowego.

(2) W kolejnym kroku rozszerzamy plan, zapewniaj _{}ac jeden z warunków wst_{}epnych istniej _{}acego już operatora (albo poprzez dodanie nowego operatora, albo poprzez dodanie poł _{}aczenia przyczynowego biegn _{}acego od wcześniej dodanego operatora).

(3) Powtarzamy tak długo, aż otrzymamy plan końcowy lub kolejny krok jest niewykonalny.

(4) W drugim przypadku, jeśli możliwe, robimy nawrót.

Op(ACTION: Start,

EFFECT: At(Home) ∧ Sells(HW S, Drill) ∧Sells(SM, Milk)∧Sells(SM, Banana)).

Op(ACTION: F inish,

PRECOND: Have(Drill) ∧ Have(Milk) ∧Have(Banana) ∧ At(Home)).

Op(ACTION: Go(there), PRECOND: At(here), EFFECT: At(there) ∧ ¬At(here)).

Op(ACTION: Buy(x), PRECOND: At(store) ∧ Sells(store, x), EFFECT: Have(x)).

Plan pocz _{}atkowy:

Poniżej: (1) Cienkie strzałki wskazuj _{}a na porz _{}adek pomi_{}edzy operatorami. (2) Pogrubione strzałki reprezentuj _{}a poł _{}aczenia przyczynowe. (System planuj _{}acy “chroni” wszystkie poł _{}aczenia przyczynowe.)

Góra: Plan zapewniaj _{}acy trzy spośród czterech warunków wst_{}epnych operatora F inish.

Dół: Plan zapewniaj _{}acy dodatkowo warunki wst_{}epne Sells w operatorach Buy.

Plan zapewniaj _{}acy warunki wst_{}epne At w operatorach Buy:

Plan zapewniaj _{}acy warunki wst_{}epne At w operatorach Go(HW S) i Go(SM) (potrzebny nawrót):

W jaki sposób system planuj _{}acy potrafi stwierdzić, że konieczny jest nawrót?

Poł _{}aczenia przyczynowe s _{}a chronione: system zapewnia, że zagrożenia (threats), czyli operatory, które mog _{}a zniszczyć zapewniony wcześniej warunek, s _{}a umieszczane przed (promocja) operatorem zapewniaj _{}acym ten warunek lub po (degradacja) operatorze wykorzystuj _{}acym ten warunek.

W naszym przypadku ani promocja, ani degradacja nie rozwi _{}azuj _{}a problemu. Dlatego system planuj _{}acy wykonuje nawrót.

Po nawrocie:

Zapewniamy warunek wst_{}epny At(x) operatora Go(SM), dodaj _{}ac nowe poł _{}aczenie postaci

Go(HW S) →^{At(HW S)} Go(SM). Niestety krok ten wprowadza nowe zagrożenie: agent może pójść ze sklepu z narz_{}edziami do supermarketu, nie kupuj _{}ac przedtem wiertarki. Zagrożenie to łatwo usunać, używaj _{}ac metody degradacji. Musimy jeszcze osi _{}agn _{}ać warunek wst_{}epny At(Home) operatora F inish. Wystarczy dodać operator Go(Home) i zapewnić, że wyst _{}api on po operatorach Buy(Milk) i Buy(Banana).

Rozwi _{}azanie:

159

W czytelniejszej formie:

160

Algorytm POP

(Partial-Order Planning Algorithm)

Uwagi:

• Algorytm POP jest algorytmem niedeterministycznym: instrukcja choose wybiera jedn _{}a z dopuszczalnych możliwości. Jeśli wszystkie dopuszczalne wybory zostały już dokonane, algorytm kończy działanie, nie znajduj _{}ac rozwi _{}azania.

• Instrukcja fail oznacza nawrót do ostatnio wykonywanej instrukcji choose.

• Algorytm POP jest algorytmem regresywnym: zaczyna od formuły celu i w każdym kroku próbuje osi _{}agn _{}ać jeden z warunków wst_{}epnych wprowadzonego wcześniej operatora.

• Wybór operatora S_{need} i warunku c w procedurze SELECT-SUBGOAL nie prowadzi nigdy do nawrotu (zauważmy, że procedura nie używa instrukcji choose). Powód: jeśli chcemy znaleźć rozwi _{}azanie, musimy zapewnić wszystkie warunki wst_{}epne wszystkich operatorów.

• Algorytm POP jest poprawny i pełny: każdy znaleziony plan jest rozwi _{}azaniem problemu; jeśli istnieje rozwi _{}azanie problemu, zostanie ono znalezione.

• Algorytm POP, w wersji podanej powyżej, nie jest do końca wyspecyfikowany: pomija ograniczenia zmiennych.

Cz_{}eściowo ukonkretnione operatory

Czy procedura RESOLVE-THREATS powinna traktować operator, którego efektem jest ¬At(x) jako zagrożenie dla warunku At(Home)? Jest to zagrożenie potencjalne.

Możliwy sposób rozwi _{}azania problemu zagrożeń potencjalnych:

Ignorujemy każde zagrożenie potencjalne do momentu, kiedy staje si_{}e ono zagrożeniem rzeczywistym. Procedura RESOLVE-THREATS nie rozważa operatora, którego efektem jest ¬At(x) jako zagrożenie dla At(Home). Ale: jeśli ograniczenie zmiennych x = Home zostanie dodane do planu, powyższe potencjalne zagrożenie staje si_{}e zagrożeniem rzeczywistym i musi zostać rozwi _{}azane. (Przy użyciu metody promocji lub degradacji.)

Planowanie hierarchiczne

(Hierarchical planning)

Planowanie odpowiada konstruowaniu programu. Planowanie hierarchiczne odpowiada konstruowaniu programu metod _{}a zst_{}epuj _{}ac _{}a.

Plan [Go(Supermarket), Buy(Milk), Go(home)] jest dobry dla człowieka, ale nie dla robota. Z drugiej strony, posługuj _{}ac si_{}e algorytmem POP, nie jesteśmy w stanie skonstruować planu [F orward(1m), T urnLeft(90deg), …].

Praktyczne systemy planuj _{}ace oparte s _{}a na metodzie hierarchicznej dekompozycji: Startujemy, posługuj _{}ac si_{}e operatorami wysokiego poziomu (operatory abstrakcyjne). W kolejnych krokach każdy abstrakcyjny operator zostaje zast _{}apiony swoj _{}a implementacj _{}a, tzn. planem, który go realizuje i który używa operatorów niższego poziomu. Kontynuujemy ten proces tak długo, aż otrzymany plan zawiera tylko operatory podstawowe (prymitywne).

Hierarchiczna dekompozycja:

166

Rozszerzenie j_{}ezyka

Dzielimy zbiór dopuszczalnych operatorów na operatory podstawowe i abstrakcyjne.

Dodajemy zbiór metod dekompozycyjnych. Każda metoda jest wyrażeniem postaci Decompose(o, p), gdzie o jest operatorem abstrakcyjnym, natomiast p jest planem.

Decompose(Construction, P lan(STEPS: {S_{1} :Build(F oundation),

S_{2} :Build(F rame), S_{3} :Build(Roof), S_{4} :Build(W alls), S_{5} :Build(Interior)}

ORDERINGS: {S_{1} ≺ S_{2} ≺ S_{3} ≺ S_{5},

S_{2} ≺ S_{4} ≺ S_{5}},

BINDINGS: {},

LINKS: {S_{1} ⟶^{F oundation} S_{2}, S_{2} ⟶^{F rame} S_{3},

S_{2} ⟶^{F rame} S_{4}, S_{3} ⟶^{Roof} S_{5}, S_{4} ⟶^{W alls} S_{5}})).

Plan p poprawnie implementuje operator o jeśli jest pełnym i poprawnym rozwi _{}azaniem problemu znalezienia planu z warunkami wst_{}epnymi i formuł _{}a celu operatora o. Dokładniej:

• p jest poprawny, tzn. zarówno zbiór w_{}ezłów porz _{}adkuj _{}acych, jak i zbiór ograniczeń zmiennych s _{}a niesprzeczne.

• Każdy efekt operatora o musi być zapewniony przez pewien operator planu p ( i nie może być “unieważniony” przez inny, późniejszy operator planu p).

• Każdy warunek wst_{}epny każdego operatora planu p musi być osi _{}agni_{}ety w wyniku realizacji pewnego operatora planu p lub być jednym z warunków wst_{}epnych operatora o.

Załóżmy, że wybrana została metoda Decompose(S_{nonprim}, p). Aktualny plan, P, zostaje zmodyfikowany nast_{}epuj _{}aco.

• Do zbioru operatorów planu P dodajemy wszystkie operatory planu p; usuwamy operator S_{nonprim}.

• Do zbioru ograniczeń zmiennych planu P dodajemy ograniczenia zmiennych planu p. Jeśli operacja ta prowadzi do sprzeczności, robimy nawrót.

• Zast_{}epujemy każdy w_{}ezeł porz _{}adkuj _{}acy postaci S_{a} ≺ S_{nonprim} zbiorem w_{}ezłów {S_{a} ≺ S_{m_{1}}, …, S_{a} ≺ S_{m_{i}}}, gdzie S_{m_{1}}, …, S_{m_{i}} s _{}a maksymalnymi (wzgl_{}edem relacji ≺) operatorami planu p. Każdy w_{}ezeł porz _{}adkuj _{}acy postaci S_{nonprim} ≺ S_{a} zast_{}epujemy zbiorem {S_{m_{1}} ≺ S_{a}, …, S_{m_{j}} ≺ S_{a}}, gdzie S_{m_{1}}, …, S_{m_{j}} s _{}a minimalnymi operatorami planu p. Nast_{}epnie wywołujemy procedur_{}e RESOLVE-THREADS w celu ewentualnego dodania nowych w_{}ezłów.

• Każde powi _{}azanie przyczynowe wyst_{}epuj _{}ace w P, postaci S_{i} →^{c} S_{nonprim}, zast_{}epujemy zbiorem powi _{}azań postaci S_{i} →^{c} S_{m}, gdzie S_{m} jest operatorem w p z warunkiem wst_{}epnym c i c nie jest warunkiem wst_{}epnym żadnego wcześniejszego operatora w p. Podobnie, każde powi _{}azanie postaci S_{nonprim} →^{c} S_{j}, wyst_{}epuj _{}ace w P, zast_{}epujemy zbiorem powi _{}azań postaci S_{m} →^{c} S_{j}, gdzie S_{m} jest operatorem w p z efektem c i c nie jest efektem żadnego późniejszego operatora w p.

Rozwi _{}azanie abstrakcyjne: pełny i poprawny plan zawieraj _{}acy przynajmniej jeden operator abstrakcyjny.

Rozwi _{}azanie: pełny i poprawny plan zawieraj _{}acy wył _{}acznie operatory podstawowe.

Plan P nazywamy abstrakcj _{}a planu p, jeśli p można otrzymać z P stosuj _{}ac metod_{}e dekompozycji.

Własność zst_{}epuj _{}acych rozwi _{}azań: Każde rozwi _{}azanie abstrakcyjne jest abstrakcj _{}a pewnego rozwi _{}azania.

Własność wst_{}epuj _{}acych rozwi _{}azań: Żaden sprzeczny plan abstrakcyjny nie jest abstrakcj _{}a rozwi _{}azania.

Przykład, że własność wst_{}epuj _{}acych rozwi _{}azań nie zawsze zachodzi:

Niech M = Decompose(o, p) b_{}edzie metod _{}a dekompozycyjn _{}a. Operator o’ wyst_{}epuj _{}acy w p nazywamy operatorem głównym metody M, jeśli każdy warunek wst_{}epny operatora o jest warunkiem wst_{}epnym operatora o’ i każdy warunek końcowy operatora o jest warunkiem końcowym operatora o’.

Jeśli każda metoda dekompozycyjna posiada dokładnie jeden operator główny, to zagwarantowana jest własność wst_{}epuj _{}acych rozwi _{}azań.

Planowanie warunkowe

(Conditional planning)

Agent musi radziać sobie z niekompletn _{}a informacj _{}a. Konstruuj _{}ac plan warunkowy musi brać pod uwag_{}e wszystkie możliwe sytuacje, które mog _{}a wynikn _{}ać w trakcie realizacji.

J_{}ezyk planu musi zawierać zdania warunkowe, np.

if Intact(T ire1)[Inflate(T ire1)] else [Remove(T ire1, P utOn(Spare)].

Realizuj _{}ac plan warunkowy, agent musi dokonywać obserwacji (akcje obserwacyjne – sensing actions), aby zdecydować, któr _{}a cz_{}eść planu wybrać.

Planowanie w zmieniaj _{}acym si_{}e

świecie

Dotyczy sytuacji, gdy jest wielu wykonawców działań.

Etapy:

(1) Konstruowanie planu:

(a) Plan pierwotny.

(b) Obserwacja, czy nie zaszły istotne zmiany w świecie tj. czy stan pocz _{}atkowy planu jest nadal taki, jak założony.

(c) Ewentualna rekonstrukcja planu.

(2) Wykonanie planu:

(a) Przed wykonaniem każdego operatora konieczna jest obserwcja, czy jego warunki wst_{}epne s _{}a spełnione.

(b) Ewentualna rekonstrukcja planu.