|
|
pl:dydaktyka:krr:lab_pddl [2015/06/10 08:17] msl [5 Automatyczne rozwiązywanie problemów zapisanych w PDDL] |
pl:dydaktyka:krr:lab_pddl [2019/06/27 15:50] |
====== - 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 w porównaniu do rozwiązania Prologowego z laborki "przeszukowanie grafów") | |
| |
| |