Problemy planowania w języku PDDL

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 wprowadzającego problematykę planowania. W szczególności należy zapoznać się i wykonać ćwiczenia z sekcji 'Program planujący'. Poniższe laboratorium stanowi niejako rozwinięcie przedstawionej tam problematyki i będzie nawiązywać do rozwiązywania problemu świata klocków przy użyciu planera STRIPS.

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:

  • plik opisujący dziedzinę
  • plik zawierające dane dotyczące konkretnej instancji problemu

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:

  1. sekcja definiująca nazwę dziedziny:
  2. (define (domain <name>) … )
  3. 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:
    1. :typing pozwalające na grupowanie obiektów modelu w kategoriach typów
    2. :equality pozwalające na sprawdzanie czy dwie nazwy wskazują na ten sam obiekt
    3. :strips zapewnia wsparcie dla opisywania problemów na wzór reprezentacji STRIPS
    4. :adl oznacza, że dana dziedzina wykracza poza STRIPS i korzysta z reprezentacji ADL
  4. opcjonalna sekcja definiująca typy (wymaga typing)
  5. sekcja z definicjami predykatów używanych do opisywania stanu świata (podobnie jak w Prologu): (:predicate (sa_polaczone ?x ?y) <predykat2> …)
  6. sekcja opisująca dostępne akcje: (:action …). Każda akcja opisana jest przy użyciu:
    1. 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>)
    2. 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 "postaw na stole"
  ; akcja "postaw 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:

  1. sekcja definiująca nazwę problemu: (define (problem <name>) … )
  2. sekcja opisująca, do jakiej dziedziny należy dany problem: (:domain <dziedzina>)
  3. sekcja opisująca obiekty (możliwe argumenty predykatów) z danego problemu: (:objects a1 a2 a3 …)
  4. sekcja opisująca zawierająca listę faktów prawdziwych w początkowym stanie świata: (:init (predykat argument) …)
  5. 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 - patrz: preliminaria.

5 Automatyczne rozwiązywanie problemów zapisanych w PDDL

Jeżeli używasz laptopa w sali C2 316, solver Fast Forward powinien już być zainstalowany i dodany do ścieżki PATH. Zatem wpisanie ff w konsoli powinno wystarczyć.

  1. 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 Ubuntu 64bit (powinno działać na serwerze uczelnianym). W razie potrzeby kompilacja wymaga zainstalowania narzędzi ''flex'' oraz ''bison'' i przebiega poprzez wykonanie kolejno:
    1. make veryclean
    2. make
  2. 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>
  3. Proszę porównać wydajność solvera do rozwiązania Prologowego z poprzedniego laboratorium - patrz: preliminaria.

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: (: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.

6.1 Ćwiczenie

Proszę uzupełnić pliki świata klocków o adnotacje i przetestować, czy nadal wszystko działa.

Czy jesteś w stanie zasymulować typowanie bez dodawania konstrukcji :typing? Jak można byłoby tego dokonać w Prologu?

6.2 Wieże Hanoi

Mając już przetestowaną reprezentację problemu świata klocków, proszę zgeneralizować problem dodając do niego dwa dodatkowe elementy:

  1. na stole jest ograniczona liczba miejsc, na których można położyć klocek
  2. ż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

7 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. ADL różni się od STRIPS w kilku zasadniczych względach, m.in.:

  • wspierane są warunki 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>)
  • świat jest otwarty (w STRIPSie, tak samo jak w Prologu świat jest zamknięty)

7.1 Ćwiczenia

  1. w definicji dziedziny świata klocków należy przy pomocy konstrukcji ADL wyeliminować clear.
pl/dydaktyka/planning/pddl.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0