1) Podstawowe problemy napotykane w Robotyce.

Podstawowym problemem w robotyce jest planowanie ruchu robota. Robot powinien "sam" planować swój ruch poprzez odpowiednio zaprogramowane urządzenie sterujące, a do tego potrzebna jest wiedza o otoczeniu, w którym ma się poruszać. Robot powinien mieć dostarczone informacje o kształcie pomieszczenia i rozmieszczeniu przeszkód stałych. W celu wykrywania przeszkód, których pojawienia się i położenia nie można przewidzieć robot może być zaopatrzony w odpowiednie sensory. Mając te informacje odpowiednie oprogramowanie wyznacza bezkolizyjną ścieżkę prowadzącą do punktu docelowego.

2) Lokalizacji za pomoca filtru Histogramowego, filtr jedno i dwuwymiarowy, aktualizacja

wag po pomiarze i ruchu, reguła Bayesa i prawdopodobienstwo całkowite.

Twierdzenie Bayesa

Jeżeli zdarzenia B1, B2, ..., Bn wykluczają się parami i mają prawdopodobieństwa dodatnie, to dla każdego zdarzenia A zawartego w sumie zdarzeń B1 ∪ B2 ∪ ... ∪ Bn:

Powyższy wzór nazywamy wzorem Bayesa. Twierdzenie Bayesa stosujemy głównie wtedy, gdy znamy wynik

doświadczenia i pytamy o jego przebieg.

Prawdopodobieństwo całkowite

Jeżeli zdarzenia B1, B2, ..., Bn wykluczają się parami i mają prawdopodobieństwa dodatnie, to dla każdego zdarzenia A zawartego w sumie zdarzeń B1 ∪ B2 ∪ ... ∪ Bn:

P(A) = P(A|B1) · P(B1) +P(A|B2) · P(B2) + ... +P(A|Bn) · P(Bn)

Powyższy wzór nazywamy wzorem na prawdopodobieństwo całkowite i pozwala nam na obliczanie prawdopodobieństw wielu zdarzeń nie tylko w doświadczeniach dwuetapowych. W doświadczeniach o większej liczbie etapów stosujemy ten wzór wielokrotnie. Zdarzenia Bi nazywamy często hipotezami..

Algorytm pozwalajacy na lokalizacje w danym srodowisku opisanym mapa. Polega

na naprzemiennym wykonywaniu pomiarów za pomoca sensorów i poruszaniu sie,

przy kazdorazowym odswiezaniu prawdopodobienstw połozenia na mapie.

Etap pomiaru za pomoca sensorów, moze wygladac nastepujaco, przyjmujac, ze robot znajduje sie w cykliczym swiecie postaci,

swiat = [sciana, sciana, drzwi, drzwi, sciana]

Robot moze sie poruszac w prawo, jezeli jest w ostatnim stanie w kolejnym kroku

przechodzi do pierwszego.

Zakładajac, ze prawdopodobienstwo bycia w jednym z obszarów swiata jest jednakowe, czyli

[0.2, 0.2, 0.2, 0.2, 0.2]

Przy ustalonej dokładnosci sensora 0.8, gdy robot w pierwszym pomiarze zarejestruje

drzwi, prawdopodobienstwa połozenia robota aktualizujemy nastepujaco

[0.2*0.2, 0.2*0.2, 0.2*0.8, 0.2*0.8, 0.2*0.2]

czyli

[0.04, 0.04, 0.16, 0.16, 0.04]

Otrzymane wartosci sa prawdopodobienstwami nieznormalizowanymi, zauwazmy, ze

ich suma wynosi 0.44, aby prawdopodobienstwa sumowały sie do jedynki, dzielimy

kazda wartosc przez otrzymana sume otrzymujac w przyblizeniu

[0.091, 0.091, 0.3635, 0.3635, 0.091]

teraz prawdopodobienstwa sumuja sie do jedynki.

Kolejnym etapem działania filtru, jest aktualizacja po wykonaniu ruchu, tak zwany

splot (convolution). Prawdopodobienstwo porusza sie wraz z robotem jest odswiezane

w zaleznosci od precyzji wykonanego ruchu. Przyjmujac, ze robot porusza sie

w sposób dokładny. Jezeli prawdopodobienstwa przed aktualizacja maja wartosc.

[0, 0, 0.5, 0.5, 0]

to po ruchu robota w prawo i aktualizacji wynosza

[0, 0, 0, 0.5, 0.5]

W rzeczywistosci roboty poruszaja sie w sposób niedokładny. Załózmy przykładowo,

ze robot zamierza przemierzyc dwa pola swiata w prawo i prawdopodobienstwo

