--- pl:dydaktyka:krr:lab_pddl [2015/06/10 00:20]
msl [2.1 Uwagi na temat składni]
+++ pl:dydaktyka:krr:lab_pddl [2019/06/27 15:50] (aktualna)
@@ Linia 32: / Linia 32: @@
     - '':adl'' oznacza, że dana dziedzina wykracza poza STRIPS i korzysta z reprezentacji ADL
   - **opcjonalna** sekcja definiująca typy (wymaga ''typing'')
-  - sekcja z definicjami predykatów używanych do opisywania świata: (:
+  - sekcja z definicjami predykatów używanych do opisywania stanu świata (podobnie jak w Prologu): ''(:predicate (sa_polaczone ?x ?y) <predykat2> ...)''
+  - sekcja opisująca dostępne akcje: ''(:action ...)''. Każda akcja opisana jest przy użyciu:
+    - listy używanych przez akcję parametrów: '':parameters (?x ?y)
+    - listy wymagań, które muszą być spełnione, aby dana akcja mogła być wykonana: '':preconditions (<warunek>)
+    - listy efektów wykonania danej akcji: '':effects (?efekt1, ?efekt2)''
-Zadanie planowania tras przejazdu to zadanie polegające na wyznaczeniu drogi łączącej zadany punkt początkowy i pożądany punk docelowy.
+==== Ćwiczenie ====
-Zwykle dążymy do wyznaczenia trasy najkrótszej, najszybszej lub o najniższym koszcie.
+Bazując na definicji problemu świata klocków, zapisanej przy użyciu Prologu (patrz: preliminaria), proszę uzupełnić poniższy model o trzy brakujące akcje:
-Modelem zadania planowania trasy jest //poszukiwanie ścieżki w grafie//.
+<code lisp>
-Zadania planowania trasy definiowane jest jako:
+(define (domain blocksworld)
+  (:requirements :strips) 		; wymagany STRIPS
+  (:predicates (on ?x ?y) 		; klocek ?x na klocku ?y
+	       (ontable ?x)			; klocek ?x na stole
+	       (clear ?x)			; na klocku ?x nic nie lezy
+	       (handempty)			; ramie robota jest puste
+	       (holding ?x)			; ramie robota trzyma ?x
+	       )
+  (:action pick-up				; akcja "podnies ze stolu"
+	     :parameters (?block)
+	     :precondition (and (clear ?block) (ontable ?block) (handempty))
+	     :effect
+	     (and (not (ontable ?block))
+		   (not (clear ?block))
+		   (not (handempty))
+		   (holding ?block)))
+  ; akcja "poloz na stol"
+  ; akcja "poloz klocek A na klocku B"
+  ; akcja "zdejmij klocek A z klocka B"
+)
+</code>
-//P = (v_I, v_G, V, E)//
+===== - Reprezentacja instancji problemu =====
-gdzie //v_I// to zadany węzeł początkowy, //v_G// to zadany węzeł docelowy, a //V// oraz //E// definiują graf (przestrzeń poszukiwań).
+Drugi plik PDDL opisuje konkretną instancję problemu, składają się na niego:
+  - sekcja definiująca nazwę problemu: ''(define (problem <name>) ... )''
+  - sekcja opisująca, do jakiej dziedziny należy dany problem: ''(:domain <dziedzina>)''
+  - sekcja opisująca obiekty (możliwe argumenty predykatów) z danego problemu: ''(:objects a1 a2 a3 ...)''
+  - sekcja opisująca zawierająca listę faktów prawdziwych w początkowym stanie świata: ''(:init (predykat argument) ...)''
+  - sekcja opisująca oczekiwany stan świata: ''(:goal (predykat argument))''
-Rozwiązaniem zadania planowania trasy jest ciąg krawędzi //e_1, e_2,...,e_n//, taki, że:
+==== - Ćwiczenie ====
-  * //{e_1, e_2,...,e_n} ⊆ E//,
+Na podstawie poniższego przykładu:
-  * //e_1// zaczyna się węźle //v_I//,
+<code lisp>
-  * krawędź //e_i// kończy się w węźle będącym początkiem krawędzi //e_i+1//,
+(define (problem easy)
-  * krawędź //e_n// kończy się w węźle //v_G//.
+  (:domain blocksworld)
+  (:objects a b c)
+  (:init (ontable a) (ontable b) (ontable c) (clear a) (clear b) (clear c) (handempty))
+  (:goal (and (on b c) (on a b)))
+)
+</code>
-Powyższy ciąg krawędzi tworzy //ścieżkę// stanowiącą plan przejazdu.
+Proszę przepisać na PDDL dwa trudniejsze przykłady z Prologowej implementacji STRIPS (laboratorium z przeszukiwania grafów).
-Zwykle wymaga się aby każdy węzeł leżący na ścieżce przejazdu odwiedzany był tylko raz (brak cykli).
+===== - Automatyczne rozwiązywanie problemów zapisanych w PDDL =====
-Znanych jest wiele algorytmów przeszukiwania grafów, zarówno w obszarze teorii grafów, badań operacyjnych jak i sztucznej inteligencji.
+  - Proszę pobrać solver {{:pl:dydaktyka:krr:ff.zip|Fast Forward}} (więcej o solverze i jego wynikach na [[https://fai.cs.uni-saarland.de/hoffmann/ff.html|jego stronie domowej]]). Archiwum ''FF.zip'' zawiera katalog z plikami źródłowymi oraz plik binarny skompilowany na Ubunty 64bit (powinno działać na serwerze uczelnianym). W razie potrzeby kompilacja wymaga zainstalowania narzędzi [[http://dinosaur.compilertools.net/|''flex'' oraz ''bison'']] i przebiega poprzez wykonanie kolejno:
+    - ''make very clean''
+    - ''make''
+  - Proszę uruchomić wyniki prac z poprzednich ćwiczeń. Solver jest wywoływany poprzez komendę:
+    * ''./ff -o <sciezka do pliku z domena> -f <sciezka do pliku z instancja problemu>''
+  - Proszę porównać wydajność solvera do rozwiązania Prologowego z laborki "przeszukowanie grafów")
-Algorytmy z obszaru sztucznej inteligencji wyróżniają się tym, że:
+===== - Typowanie =====
-  * często korzystają z heurystyk odległościowych (np. opartych na oszacowaniu odległości Euklidesowej i wg metryki ulicznej),
-  * pozwalają na uwzględnianie dodatkowych ograniczeń, np. węzłów zabronionych,
-  * pozwalają na przeszukiwanie przestrzeni o bardzo dużych rozmiarach,
-  * pozwalają na przeszukiwanie przestrzeni zadanych niejawnie (nowe węzły lub stany pojawiają się w wyniku wywołania funkcji generującej).
+Poprzez dopisanie '':typing'' w sekcji '':requirements'' można rozszerzyć możliwości języka PDDL o dodanie typów do istniejących obiektów, czy też parametrów akcji. Można w ten sposób małym kosztem wyeliminować dużą liczbę nielegalnych akcji.
-Zapoznaj się z podstawowymi algorytmami:
+Typy definiowane są po sekcji '':requirements'' poprzez dopisanie: ''(:types nazwa1 nazwa2 ...)'' dla typów o nazwach ''nazwa1'', ''nazwa2'', etc. Następnie każdy parametr predykatu i akcji musi zostać opatrzony odpowiednią adnotacją określającą jego typ, np. ''?x - typ'' oznacza, że parametr ''?x'' musi być typu ''typ'' w danej akcji lub predykacie.
-  * [[http://pl.wikipedia.org/wiki/Przeszukiwanie_grafu|Algorytmy przeszukiwania w głąb i wszerz]],
+Podobnie w definicji instancji problemu należy wszystkie obiekty opatrzyć odpowiednimi adnotacjami (''- typ'' określającymi ich typ.
-  * [[http://pl.wikipedia.org/wiki/Algorytm_Dijkstry|Klasycznym algorytmie Dijkstry i problemem najkrótszej ścieżki]],
-Plan //dopuszczalny// to plan stanowiący rozwiązanie (ścieżka łącząca węzeł początkowy i docelowy) i ew. spełniający zadane ograniczenia (np. długości, omijania wybranych węzłów zabronionych, przechodzenia przez zadane węzły wymagające odwiedzenia, etc. Plan ten nie musi być 'najlepszy'.
+==== - Ćwiczenie ====
-Plan //optymalny// to plan najlepszy w sensie wybranego kryterium, np.
+Proszę uzupełnić pliki świata klocków o adnotacje i przetestować, czy nadal wszystko działa.
-  * plan zawierający najmniejszą liczbę węzłów,
-  * plan realizujący najkrótszą trasę,
-  * plan o najtańszej trasie przejazdu,
-  * plan pozwalający na najszybszy przejazd.
-===== - Wyszukiwanie najkrótszej ścieżki =====
+<WRAP center round tip 60%>
-  - Zapoznaj się z narzędziem [[http://home.agh.edu.pl/~kk/psi/pathfinder]]
+Czy jesteś w stanie zasymulować typowanie bez dodawania konstrukcji '':typing''? Jak można byłoby tego dokonać w Prologu?
-    * Przeczytaj instrukcje wyświetlane w lewym górnym rogu.
+</WRAP>
-    * Wypróbuj działanie dostępnych algorytmów przeszukiwania dla domyślnego problemu bez ograniczeń (bez ścian):
-      * Zaobserwuj obszar analizowany przez poszczególne algorytmy działające dla domyślnych ustawień.
-      * Zanotuj statystyki: długość znalezionej ścieżki, czas potrzebny do jej znalezienia, liczbę przeprowadzonych operacji.
-      * Warto zauważyć, że koszt przejścia do węzła powyżej, poniżej, na lewo i na prawo jest równy 1. Natomiast koszt przejścia do węzła po przekątnej wynosi 1.4.
-  - Dla algorytmów heurystycznych zdefiniuj heurystykę wpisując w pole //My heuristic// wartość "dx".
-    * Ponownie zaobserwuj działanie algorytmów i zanotuj statystyki. Czy dodanie heurystyki poprawia działanie algorytmu?
-  - Jakie są najpopularniejsze heurystyki dla wyszukiwania na płaszczyźnie?
-    * Przeczytaj [[http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#heuristics-for-grid-maps|artykuł]] i wprowadź opisane w nim heurystyki obserwując zmiany działania algorytmu (aby wykonać operację pierwiastkowania wpisz ''Math.sqrt(x)'').
-==== Zadania ====
+==== - Wieże Hanoi ====
-Przed wykonaniem zadań należy odświeżyć stronę aby przywrócić jej stan początkowy.
-**Zadanie 1**
+Mając już przetestowaną reprezentację problemu świata klocków, proszę zgeneralizować problem dodając do niego dwa dodatkowe elementy:
-  - Po wygenerowaniu siatki, naciśnij przycisk //Build test//, plansza powinna wyglądać następująco: {{ :pl:dydaktyka:ai:test-initial.png?300 |}}
+  - na stole jest ograniczona liczba miejsc, na których można położyć klocek
-  - Używając algorytmu wyszukaj najkrótszą ścieżkę, niezależnie od jego rodzaju powinna ona przebiegać następująco: {{ :pl:dydaktyka:ai:test-shortest.png?300 |}}
+  - żeby położyć klocek A na klocku B, wymagane jest, aby klocek B był większy od klocka A
-  - Zmodyfikuj heurystykę algorytmu //Best-First Search// i //A*// w taki sposób aby znaleziona ścieżka przebiegała nad dłuższą krawędziom - tak jak na poniższym rysunku: {{ :pl:dydaktyka:ai:test-wrong.png?300 |}}
+Uwagi:
+  * nie jest wymagane, aby w problemie istniał tylko jeden klocek danego rozmiaru
+  * na początku można przyjąć, ze liczba miejsc na stole jest stała i wynosi, np. 3.
+  * można również założyć, że istnieje określona liczba klocków
+  * następnie należy jednak zgeneralizować model, tak by obsługiwał różną liczbę wolnych miejsc i klocków zdefiniowaną w pliku instancji problemu
-**Zadanie 2**
+===== - Action Description Language =====
-  - Zamodeluj planszę jak na rysunku poniżej {{ :pl:dydaktyka:ai:test-l1.png?300 |}}
-  - Spróbuj wymyślić heurystykę która pozwoli na jak najszybsze znalezienie ścieżki:
-    * Przetestuj różne warianty np. "dy", "dx", "5*dx"
-    * Zanotuj najlepszy rezultat.
-    * Dlaczego algorytm tak wolno porusza się wewnątrz labiryntu?
-    * W celu lepszego zrozumienia zachowania algorytmu włącz pokazywanie wartości (kliknij "Show values"):
-      - ''f'' - oszacowania długości trasy.
-      - ''g'' - długości dotychczasowej ścieżki.
-      - ''h'' - oszacowania od punktu docelowego (heurystyki).
-  - Uruchom wyszukiwanie dwukierunkowe w we wszystkich algorytmach (zaznacz opcje "Bi-directional").
-  - Przetestuj różne heurystyki.
-  - Czy Twoja najlepsza heurystyka w wyszukiwaniu jednokierunkowym jest w którymś przypadku lepsza?
-  - Dla tego konkretnego przypadku zaproponuj najszybszy sposób wyznaczania najkrótszej ścieżki pomiędzy punktami końcowymi z wykorzystaniem przeszukiwania jednokierunkowego. \\ Spróbuj osiągnąć czas poniżej 50ms i poniżej 200 operacji :!: Jak tego dokonać :?:
+Reprezentacja STRIPS jest bardzo ograniczona i, aby rozszerzyć warunki akcji o nowe konstrukcje, należy dopisać w sekcji '':requirements''  dopisać dodatkowe wymaganie '':adl''. [[http://en.wikipedia.org/wiki/Action_description_language#Comparison_between_STRIPS_and_ADL|ADL]] różni się od STRIPS w kilku zasadniczych względach, m.in.:
+  * wspierane są warunki [[http://pl.wikipedia.org/wiki/Rachunek_predykat%C3%B3w_pierwszego_rz%C4%99du|pierwszego rzędu]] (w praktyce oznacza to dodanie kwantyfikatorów do języka): ''(forall (?x1 ?x1 ...) <warunek>) (exists (?x1 ?x2 ...) <warunek>)''
+  * warunki mogą zawierać negatywne literały: ''(not <warunek>)''
+  * warunki mogą zawierać alternatywy: ''(or <warunek1> <warunek2>)''
+  * [[http://en.wikipedia.org/wiki/Closed-world_assumption|świat jest otwarty]] (w STRIPSie, tak samo jak w Prologu [[http://en.wikipedia.org/wiki/Closed-world_assumption|świat jest zamknięty]])
-===== Problem n-puzzli =====
+==== - Ćwiczenia ====
-{{ :pl:dydaktyka:ai:2015:labs:neverhood_3puzzle.png?200|Puzzle 3x3 z niezapomnianej gry The Neverhood Chronicles}} Opisane w poprzednich sekcjach algorytmy nie są ograniczone jedynie do dziedziny planowania tras przejazdu. W ogólnym przypadku pozwalają na znajdywania najkrótszych ścieżek w dowolnych¹ grafach, które dzięki abstrakcyjnej strukturze mogą modelować wiele problemów, będących obiektami zainteresowania sztucznej inteligencji. Sztandarowym przykładem może być tutaj problem n-puzzli, czyli popularna zagadka-układanka, w której należy odtworzyć zadany wzorzec poprzez przesuwanie puzzli zamkniętych w kwadratowej ramce. Jeżeli ktoś nigdy nie grał, to może spróbować [[http://mypuzzle.org/sliding|na tej stronie]] lub w przypadku braku wtyczki Flash [[http://pdanis.github.io/angular-puzzle/#/sliding-puzzle|tutaj]].
+  - w definicji dziedziny świata klocków należy przy pomocy nowych konstrukcji wyeliminować ''clear''.
-Z punktu widzenia informatyki rozwiązaniem problemu n-puzzli jest skończony ciąg ruchów //[m_1, m_2, ..., m_k]//, których wykonanie w danej kolejności pozwoliłoby na przejście z zadanego stanu początkowego //S// do stanu końcowego //G//.
-¹oczywiście, istnieją pewne ograniczenia, np. nie może istnieć w grafie cykl o ujemnej sumie wag należących do niego krawędzi. W takim wypadku dla pewnych wierzchołków najkrótsza ścieżka nie istnieje. W problemie znajdywania najkrótszej trasy na mapie sytuacja taka w oczywisty sposób nie występuje.
-==== Reprezentacja grafowa ====
-Problem n-puzzli w prosty sposób daje się przedstawić w postaci problemu znajdowania najkrótszej ścieżki w nieskierowanym grafie:
-  - Za wierzchołki grafu należy przyjąć wszystkie możliwe kombinacje puzzli na planszy.
-  - Między wierzchołkami grafu //v_1// i //v_2// istnieje krawędź wtedy i tylko wtedy, gdy istnieje pojedynczy ruch, który pozwala na przejście między tymi stanami.
-Przy takim kodowaniu problemu, do jego rozwiązania może zostać użyty dowolny z algorytmów zaprezentowanych w poprzednich zadaniach.
-==== Zadania ====
-  - Oszacuj liczbę wierzchołków w grafie reprezentującym puzzle 5x5. Następnie odpowiedz na poniższe pytania:
-    - Czy taki graf zmieści się w pamięci współczesnego komputera (załóż, że jeden wierzchołek zajmuje w pamięci 32 bity, zignoruj krawędzie)?
-    - Czy graf musi być w całości wygenerowany przed przystąpieniem do szukania rozwiązania?
-  - Zapoznaj się z narzędziem http://home.agh.edu.pl/~kk/psi/npuzzles:
-    - Przeczytaj opis problemu i instrukcję obsługi.
-    - Użyj narzędzia w trybie "//single-step//" na domyślnych stanach początkowych i końcowych.
-      * Wypróbuj różne algorytmy i heurystyki, zapisz liczbę odwiedzonych przez nie wierzchołków.
-      * Czym różni się heurystyka "//Tiles Out-of-place//" od heurystyki "//Manhattan Distance//"? Możesz spróbować zaobserwować różnice na inaczej zdefiniowanych stanach początkowych/końcowych.
-    - Powtórz eksperyment {{:pl:dydaktyka:ai:2015:labs:3x3puzzle.png?linkonly|po zamienieniu 1 z 2 w domyślnym stanie początkowym}}. Następnie odpowiedz na następujące pytania:
-      * Czy algorytm jest w stanie znaleźć rozwiązanie?
-      * Jaka jest przyczyna zaobserwowanego stanu rzeczy?
-        * //Podpowiedź 1//: Czy zmiana w {{:pl:dydaktyka:ai:2015:labs:3x3puzzle_problem2.png?linkonly|stanie końcowym (zamiana 2 z 8)}} zmienia sytuację?
-        * //Podpowiedź 2//: Dowiedz się, czym są, a czym nie są [[http://pl.wikipedia.org/wiki/Graf_sp%C3%B3jny|grafy spójne]].
-===== Świat klocków =====
-{{ :pl:dydaktyka:ai:2015:labs:blokken.png?direct&300|Przykładowy problem ze świata bloków.}} Kolejnym problemem, który może zostać zamodelowany przy użyciu grafu jest, tzw. świat klocków. Problem jest pozornie mało ambitny: polega na znalezieniu odpowiedniej sekwencji ruchów, pozwalających na przestawienie klocków ze stanu początkowego do zadanego stanu końcowego. W świecie klocków istnieje określona liczba klocków (tradycyjnie każdy klocek wyróżnia narysowana na nim literka) oraz kilka kolumn, w których te klocki mogą leżeć. Każdy klocek leży na dnie jednej z kolumn lub umieszczony jest na innym klocku. Przykładowe stany początkowy i końcowy pokazane są na obrazu powyżej. Jedyną możliwą akcją w świecie klocka jest podniesienie klocka, który jest na szczycie kolumny i położenie go na szczycie kolumnie.
-Kodowanie problemu w postaci nieskierowanego grafu działa podobnie jak w n-puzzlach: każdy wierzchołek to możliwe ustawienie klocków; każda krawędź między wierzchołkami //v_1// i //v_2// odpowiada dozwolonemu przełożeniu klocka, które stan //v_1// przekształca w stan //v_2// (i vice versa).
-==== Heurystyka ====
-Chociaż świat klocków wydaje się być dziecinny, nie funkcjonują w nim standardowe heurystyki napotkane w poprzednich sekcjach, podczas, gdy jego najtrudniejsze wersje są NP-zupełne. Przykładowa heurystyka dla problemu klocków może zostać zdefiniowana w dwóch następujących regułach:
-  - Jeżeli klocek leży nie w tej kolumnie, w której powinien (w stanie docelowym), należy dodać 1 do wartości heurystyki --- intuicyjnie: z pewnością konieczne będzie chociaż jedno przełożenie tego klocka
-  - Jeżeli klocek leży w dobrej kolumnie, ale struktura klocków pod nim nie zgadza się ze stanem docelowym, należy dodać 2 do heurystyki --- intuicyjnie: z pewnością trzeba będzie ten klocek przełożyć na inną kolumnę, by potem go przełożyć z powrotem na dobrą kolumnę.
-**Te dwie reguły są sprawdzane i wykonywane dla każdego klocka osobno.**
-==== Zadania ====
-  - Pobierz i rozpakuj {{:pl:dydaktyka:ai:blocks.zip|narzędzie aispace search z przykładowym grafem blocks.xml}}
-  - Uruchom rozpakowany applet (narzędzie jest proste, w razie czego tu jest [[http://aispace.org/search/help/index.shtml|instrukcja obsługi]])
-  - Otwórz w narzędziu załączony graf ''blocks.xml''.
-  - Dokończ budowę grafu:
-    - Dodaj wierzchołki dla pozostałych stanów świata klocków:
-      * Podpowiedź: Etykieta węzła opisuje stan 3-kolumnowego, 2-klockowego świata, np. "''|ab| | |''" oznacza, że w pierwszej kolumnie klocek "//a//" leży na klocku "//b//", a pozostałe kolumny są puste.
-    - W każdym wierzchołku wpisz ręcznie wartość heurystyki wyliczonej według dwóch reguł podanych powyżej (dla stanu początkowego została już policzona).
-    - Dodaj krawędzie między odpowiednimi stanami.
-      * Podpowiedź: Graf dla świata klocków powinien być nieskierowany. Krawędź nieskierowaną można symulować dwiema krawędziami skierowanymi.
-    - Uruchom na gotowym grafie algorytm przeszukiwania i zapisz wyniki.
-===== Dla zainteresowanych =====
-Podczas tego laboratorium dotknęliśmy bardzo ważnej i wszechobecnej (przemysł, robotyka, gry komputerowe, etc.) dziedziny AI, jaką jest planowanie. Zasadniczo  planowanie polega na znalezieniu ciągu akcji (zwanego planem), który po zastosowaniu na stanie początkowym S, doprowadzi do osiągnięcia stanu docelowego G. Każda akcja posiada warunki, w których może zostać wykonana oraz skutki jej zastosowania. Planowanie jest **trudne**, o ile nie założy się odpowiednich ograniczeń na akcje, jego złożoność jest klasy[[http://en.wikipedia.org/wiki/PSPACE|PSPACE-zupełnej]]. Trzeba ponadto zauważyć, że w realnych nie zabawkowych problemach występują dodatkowe czynniki zwiększające trudność problemu:
-  * niepełna wiedza o aktualnym stanie (np. brak odpowiednich sensorów w robocie)
-  * niepewność wynikająca z zawodności akcji (niektóre akcje mogą się zwyczajnie nie powieść)
-  * wykonywanie akcji zajmuje **czas** --- plan powinien brać pod uwagę temporalny wymiar problemu
-  * mogą wydarzać się zdarzenia niezależne od agenta --- np. wypadek drogowy na drodze autonomicznego samochodu.
-Świat bloków jest jednym z najbardziej popularnych problemów/zabawek w świecie planowania.
-==== STRIPS ====
-Jednym z najbardziej znanych programów planujących jest powstały na Stanfordzie w latach 70 program STRIPS. Używana w nim reprezentacja wiedzy jest do dzisiaj podstawą większości narzędzi planujących. Przykładowa struktura problemu może być zdefiniowana następująca:
-  * na stan składa się z listy zachodzących w nim faktów
-  * akcja jest zdefiniowana jako czwórka:
-    - nazwa akcji plus jej argumenty
-    - warunki: lista faktów, które muszą zachodzić, aby akcja była wykonalna
-    - fakty dodawane: lista faktów, które stają się prawdziwe po wykonaniu akcji
-    - fakty usuwane: lista faktów, które przestają być prawdziwe po wykonaniu akcji
-Mając taką reprezentację wiedzy, klasyczny program planujący działa według bardzo prostego wzorca (dla zadanego stanu końcowego G i początkowego S):
-  - Sprawdź, czy aktualny stan jest stanem końcowym. Jeżeli tak, wypisz znaleziony plan.
-  - Znajdź fakt F, który jest prawdziwy w stanie końcowym, ale nie jest prawdziwy aktualnym stanie.
-  - Znajdź akcję A, którą na liście faktów dodawanych F.
-  - Uruchom rekurencyjnie rutynę planującą, aby znaleźć plan doprowadzający do stanu, który spełnia warunki wykonania akcji A.
-  - Wykonaj akcję A i zaktualizuj aktualny stan do stanu S'.
-  - Uruchom rutynę planującą zaczynając od nowego stanu S'.
-Efektem powyższej procedury będzie "odwrócony plan", aby miał sens, należy go wypisać idąc od końca. Drugi haczyk polega na unikaniu zapętlenia w planowaniu - jeżeli chcemy osiągnąć warunki wykonania akcji A (punt 4.) należy wyłączyć ją z procesu planowania.
-Poniższy  kod jest jego prostą implementacją STRIPS w języku Prolog:
-<code prolog | STRIPS regression planner>
-% Strips as a regression planner.
-% Top-level interface.
-strips(InitState, GoalList, Plan) :-
-	strips1(InitState, GoalList, [], [], _, RevPlan),
-	reverse(RevPlan, Plan).
-% Base case: All goals satisfied in State.
-strips1(State, GoalList, Plan, _, State, Plan) :-
- subset(GoalList, State).
-% Plan
-strips1(State, GoalList, Plan, BadActions, NewState, NewPlan) :-
-	member(Goal, GoalList),
-	not(member(Goal, State)),    % Find unsatisfied goal.
-	write('\nAttempting goal:  '),write(Goal),nl,
-	adds(Ac, Goal),              % Find action that achieves it.
-	write(' Choosing Action:  '),write(Ac),
-	not(member(Ac, BadActions)), % Do not repeat actions (dangerous).
-	write(' -- not a bad action.'),nl,
-	preclist(Ac, PrecList),      % Find preconds and achieve them.
-	strips1(State, PrecList, Plan, [Ac|BadActions], TmpState1, TmpPlan1),
-	apply_rule(Ac, TmpState1, TmpState2),  % Recurse w/new state and goals.
-	strips1(TmpState2,GoalList,[Ac|TmpPlan1],BadActions,NewState,NewPlan).
-% Apply Rule
-apply_rule(Ac, State, NewState) :-
-	write('\nSimulating '),write(Ac),nl,
-	write('From: '), write(State), write('\n----> '),
-	dellist(Ac, DelList),                     % find deleted props
-	subtract(State, DelList, TmpState),       % remove deleted props
-	addlist(Ac, AddList),                     % find added props
-	union(AddList, TmpState, NewState),       % add props to old state
-	write(NewState).
-% Utilities
-preclist(Action, Plist) :- strips_rule(Action, Plist, _, _).
-prec(Action, Cond) :- preclist(Action, Plist), member(Cond, Plist).
-addlist(Action, Alist) :- strips_rule(Action, _, Alist, _).
-adds(Action, Cond) :- addlist(Action, Alist), member(Cond, Alist).
-dellist(Action, Dlist) :- strips_rule(Action, _, _, Dlist).
-dels(Action, Cond) :- dellist(Action, Dlist), member(Cond, Dlist).
-% Pretty-print Init, Goal, and Plan.
-plan(InitState, Goal) :-
-	strips(InitState,Goal,Plan),
-	write('\n\nInit: '), write(InitState),nl,
-	write('Goal: '),write(Goal),nl,
-	write('Plan:\n'),
-        writeplan(Plan),nl.
-% Pretty-print the plan.
-writeplan([]).
-writeplan([A|B]):-
-  write('       '),write(A),nl,
-  writeplan(B).
-</code>
-==== Zadania ====
-  - Należy pobrać {{:pl:dydaktyka:ai:2015:labs:strips_planner.pl|kod programu planującego}} i uzupełnić go o informacje potrzebne do rozwiązania problemu bloków (sekcje ''%TODO:''). Objaśnienia:
-    - dla wygody planowania możemy pominąć numery kolumn, a stan może być reprezentowane przez pięć typów faktów (przykładowe stany można zobaczyć w sekcji ''EXAMPLES OF USAGE''):
-      - ''ontable/1'' --- dany klocek leży na stole, np. ''ontable(a)''
-      - ''on/2'' --- dany klocek leży na drugim klocku, np. ''on(a,b)''
-      - ''clear/1'' --- na danym klocku nic nie leży, np. ''clear(a)''
-      - ''holding/1'' --- dany klocek został właśnie podniesiony, np. ''holding(a)''
-      - ''handempty/0'' --- żaden klocek nie jest aktualnie podniesiony, czyli: ''handempty''
-    - potrzebne są cztery rodzaje akcji (jedna z nich już jest zaimplementowana)
-      - połóż klocek ''X'' na klocku ''Y'': wykonalna, o ile klocek ''X'' jest aktualnie trzymany, a ''Y'' jest czysty. Po wykonaniu akcji klocek ''X'' leży na klocku ''Y'' i jest czysty, klocek ''Y'' przestaje być czysty i żaden klocek nie jest aktualnie podniesiony.
-      - zdejmij klocek ''X'' z klocka ''Y'': wykonalna, o ile klocek ''X'' jest czysty i aktualnie leży na klocku ''Y''. Po wykonaniu akcji klocek ''X'' przestaje być czysty, przestaje leżeć na klocku ''Y'' i zostaje podniesiony. Klocek ''Y'' natomiast staje się czysty.
-      - połóż klocek ''X'' na stole: analogicznie do akcji pierwszej z taką różnicą, że nie ma wymagań i zmian względem ''Y''
-      - zdejmij klocek ''X'' ze stołu: analogicznie do akcji drugiej
-  - Proszę uruchomić planowanie dla trzech załączonych przykładów oraz dla jednej zamodelowanego samodzielnie.
-  - Proszę usunąć z części warunkowej akcji wszystkie warunki o postaci ''clear/1'' i ponownie uruchomić planowanie dla czterech przypadków.
-    - jaką wartość mają tak wygenerowane plany?
-    - przeczytać pobieżnie [[http://en.wikipedia.org/wiki/Relaxation_%28approximation%29|stronę wikipedii na temat relaksacji]].

pl/dydaktyka/krr/lab_pddl.1433888418.txt.gz · ostatnio zmienione: 2019/06/27 15:52 (edycja zewnętrzna)

Pokaż stronę Poprzednie wersje

Menadżer multimediów Do góry

AIwiki

Menu

Dla Studentów

Old specialized AI courses

SMaDA/SMaIDA/AIDA

Informatyka (EAIiIB)

Studia Dr

Inne materialy dydaktyczne

Archiwum

Dyplomanci

Geist Season of Code

HeKatE

Public

Różnice