Metody i algorytmy sztucznej inteligencji.
Algorytm uczenia ze wzmocnieniem dla małego robota mobilnego klasy (2,0).
Metody i algorytmy sztucznej inteligencji.
prowadzący dr.inż. Witold
Paluszynski
wykonał Jan Kędzierski 133104
Date: 21.06.07
Uczenie ze wzmocnieniem [1][2] w pewnym sensie jest metodą prób i błędów. System, który ma działać w pewnym zupełnie nei znanym środowisku powinien realizować zadania w określony sposób (wg konkretnej strategii). Tyle tylko, że jego strategia działania zależeć będzie od podjętych wcześniej decyzji. Tzn. jeśli wcześniej system popełniał błędy teraz będąc w tym samym stanie nie powinien podejmować takich akcji. Wiedząc jak ocenione zostają jego decyzje może starać się je tak zmodyfikować strategię, aby w kolejnych krokach otrzymać jak największą ocenę. Oceny za podjęte akcje są skutkiem pewnego sprzężenia które działa na uczący się system. Modelem matematycznym zadania RL jest problem decyzyjny Markowa [3]. Jest to problem znalezienia optymalnej strategii decyzyjnej dla środowiska, którego modelem jest proces decyzyjny Markowa. W procesie tym wartość funkcji wzmocnienia jest zmienna losową.
Rys. 1 Uczenie ze wzmocnieniem
Scenariusz uczenia ze wzmocnieniem:
Uczeń dokonując eksploracji przestrzeni stanu otrzymuje nagrodę jeżeli stan ten jest docelowy lub karę jeśli znalazł się w stanie niedozwolonym. Dla przykładu uczący się robot, który dotrze do zadanej pozycji dostanie nagrodę o wartości 1lub -1 czyli karę jeśli np. uderzy w przeszkodę. Dla wszystkich pozostałych przypadków nagroda ma wartość równą 0.
Naturalnie algorytm ten nie może się wykonywać nieskończenie wiele razy. Można go zaprzestać w momencie kiedy tablica Q będzie dostatecznie wzmocniona.
W przypadku kiedy mamy odczynienia z sporą ilością stanów, co za tym idzie jeszcze większą ilością par stan-akcja można posłużyć się metodą HEDGER lub/i JAQL [4]. Załóżmy, że mamy do przebycia drogę 10m przy pomocy robota. Nagrodę otrzymamy dopiero wtedy, kiedy dotrzemy na miejsce. W pozostałych stanach będzie ona równa 0. A zatem nagroda nie dotrze do punktu startu zbyt szybko. Dla n stanów drogę należało by przejechać co najmniej n razy. Dlaczego więc nie stosuje się kar w postaci np. odległość od punktu docelowego? Wymaga to od ucznia wielu szczegółowych informacji, a ich przetwarzanie bywa niekiedy bardzo trudne. Łatwiej jest jedynie stwierdzać, że robot w danym momencie znalazł się w docelowym stanie nie dokonując przy tym żadnych obliczeń. Drugim powodem może być np. kompletny brak wiedzy na temat zastosowanych czujników w urządzeniu a nawet samej kinematyki robota . Nie wiemy czy wyniki pomiarów są dla nas korzystne czy tez nie. Poddając system algorytmowi samo uczenia się po pewnym czasie okaże się, kiedy sensory wskazują pozytywną strategie a kiedy nie.
Metoda JAQL dzieli proces uczenia na dwie fazy. W pierwszej fazie robotem steruje człowiek np. przy pomocy joysticka. W tym momencie system uczy się niejako w sposób pasywny. Tzn. obserwuje stany, akcje i otrzymane nagrody i zapamiętuje je. Nie ma wpływu na strategię sterowania. Gdy dla pewnego stanu zostanie otrzymana nagroda wtedy system odtwarza zapamiętane stany wstecz. Gdy stwierdzimy, że system został dostatecznie nauczony przechodzimy do fazy drugiej, który działa już jak klasyczny algorytm RL. Dzięki tej metodzie proces uczenia znacznie się przyspiesza.
Rys. 2 Faza 1
Rys. 3 Faza 2
Klasyczny algorytm RL z powodzeniem nadaje się do różnych gier hazardowych. Używa się często tzw. cech. np. ilość koników szachowych po stronie przeciwnika po wygranej grze. Innym przykładem użycia cech może być np. ilość asów po przegranej kolejce. Dzięki temu estymując daną cechę można wpływać na strategię gry. Skoro duża liczba asów zwykle zdarzała się po przegranej w następnym rozdaniu należy się ich pozbywać jak najszybciej.
Zupełnie inaczej przedstawia się to w przypadku robotów mobilnych. W prawdzie
można tu użyć estymacji cech środowiska nie koniecznie dyskretyzując przestrzeń
zadaniową jednakże w opisanym poniżej przykładzie posłużono się klasycznym
odzwierciedleniem stanu robota w trój wymiarowym układzie współrzędnym (x,y,theta).
Do realizacji eksperymentu posłużono się robotem mobilnym klasy (2,0)
[6]. Robot ten został
skonstruowany w ramach projektów w Kole Naukowym KoNaR oraz na zajęciach.
Wyposażono go w czujniki przyspieszenia, optyczny czujnik przemieszczenia oraz
enkodery. W eksperymencie przedstawionym poniżej wykorzystano optyczny czujnik
przemieszczenia.
Fot. 1 Platforma
.
Do realizacji algorytmu napisano program w języku C# w środowisku Microsoft Visual Studio 2005. Umieszczono w nim okno terminala na którym pojawiały się informacje o aktualnym stanie, nagrodzie, podjętych akcjach oraz błędach transmisji.
Fot. 2 Program realizujący algorytm
Fot. 3 Widok stanowiska.
Początkowo zakładano, że robota nuczy się jeździć po liniach prostych pomimo np. zainstalowaniu kół o różniących się średnicach. Eksperyment powiódł się lecz był mało ciekawy. Zwłaszcza jeśli założymy, że istnieje przejście pomiędzy każdym ze sterowań kół. Nagrodę przyznawano gdy robot zaczął jechać prosto (w pewna tolerancją), a karę w przeciwnym przypadku. Rozwiązanie było gotowe po jednokrotnym przejściu przez pary stan-akcja. Dlatego zdecydowano o nie umieszczaniu wyników.
Drugim eksperymentem był problem podążania korytarzem (corridor following) [4]. Celem robota jest jak najszybsze przejechanie na drugi koniec korytarza bez stłuczki ze ścianami.
Rys. 4 Zadanie podążania korytarzem
Prędkość liniowa robota była kontrolowana w następujący sposób: im bliżej ściany tym prędkość była mniejsza. Najszybciej robot przemieszczał się w środkowej części korytarza. Zakres prędkości liniowych był następujący
Każdy stan był częścią wymiaru: odległość do końca korytarza, odległość od ściany, orientacja robota. Zbiór akcji to: zadaj prędkość kątową -1,0,1. Dla długości korytarza 100cm, szerokości 10cm i dozwolonej zmiany kąta (+/- 1rad co 0.1) daje to dokładnie 6000 stanów. Należy jednak pamiętać, że nie wszystkie stany są osiągalne. Gdy platforma znajdowała się możliwie jak najbliżej ściany możliwe było sterowanie jedynie w kierunku środka korytarza. Robot zawsze startował ze środka korytarza z losowo skierowaną orientacją. Akcje były wybierane w sposób zachłanny czyli w danym stanie wybierano akcję o największej wartości tablicy Q. Jeżeli dla wszystkich akcji wartości te były równe zero wtedy system wybierał akcję losowo z prawdopodobieństwem o rozkładzie jednostajnym. Zadanie polegało na zminimalizowaniu kroków potrzebnych do osiągnięcia celu.
Przyjęto:
Tab.1 Próba przejechania korytarza przed uczeniem.
Tab.2 10 prób w pierwszej fazie i 20 w drugiej.
Tab.3 20 prób w pierwszej fazie i 20 w drugiej.
Tab.4 Próba przejechania korytarza przed uczeniem.
Tab.5 10 prób w pierwszej fazie i 10 w drugiej.
Na podstawie eksperymentów można stwierdzić, że system z pewnością z czasem zdobywał wiedzę o środowisku. Proces ten odbywał się bardzo powoli ze względu na dużą liczbę stanów. Szkoda, że nie udało się zaimplementować metody HEDGER [5], która jak zapewnia jej autor jeszcze szybciej przyspiesza proces uczenia się. Warto zaznaczyć, że szerokość korytarza 10cm to bardzo mało. Przyjęto tak aby ograniczyć liczbę stanów. Należy zwrócić uwagę, że wszystkie eksperymenty były przeprowadzane na rzeczywistym obiekcie co stanowczo spowalniało pracę. Na potrzeby badań algorytmu, można było się posłużyć symulatorem.
[1] Radosław Rudek Praca Magisterska „System eksperymentowania na potrzeby analizy adaptacyjnych algorytmów dobru tras w sieciach komputerowych.”
[2] Paweł Cichosz „Systemy uczące się.”
[3] Witold Paluszyński „Metody i Algorytmy Sztucznej Inteligencji.'” http://sequoia.ict.pwr.wroc.pl/ witold/aiarr/
[4] William D. Smart, Leslie Pack Kaelbling „Effective Reinforcement Learning for Mobile Robots”.
[5] William D. Smart „Making Reinforcement Learning Work on Real Robots”.
[6] Kędzierski J. Ostrowski E. „Platforma mobilna BlueScreen”. http://www.konar.ict.pwr.wroc.pl/infopage.php?id=13