tego ruchu wynosi 0.8, robot moze nie dotrzec do celu wykonujac jeden ruch z

prawdopodobienstwem 0.1, oraz moze przejsc o jedna kratke dalej od celu z prawdopodobienstwem

0.1. Przy takich załozeniach po jednym ruchu, aktualizacja, dla

rozkładu prawdopodobienstwa,

[1, 0, 0, 0, 0]

jest postaci,

[0, 0.1, 0.8, 0.1, 0]

aktualizacja pola2, to przykładowo 0*0.1+0*0.8+1*0.1, czyli 0.1

3) Idea lokalizacji za pomoc filtru partykułowowego (particle filter)

Algorytm wywodzący się z metod Monte Carlo, opierający się na symulacji. Stosuje go dla modeli o większym stopniu skomplikowania – kiedy mamy do czynienia z modelem nieliniowym lub z niegaussowskim rozkładem prawdopodobieństwa.

x_k = f(x_k − 1) + w_k

y_k = h(x_k) + v_k

gdzie: xk – chwilowa wartość wektora stanu w chwili k

yk – wektor pomiarowy w chwili k

wk – wektor szumu pomiarowego

vk – wektor szumu przetwarzania

k = 0,1,2,3,…

4) Sledzenie obiektów za pomoca filtru Kalmana, w szczególnosci, definicja Gaussian’u

- jego cechy charakterystyczne, etap aktualizacji po pomiarze, etap aktualizacji

po ruchu.

Definicja śledzenia obiektów

Śledzeniem nazywamy sprawdzanie położenia i orientacji zdefiniowanych obiektów w czasie wykorzystując system wizyjny.

Algorytm filtru Kalmana

Jest to algorytm wyznaczania minimalno-wariacyjnej estymaty wektora stanu modelu liniowego dyskretnego układu dynamicznego. Jest to algorytm rekurencyjny i przyjmuje, że występowanie dużego błędu o rozkładzie gaussowskim.

Algorytm ten został opracowany przez Rudolfa Emila Kalmana w 1960 roku i znalazł zastosowanie nie tylko w śledzeniu obiektów, ale także w elektronice, inżynierii dźwięku i w wielu innych dziedzinach techniki. Mimo tego, że jest to stara metoda, ma ona nadal zastosowanie w wielu aplikacjach.

Filtr Kalmana można zamodelować w postaci równań stanu:

x(t+1) = Ax(t) + Bu(t) + v(t); y(t) = C^Tx(t) + w(t)

gdzie:

t = …,-1,0,1,2,.. oznacza dyskretną chwilę czasu

x(t) – chwilowa wartość wektora stanu

A – macierz przejścia układu

B – macierz wejściowa

C – macierz wyjściowa

v(t) – wektor szumu przetwarzania

w(t) – wektor szumu pomiarowego

y(t) – wektor pomiarowy

5) Algorytm A* wyszukiwania optymalnej sciezki - w grafie, drzewie i siatce.

Algorytm A* od wierzchołka początkowego tworzy ścieżkę, za każdym razem wybierając wierzchołek x z dostępnych w danym kroku niezbadanych wierzchołków tak, by minimalizować funkcję f(x) zdefiniowaną:

f(x) = g(x) + h(x)

gdzie:

g(x) – droga pomiędzy wierzchołkiem początkowym a x. Dokładniej: suma wag krawędzi, które należą już do ścieżki plus waga krawędzi łączącej aktualny węzeł z x.

h(x) – przewidywana przez heurystykę droga od x do wierzchołka docelowego.

W każdym kroku algorytm dołącza do ścieżki wierzchołek o najniższym współczynniku f. Kończy w momencie natrafienia na wierzchołek będący wierzchołkiem docelowym.

7) Kontroler PID - opis trzech etapów budowy kontrolera.

Regulator PID pracuje w pętli sprzężenia zwrotnego, oblicza wartość uchybu jako różnicę pomiędzy zmierzoną wartością zmiennej procesu i pożądaną wartością zadaną i działa w taki sposób, by zredukować uchyb poprzez odpowiednie dostosowanie sygnału podawanego na wejście regulowanego obiektu.

Algorytm obliczeń regulatora PID zawiera trzy oddzielne stałe parametry i dlatego czasami bywa nazywany regulatorem z trzema członami: proporcjonalnym, całkującym i różniczkującym, oznaczonymi odpowiednio P, I i D.

Poglądowo działanie tych członów w odniesieniu do czasu można zinterpretować następująco:

• działanie członu P kompensuje uchyb bieżący

• człon I kompensuje akumulację uchybów z przeszłości

