Różnice między wybraną wersją a wersją aktualną.
|
pl:dydaktyka:krr:lab_pddl [2017/07/17 10:08] |
pl:dydaktyka:krr:lab_pddl [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| + | ====== - LAB: ====== | ||
| + | |||
| + | Celem laboratorium jest zapoznanie się z językiem PDDL, czyli ustandaryzowaną notacją używaną do reprezentacji problemów planowania. | ||
| + | |||
| + | ===== - Preliminaria ===== | ||
| + | |||
| + | Przed podejściem do tego laboratorium polecane jest wykonaniu zadań z [[http://ai.ia.agh.edu.pl/wiki/pl:dydaktyka:ai:2015:labs:lab_search|laboratorium dotyczącego przeszukiwania grafów]]. W szczególności należy zapoznać się i wykonać ćwiczenia z sekcji dla zainteresowanych (świat klocków). Poniższe laboratorium stanowi niejako rozwinięcie przedstawionej tam problematyki. | ||
| + | |||
| + | |||
| + | ===== - Wprowadzenie ===== | ||
| + | |||
| + | PDDL jest próbą wprowadzenie jednolitej reprezentacji wiedzy dla [[http://en.wikipedia.org/wiki/Automated_planning_and_scheduling|szczególnej klasy problemów dotyczących automatycznego planowania]]. Dziedzina problemu oraz jego poszczególne instancje są oddzielone od solverów, których zadaniem jest znalezienie ciągu akcji, który doprowadziłby w danej dziedzinie z zadanego stanu początkowego do stanu końcowego. Na reprezentację problemu w PDDL składają się dwa pliki: | ||
| + | |||
| + | * plik opisujący dziedzinę | ||
| + | * plik zawierające dane dotyczące konkretnej instancji problemu | ||
| + | |||
| + | ==== - Uwagi na temat składni ==== | ||
| + | |||
| + | PDDL korzysta z notacji prefiksowej inspirowanej językiem LISP (tzw. [[http://en.wikipedia.org/wiki/S-expression|S-wyrażenia]]. W uproszczeniu: każde wyrażenie o postaci ''(f a1 a2 a3)'' należy interpretować jako ''f(a1, a2, a3)'', np. ''(= ?x (+ 3 2))'' należy interpretować jako równoważne ''5 = 3 + 2''. Element S-wyrażenia poprzedzony pytajnikiem, np. ''?x'' reprezentuje zmienną, same nawiasy natomiast jedynie grupują symbol funkcyjnego z jego argumentami. W szczególności cały program LISP-owy jest S-wyrażeniem, co przekłada się na łatwe parsowanie pliku i przetwarzanie kodu (metaprogramowanie). | ||
| + | |||
| + | |||
| + | ===== - Reprezentacja dziedziny ===== | ||
| + | |||
| + | Na plik PDDL opisujący dziedzinę problemu składają się z następujące elementy: | ||
| + | |||
| + | - sekcja definiująca nazwę dziedziny: | ||
| + | - ''(define (domain <name>) ... )'' | ||
| + | - sekcja opisująca, jakie konstrukcje są wykorzystywane w danym modelu. Pozwala to ustalić, czy dany solver jest w stanie przetworzyć opisywaną dziedzinę: ''(:requirements <wymaganie1> <wymaganie2>)''. Takimi konstrukcjami mogą być na przykład: | ||
| + | - '':typing'' pozwalające na grupowanie obiektów modelu w kategoriach typów | ||
| + | - '':equality'' pozwalające na sprawdzanie czy dwie nazwy wskazują na ten sam obiekt | ||
| + | - '':strips'' zapewnia wsparcie dla opisywania problemów na wzór reprezentacji STRIPS | ||
| + | - '':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 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)'' | ||
| + | |||
| + | ==== Ćwiczenie ==== | ||
| + | |||
| + | 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: | ||
| + | |||
| + | <code lisp> | ||
| + | |||
| + | (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> | ||
| + | |||
| + | ===== - Reprezentacja instancji problemu ===== | ||
| + | |||
| + | 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))'' | ||
| + | |||
| + | ==== - Ćwiczenie ==== | ||
| + | |||
| + | Na podstawie poniższego przykładu: | ||
| + | <code lisp> | ||
| + | (define (problem easy) | ||
| + | (: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> | ||
| + | |||
| + | Proszę przepisać na PDDL dwa trudniejsze przykłady z Prologowej implementacji STRIPS (laboratorium z przeszukiwania grafów). | ||
| + | |||
| + | ===== - Automatyczne rozwiązywanie problemów zapisanych w PDDL ===== | ||
| + | |||
| + | - 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") | ||
| + | |||
| + | ===== - Typowanie ===== | ||
| + | |||
| + | 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. | ||
| + | |||
| + | 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. | ||
| + | |||
| + | Podobnie w definicji instancji problemu należy wszystkie obiekty opatrzyć odpowiednimi adnotacjami (''- typ'' określającymi ich typ. | ||
| + | |||
| + | ==== - Ćwiczenie ==== | ||
| + | |||
| + | Proszę uzupełnić pliki świata klocków o adnotacje i przetestować, czy nadal wszystko działa. | ||
| + | |||
| + | <WRAP center round tip 60%> | ||
| + | Czy jesteś w stanie zasymulować typowanie bez dodawania konstrukcji '':typing''? Jak można byłoby tego dokonać w Prologu? | ||
| + | </WRAP> | ||
| + | |||
| + | ==== - Wieże Hanoi ==== | ||
| + | |||
| + | Mając już przetestowaną reprezentację problemu świata klocków, proszę zgeneralizować problem dodając do niego dwa dodatkowe elementy: | ||
| + | - na stole jest ograniczona liczba miejsc, na których można położyć klocek | ||
| + | - żeby położyć klocek A na klocku B, wymagane jest, aby klocek B był większy od klocka A | ||
| + | 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 | ||
| + | |||
| + | ===== - Action Description Language ===== | ||
| + | |||
| + | 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]]) | ||
| + | |||
| + | ==== - Ćwiczenia ==== | ||
| + | |||
| + | - w definicji dziedziny świata klocków należy przy pomocy nowych konstrukcji wyeliminować ''clear''. | ||
| + | | ||
