| T | | B | | T |
| | F | | F | |
| B | | S | | B |
| | F | | F | |
| T | | B | | T |
Uwaga: stany specjalne nie są terminalne. Stany specjalne są jak zwykłe
stany, tylko mają indywidualne wartości nagrody.
Szczegółowe zasady:
- Agent może wykonywać ruchy: (L)eft, R(ight), (U)p, i D(own). Wykonanie
ruchu w danym kierunku z prawdopodobieństwem p1 kończy się w zamierzonym
miejscu, z prawdopodobieństwem p2 kończy się na lewo od punktu startu, z
prawdopodobieństwem p3 kończy się na prawo od punktu startu, a z
prawdopodobieństwem (1-p1-p2-p3) kończy się w miejscu przeciwnym do
zamierzonego kierunku ruchu (w przykładach omawianych na wykładzie było
p1=0.8 i p2,p3=0.1).
- W przypadku gdy agent znajduje się przy ścianie i efekt danego ruchu
wyprowadziłby go poza granice świata, albo do stanu zabronionego, w efekcie
ruchu agent pozostaje w miejscu (i otrzymuje właściwą dla niego nagrodę).
Można powiedzieć, że agent „odbija się” od ścian i stanów zabronionych.
- Każdy ruch powoduje otrzymanie nagrody przez agenta (którą, jeśli jest
ujemna, można też interpretować jako koszt ruchu). Wartość otrzymanej
nagrody zależy od stanu, do którego agent przeszedł. Dla zwykłych stanów
obowiązuje domyślna wartość nagrody r. Natomiast dla każdego stanu
terminalnego i specjalnego wartości nagrody są określone indywidualnie.
- Wynikiem działania agenta jest suma nagród uzyskanych we wszystkich
krokach, obliczona z uwzględnieniem współczynnika dyskontowania γ.
Parametrami zadania są zatem: N,M,p1,p2,p3,r,γ, oraz indywidualne
wartości nagrody dla poszczególnych stanów terminalnych i specjalnych.
Dodatkowo, w drugiej części zadania występuje parametr eksploracji ε.
Część I: bezpośrednie rozwiązywanie MDP
Napisz program rozwiązujący dyskretne problemy MDP opisanego typu, metodą
iteracji wartości lub iteracji polityki. Program powinien wyświetlić na
wyjściu obliczoną politykę agenta oraz rozkład funkcji użyteczności
w formacie zgodnym z geometrią świata MDP.
Przez rejestrowanie przez program wyników częściowych, zaimplementuj analizę
zbieżności algorytmu tworząc wykres wartości użyteczności stanów programem
Gnuplot. Załącz zarówno wynikowy wykres, jak i opracowany komplet poleceń
Gnuplota, oraz pliki danych, pozwalające wygenerować ten wykres dla każdej
instancji problemu.
- Oblicz rozwiązanie zagadnienia 4x3 omawianego na wykładzie, Rys.1,
γ=1.0. W raporcie podaj: komplet otrzymanych użyteczności stanów z
dokładnością do czwartego miejsca po przecinku, politykę, wykres zbieżności,
oraz liczbę wykonanych iteracji algorytmu. Użyteczności i politykę
przedstaw w tabelce zgodnej z układem świata. Politykę zapisz znakami:
> < ^ v. Jako kryterium stopu algorytmu możesz przyjąć zejście
wszystkich różnic wartości między kolejnymi iteracjami poniżej 0.0001.
Porównaj wyniki ze znanymi z literatury i wykładu. Jeśli Twoje wyniki
różnią się, to znaczy że masz niepoprawną implementację algorytmu!
Rys.1:
- Znajdź rozwiązanie zagadnienia pokazanego na Rys.2 (N=4, M=4),
przyjmując model niepewności ruchów dokładnie taki sam jak w przykładach
omawianych na wykładzie (p1=0.8, p2,p3=0.1), i współczynnika dyskontowania
γ=0.99. Funkcja nagrody wynosi +100 dla stanu terminalnego, -20 dla
stanu specjalnego, i r=-1 dla zwykłych stanów. Podaj politykę optymalną,
komplet wartości użyteczności (cztery miejsca po przecinku), i wykres
zbieżności. Jako kryterium stopu algorytmu ponownie proszę przyjąć zejście
wszystkich różnic wartości między kolejnymi iteracjami poniżej 0.0001.
Rys.2:
- Zmień funkcję nagrody dla stanów normalnych, specjalnych, i/lub
terminalnych (względem podstawowej wersji zadania 4x4 z Rys.2) w taki
sposób, aby skutkowało to zauważalną zmianą polityki optymalnej. Przedstaw
komplet rozwiązań dla zmienionego zadania (użyteczności, politykę, wykres).
Wyjaśnij uzyskane wyniki.
- Zmień model niepewności ruchów (względem podstawowej wersji zadania
4x4 z Rys.2) w taki sposób, aby skutkowało to zmianą polityki optymalnej.
Przedstaw komplet rozwiązań dla zmienionego zadania (użyteczności, politykę,
wykres). Wyjaśnij uzyskane wyniki.
- Zmień współczynnik dyskontowania (względem podstawowej wersji zadania
4x4 z Rys.2) w taki sposób, aby skutkowało to zmianą polityki optymalnej.
Przedstaw komplet rozwiązań dla zmienionego zadania (użyteczności, politykę,
wykres). Wyjaśnij uzyskane wyniki.
Modyfikacje w ostatnich trzech punktach zadania powinny być na tyle istotne,
aby dało się zauważyć ich wpływ na politykę agenta, ale jednocześnie na tyle
ograniczone, aby dało się sensownie porównać wersję zmodyfikowaną i oryginalną.
Część II: rozwiązywanie MDP metodą Q-learning
Zaimplementuj obliczanie optymalnej polityki agenta metodą Q-learning z
eksploracją. Przyjmij te same podstawowe parametry co w pierwszej części
zadania. Jednak model ruchów i wartości nagrody są tu nieznane agentowi,
zostaną tylko użyte dla wygenerowania przebiegów uczących. Zatem program musi
składać się z dwóch części: agenta, który generuje akcje i uczy się funkcji Q
z przebiegów uczących, oraz symulatora, który te przebiegi uczące generuje
począwszy od zadanego stanu startowego, przez generowanie losowych reakcji na
akcje agenta.
Agent powinien generować akcje łączące eksploatację z eksploracją w
następujący sposób, sterowany parametrem eksploracji ε. Najlepszy
ruch dla danego stanu (eksploatacja) powinien być wybierany z
prawdopodobieństwem 1-ε, a z prawdopodobieństwem ε powinien
być wykonywany ruch wybrany losowo (eksploracja).
Rozwiąż instancję problemu dla świata z Rysunku 2 z ustawieniami: p1=0.8,
p2,p3=0.1, γ=0.99 i współczynnikiem uczenia α=1/N(s,a) gdzie
N(s,a) jest liczbą razy jaką akcja a została wybrana w stanie s w
dotychczasowych przebiegach. Uwzględnij dwie strategie eksploracji, z
ε=0.05 i ε=0.2.
W tej części zadania trudno będzie osiągnąć dokładność podobną jak w części
pierwszej. Orientacyjnie pożądane byłoby osiągnięcie dokładności jednej cyfry
dziesiętnej. Przeprowadź eksperymenty dla ustalenia ile przebiegów jest
potrzebnych dla osiągnięcia takiego wyniku. Zacznij od 10,000 przebiegów.
zawsze startując ze stanu startowego S aż do osiągnięcia stanu terminalnego.
Oszacuj z jaką dokładnością obliczone zostały wartości funkcji Q, w
szczególności ile przebiegów uczących było potrzebne dla osiągnięcia tej
dokładności dla różnych wartości ε.
W raporcie przedstaw w postaci tabeli odpowiadającej geometrii świata:
znalezioną politykę optymalną, użyteczności stanów oraz wartości Q (jedną
cyfrę dziesiętną), z podaniem liczby wygenerowanych przebiegów uczących.
Wymagania dotyczące programów
Opracowane programy powinny wyznaczać optymalną politykę, oraz rozkład funkcji
użyteczności U (pierwsza część zadania), albo rozkład funkcji wartości akcji Q
(druga część zadania). Programy mogą wykorzystywać dowolne ogólnie dostępne
dla danego języka biblioteki i funkcje.
Każdy program powinien rozwiązać podane zadanie, wyniki częściowe (do
tworzenia wykresów zbieżności) zapisać w pliku/ach na dysku, natomiast końcowe
wyniki w postaci rozkładu polityki, użyteczności U lub wartości akcji Q,
powinien wyświetlić w postaci tabeli zgodnej z geometrią świata. Pierwszy
parametr rozmiaru świata traktujemy jako rozmiar poziomy, a drugi jako
pionowy, z początkiem układu w lewym dolnym rogu.
Wszystkie wyniki należy wyswietlic w postaci tekstowej na wyjściu stdout.
Proszę używać czystego kodu ASCII (7-bitowego), bez znaków polskich, ani
żadnych znaków graficznych. Politykę proszę wyświetlić za pomocą znaków:
<,>,v,^
Parametry zagadnienia MDP program powinien wczytać z zadanego pliku o formacie
opisanym poniżej. Plik zawiera parametry N,M,p1,p2,p3,r, które są
parametrami zagadnienia MDP, oraz może opcjonalnie zawierać parametry γ
i ε, które są parametrami agenta wpływającymi na kształt i sposób
wyznaczenia rozwiązania.
Parametry γ i ε program powinien przyjmować również jako
argumenty wywołania zadane w wierszu wywołania w sposób pozycyjny (pierwszy
γ i drugi ε). Argumenty wywołania są opcjonalne, i jeśli nie
zostały podane, to obowiązują parametry wczytane z pliku zadania. Brak
kompletu parametrów, lub ich nieprawidłowe wartości powinny spowodować
zatrzymanie programu z odpowiednim komunikatem.
Dopuszczalne sposoby dostępu do pliku danych zadania: (0) otwarcie pliku tylko
do jednorazowego odczytu sekwencyjnego, (1) nazwa pliku może być zadana
argumentem wywołania w wierszu poleceń, albo (2) nazwa pliku może być ustalona
na stałe i wbudowana w program, albo (3) nazwa pliku może być zadana zmienną
środowiskową (to jest dobra opcja dla systemów rodziny Unix, ale nie wiem czy
istnieje na Windows). Niedopuszczalne jest aby program pytał interakcyjnie o
nazwę pliku, ogólnie wymagał jakiejkolwiek interakcji z użytkownikiem, albo w
ogóle czytał cokolwiek z wejścia stdin.
Program należy napisać w zadanym języku programowania w sposób niezależny od
systemu operacyjnego i okienkowego: Windows, Linux, X11, Android, itp.,
również przy kompletnym braku systemu okienkowego.
Specyfikacja formatu danych
Plik danych zawierający opis instancji świata i parametrów eksperymentu jest
plikiem tekstowym składającym się z szeregu wierszy. Każdy wiersz zawiera na
początku etykietę (napis tekstowy), i po niej jeden do trzech parametrów
liczbowych. Dopuszczalne są następujące etykiety:
- W (obowiązkowy) określa rozmiar świata: poziomy i pionowy (2xINT),
- S (opcjonalny) określa współrzędne stanu startowego (2xINT),
- P (obowiązkowy) określa rozkład prawdopodobieństwa p1 p2 p3 (3xFLOAT),
- R (obowiązkowy) określa domyślną wartość nagrody r (1xFLOAT),
- G (opcjonalny) określa współczynnik dyskontowania γ (1xFLOAT),
- E (opcjonalny) określa współczynnik eksploracji ε (1xFLOAT),
- T (wielokrotny - musi wystąpić 1 lub więcej razy) definiuje pojedynczy
stan terminalny: dwie współrzędne i indywidualną wartość nagrody (2xINT+1xFLOAT),
- B (wielokrotny - może wystąpić 0 lub więcej razy) definiuje pojedynczy
stan specjalny: dwie współrzędne i indywidualną wartość nagrody (2xINT+1xFLOAT),
- F (wielokrotny - może wystąpić 0 lub więcej razy) definiuje pojedynczy
stan zabroniony: dwie współrzędne (2xINT).
Stan startowy jest opcjonalny. Algorytm iteracji wartości nie używa go.
W części II zadania (Q-learning), gdy nie został zadany stan startowy, należy
losowo wybrać jeden ze stanów nieterminalnych jako początek każdego przebiegu.
Parametry γ i ε są opcjonalne, ponieważ mogą być również
zadane jako argumenty wywołania programu.
Współrzędne stanów liczone są od 1 i początkiem układu współrzędnych jest
lewy dolny narożnik wyświetlanej reprezentacji świata.
Dopuszczalna jest dowolna kolejność wierszy pliku, pod warunkiem wystąpienia
dokładnie po jednym z wierszy obowiązkowych, i co najwyżej po jednym z wierszy
opcjonalnych. Musi również wystąpić co najmniej jeden stan terminalny.
Ponadto parametry świata MDP muszą spełniać następujące warunki:
p1, p2, p3 >= 0.0 <= 1.0
p1+p2+p3 <= 1.0
gamma > 0.0 <= 1.0
wszystkie jawnie zdefiniowane stany (S, T, B, F) muszą leżeć w określonych rozmiarach świata
Przykładowa treść pliku danych opisująca instancję problemu MDP z wykładu
(i podręcznika Russella i Norviga):
W 4 3
S 1 1
P .8 .1 .1
R -0.04
G 1.00
T 4 3 1.
T 4 2 -1.
F 2 2
Oddawanie zadania
Należy opracować zwięzły raport opisujący wyniki uzyskane w poszczególnych
częściach zadania, z niezbędnymi wyjaśnieniami, interpretacjami, oraz wnioskami.
W raporcie proszę wymienić wszystkie wykorzystane materiały, zarówno pozycje
literatury, jak i konkretne moduły programowe: biblioteki programowe inne niż
domyślne, a także ewentualnie wykorzystane gotowe programy lub fragmenty
programów, i ich źródła.
Dodatkowo, należy stworzyć pakiet uruchomieniowy zawierający wszystkie
niezbędne pliki źródłowe, utworzone zestawy danych, niezbędne do uruchomienia
programów. Sposób kompilacji i uruchamiania programu powinien być opisany w
pliku README zawartym w pakiecie.
Pakiet powinien pozwolić na uruchomienie opracowanych programów w celu
przetestowania ich na innych instancjach MDP zgodnych z wymaganiami zadania.
| | |