• człon D kompensuje przewidywane uchyby w przyszłości.

Ważona suma tych trzech działań stanowi podstawę sygnału podawanego na człon wykonawczy w celu regulacji procesu (np. zmiana położenia zaworu regulacyjnego albo zwiększenie mocy grzejnika).

Regulator PID stanowi najlepsze rozwiązanie w przypadku braku wiedzy na temat obiektu regulacji. Poprzez odpowiedni dobór nastaw regulatora PID, uzyskuje się regulację dostosowaną dla danego obiektu. Odpowiedź regulatora opisuje się, przedstawiając jego reakcję na uchyb: stopień przeregulowania i poziom oscylacji układu. Należy przy tym pamiętać, że algorytm regulacji PID nie zapewnia sterowania optymalnego ani nie gwarantuje stabilności układu.

LUB!!!!

Zacznijmy od opisania P-kontrolera. Jezeli cte - jest odchyleniem od ustalonego

kierunku jazdy, _ katem sterowania robota, _ współczynnikiem zmiany kata jazdy,

wtedy kat sterowania _ wyliczany proporcjonalnie do odchylenia toru jazdy przyjmuje

wartosc,

α = −Ɛ* cte

Sterowanie robotem w ustalonym kierunku z pomoca P-kontrolera daje efekt widoczny na rysunku 4.

Rysunek 4: Koncowy efekt działania kontrolera proporcjonalnego do błedu toru jazdy (P-kontrolera)

Robot szybko zwraca sie w kierunku docelowym, gdy jest juz na odpowiedniej

trajektorii delikatnie oscyluje (patrz rysunek 4). Aby zniwelowac efekt oscylacji

mozna w kontrolerze uwzglednic zmiane błedu toru jazdy w czasie, (stworzyc

PD-kontroler), ustalamy współczynnik δ, i kazdorazowo wyliczamy róznice cte w

poprzednim i nastepnym kroku, czyli w czasie t − 1 i t, róznica miedzy kolejnymi

odchyleniami od toru jazdy jest obliczana nastepujaco, Dcte = $\frac{\text{cte}_{t} - \text{cte}_{t - 1}}{t}$ , przyjmujac,

ze róznica jest sprawdzana cyklicznie z tym samym odstepem czasu, kat

sterowania PD-kontrolera moze byc wyliczony nastepujaco,

α = −Ɛ * cte − δ * Dcte

Rysunek 5: Efekt działania kontrolera proporcjonalnego do błedu toru jazdy i zmiany

błedu w czasie (PD kontroler)

Kolejnym problemem jaki mozemy napotkac podczas kontroli robota mobilnego

w ustalonym kierunku jest niedokładnosc kół pojazdu prowadzaca do rozbieznosci

połozenia robota od zamierzonej sciezki, która miał sie poruszac. Problem obrazujemy

na rysunku 6.

Rysunek 6: Rozbieznosc połozenia robota od zamierzonej sciezki jazdy.

Problem moze byc rozwiazany przez odjecie parametryzowanej wartosci sumy

wszystkich zaobserwowanych błedów rozbieznosci od docelowego kierunku, przyjmijmy

parametr rozbieznosci jako τ , po uwzglednieniu ewentualnego odchylenia od

toru jazdy kat sterowania przyjmuje ostateczna wartosc,

α = −Ɛ * cte − δ * Dcte – τ * Σ cte

8) Algorytmy genetyczne - operacja mutacji i krzyzowania - algorytm wczesnego

stopu.Pojęcia związane z algorytmami genetycznymi, krzyżowanie i mutacja.

populacja – zbior osobnikow o okreslonej liczebnosci

osobnikami populacji - w alg gen sa zakodowane w postaci chromosomow zbiory parametrow zdania, czyli rozwiazania, okreslane jako punkty przestrzeni poszukiwania

chromosomy – innaczej lancuchy lub ciagi kodowe – to uporzadkowane ciagi genow

gen – nazwany tez cecha znakiem detektorem – stanowi pojedynczy element genotypu, w szczegolnosci chromosomu

genotyp – czyli struktura, to zespol chromosomow danego osobnika. Zatem osobnikami populacji moga byc genotypy albo pojedyncze chromosomy.

Fenotyp – jest zestawem wartosci odpowiadajacych danemu genotypowi, czyli zdekodowana struktura, a wiec zbiorem parametrow zdania (rozwiazaniem, punktem przestrzeni poszukiwan).

Allel – wartosc danego genu, okreslana tez jako wartosc cechy lub wariant cechy

locus – to pozycja wskazujaca miejsce polozenia danego genu w lancuchu, czyli chromosomie.

