[PDDL] - co to jest?

Tutaj umieszczamy tematy związane z językami programowania niepasującymi do innych działów.
Regulamin forum
Temat prosimy poprzedzić nazwą języka umieszczonego w nawiasach kwadratowych np. [Pascal].
Awatar użytkownika
dambo
User
User
Posty: 356
Rejestracja: czwartek 17 mar 2016, 17:12

[PDDL] - co to jest?

Postautor: dambo » czwartek 22 wrz 2016, 19:02

Witam

Co to jest PDDL - jest to Planning Domain Definition Language - po naszemu język w którym możemy planować działania/kolejność działań w celu uzyskania interesującego nas rezultatu. Samo planowanie może zrobić każdy, ale z wykorzystaniem PDDLa znajdziemy najbardziej optymalne rozwiązanie. Nie chcę tu przedstawiać teorii (na której i tak średnio się znam) tylko pokazać prosty przykład z czym to się je. W internecie jest dużo materiałów o tym, na polskich forach itp prawie wcale. Tutaj podlinkuję stronkę osoby z którą miałem zajęcia z tego:
http://www.cs.put.poznan.pl/jpotoniec/?page_id=356
jeśli kogoś to bardziej ciekawi.

Zacznę od omówienia elementów tego języka bazując już na praktycznym przykładzie.
Otóż mamy prostą gierkę. "Labirynt" 3x3 czyli 9 pokoi nazwanych A-I, w wybranym pokoju znajduje się gracz, pomiędzy niektórymi pokojami są bramy, przez które możemy przejść. Znajdujemy się w pokoju G i naszym celem jest dotarcie do pokoju A. Mały rysunek dla ułatwienia.
qqqq.jpg

Mamy więc zarysowane już z góry nasze "otoczenie", wiemy jak to wygląda na początku i na końcu.
Pewnie wszyscy dokładnie rozumieją założenia, ale jak zrobić, żeby komputer je zrozumiał? Jak wyznaczyć mu jakie zależności tam zachodzą, jakie akcje można podejmować, co się zmienia itp? Zawsze trzeba założyć, ze komputer jest głupi i trzeba mu mega dokładnie wszystko opisać.
Otóż naszą przestrzeń działania dzielimy na:
- obiekty
- predicates - właściwości jakie mogą mieć obiekty
- Initial state - stan wejściowy naszych obiektów
- Final State - stan końcowy w jakim ma się znajdować przestrzeń po zakończeniu pracy
- Actions/Operators - jakie akcje możemy podejmować, żeby wpłynąć na naszą przestrzeń

OK - działamy dalej na naszym przykładzie:
- obiekty - obiektami w naszym przypadku jest gracz i pokoje
- predicates - jakie właściwości mogą mieć nasze obiekty - standardowo muszą mieć właściwość odnośnie swojego typu tzn np właściwość "jest-graczem", "jest-pokojem" - w celu identyfikacji typu obiektu. Potrzebujemy właściwość "czy-jest-w-pokoju" - aby stwierdzić, czy gracz jest w danym pokoju oraz właściwość "ma-brame-do", która informuje komputer, że pokój G ma bramę do pokoju D.
- Initial state - wszystkim pokojom przypisujemy właściwość "jest-pokojem" podobnie z graczem ("jest-graczem") oraz odpowiednie ułożenie bram. Gracza umieszczamy w pokoju G za pomocą właściwości "jest-graczem".
- Final State - naszym celem jest, aby gracz znajdował się w pokoju "A"
- Actions - jedyną akcją jaką będziemy podejmować jest przejście z pokoju do pokoju (oczywiście, żeby taka akcja nastąpiła muszą być spełnione pewne warunki, a także musimy podać jak ta akcja wpłynie na nasze otoczenie)

Problemy w PDDL rozdzielone są na 2 pliki:
- plik z opisem jakie występują właściwości i jakie akcje możemy podjąć
- plik z obiektami, jaki jest stan początkowy i jaki jest cel.

W czym będziemy "kodzić" -nie trzeba nic instalować skorzystamy ze stronki: http://editor.planning.domains/

Nie będę tutaj specjalnie omawiał składni tego języka - na podstawie przykładu można swój zrobić analogicznie.
Zaczynamy od pliku z właściwościami i akcjami:

Kod: Zaznacz cały

(define
   (domain przyklad)
   (:requirements :adl)
   (:predicates
      (jest-graczem ?co)
      (jest-pokojem ?co)
      
      (ma-brame-do ?co ?dokad)
      
      (jest-w-pokoju ?co ?jakim)
   )
   
   ; akcja przejscia do pokoju
   (:action idz-do-pokoju
      :parameters (?gracz ?z-pokoj ?do-pokoj)
      :precondition
      (and
         (jest-graczem ?gracz)
         (jest-pokojem ?z-pokoj)
         (jest-pokojem ?do-pokoj)
         (jest-w-pokoju ?gracz ?z-pokoj)
         (ma-brame-do ?z-pokoj ?do-pokoj)
      )
      :effect
      (and
         (not (jest-w-pokoju ?gracz ?z-pokoj))
         (jest-w-pokoju ?gracz ?do-pokoj)
      )
   )
)


