Instytut Informatyki Uniwersytetu Wrocławskiego
Sztuczna Inteligencja
6 lipca 2010
Konrad Jamrozik
Niniejszy dokument jest raportem z wykonania projektu na zajęcia ze sztucznej inteligencji 2010 prowadzonych przez dr Witolda Paluszyńskiego w Instytucie Informatyki Uniwersytetu Wrocławskiego. Dokument został przygotowany przez autora projektu, Konrada Jamrozika.
Język programowania logicznego Prolog świetnie nadaje się do implementacji inteligentnych agentów rozumujących w oparciu o wiedzę (zbiór faktów i reguł postępowania) oraz bodźce, zwane perceptami. Typową interakcję agenta ze środowiskiem można wyrazić w postaci następującej pętli:
Oczywiście zanim agent otrzyma pierwszy zestaw bodźców może już posiadać pewną wstępną wiedzę (ang. background knowledge ).
Świat wumpusa jest nieskomplikowanym środowiskiem, które jest powszechnie wykorzystywane do prezentacji działania prostych agentów z wiedzą. Świat wumpusa jest jaskinią składającą się z pomieszczeń połączonych tunelami. Bardziej formalnie, jest dwuwymiarową planszą o polach o naturalnych współrzędnych, gdzie pola różniące się jedną współrzędną o 1 są połączone. W jednym z pomieszczeń znajduje się wumpus, który może zostać zastrzelony przez agenta. Agent posiada łuk i dokładnie jedną strzałę, którą może wystrzelić by zabić wumpusa. Niektóre pomieszczenia zawierają bezdenny dół. Jeśli agent wejdzie do pomieszczenia z wumpusem, zostaje zjedzony, tym samym zaliczając zgon. Jeśli agent wejdzie do pomieszczenia z dołem, wpada do niego, zaliczając zgon. Wumpus nie wpada do dołu, gdyż jest zbyt otyły od zjedzenia poprzednich agentów i nie mieści się w nim. Jedynym pozytywnym aspektem świata wumpusa jest obecność złota na jednym z pól, które agent może zabrać.
W tym dokumencie przyjęto definicję świata Wumpusa bazującą na definicji z rozdziału 7.2 książki [1], na którą składają się cztery elementy: ocena, środowisko, działania i zmysły (odpowiednio ang. performance measure, environment, actuators, sensors ):
Ocena
+1000 punktów za podniesienie złota, -1000 za wpadnięcie do dołu lub zostanie zjedzonym przez wumpusa, -1 za każde wykonane działanie i -10 za zużycie strzały.
Środowisko
Kratownica o rozmiarze X na Y, gdzie X, Y ≥ 1. Agent zaczyna w polu o współrzędnych (1,1) i patrzy na wschód (w kierunku rosnącej współrzędnej X). Pole w którym znajduje się wumpus jest wybierane losowo z jednakowym prawdopodobieństwem, z zastrzeżeniem, że nie może to być pole o współrzędnych (1,1). Pozycja złota także jest losowana z jednakowym prawdopodobieństwem i także nie może ono znajdować się na polu o współrzędnych (1,1). Na każdym polu, oprócz pola o współrzędnych (1,1), jest losowany dół z prawdopodobieństwem wystąpienia równym 0.2.
Działania
Zmysły
Ponadto gracz przed wykonaniem pierwszej czynności posiada wiedzę o rozmiarach świata.
Celem projektu było napisanie aplikacji posiadającej następujące funkcjonalności:
Aplikacja posiada następujące funkcjonalności:
Aplikację uruchamia się z katalogu z plikiem Jovolog.jar poleceniem java -jar Jovolog.jar
Dalej zakłada się, że jest to bieżący katalog.
Aplikacja ładuje światy z katalogu "./worlds". Muszą one posiadać rozszerzenie pl oraz implementować interfejs opisany w rozdziale 6.
Agenci są ładowani z katalogu "./players". Muszą oni posiadać rozszerzenie pl oraz implementować interfejs opisany w rozdziale 7.
Rysunki (.png, .bmp, .jpg) służące do wizualizacji świata muszą znajdować się w katalogu "./images".
Aplikacja została zaimplementowana w Javie i korzysta z biblioteki tuProlog [2] do interpretowania źródeł światów i graczy napisanych w prologu. Aplikację napisano w IDE NetBeans 6.9. Do implementacji GUI wykorzystano NetBeans GUI Builder oraz Swing Application Framework. Agenci i światy (środowiska) są implementowani w Prologu. Do testów źródeł prologa wykorzystano SWI-Prologa [3]. Do aplikacji zostały przygotowane przykładowe implementacje świata wumpusa i agenta.
Interfejs agenta określa jedną funkcjonalność: sposób zwracania decyzji podjętej przez agenta i wiedzy przez niego zachowanej.
Agent musi posiadać regułę o nagłówku act(Action,Knowledge). Zmienna Action musi unifikować się do atomu zrozumiałego przez świat, do którego agent został napisany. Zmienna Knowledge musi unifikować się do listy predykatów, które agent będzie posiadał w swojej bazie wiedzy przy kolejnym wywoływaniu reguły act/2.
Interfejs składa się z reguł o następujących nagłówkach i funkcjonalnościach:
default_world_params(Params)
Zwraca listę predykatów Params opisującą sposób wygenerowania świata. Predykaty te będą widoczne i edytowalne w interfejsie użytkownika. Predykaty te, opcjonalnie po zmianach dokonanych przez użytkownika, będą obecne w bazie wiedzy świata w momencie wywoływania reguły generate_world/3.
generate_world(GeneratedWorld, PlayerKnowledge, PlayerPercepts)
Generuje początkowy świat oraz początkową wiedzę i bodźce gracza. Predykaty z listy GeneratedWorld będą znajdować się w bazie wiedzy świata w momencie pierwszego wywołania predykatu react/3. Predykaty z listy PlayerKnowledge oraz listy PlayerPercepts będą znajdować się w bazie wiedzy agenta w momencie pierwszego wywołania predykatu act/2.
point(Points)
Zwraca w zmiennej Points liczbę punktów agenta w obecnym stanie świata. Punkty te będą widoczne w graficznym interfejsie użytkownika.
generate_display(DisplaySize,Display)
Zwraca informacje konieczne do wykonania wizualizacji obecnego stanu świata.
DisplaySize to para (ŚX,ŚY) zawierająca rozmiary świata,
a Display to lista trójek postaci (X,Y,Nazwa). X,Y oznaczają współrzędne pola,
które ma być wizualizowane, a Nazwa oznacza nazwę pliku w katalogu "./images", który zostanie wyświetlony
jako wizualizacja danego pola. Przykład wartości zmiennych:
DisplaySize = (2,2)
Display = [(1,1,'player.bmp'),(1,2,'stench.bmp'),(2,1,'gold.bmp'),(2,2,'wumpus.bmp')]
react(GameStatus, NextWorld, PlayerPercepts)
Iteruje świat. W momencie wywoływania react/3 w bazie wiedzy znajduje się informacja o akcji agenta player_action(A), gdzie A to wartość zmiennej Action zwróconej z ostatniego wywołania reguły act/2 agenta. Ponadto, w bazie wiedzy znajdują się predykaty zwrócone w liście GeneratedWorld, jeśli to pierwsze wywołanie react/3, lub predykaty zwrócone w liście NextWorld poprzedniego wywołania react/3, jeśli świat był już iterowany.
GameStatus określa stan symulacji.
Jeśli GameStatus = continue(Msg), to symulacja toczy się
dalej, a Msg zostaje wypisane w rejestrze zdarzeń.
Jeśli GameStatus = end(Msg), to symulacja kończy się,
a w rejestrze zdarzeń zostaje podany powód zakończenia rozgrywki Msg.
W obu przypadkach Msg musi być ciągiem znaków w pojedynczych apostrofach.
NextWorld to lista predykatów które będą obecne w bazie wiedzy świata w momencie wywoływania następnego react/3.
PlayerPercepts to lista predykatów, które będą dostępne w bazie wiedzy agenta w momencie następnego wywołania reguły act/2.
Iterowanie symulacji wiąże się z następującymi czynnościami i wywołaniami predykatów w zadanej kolejności:
Niepotrzebne i nieaktualne predykaty są czyszczone z baz wiedzy, więc nigdy nie znajdują się w nich żadne "śmieci".
UWAGA! Predykat player_action/1 nie znajduje się w bazie wiedzy świata w momencie wywoływania predykatów generate_display/1 oraz points/1.
Do aplikacji zostały przygotowane następujące implementacje światów i graczy:
| ./worlds/wumpus_world.pl | implementacja świata wumpusa; |
| ./players/cautious.pl | implementacja agenta świata wumpusa; |
| ./worlds/world_template.pl | szablon do przygotowywania własnych implementacji światów; |
| ./players/player_template.pl | szablon do przygotowywania własnych agentów. |
Wszystkie te pliki są starannie skomentowane.
Plik "./worlds/wumpus_world.pl" zawiera implementację świata wumpusa umożliwiającą generowanie losowych światów zgodnych z definicją podaną w tym dziale oraz konfigurowanie światów w których:
Domyślne parametry świata tworzą świat z wieloma wumpusami, złotami itp., więc by zobaczyć w jaki sposób skonfigurować świat, należy uruchomić aplikację, załadować wumpus_world.pl i popatrzeć na parametry świata.
By wylosować świat, w parametrach świata z poziomu aplikacji należy dokonać następujących wpisów:
randomize. worldSize(X,Y).
gdzie X,Y to rozmiary świata.
By wygenerować jeden z wcześniej przygotowanych światów, w parametrach świata należy podać jeden wpis:
preset(N).
gdzie N jest liczbą naturalną z przedziału [1,7].
By dowiedzieć się, jakie akcje gracza interpretuje świat, oraz jakie generuje percepty i wiedzę początkową, proszę odwołać się do źródła świata.
Plik "./players/cautious.pl" zawiera agenta przystosowanego do świata opisanego w tym dziale, w szczególności agent ten zakłada, że ma 1 strzałę, jest 1 wumpus, 1 złoto, że startuje w pozycji (1,1) i że jest skierowany na wschód. Agent realizuje algorytm przeszukiwania wgłąb i nigdy nie ryzykuje, w szczególności nie strzela, jeśli nie ma pewności, że trafi wumpusa.
Gracz jest kompatybilny ze światem "./worlds/wumpus_world.pl", pod warunkiem przestrzegania założeń podanych w poprzednim paragrafie.