Identyfikacja kinematyki oraz uczenie zachowań robota mobilnego wyposażonego w systemu wizyjnego cd.

3. System sterowania

Posiadając tablicę cech statycznych robota oraz środowiska, system wizyjny przekazuje dane do modułu sterowania, który przeprowadza identyfikacje kinematyki robota. System sterowania posiadając ilościową wiedze o alfabecie słów wyjściowych i może przystąpić do testowania, uczenia się sterowania robotem. Komunikacja z systemem robota odbywa się poprzez port podczerwieni tj. na rys. 2 poprzez wysyłanie słów sterujących do odbiornika robota. Słowa sterujące potwierdzane są według przyjętego protokołu, a następnie zamieniane przez firmaware na akcje wykonywane przez układ jezdny robota.

3. 1. Identyfikacja słów sterujących robotem

W celu zidentyfikowania akcji przypisanych konkretnym słowom wyjściowym i zbudowaniu tablicy wiedzy na temat sterowania system losuje ze zbioru słowo sterujące po czym sprawdza czy jest ono słowem sterującym danego obiektu czekając na potwierdzenie od robota. W przypadku odpowiedzi negatywnej lub jej braku słowo testowane jest usuwane ze zbioru słów, a mnogość zbioru i zmniejszana o jeden i=i–1. W momencie otrzymania potwierdzenia poprawności słowa jest ono wykonywane przez robota, a system sterowania czeka na otrzymanie kolejnej paczki danych od systemu wizyjnego. Zapisana wcześniej pozycja robota, przeszkód oraz punktu docelowego jest porównywana z nowo dostarczonymi pozycjami. Na bazie tych współrzędnych tworzony jest wektor przesunięcia robota i punktu docelowego ( jeśli to jest piłka ).



Niech będzie wektorem oznaczającym kierunek, w którym robot się porusza, a będzie wektorem kierunku, w którym robot powinien się poruszać, aby dojechać do celu. Jeżeli kąt miedzy wektorami i oznaczymy jako to, aby rozpoznać kierunek, w jakim robot musi się obracać, możemy się posłużyć iloczynem skalarnym i wektorowym.

Mamy z iloczynu skalarnego:



oraz z iloczynu wektorowego:


Mając dane sinus kąta możemy określić, „po której stronie” wektora znajduje się wektor oraz cosinus kąta, jeżeli są one równoległe to jak mają skierowane zwroty. Zatem otrzymaliśmy odpowiedź o akcji, które wykonuje losowo wybrane słowo. Słowo to jest zapisane w tablicy wiedzy pod nazwą kierunku jazdy np. „jedź do przodu”. System sterowania testuje słowa do momentu wykorzystania ostatniego nie sprawdzonego słowa alfabetu.

3. 2. Planowanie trasy przejazdu robota na scenie

3.2.1. Propagacja fali

Planowanie trasy przejazdu robota jest realizowane algorytmem propagacji fali, która jest metodą ogólnego przeznaczenia i jako taka jest wykorzystywana w aplikacjach robotyki mobilnej. Robot może poruszać się po scenie roboczej w dowolnym kierunku z jednakową łatwością pod warunkiem, że na swojej drodze nie napotyka przeszkody. Działanie tej metody polega na podziale dwuwymiarowej przestrzeni sceny roboczej na elementarne komórki zwane rastrami o jednakowych wymiarach. Planowanie odbywa się przez przypisanie każdej komórce znacznika wagi. Rastry, w których znalazła się przeszkoda jest opatrywana znacznikiem zajętości. Pozostałe rastry będą posiadać wagi dodatnie. Metoda wyznaczania trasy odbywa się w dwóch częściach:
1. ocechowanie wszystkich komórek przez przypisanie im wagi zajętości dla przeszkód oraz wartości 0 dla położenia robota, dla komórek sąsiadujących z komórką o wadze 0 są nadawane wagi o jeden większą czyli 1,
2. dla komórki, w której znajduje się obiekt docelowy wyznacza się drogę powrotną do rastra z wagą 0



Najważniejszą zaletą tego algorytmu jest szybkość przejazdu robota, ponieważ pokonuje on jednorazowo całe prostoliniowe odcinki trasy, przy okazji im dłuższe przejazdy tym błędy względne wyznaczania aktualnej pozycji robota są mniejsze.



3.2.2. Planowanie z wykorzystaniem algorytmów genetycznych