W sekcji predicates widzimy nasze właściwości, a w sekcji action naszą "funkcję" przejścia z pokoju do pokoju, przyjmuje ona 3 argumenty, w sekcji preconditions sprawdza, czy spełniają one określone założenia - w tym przypadku - "?gracz" musi być graczem, "?z-pokoj" i "?do-pokoj" muszą być pokojami, "?gracz" musi być w "?z-pokoj" i "?z-pokoj" musi miec bramę do "?do-pokoj". Potem podajemy jaki jest efekt tej akcji tzn "?gracz" nie jest już w pokoju "?z-pokoj", natomiast znajduje się w "?do-pokoj".

Drugi plik wygląda następująco:

Kod: Zaznacz cały

(define (problem p1)
   (:domain przyklad)
   ; JAKIE OBIEKTY WYSTEPUJA W NASZYM ZADANIU
   (:objects gracz A B C D E F G H I )
   ; JAKI JEST STAN WEJSCIOWY NASZEGO UKLADU
   (:init
   ;gracz
      (jest-graczem gracz)
      (jest-w-pokoju gracz G)
   ;pokoje
      (jest-pokojem A)
      (jest-pokojem B)
      (jest-pokojem C)
      (jest-pokojem D)
      (jest-pokojem E)
      (jest-pokojem F)
      (jest-pokojem G)
      (jest-pokojem H)
      (jest-pokojem I)
   ; bramy
      (ma-brame-do G D)
      (ma-brame-do D E)
      (ma-brame-do E H)
      (ma-brame-do H I)
      (ma-brame-do I F)
      (ma-brame-do F C)
      (ma-brame-do C B)
      (ma-brame-do B A)
   )
   ; CO JEST NASZYM CELEM
   (:goal
      (jest-w-pokoju gracz A)
   )
)


Myślę, że ten układ jest logiczny i nie potrzebujemy dokładniejszego tłumaczenia.

Na podanej wyżej stronce tworzymy nasze pliki:
2.png

3.png

Klikamy "solve":
4.png
4.png (4.25 KiB) Przejrzano 224 razy

Pokazujemy który plik jest opisem, a który problemem:
6.png
6.png (6.99 KiB) Przejrzano 224 razy

Klikamy plan i otrzymujemy wynik:
8.png

Mamy opis jak przejść z pokoju G do pokoju A. Możemy sprawdzić rozwiązując ten "labirynt" na kartce. Ale czy wynik jest optymalny? Prezentowany wynik to jedyna droga, dodajmy więc drzwi z pokoju E do B.
wwww.jpg

Tzn w pliku z problemem w stanie inicjalizacyjnym dodajmy: (ma-brame-do E B). Otrzymamy wtedy taki wynik:
10.png


Widzimy, że za pomocą języka PDDL rozwiązaliśmy nasz problem. Oczywiście pokazałem tylko ułamek możliwości tego języka - bo tylko tyle umiem :p
Za jego pomocą możemy planować optymalną kolejność przenoszenia skrzynek przez robota w magazynie itp itd. Można dodać parametry czasowe i otrzymamy wtedy najoptymalniejszy plan działania z uwzględnieniem czasu wykonywania poszczególnych akcji - jednak tego już wam nie wytłumaczę, bo do tego nie dojechałem, ale mam nadzieję, że opis chociaż kogoś zaciekawi i zgłębi on możliwości PDDLa dalej, a nawet może wykorzysta to w pracy/życiu do czegoś (lub potraktuje jako ciekawostkę).

Tutaj: http://www.cs.put.poznan.pl/jpotoniec/?page_id=410 możemy znaleźć nawet zadanka z PDDLa z animacjami podczas ich testowania.
Zapraszam na mojego pseudobloga z projekcikami: http://projektydmb.blogspot.com/

Awatar użytkownika
matty24
User
User
Posty: 218
Rejestracja: sobota 31 paź 2015, 20:11
Lokalizacja: Małopolska

Re: [PDDL] - co to jest?

Postautor: matty24 » czwartek 22 wrz 2016, 19:41

Hmm... nigdy wcześniej o czymś takim nie słyszałem. Jak ktoś się biegle nauczy tego języka to faktycznie może ułatwić pewne sprawy. Szczególnie jak mamy do czynienia z rozbudowanym układem. Jednak w miarę prostych problemach amator szybciej wyliczy optymalne rozwiązanie ręcznie.

Awatar użytkownika
dambo
User
User
Posty: 356
Rejestracja: czwartek 17 mar 2016, 17:12

Re: [PDDL] - co to jest?

Postautor: dambo » czwartek 22 wrz 2016, 20:22

Oczywiście :)

Warto jednak wiedzieć, że takie coś jest i co można tym zrobić. Pewnie wszystkie gierki logiczno-platformowe z przesuwaniem czegoś, spadaniem itp można tym rozwiązywać. A w praktyce rozpisywać plan działania wielkiej firmy
Zapraszam na mojego pseudobloga z projekcikami: http://projektydmb.blogspot.com/


Wróć do „Inne języki programowania”

Kto jest online

Użytkownicy przeglądający to forum: Obecnie na forum nie ma żadnego zarejestrowanego użytkownika i 1 gość