To jest stara wersja strony!
LAB:
Celem laboratorium jest zapoznanie się z językiem PDDL, czyli ustandaryzowaną notacją używaną do reprezentacji problemów planowania.
1 Preliminaria
Przed podejściem do tego laboratorium polecane jest wykonaniu zadań z 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.
2 Wprowadzenie
PDDL jest próbą wprowadzenie jednolitej reprezentacji wiedzy dla 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:
2.1 Uwagi na temat składni
PDDL korzysta z notacji prefiksowej inspirowanej językiem LISP (tzw. 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).
3 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:
(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"
)
4 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))
4.1 Ćwiczenie
Na podstawie poniższego przykładu:
(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)))
)
Proszę przepisać na PDDL dwa trudniejsze przykłady z Prologowej implementacji STRIPS (laboratorium z przeszukiwania grafów).
5 Automatyczne rozwiązywanie problemów zapisanych w PDDL
Proszę pobrać solver
Fast Forward (więcej o solverze i jego wynikach na
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
''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ę:
Proszę porównać wydajność solvera w porównaniu do rozwiązania Prologowego z laborki „przeszukowanie grafów”)
6 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: (:typing 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.
6.1 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