Funkcja oceny (dopasowania/oceny) – stanowi ona miare przystosowania danego osobnika w populacji.

Właściwości algorytmu wczesnego stopu

Najpopularniejszą metodą zabezpieczenia się przed wystąpieniem zjawiska przeuczenia jest poszerzenie wykorzystywanej metody wstecznej propagacji błędu i połączenie z algorytmem wczesnego stopu (ang. early stopping). Powyższa metoda, nazywana także zatrzymanym uczeniem proponuje:

Podział wszystkich obserwacji na zbiór uczący, wykorzystywany do modyfikowania wag sieci, oraz zbiór testujący używany przy obliczaniu zadanego błędu dopasowania.

Korzystanie z dużej liczby neuronów w warstwach ukrytych, czyli w 2 i 3 warstwie perceptronowej.

Wylosowanie bardzo małych wartości startowych dla wag.

Ustalenie małej, czyli spowalniającej optymalizację, wartości współczynnika uczenia.

Systematyczne obliczanie zadanego błędu dopasowania i zatrzymanie procesu gdy jego wartość zacznie rosnąć.

Operacja krzyzowania:

W sensie systemu decyzyjnego jest mechanizmem polegajacym na wytwarzaniu z

pewnych ustalonych czesci dwóch losowych obiektów nowego obiektu potomnego.

W naszym cwiczeniu przyjmujemy, ze operacja krzyzowania jest postaci,

Dzielimy dwa losowe obiekty systemu decyzyjnego na czesci,

1 2 3 8 1 5 1

5 4 2 1 7 8 2

i wytwarzamy z nich dwa obiekty potomne postaci,

1 2 3 1 7 8 1

5 4 2 8 1 5 2

Operacja mutacji:

Przyjmujemy, ze mutacja obiektów to zamiana miejscami losowych atrybutów pary

losowych obiektów. Przyjmijmy, ze wylosowalismy dwa obiekty postaci

1 2 3 8 1 5 1

5 4 2 1 7 8 2

wylosowalismy atrybut numer 3 i zamieniamy miejscami wartosci 3 oraz 2 otrzymujac

obiekty,

1 2 2 8 1 5 1

5 4 3 1 7 8 2

Operacje krzyzowania i mutacji stosowane sa z mysla utworzenia obiektów potomnych

w systemie decyzyjnym treningowym o cechach lepszych od obiektów pierwotnych

w sensie lepszej efektywnosci w klasyfikacji danych testowych.

9) Algorytm propagacji wstecznej błedu (trzy etapy w szczegółach).

Algorytm wstecznej propagacji błędów

Jest to podstawowy algorytm uczenia nadzorowanego wielowarstwowych jednokierunkowych sieci neuronowych. Podaje on przepis na zmianę wag wij dowolnych połączeń elementów przetwarzających rozmieszczonych w sąsiednich warstwach sieci. Oparty jest on na minimalizacji sumy kwadratów błędów uczenia z wykorzystaniem optymalizacyjnej metody największego spadku. Dzięki zastosowaniu specyficznego sposobu propagowania błędów uczenia sieci powstałych na jej wyjściu, tj. przesyłania ich od warstwy wyjściowej do wejściowej, algorytm propagacji wstecznej stał się jednym z najskuteczniejszych algorytmów uczenia sieci.

Zgodnie z algorytmem wstecznej propagacji błędu w każdym cyklu uczącym wyróżnia się następujące etapy uczenia:

- Analiza sieci neuronowej o zwykłym kierunku przepływu sygnałów. W wyniku takiej analizy otrzymuje się wartości sygnałów wyjściowych neuronów warstw ukrytych oraz warstwy wyjściowe a także odpowiednie pochodne funkcji aktywacji w poszczególnych warstwach.

- Utworzenie sieci propagacji wstecznej przez odwrócenie kierunków przepływu sygnałów, zastąpienie funkcji aktywacji przez ich pochodne, a także podanie do byłego wyjścia (obecnie wejścia) sieci wymuszenia w postaci odpowiedniej różnicy między wartością aktualną i żądaną. Dla tak utworzonej sieci należy obliczyć wartości odpowiednich różnic wstecznych.

- Adaptacja wag (uczenie sieci) odbywa się na podstawie wyników uzyskanych w punkcie pierwszym i drugim dla sieci zwykłej i sieci o propagacji wstecznej według odpowiednich wzorów.

Cały proces należy powtórzyć dla wszystkich wzorców uczących, kontynuując go do chwili spełnienia warunku zatrzymania algorytmu. Działanie algorytmu kończy się w momencie, gdy norma gradientu spadnie poniżej pewnej wartości określającej dokładność procesu uczenia.