Wyznaczanie trasy w środowisku robota mobilnego ma na celu znalezienie bezkolizyjnego połączenia pomiędzy dwiema pozycjami (start – koniec). Opisywany sposób wyznaczania drogi, wykorzystuje do tego celu algorytmy genetyczne (GA). Nawigator ewolucyjny (Evolutionary Planner/Nawigator – EP/N) oparty jest na chromosomach o zmiennej długości[8], co umożliwia przeszukiwanie całej powierzchni w celu znalezienie drogi bliskiej optymalnej. Środowisko robota jest przedstawione w postaci prostokątnej mapy z zaznaczoną pozycją robota i punktem docelowym. W celu uproszczenia obliczeń, zarówno robot jak i punkt docelowy, reprezentowane są przez pojedyncze punkty. Przeszkody są opisywane przez współrzędne ich kolejnych wierzchołków, co ułatwia sprawdzanie warunku dopuszczalności węzła. Przyjmujemy ponadto, że środowisko robota jest niezmienne, tzn. żadne nowe obiekty nie mogą się pojawić w trakcie pokonywania trasy.

Droga którą ma przebyć robot złożona jest z jednego lub więcej odcinków. Miejsce w którym odcinki się łącza nazywamy węzłem i reprezentujemy przez parę współrzędnych X, Y. Chromosomy natomiast są listą węzłów, uporządkowanych w kolejności, w jakiej mają być pokonywane[8]. Pierwszym węzłem jest start, a ostatnim finish. Jak wspomniano wyżej osobniki reprezentowane są przez chromosomy o zmiennej długości. Jednak na rozmiary chromosomu nałożone są pewne ograniczenia. Minimalna długość chromosomu to 2 (węzeł 1 – start, węzeł 2 – finish). Co do maksymalnej długości chromosomu nie ma praktycznie żadnych ograniczeń, jednak oczywistym jest, że ilość węzłów potrzebnych do przebycia z punktu startowego do docelowego nie jest większa niż ilość wierzchołków wszystkich przeszkód. Dlatego ta właśnie liczba będzie ograniczała długość chromosomu od góry.

Osobniki powstałe w wyniku działania algorytmu ewolucyjnego mogą zawierać tzw. „węzły niedopuszczalne”. Węzeł niedopuszczalny to taki, który nie ma połączenia z kolejnym węzłem, tzn. między nimi jest przeszkoda, lub węzeł ten jest umieszczony na przeszkodzie[8]. Dodatkowym kryterium dopuszczalności węzła może być jego odległość od przeszkody, co jest bardzo ważne zarówno ze względu na bezpieczeństwo robota jak również obiektów w jego otoczeniu. Każdy węzeł w chromosomie będzie zawierał dodatkową zmienna, która w zależności od dopuszczalności węzła będzie przyjmować wartość 1 – dla węzła dopuszczalnego i 0 – dla węzła niedopuszczalnego.

Początkowe populacje chromosomów generowane są losowo, zarówno ich długość jak i wartości węzłów, z uwzględnieniem wcześniej wymienionych ograniczeń.

Wiele tradycyjnych metod planowania drogi jako kryterium oceny danego rozwiązania przyjmuje tylko jego długość. Jednak nie jest to dobre rozwiązanie, gdyż drogi krótsze (oceniane lepiej) mogą przebiegać bliżej przeszkód, a także zawierać większą ilość węzłów, a więc ich pokonanie przez robota może przysporzyć wiele problemów, nie są więc optymalnym rozwiązaniem. Funkcja oceny będzie miała postać[8]:

eval(p) = wddist(p) + wssmooth(p) + wcclear(p)

gdzie wd , ws i wc reprezentują wagi całkowitego kosztu drogi. Funkcje wyglądają następująco:
- - gdzie jest odległością między węzłami - funkcja obliczająca całkowitą długość drogi
- , gdzie funkcja oblicza krzywiznę w węźle
- , gdzie
jeśli
w przeciwnym przypadku
jest odległością segmentu od wszystkich znanych obiektów, jest parametrem definiującym bezpieczną odległość, a jest współczynnikiem. Funkcja określa najmniejszą odległość węzła od przeszkód
Dla tras zawierających węzły niedopuszczalne funkcja oceny wygląda inaczej, i jej wartość jest taka, że trasa ta jest zawsze oceniana gorzej od najgorszej trasy spośród tras dopuszczalnych.

Selekcję osobników do reprodukcji można przeprowadzić metodą turniejową [9]. Wybierane są dwa osobniki (losowo) i do dalszej reprodukcji przechodzi lepszy. Do tak wyselekcjonowanych osobników należy następnie zastosować operatory genetyczne (nie zawsze wszystkie one są potrzebne). Operatory genetyczne[11]:

a) Krzyżowanie – będziemy stosować najprostszy sposób krzyżowania, krzyżowanie jednopunktowe. Dwa wybrane chromosomy są rozcinane w pewnym miejscu, a następnie krzyżowane: pierwsza część pierwszego osobnika z drugą częścią drugiego oraz pierwsza część drugiego z drugą częścią pierwszego. Jeśli chromosom zawiera niedopuszczalne węzły, to punkt rozcięcia wypada za jednym z nich. W przypadku chromosomów dostępnych punkt krzyżowania jest wybierany dowolnie.
b) Mutacja – modyfikuje współrzędne losowo wybranego węzła
c) Wstawianie – wstawia nowy węzeł między dwa losowo wybrane
d) Usuwanie – usuwa losowo wybrany węzeł z drogi
e) Wygładzanie – wycina ostre zakręty z trasy

Zarówno operator wstawiania jak również usuwania wydają się być bardziej przydatne w przypadku chromosomów o węzłach niedopuszczalnych. Powodują one bowiem dosyć znaczne zmiany kształtu trasy, a w szczególnych przypadkach mogą wpłynąć na zmianę stanu chromosomu z „niedopuszczalny” na „dopuszczalny”. Należy również zachować ostrożność w stosowaniu tych operatorów wobec osobników dopuszczalnych (prawdopodobieństwo ich użycia powinno być mniejsze). Oczywiście wyżej wymienione operatory nie wyczerpują wszystkich możliwości, w [11] zaproponowano ich łącznie 8. Odpowiednie dobranie kombinacji operatorów jest bardzo skomplikowanym problemem. Jednak te które przedstawiłem są wystarczające na potrzeby naszego robota.

Podsumowanie:

Przedstawione algorytmy i zagadnienia oczywiście nie wyczerpują tematu identyfikacji i sterowania. Jest to preludium do pracy, którą nasze koło naukowe będzie rozwijać. Samodzielne systemy autonomiczne są dziedziną badań, która gwałtownie się rozwija i która w przyszłości doprowadzi do powstania maszyn mogących przystosowywać się samodzielnie działania i kalibrowania tuż po uruchomieniu.

Autorzy projektu: Maciej Dzikowicki, Paweł Biniek, Michał Jura, Mateusz Kurjański, Michał Buraczyński, Piotr Czech, Maciej Wierciński
Opiekun naukowy: dr inż. Marek Piasecki, dr inż. Paweł Rogaliński

Literatura

[1]. Zdzisław Bubnicki „Teoria i algorytmy sterowania” Wydawnictwo Naukowe PWN, Warszawa 2002
[2]. Witold Jacak, Krzysztof Tchoń „Podstawy robotyki” Politechnika Wrocławska ,Wrocław 1992
[3]. Theo Pavlidis „Grafika i przetwarzanie obrazów” WNT, Warszawa 1987
[4]. M.J. Giergiel, Z. Hendzel, W. Żylski „Modelowanie i sterowanie mobilnych robotówkołowych“ PWN, Warszawa
[5]. T. Kaczorek „Teoria sterowania i systemów” PWN
[6].E. Radosiński „Systemy informatyczne w dynamicznej analizie decyzyjnej” PWN
[7]. Christopher D. Watkins, Alberto Sadun, Stephen Marenka „Nowoczesne metody przetwarzania obrazu” WNT, Warszawa
[8]. Z. Michalewicz, „Algorytmy genetyczne + struktury danych = programy ewolucyjne” wydanie trzecie, pp. 289 – 298, 2003.
[9]. Ahmed Elshamli, Hussein A. Abdullah, Shawki Areibi, Genetic Algorithm for Dynamic Path Planninig, School of Engineering, University of Guelph, CANADA
[10]. Eiben, A.E., Hinterding, R., and Michalewicz, Z., Parameter Control in Evolutionary Algorithms, IEEE Transactions on Evolutionary Computation, Vol.3, No.2, 1999, pp.124-141.
[11].Xiao, J., Michalewicz, Z., Zhang, L., and Trojanowski, K., Adaptive Evolutionary Planner/Navigator for Mobile Robots, IEEE Transactions on Evolutionary Computation, Vol.1, No.1, 1997, pp.18-28.