WSTĘP

Samoorganizująca się mapa jest skutecznym i bardzo popularnym narzędziem do grupowania i wizualizacji danych. Dzięki tej metodzie próbki wejściowe są rzutowane na przestrzeń o małych wymiarach, zachowując jednocześnie ich topologię. Próbki są opisane zestawem cech. Przestrzenią wejściową jest zazwyczaj przestrzeń wielowymiarowa R^d. Do wizualizacji w przestrzeni niskowymiarowej (2 lub 3) bardzo często wykorzystywane są mapy 2D lub 3D. W przypadku wielu zastosowań, zwykle w psychologii, biologii, genetyce, przetwarzaniu obrazu i sygnałów, taki opis wektorowy nie jest dostępny; dostarczane są tylko dane dotyczące odmienności parami. Na przykład zastosowania w eksploracji tekstu lub eksploracji ADN są bardzo ważne w tej dziedzinie, a obserwacje są zwykle opisywane poprzez ich odległości wyrażone jako odległości "Levenshteina" lub "String Edit" . Pierwsze podejście polega na przekształceniu macierzy odmienności w prawdziwą euklidesową macierz odległości. Prostą strategią jest użycie technik "skalowania wielowymiarowego" aby zapewnić przestrzeń cech. Zatem można w naturalny sposób zastosować algorytm wektora początkowego SOM. Jeśli ta transformacja wiąże się z dużymi zniekształceniami, początkowy model wektorowy dla SOM przestaje być ważny, a analiza danych dotyczących odmienności wymaga specyficznych technik , a mapa samoorganizująca się odmienności (DSOM) jest nowa. W związku z tym rośnie zainteresowanie adaptacją Mapy Samoorganizującej się (SOM) do danych dotyczących odmienności. W ciągu ostatniej dekady pojawiły się różne propozycje rozszerzenia wektorowego modelu SOM na dane dotyczące odmienności parami. Główną motywacją jest radzenie sobie z dużymi bazami danych zbliżeniowych do eksploracji danych. W tym artykule prezentujemy nową adaptację algorytmu SOM, którą porównujemy z dwoma istniejącymi.

TŁO

Zasadniczo istnieją dwa główne podejścia do rozszerzenia SOM dotyczące danych dotyczących odmienności. W pierwszym z nich zastosowano ramy probabilistyczne, jak na przykład Graepel i Obermayer (1999), gdzie topograficzne mapowanie bliskości uzyskuje się poprzez symulowane wyżarzanie. Drugie podejście wykorzystuje bezpośrednio początkową strukturę SOM w celu dostosowania dwóch zwykłych kroków (afektu, reprezentacji) do danych dotyczących odmienności, jak na przykład u Kohonena i Somervuo , u El Golli, Conan-Guez i Rossi oraz u Ambroise i Govaert. Nasza praca inspirowana jest tym ostatnim podejściem i porównaliśmy naszą propozycję z algorytmami zaproponowanymi przez Kohonena oraz El Golli . Do porównania wykorzystywane są trzy metryki oceny jakości (kwantyzacja i sąsiedztwo). Doświadczenia numeryczne na danych sztucznych i rzeczywistych pokazują jakość algorytmu. Mocną stroną proponowanego algorytmu jest dokładniejsze oszacowanie prototypu, co jest jedną z najtrudniejszych części algorytmów Dissimilarity SOM. Główną trudnością DSOM jest ograniczenie reprezentacji danych wyjściowych. Dla (wektorowego) algorytmu SOM istnieje ukryty model danych dla każdego prototypu wyjściowego (rozkład sferyczny, którego prototypem jest środek ciężkości). W przypadku DSOM nie ma modelu danych dla każdego prototypu wyjściowego. Jedna obserwacja referencyjna jest wyraźnie powiązana z każdym prototypem wyjściowym, zamiast jego dostrajania poprzez przetwarzanie w centrum barykady. Odniesienie to jest zwykle wybierane spośród obserwacji wejściowych na końcu procesu optymalizacji. W rezultacie kilka prototypów może niestety mieć ten sam desygnat, a kolizje te powodują duże zniekształcenia mapy wyjściowej. Aby uniknąć tej trudności, proponujemy tutaj ukryte odniesienie dla każdego prototypu, które jest dostosowywane podczas iteracji szkoleniowych. Dzięki temu nie dochodzi do kolizji w fazie uczenia się, co w konsekwencji znacznie poprawia jakość projekcji.

ADAPTACJA SOM DO DANYCH O RÓŻNICY

W artykule przedstawiono nowy algorytm DSOM dla danych dotyczących odmienności. Najpierw zaprezentujemy algorytmy DSOM, które zostały bezpośrednio wyprowadzone z początkowej struktury SOM. W kolejnych częściach szczegółowo przedstawimy proponowany przez nas algorytm oraz kilka eksperymentów mających wykazać jego skuteczność w porównaniu z innymi algorytmami DSOM.

Opis algorytmów DSOM

Zasadniczo punktem wyjścia algorytmu DSOM jest algorytm "wsadowy" wektora początkowego SOM. Przypomnijmy sobie ten algorytm "wsadowy". W każdej iteracji prezentowany jest cały zbiór danych. Rozważamy zbiór danych X składający się z N obserwacji, X = {o_i, i = 1..N}. SOM jest skonfigurowany z węzłami C (neuronami) a priori połączonymi ze sobą mapą wyjściową, gdzie δ(c,l) to odległość pomiędzy węzłami c i l. W iteracji t każdy węzeł jest reprezentowany przez prototyp ω_c^t w przestrzeni wejściowej. Po etapie inicjalizacji w każdej iteracji przetwarzane są sekwencyjnie etap afektacji i etap reprezentacji. Rolą tego pierwszego jest przypisanie każdej obserwacji o_i najlepiej pasującej jednostki ω_c*^t , zgodnie z odległością euklidesową. Funkcja afektacji to:



W ten sposób realizowany jest podział całego zbioru danych. W tym drugim przypadku prototyp ω_c jest dostosowywany tak, aby jak najlepiej reprezentował każdą partycję X_c. Prototyp ten jest obliczany jako średnia ważona próbek wejściowych. Wagi są oceniane na podstawie sąsiedztwa funkcja h^T(⋅), która jest nierosnącą funkcją odległości na mapie i sterowana jest malejącym w czasie parametrem promienia T(t). Ostatecznie prototypem ?c jest środek ciężkości przegrody X_c. Tego etapu reprezentacji nie można bezpośrednio przenieść na dane dotyczące odmienności. Alternatywną implementacją jest aproksymacja prototypów C za pomocą obserwacji referencyjnych należących do początkowego zbioru danych X. Następnie ten krok staje się bardzo czasochłonny: wszystkie obserwacje wejściowe są kandydatami i muszą zostać ocenione. Zaproponowano pewne strategie mające na celu skrócenie czasu obliczeń . Zauważmy D = [d_ij] i, j = 1..N, dane dotyczące odmienności. Te różnice opisują przestrzeń niemetryczną. Jednakże rozważamy wszystkie algorytmy DSOM symetryczne różnice. W przypadku DSOM zaproponowanego przez Kohonena każdy prototyp będzie reprezentowany przez jedną obserwację referencyjną, ω_c = lub o_r(c). Na etapie inicjalizacji C obserwacje w wejściowym zbiorze danych są losowo przypisywane do prototypów. Na etapie afektacji funkcja afektacji wykorzystuje po prostu wejściowe dane dotyczące odmienności. Każda obserwacja jest przypisana do najbliższego prototypu:



Na etapie reprezentacji prototypowi ω_c przypisuje się nową obserwację lub o_r(c), minimalizując następującą funkcję kosztu:



gdzie E(c, j) jest ważonym zniekształceniem lokalnym, jeśli o_j jest desygnatem prototypu ω_c:



Globalna funkcja kosztu, która jest następnie minimalizowana, to globalne zniekształcenie wszystkich prototypów:



Na etapie reprezentacji możliwe są różne warianty. Funkcja sąsiedztwa w równaniu (4) można po prostu zintegrować po sąsiedztwie prototypu (wyszukiwanie odbywa się po połączeniu partycji w sąsiedztwie wyjściowym), a nie po różnicach ważonych. Jest to "wyszukiwanie ustawionej średniej". Również wykładnik "2" w równaniu. (4) można pominąć: jest to "ustawione wyszukiwanie mediany". Różne prototypy mogą mieć ten sam desygnat (kolizja), gdy przeszukiwanie obserwacji referencyjnych ogranicza się do obserwacji wejściowych. Zatem istnieje niejednoznaczność dotycząca etapu uczucia w następnej iteracji. To jest główna trudność tego podejścia. W niektórych zastosowaniach, na przykład przy organizacji ciągów symboli, możliwe jest przeszukiwanie "mediany" lub "średniej" poza zbiorem początkowym: odniesienia w DSOM niekoniecznie są reprezentowane przez elementy należące do przestrzeni wejściowej. Ale ta optymalizacja jest problemem NP-trudnym. Teoretycznym zainteresowaniem tego podejścia jest możliwość przedstawienia prototypu za pomocą więcej niż jednej obserwacji referencyjnej (q ≥ 1). Pozwala to uwzględnić bardziej złożoną strukturę danych ukrytych (na przykład dystrybucję multimodalną) dla każdej partycji. Niestety w praktyce jest to trudne wybierz liczbę (q) referencji według prototypu, a etap optymalizacji stanie się jeszcze bardziej czasochłonny. Opiszmy tutaj algorytm dla q = 1. Dla etapu afektacji odległość pomiędzy obserwacją a prototypem jest zdefiniowana w równaniu (6). Kiedy sąsiedztwo się zmniejsza, odległość ta zbiega się ku początkowej odmienności. Etap reprezentacji jest taki sam jak poprzednio. W przypadku zbieżności te dwa algorytmy są podobne.



Ambroise i Govaert (1996) proponują odmienne podejście inspirowane algorytmem SEM (Stochastyczna Maksymalizacja Oczekiwań). Etapem reprezentacji jest "ustawianie wyszukiwania mediany". Etap przypisywania wykorzystuje proces stochastyczny, aby wpłynąć na każdą obserwację prototypy przez rozkład wielomianowy (proporcje zależą od funkcji sąsiedztwa i wpływu na prototypy).

Opis proponowanego algorytmu DSOM

Jak wyjaśniono wcześniej, trudnością jest etap reprezentacji ze względu na brak modelu danych. Zbiór kandydatów na referencje jest skończony i jeśli kilka prototypów ma ten sam desygnat, pojawiają się zniekształcenia. Aby przezwyciężyć tę sytuację, proponujemy krok reprezentacji ukrytej. Zauważmy, że podczas uczenia i do czasu zbieżności obserwacja referencyjna służy jedynie do określenia odległości pomiędzy prototypem a obserwacją wejściową. Zatem zdefiniujemy miarę bliskości D^T(o_i,ω_c) bez wyraźnego odniesienia do prototypu ω_c. Faza reprezentacji po prostu dostosuje tę bliskość, biorąc pod uwagę nowy podział obserwacji i aktualizacja funkcji sąsiedztwa. Ta prosta implementacja ma swój odpowiednik: konieczne jest zdefiniowanie modelu danych w oparciu o ukryte założenia euklidesowe. Rozważmy zbiór X próbek wektorowych, X = {x_i, i = 1..N, x_i ∈ R^d}. Niech g będzie środkiem ciężkości X iI(X), jego bezwładność:



Wszystkie próbki mają tę samą jednolitą masę (1/N). Bezwładność względem dowolnej obserwacji e jest następnie definiowana i rozkładana dzięki twierdzeniu Huygensa:



Co więcej, I(X) można obliczyć, biorąc pod uwagę wszystkie odległości d(x_i, x_j):



Zatem przy hipotezie euklidesowej nie ma potrzeby znajomości środka ciężkości g, aby obliczyć odległość dowolnej obserwacji e do tego środka ciężkości: d²(g,e) = I(X,e) - I(X). Zasadę tę stosujemy do danych dotyczących odmienności. Dane wejściowe są zauważane o_i zamiast x_i dla danych wektorowych. Ten sam wzór uogólniono na niejednorodne obserwacje ważone. Rozważmy jedną partycję X_c powiązaną z prototypem ω_c po etapie afektacji. Następnie definiuje się bliskość obserwacji o_i do prototypu ω_c, stosując wagi m_j/c dla każdej obserwacji o_j, biorąc pod uwagę prototyp ω_c. Bezwładność I(X_c) jest oceniana po wszystkich ważonych różnicach:



Dlatego algorytm jest następujący:

o Etap inicjalizacji: Posiadanie początkowego podziału, X_c, c = 1..C, na przykład z afektacją z początkowego losowego zbioru obserwacji referencyjnych.
o Krok reprezentacji: Dla wszystkich prototypów ω_c i obserwacji o_i oblicz wagi m_i/c w równaniu (9) i bezwładność I(X_c) w równaniu (10), zaktualizuj funkcję sąsiedztwa dla następnej iteracji.
o Krok afektacji: Wpływaj każdą obserwacją na prototyp ?_f(i) zgodnie z minimalną odległością z równania (9):



Krok reprezentacji i etap afektacji są obliczane sekwencyjnie aż do zbieżności. Parametry uczenia malejącej funkcji sąsiedztwa są zgodne ze zwykłymi zaleceniami dla algorytmów SOM: szybkie, a następnie powolne zmniejszanie. W przypadku zbieżności, jeśli jest to konieczne do wizualizacji ostatecznej mapy, obserwację referencyjną można powiązać z każdym prototypem, na przykład zgodnie z "ustawionym wyszukiwaniem średniej" (lub ustawioną medianą) lub "wyszukiwaniem średniej" (lub medianą). Poniżej porównamy trzy DSOM w naszej propozycji nazywane odpowiednio DSOM(K), DSOM(EG) i DSOM. Aby porównać podejścia "ustaw średnią" i "ustaw medianę" dla trzech algorytmów, d²(o_i, o_j) zostanie zastąpione przez d^γ(o_i, o_j): "ustaw medianę" odpowiada γ = 1, a "ustaw średnią" γ = 2. Testowane będą również różne wartości mocy γ. Do macierzy odmienności można zastosować inne transformacje, aby przekształcić ją w macierz odległości, na przykład poprzez dodanie stałej lub połączenie obu . Metoda "dodawania stałej" powoduje duże zniekształcenia początkowych danych dotyczących odmienności. Nasze eksperymenty to potwierdzają. Lepsze rezultaty daje metoda "na siłę". Jeśli chodzi o czas obliczeń, te DSOM algorytmy są równoważne, ale przyczyny są różne. W przypadku DSOM(K) i DSOM(EG) etap reprezentacji jest najbardziej czasochłonny ze względu na optymalizację dla każdego referenta. W naszej propozycji optymalizacja ta jest ukryta, ale krok ten pozostaje czasochłonny ze względu na obliczenie wag m_i/c i bezwładności I(X_c).

Metodologia .Opis eksperymentu

Do oceny 3 algorytmów DSOM zostaną użyte dwie metryki. Pierwszym z nich jest klasyczny błąd kwantyzacji (E_g). Drugi dotyczy zachowania topologii. Spośród istniejących kryteriów wybraliśmy dwie miary w równaniu (11) kompatybilne z danymi o odmienności: "wiarygodność" (M₁) i "ciągłość" (M₂) . Wiarygodność odnosi się do błędu powodowanego przez nowe obserwacje w sąsiedztwie wyjściowym, podczas gdy nie znajdują się one w sąsiedztwie wejściowym; odwrotnie, jeśli chodzi o ciągłość. M₁ i M₂ są oceniane w funkcji liczby (k) najbliższych sąsiadów i normalizowane w zakresie od 0 do 1. Dla wizualizacji według Venny i Kaskiego wiarygodność jest ważniejsza niż ciągłość. Im większe M₁(k) i M₂(k), tym lepsza jakość projekcji. Obliczamy także całkę M_i(k) aż do otoczenia obejmującego 10% całych próbek: te wartości mierzą jakość zachowania lokalnej topologii.



Przy o zbiorach k pierwszych sąsiadów o_i w przestrzeni wejściowej, przestrzeni wyjściowej;



szeregi o_j w sąsiedztwie o_i w przestrzeni wejściowej, przestrzeni wyjściowej. Wykorzystywane są trzy bazy danych. Pierwszy z nich to sztuczny ataset: 100 jednolitych próbek w R², dane dotyczące odmienności to dokładna odległość euklidesowa, parametr konfiguracyjny γ jest ustawiony na 2. Drugi to "Chicken Silhouette" . Dane te obejmują 446 próbek (obrazy binarne części kurczaka) sklasyfikowanych w 5 klasach. Macierz odległości obliczana jest zgodnie z "AngleCostFunction" (Barbara Spillmann, 2004) w oparciu o lokalną orientację konturów próbki. Trzeci zbiór danych jest większy. Jest wyodrębniany z list słów SCOWL . Po pewnej redukcji form liczby mnogiej i dzierżawczej z małego słownika angielskiego, zbiór danych składa się z 2000 słów. Następnie do obliczenia różnic między parami wykorzystuje się odległość Levenshteina .

Wyniki

Na sztucznym zbiorze danych działanie trzech algorytmów jest bardzo podobne . W przypadku wektora SOM wyniki są identyczne. Mapa jest sześciokątna z siatką neuronów 5 x 5. Zgodnie z oczekiwaniami zachowanie trzech algorytmów różni się od rzeczywistych zbiorów danych. W przypadku baz danych "Chicken" mapa ma kształt sześciokątny z siatką neuronów 7 x 7. DSOM prezentuje najlepsze zachowanie topologii według M₁(k) i M₂(k) oraz najlepszy kompromis pomiędzy kwantyzacją a zachowaniem topologii. Zmieniając ?, obserwujemy ewolucję tych kryteriów. Zauważamy, że każdy algorytm ma inną wartość mocy optymalnej γ: γ = 1 dla DSOM(K), γ = 1,5 dla DSOM(EG), γ = 3 dla DSOM. Jednakże γ = 1 można uznać za najlepszy kompromis dla trzech algorytmów i zostanie ono wykorzystane do prezentacji wyników. Rysunek 2 przedstawia prototypy wszystkich węzłów dla DSOM.



Sąsiednie węzły mają podobne prototypy. Mapa jest zorganizowana tak, aby jak najlepiej uwzględniać dane pogrupowane w 5 klas. W przypadku trzeciego zbioru danych zastosowano mapę sześciokątną z siatką neuronów 12 x x12. Wnioski są takie same.
PRZYSZŁE TENDENCJE

Zaproponowany algorytm opiera się na obliczeniu "pseudo" środka ciężkości dla każdego prototypu. Obliczenia te uzasadnia się założeniem istnienia ukrytej przestrzeni euklidesowej. Oznacza to, że dane dotyczące odmienności muszą być izometryczne w stosunku do normy L2. W praktyce wymóg ten jest bardzo rzadko ściśle sprawdzany i często wystarczające jest przybliżenie. Dlatego, aby całkowicie zweryfikować ten nowy DSOM, konieczne jest przetestowanie go z większą liczbą innych typów danych i większymi bazami danych posiadającymi "podstawową prawdę". Organizacja danych jest interpretowana po rzucie na ostateczną mapę, a sąsiedztwo na mapie wyjściowej musi ujawnić główne ukryte właściwości obserwacji, które muszą być zgodne z "podstawową prawdą".

WNIOSEK

W artykule przedstawiono nowy algorytm afektywny dla DSOM. Dzięki kryteriom wiarygodności i ciągłości ten DSOM zapewnia dobre zachowanie topologii. Głównym powodem tego ulepszenia jest etap reprezentacji, w którym możliwe jest ciągłe dostosowywanie odniesienia każdego prototypu, podobnie jak w przypadku modelu wektorowego. Aby to osiągnąć, na etapie reprezentacji używamy ukrytego odniesienia dzięki twierdzeniu Huygensa. Nawet jeśli założenia euklidesowe nie zostaną dokładnie zweryfikowane w praktyce, zniekształcenia wynikające z tego niedopasowania są w rzeczywistości mniej istotne niż te, które powstały przy efekcie kolizji, co jest trudnym problemem dla klasycznych algorytmów DSOM. Efektywność ta jest reprezentowana w tym artykule przez lepszą wydajność zaproponowanego algorytmu w porównaniu z innymi

WSTĘP

Konwencjonalnie modelowanie i symulacja złożonych systemów nieliniowych polegała na budowaniu modelu matematycznego i badaniu ewolucji systemu lub jego sterowania. Takie podejście może zawieść w przypadku wielu bardzo dużych systemów nieliniowych i złożonych, które są obecnie badane. Wraz z wynalezieniem nowych, zaawansowanych komputerów o dużej szybkości i zastosowaniem paradygmatów sztucznej inteligencji, pojawiły się nowe techniki. W szczególności sieci neuronowe i logika rozmyta do modelowania nieliniowego oraz algorytmy genetyczne i algorytmy ewolucyjne do metod optymalizacji stworzyły nowe możliwości rozwiązywania systemów złożonych . W niniejszym artykule rozważane są zagadnienia związane z projektowaniem wielowarstwowych i hierarchicznych systemów logiki rozmytej. Zaproponowano technikę dekompozycji systemów złożonych na hierarchiczne i wielowarstwowe podsystemy logiki rozmytej. Uczenie się reguł rozmytych i parametrów wewnętrznych w sposób nadzorowany odbywa się za pomocą algorytmów genetycznych. Rozkład złożonych systemów nieliniowych na hierarchiczne i wielowarstwowe podsystemy logiki rozmytej znacznie zmniejsza liczbę definiowanych reguł rozmytych i poprawia szybkość uczenia się takich systemów. W niniejszym artykule opisano również metodę łączenia podsystemów w celu utworzenia hierarchicznego i wielowarstwowego systemu logiki rozmytej. Rozważane obszary zastosowań to: prognozowanie stopy procentowej, stopy bezrobocia oraz prognozowanie zużycia energii elektrycznej. Algorytmy genetyczne mogą być wykorzystywane jako narzędzie do projektowania i generowania reguł rozmytych dla systemu logiki rozmytej. To automatyczne projektowanie i generowanie reguł rozmytych za pomocą algorytmów genetycznych można podzielić na dwie techniki uczenia się, a mianowicie nadzorowaną i nienadzorowaną. W uczeniu nadzorowanym występują dwie odrębne fazy. W pierwszej fazie każdy osobnik jest oceniany na podstawie sygnału wejściowego, który jest propagowany w systemie, generując odpowiedź wyjściową. Rzeczywista wygenerowana odpowiedź jest następnie porównywana z odpowiedzią pożądaną, generując sygnały błędów, które następnie są wykorzystywane jako dopasowanie osobnika w populacji algorytmów genetycznych. Uczenie nadzorowane zostało z powodzeniem zastosowane do rozwiązania niektórych trudnych problemów. W niniejszym artykule rozważa się zaprojektowanie i rozwój uczenia nadzorowanego opartego na algorytmie genetycznym dla modeli rozmytych z zastosowaniem do kilku problemów. Hybrydowa zintegrowana architektura łącząca logikę rozmytą i algorytm genetyczny może generować reguły rozmyte, które mogą być wykorzystywane w systemach logiki rozmytej do modelowania, sterowania i predykcji. Systemy logiki rozmytej zwykle mają bazę wiedzy składającą się ze zbioru reguł w postaci If (x₁ is A₁ ′ and x₂ is A₂ ′ and … and x_n is A_n ′) Then (z₁ is B₁ ′^l else z₂ is B₂ ′L^l else … else z_m is B_m ′^l) gdzie A_k′^l ;k = 1, …, n są znormalizowanymi zbiorami rozmytymi dla n zmiennych wejściowych x_k , k = 1 ;…, n, a gdzie B_k ′^l , k ; k = 1, …, m są znormalizowanymi zbiorami rozmytymi dla m zmiennych wyjściowych z_k , k = 1, … ,m. Sercem systemu logiki rozmytej jest silnik wnioskowania, który stosuje zasady inteligentnego ludzkiego rozumowania do interpretowania reguł w celu wyprowadzenia działania z danych wejściowych. W literaturze istnieje wiele typów silników wnioskowania, w tym popularny silnik wnioskowania Mamdaniego. Biorąc pod uwagę bazę reguł rozmytych z M regułami i n zmiennymi poprzednimi, regulator rozmyty, jak podano w Równaniu 1, wykorzystuje fuzzifikator singletonowy, silnik wnioskowania iloczynowego Mamdaniego i defuzzifikator średniej centralnej do wyznaczania zmiennych wyjściowych, ma ogólną postać dla pojedynczej zmiennej wyjściowej, np. z₁.



gdzie y^l_k są środkami zbiorów wyjściowych B^l_k, a funkcja przynależności μ definiuje dla każdego zbioru rozmytego A^l_i wartość x_i w zbiorze rozmytym, mianowicie μ Aⁱ₁ x_i . Typowe kształty funkcji przynależności to zazwyczaj trójkątny, trapezowy i gaussowski. Pierwszym krokiem w konstrukcji systemu logiki rozmytej jest określenie,które zmienne są fundamentalnie ważne. Wiadomo, że całkowita liczba reguł w systemie jest funkcją wykładniczą liczby zmiennych systemowych. Aby zaprojektować system rozmyty o wymaganej dokładności, liczba reguł rośnie wykładniczo wraz z liczbą zmiennych wejściowych i powiązanych z nimi zbiorów rozmytych w systemie rozmytym. Sposób na uniknięcie eksplozji baz reguł rozmytych w systemie rozmytym W systemach logicznych rozmytych należy rozważyć hierarchiczne systemy logiki rozmytej .Hierarchiczne systemy logiki rozmytej mają tę właściwość, że liczba reguł potrzebnych do ich zbudowania rośnie liniowo wraz z liczbą zmiennych w systemie. Idea hierarchicznych systemów logiki rozmytej polega na umieszczeniu zmiennych wejściowych w zbiorze niskowymiarowych systemów logiki rozmytej, zamiast tworzenia pojedynczej, wysokowymiarowej bazy reguł dla systemu logiki rozmytej. Każdy niskowymiarowy system logiki rozmytej stanowi poziom w hierarchicznym systemie logiki rozmytej. Załóżmy, że istnieje n zmiennych wejściowych x₁,…,x_n, wówczas hierarchiczny system logiki rozmytej konstruuje się w następujący sposób

o Baza reguł rozmytych pierwszego poziomu dla systemu rozmytego z n₁ zmiennymi wejściowymi x₁,…,x_n, która jest konstruowana z reguł

Jeśli x₁ jest równe A^t₁ i … i x_n to A^t_n1 , wtedy y₁ to B^l₁ gdzie 2 ≤ n₁≤ n, i l = 1,2,…, M₁.
o Baza reguł rozmytych i-tego poziomu (i > 1) dla układu rozmytego z n_i + 1 (n_i≥ 1) zmiennymi wejściowymi, która jest konstruowana z reguł

Jeśli x_Ni+1 to A_Ni+ i … a A^l_Nni i y_i-1. Wtedy y_i to B_i^l

gdzie



i l =1,2,…M_i

o Konstrukcja baz reguł rozmytych dla układów rozmytych jest kontynuowana, aż i = l takie, że



czyli dopóki wszystkie zmienne wejściowe nie zostaną użyte w jednej z poziomów. Pierwszy poziom ma n₁ zmiennych wejściowych x₁,…,x_n z jedną zmienną wyjściową y₁, która jest następnie przesyłana do drugiego poziomu x jako dane wejściowe. Na drugim poziomie kolejne n₂ zmiennych x_ni+1,…x_n1+n2 oraz zmienna y₁ są łączone, aby wygenerować zmienną wyjściową y₂, która jest następnie przesyłana do trzeciego poziomu. Ta procedura jest kontynuowana, aż wszystkie zmienne x₁,…,x_n zostaną wykorzystane . Liczba reguł w hierarchicznym systemie logiki rozmytej jest funkcją liniową liczby zmiennych wejściowych i powiązanych z nimi zbiorów rozmytych . Inne sposoby redukcji reguł rozmytych w systemie logiki rozmytej to:

1. Scalanie zmiennych przed wprowadzeniem ich do silnika wnioskowania, co zmniejsza liczbę reguł w bazie wiedzy,
2. Grupowanie reguł w priorytetyzowane poziomy w celu zaprojektowania struktur hierarchicznych lub wielowarstwowych,
3. Bezpośrednie zmniejszenie rozmiaru silnika wnioskowania poprzez wykorzystanie koncepcji pasywnego rozkładu relacji rozmytych,
4. Rozłożenie systemu na skończoną liczbę podsystemów zredukowanego rzędu, co eliminuje potrzebę stosowania silnika wnioskowania o dużej pojemności.
5. Zmniejszenie liczby zbiorów rozmytych każdej zmiennej wejściowej, co zmniejsza liczbę reguł w bazie wiedzy systemu logiki rozmytej. W przypadku hierarchicznych systemów logiki rozmytej, parametry o największym wpływie są zazwyczaj wybierane jako zmienne systemowe na pierwszym poziomie, kolejne najważniejsze parametry są wybierane jako zmienne systemowe na drugim poziomie itd. W tej hierarchii pierwszy poziom daje przybliżony wynik, który jest następnie modyfikowany przez zestaw reguł drugiego poziomu. Tę procedurę można powtarzać na kolejnych poziomach hierarchii. Liczba reguł w kompletnym zestawie reguł jest więc zredukowana do funkcji liniowej liczby zmiennych, ale liczba ta może być nadal wysoka. Ponadto, biorąc pod uwagę istnienie różnych struktur hierarchicznych i wielowarstwowych, w jaki sposób można skutecznie nauczyć się rozmytej bazy wiedzy i powiązanych parametrów w każdej warstwie? W niniejszym artykule omówiono podejście uczenia się oparte na algorytmach genetycznych, służące do określania tych baz wiedzy i powiązanych parametrów.

WYBÓR ZMIENNYCH, NAUKA BAZY REGUŁ I ROZKŁAD

Prognozowanie stóp procentowych

W [Kingham, M., Mohammadian, M. i Stonier, R. J. (1998)] autorzy wykorzystali hierarchiczne struktury logiki rozmytej i wielowarstwowe struktury sieci neuronowych do modelowania i prognozowania australijskiej stopy procentowej z 14 zmiennymi wejściowymi, na podstawie rzeczywistych danych kluczowychwskaźników ekonomicznych, które stanowiły ograniczony zbiór danych. Wykorzystując wiedzę ekspercką ekonomisty, wybrano następujące zmienne wejściowe i podzielono je na 5 różnych grup:

1. Zatrudnienie (Wakaty, Stopa bezrobocia)
2. Kraj (Produkt krajowy brutto, Wskaźnik cen konsumpcyjnych)
3. Oszczędności (Wskaźnik oszczędności gospodarstw domowych, Kredyty hipoteczne, Średnie tygodniowe zarobki)
4. Zagranica (Rachunek bieżący, Wskaźnik RBA, Wskaźnik ważony handlem)
5. Firma (Wskaźnik całego przemysłu, Zysk firmy, Nowe pojazdy silnikowe)

które następnie utworzono w dwuwarstwowy system rozmyty.



Aktualna stopa procentowa została wprowadzona do każdego z pięciu systemów rozmytych w pierwszej warstwie, a ostatecznym wynikiem drugiej warstwy była przewidywana stopa procentowa. Zakłada się, że pierwsza warstwa daje pierwszą iterację nowej stopy procentowej i jest ona wprowadzana do drugiej warstwy. Jednak zmienne wyjściowe z pierwszej warstwy nie muszą być koniecznie utożsamiane ze stopą procentową. Zakładając, że istnieje pięć zbiorów przynależności dla wszystkich zmiennych, w tym tych wchodzących do drugiej warstwy, w tej strukturze znajduje się 5250 reguł rozmytych. Gdyby wszystkie czternaście zmiennych zostało wprowadzonych do jednowarstwowej struktury systemu logiki rozmytej, istniałoby około 6 milionów reguł (5¹⁶). W związku z tym następuje znaczna redukcja liczby reguł dla tej prostej, dwuwarstwowej hierarchicznej struktury systemu logiki rozmytej. Jest jednak oczywiste, że nie jest to jedyny rozkład, jaki mógł powstać w wyniku grupowania zmiennych lub liczby poziomów struktury wielowarstwowej. Do poznania reguł w tym systemie rozmytym wykorzystano algorytm genetyczny i stwierdzono, że hierarchiczna struktura systemu logiki rozmytej była poprawna .Nadal jednak pozostaje pytanie, czy dwuwarstwowa hierarchiczna struktura systemu logiki rozmytej zapewnia najlepsze rozwiązanie? Aby odpowiedzieć na to pytanie, można rozpocząć budowę trzy- lub czterowarstwowej hierarchicznej struktury systemu logiki rozmytej metodą prób i błędów, aby ewentualnie znaleźć odpowiednią liczbę wymaganych warstw. Może to być uciążliwe . Algorytmy genetyczne można wykorzystać do rozwiązania tego problemu, określając liczbę warstw w hierarchicznym systemie logiki rozmytej i prawidłową kombinację rozmytych baz wiedzy dla każdej warstwy. Algorytm genetyczny opracowano w taki sposób, aby zapewnić najlepszą możliwą architekturę do projektowania hierarchicznych systemów logiki rozmytej do przewidywania stóp procentowych w Australi. Wykorzystując wskaźniki ekonomiczne, opracowano pięć systemów logiki rozmytej, jak opisano powyżej. Algorytmy genetyczne wykorzystano następnie do zaprojektowania i opracowania hierarchicznego systemu logiki rozmytej. Opracowany hierarchiczny system logiki rozmytej został następnie wykorzystany do przewidywania stóp procentowych. Dla każdej z tych grup (jak opisano wcześniej) stopa procentowa bieżącego kwartału jest uwzględniana w używanych wskaźnikach. W celu kodowania i dekodowania hierarchicznego systemu logiki rozmytej, najpierw każdemu systemowi logiki rozmytej utworzonemu z grupy wskaźników przypisuje się liczbę. W tej symulacji liczba przypisana do każdej grupy jest pokazana poniżej: 1 = Zatrudnienie, 2 = Kraj, 3 = Oszczędności, 4 = Zagranica, 5 = Firma. Liczba warstw i systemów logiki rozmytej dla każdej warstwy jest określana przez algorytmy genetyczne. Algorytmy genetyczne losowo kodują każdy system logiki rozmytej na liczbę z zakresu od 1 do 5 dla wszystkich możliwych kombinacji systemów logiki rozmytej. Poziom w hierarchii, do którego przypisany jest system logiki rozmytej, jest również zakodowany w każdym ciągu reprezentującym jednostkę w populacji algorytmów genetycznych. Zakodowany w ten sposób ciąg znaków można przedstawić na Rysunku 3. Każdy pojedynczy ciąg znaków jest następnie dekodowany do hierarchicznego systemu logiki rozmytej, który definiuje system/systemy logiki rozmytej dla każdego poziomu hierarchicznego systemu logiki rozmytej. Powyższy ciąg znaków po zdekodowaniu będzie stanowił hierarchiczny system logiki rozmytej, jak pokazano na Rysunku 2. Zestaw hierarchicznych systemów logiki rozmytej opracowany w ten sposób jest oceniany, a każdemu ciągowi znaków przypisuje się wartość dopasowania. Definiujemy zadowalający hierarchiczny system logiki rozmytej jako taki, którego wartość dopasowania (przewidywana stopa procentowa) różni się od pożądanego wyniku systemu (w tym przypadku rzeczywistej stopy procentowej) o bardzo małą wartość. Obliczono średni błąd systemu dla zbioru treningowego i zbiorów testowych, korzystając z następującego wzoru



gdzie E to średni błąd, P_i to przewidywana stopa procentowa w okresie i, Ai to rzeczywista stopa procentowa dla kwartału, a n to liczba przewidywanych kwartałów. Zastosowanie algorytmów genetycznych do zaprojektowania i opracowania hierarchicznego systemu logiki rozmytej przyniosło dobre rezultaty. Hierarchiczne systemy logiki rozmytej opracowane z wykorzystaniem algorytmów genetycznych przewidują stopę procentową z różnym stopniem dokładności. Interesujące jest jednak to, że algorytmy genetyczne są w stanie zapewnić różne struktury hierarchicznych systemów logiki rozmytej do przewidywania stopy procentowej. Należy zauważyć, że algorytm genetyczny jest również w stanie znaleźć liczbę warstw w hierarchicznym systemie logiki rozmytej.

Prognozowanie stopy bezrobocia

Opracowano system logiki rozmytej do nadzorowanego uczenia się w celu prognozowania kwartalnej stopy bezrobocia w Australii. Następujące wskaźniki ekonomiczne zostały wykorzystane jako dane wejściowe do systemu logiki rozmytej.

o Stopa bezrobocia to odsetek siły roboczej aktywnie poszukującej pracy w kraju.
o Stopa procentowa, która jest wskaźnikiem, który chcemy prognozować. Użyta tutaj stopa procentowa to 10-letnie obligacje skarbowe rządu Wspólnoty Narodów Australii.
o Wolne miejsca pracy to stanowiska dostępne do natychmiastowego obsadzenia lub dla których podjęto działania rekrutacyjne.
o Współczynnik oszczędności gospodarstw domowych to stosunek dochodów gospodarstw domowych zaoszczędzonych do dochodów rozporządzalnych gospodarstw domowych.
Każde dane wejściowe podzielono na pięć zestawów reguł rozmytych, co daje łącznie 625 reguł. Reguły te tworzą bazę wiedzy systemu. Do znalezienia rozmytej bazy wiedzy dla systemu zastosowano strategię uczenia nadzorowanego z wykorzystaniem algorytmów genetycznych . Za pomocą symulacji wykazano, że system logiki rozmytej jest w stanie z dużym powodzeniem przewidywać kwartalną stopę bezrobocia. Uzyskane wyniki dowiodły, że strategia uczenia nadzorowanego precyzyjnie przewidywała wahania stopy bezrobocia, a wszelkie drobne błędy w prognozie można było zredukować poprzez zwiększenie danych treningowych i wydłużenie czasu działania algorytmu uczenia.

Prognozowanie obciążenia elektrycznego

Przedstawiono hierarchiczny system logiki rozmytej wykorzystujący algorytmy genetyczne do przewidywania i modelowania dziennych wahań obciążenia elektrycznego. System jest dodatkowo trenowany w celu modelowania i przewidywania zużycia energii elektrycznej w szczytowych okresach dobowych. Istnieje wiele możliwych wskaźników, które można by wykorzystać doprognozowania obciążenia elektrycznego. Wskaźniki użyte w tym hierarchicznym systemie logiki rozmytej to: obciążenie elektryczne (czyli poprzednie zużycie energii elektrycznej (godzinowo)), przewidywana temperatura minimalna to przewidywana temperatura minimalna, przewidywana temperatura maksymalna to przewidywana temperatura maksymalna, rzeczywista temperatura minimalna to rzeczywista przewidywana temperatura minimalna.

Rzeczywista temperatura maksymalna to rzeczywista przewidywana temperatura maksymalna.
Pora roku to jedna z czterech pór roku.
Dzień tygodnia to jeden z siedmiu dni tygodnia.
Święto to jedno z kilku świąt państwowych w roku. Pora dnia jest tutaj podzielona na 48 części, z których każda trwa 30 minut.

Bieżące obciążenie elektryczne jest uwzględniane we wskaźnikach wejściowych systemu, ponieważ przewidywane obciążenie elektryczne jest w dużym stopniu zależne od aktualnego natężenia prądu, a wahania obciążenia elektrycznego mogą wynikać jedynie z bieżącego obciążenia. Powiązane wskaźniki (wejścia) są zgrupowane ze względu na wspólne powiązania i relacje między nimi, takie jak temperatura, pora dnia itp. Grupy te są następujące:

Grupa przewidywanej temperatury - ta grupa zawiera obciążenie elektryczne, przewidywaną temperaturę minimalną, przewidywaną temperaturę maksymalną, porę dnia.
Grupa rzeczywistej temperatury - ta grupa zawiera obciążenie elektryczne, rzeczywistą temperaturę minimalną, rzeczywistą temperaturę maksymalną, porę dnia.
Grupa pory roku - ta grupa zawiera obciążenie elektryczne, porę roku (wartość od 1 do 4 reprezentującą każdą porę roku), dzień tygodnia (dwie wartości, jedna dla dni powszednich i zero reprezentujące weekend), święto (dwie wartości, jedna dla świąt i zero reprezentujące dni robocze), porę dnia.
Używając hierarchicznej struktury systemu logiki rozmytej, możliwe jest rozwiązanie tego problemu. Każda z trzech grup utworzonych do prognozowania obciążenia elektrycznego generuje prognozowane obciążenie elektryczne. Następnie są one przekazywane do kolejnej warstwy hierarchii, gdzie znajduje się ostateczne prognozowane obciążenie elektryczne . Całkowita liczba reguł dla hierarchicznego systemu logiki rozmytej wynosi 1455. Na podstawie wyników symulacji stwierdzono, że hierarchiczny system logiki rozmytej jest zdolny do dokładnego przewidywania obciążenia elektrycznego .

TRENDY NA PRZYSZŁOŚĆ

Grupowanie parametrów wejściowych rozpatrywanych powyżej systemów przeprowadzono z wykorzystaniem wiedzy eksperckiej. Interesujące byłoby wykorzystanie algorytmów genetycznych do określenia zależności między parametrami wejściowymi takich systemów i porównania uzyskanych w ten sposób wyników z grupowaniem parametrów sugerowanym przez eksperta.

WNIOSKI

W niniejszym artykule rozważane są zagadnienia związane z konstrukcją systemu logiki rozmytej do modelowania złożonego (nieliniowego) systemu, a mianowicie dekompozycja na hierarchiczne/wielowarstwowe podsystemy logiki rozmytej oraz uczenie się reguł rozmytych i parametrów wewnętrznych. Chociaż dekompozycja na hierarchiczne/wielowarstwowe podsystemy logiki rozmytej znacznie zmniejsza liczbę reguł rozmytych, które należy zdefiniować i nauczyć, pojawiają się inne problemy, takie jak niejednoznaczność dekompozycji i możliwość powstania zmiennych bez znaczenia fizycznego. W przypadku problemu z dużą liczbą zmiennych wejściowych, na przykład problemu prognozowania stóp procentowych, niejednoznaczność dekompozycji prowadzi do licznych różnych struktur do zbadania w celu znalezienia takiej, która w pewnym sensie jest "najlepszą" strukturą.

WSTĘP

Oprócz możliwości nawigacji z punktu początkowego do wyznaczonego celu i omijania wszystkich przeszkód statycznych i dynamicznych, robot mobilny musi posiadać dwie dodatkowe kompetencje: tworzenie map i lokalizację, aby być użytecznym. Robot mobilny pozyskuje informacje o swoim otoczeniu poprzez proces tworzenia map. Mapy dla robotów mobilnych są powszechnie podzielone na mapy siatki zajętości i mapy topologiczne. Mapy siatki zajętości mają na celu przedstawienie geometrycznych właściwości otoczenia. Mapowanie siatki zajętości zostało po raz pierwszy zaproponowane przez Elfesa w 1987 roku, a pomysł ten został opublikowany w jego rozprawie doktorskiej w 1989 roku. Mapowanie topologiczne zostało po raz pierwszy wprowadzone w 1985 roku jako alternatywa dla mapowania siatki zajętości przez R. Chatilę i J.-P. Laumond). Mapy topologiczne opisują łączność różnych lokalizacji w otoczeniu. Pozycja robota mobilnego musi być zawsze znana, aby mógł on nawigować i precyzyjnie tworzyć mapę. Jest to problem lokalizacji, który został po raz pierwszy opisany pod koniec lat 80. XX wieku przez R. Smitha. W tym artykule omówione zostaną niektóre kluczowe algorytmy tworzenia i lokalizacji map.

TŁO

Budowanie map to proces pozyskiwania informacji o otoczeniu za pomocą danych sensorycznych i przedstawiania uzyskanych informacji w formacie zrozumiałym dla robota. Uzyskana mapa otoczenia może być wykorzystana przez robota do poprawy jego wydajności w nawigacji. Lokalizacja to proces znajdowania pozycji robota w otoczeniu. Jest to prawdopodobnie najważniejsza kompetencja, jaką musi posiadać robot mobilny. Wynika to z faktu, że robot musi znać swoją pozycję w otoczeniu, zanim będzie mógł zaplanować ścieżkę do celu lub podążać zaplanowaną ścieżką do celu. W tym artykule omówiono dwa kluczowe algorytmy budowania map: siatkę zajętości i mapowanie topologiczne. Siatka zajętości i mapy topologiczne to dwie różne metodologie reprezentacji środowiska w pamięci robota. Omówiono również dwie kluczowe metody lokalizacji: lokalizację z filtrem Kalmana i filtrem cząsteczkowym.

BUDOWANIE MAP

Jak widać ze zintegrowanego algorytmu z części I artykułu, robot mobilny musi być w stanie pozyskiwać mapy nieznanego środowiska, aby osiągnąć wyższy poziom autonomii. Budowanie map to proces, w którym informacje sensoryczne o otoczeniu są dostarczane robotowi mobilnemu. W tej sekcji omówiono dwa kluczowe podejścia do budowania map: siatkę zajętości i mapowanie topologiczne.

Mapy zajętości-siatki

Mapy zajętości-siatki przedstawiają środowisko jako mozaikę komórek siatki. Każda z komórek siatki odpowiada obszarowi w środowisku fizycznym i zawiera wartość zajętości, która wskazuje prawdopodobieństwo, czy komórka jest zajęta, czy wolna. Wartość zajętości i-tej komórki siatki w bieżącym czasie t będzie oznaczona jako p_t,i. Należy zauważyć, że p_t,i musi mieścić się w zakresie od 0 do 1, zgodnie z aksjomatami prawdopodobieństwa. p_t,i = [0,0,5) wskazuje poziom ufności, że komórka jest pusta, gdzie 0 oznacza absolutną pewność, że komórka jest pusta. p_t,i= 0,5,1] wskazuje poziom ufności, że komórka jest zajęta, gdzie 1 oznacza absolutną pewność, że komórka jest zajęta. pp_t,i = 0,5 wskazuje, że komórka jest obszarem niezbadanym. Robot nie ma żadnej wiedzy o świecie, gdy został po raz pierwszy umieszczony w nieznanym środowisku. Dlatego intuicyjne jest ustawienie p_t,i = 0,5 dla wszystkich i w czasie t = 0. Mapa jest aktualizowana za pomocą reprezentacji logarytmicznych szans zajętości. Zaletą reprezentacji logarytmicznych szans jest to, że może uniknąć niestabilności numerycznych dla prawdopodobieństwa bliskiego 0 lub 1. i-ta komórka siatki, która przechwytuje linię widzenia czujnika, jest aktualizowana zgodnie z

I_t,i = I_t-1,i + I_sensor (1)

gdzie l_t-1,i to logarytm szans obliczony na podstawie wartości zajętości komórki w momencie t-1.



l_sensor = l_occ, jeśli komórka odpowiada pomiarowi czujnika, oraz l_sensor = l_free, jeśli zasięg do komórki jest krótszy niż zasięg czujnika. Pozostałe komórki na mapie pozostają niezmienione.



Rysunek 1(a) ilustruje proces aktualizacji mapy. Komórka odpowiadająca pomiarowi czujnika jest zaznaczona na czarno, a wszystkie komórki przechwytujące wiązkę pomiarową czujnika są zaznaczone na biało. Rysunek 1(b) przedstawia przypadek, w którym pomiar czujnika jest równy maksymalnemu zasięgowi czujnika, a l_sensor = l_free dla wszystkich komórek przechwytujących wiązkę czujnika. Dzieje się tak, ponieważ zakłada się, że żadna przeszkoda nie zostanie wykryta, jeśli pomiar czujnika jest równy maksymalnemu zasięgowi czujnika. Parametry l_occ i l_free są obliczane z



gdzie p_occ i p_free oznaczają prawdopodobieństwo, że pomiar czujnika prawidłowo wywnioskuje, czy komórka siatki jest zajęta, czy pusta. Suma tych dwóch prawdopodobieństw musi wynosić 1, a ich wartości zależą od dokładności czujnika. W przypadku dokładnego czujnika p_occ i p_freebędą miały wartości bliższe 1 i 0. Wartości p_occ i p_free muszą zostać określone eksperymentalnie i pozostać stałe w procesie tworzenia mapy. Wartość zajętości komórki siatki można łatwo odzyskać z



Rysunek 2 przedstawia mapę siatki zajętości korytarza wzdłuż bloku EA poziomu 3 na Wydziale Inżynierii Narodowego Uniwersytetu Singapuru (NUS), uzyskaną za pomocą dalmierza laserowego. Czarne obszary oznaczają przeszkody, białe obszary oznaczają wolną przestrzeń, a szare obszary oznaczają obszary niezbadane.



Mapy topologiczne

W przeciwieństwie do map siatki zajętości, mapy topologiczne nie próbują przedstawiać informacji geometrycznych o środowisku. Zamiast tego mapy topologiczne przedstawiają środowiska w postaci grafów. Przykład mapy topologicznej przedstawiono na rysunku 3.



Lista istotnych cech, takich jak ściany, narożniki, drzwi lub korytarze, jest reprezentowana jako węzły m_i, a łączność między sąsiednimi cechami jako krawędzie u_jk. Na wielu mapach topologicznych odległości między sąsiednimi cechami są również reprezentowane przez krawędzie łączące węzły. Sukces map topologicznych w dużej mierze zależy od wydajności ekstrakcji cech. Mapy topologiczne są lepszym wyborem do mapowania, jeśli przestrzeń pamięci jest priorytetem. Wynika to z faktu, że do przechowywania węzłów potrzeba mniej pamięci w porównaniu z dużą liczbą komórek siatki w mapach siatki zajętości. Zaletą mniejszego zużycia pamięci przez mapę topologiczną jest jednak mniejsza dokładność. Wynika to z faktu, że niektóre ważne informacje, takie jak dokładna lokalizacja wolnych przestrzeni w otoczeniu, mogą nie być reprezentowane na mapach. Ograniczona dokładność map topologicznych ogranicza zatem możliwości robota w zakresie szybkiej i bezpiecznej nawigacji.

LOKALIZACJA

Większość robotów mobilnych lokalizuje swoje położenie x_t względem danej mapy na podstawie odczytów odometrycznych. Niestety, poślizgi i dryfty kół powodują przyrostowe błędy lokalizacji . Błędy te powodują, że robot mobilny traci kontrolę nad własnym położeniem, a tym samym traci zdolność do autonomicznej nawigacji z jednego punktu na mapie do drugiego. Rozwiązaniem problemu lokalizacji jest wykorzystanie informacji o otoczeniu z dodatkowych czujników. Przykładami używanych czujników są dalmierz laserowy i czujnik sonarowy, które mierzą odległość między robotem a najbliższymi przeszkodami w otoczeniu. Rozszerzony filtr Kalmana (EKF) i filtr cząsteczkowy to dwa algorytmy lokalizacji, które wykorzystują odometrię i dodatkowe dane sensoryczne otoczenia do lokalizacji robota mobilnego. Oba algorytmy są metodami probabilistycznymi, które pozwalają na uwzględnienie niepewności wynikających z oszacowania położenia robota i odczytów czujników w sposób zasadniczy.

Lokalizacja z rozszerzonym filtrem Kalmana

EKF jest prawdopodobnie najbardziej uznanym algorytmem lokalizacji robotów mobilnych ze względu na swoją solidność i wydajność. EKF to rekurencyjny algorytm szacowania pozycji robota z zaszumionymi odczytami czujników. Kluczową cechą EKF jest to, że utrzymuje on a posteriori przekonanie bel(x_t) oszacowania pozycji, które podąża za rozkładem Gaussa, reprezentowanym przez średnią x_t i kowariancję P_t. Średnia x_t reprezentuje najbardziej prawdopodobną pozycję robota w czasie t, a kowariancja P_t reprezentuje kowariancję błędu tego oszacowania. EKF składa się z dwóch kroków: predykcji i aktualizacji. W kroku predykcji przewidywane przekonanie jestnajpierw obliczane przy użyciu modelu ruchu, który opisuje dynamikę stanu robota. jest następnie przekształcane w bel(x_t) poprzez uwzględnienie pomiarówz czujnika w kroku aktualizacji. Jak wspomniano powyżej, przewidywane przekonanie które jest reprezentowane przez przewidywaną średnią i kowariancję jest obliczane na podstawie kroku predykcji podanego przez



gdzie f(⋅) jest modelem ruchu robota mobilnego, F jest Jakobianem f(⋅) obliczonym w x_t-1, Q_t jest kowariancją modelu ruchu, a u_t są danymi sterującymi robota. t) przez włączenie pomiaru czujnika z_t do kroku aktualizacji EKF pokazanego w równaniach 7, 8 i 9.



K_t, obliczone w Równaniu 7, nazywane jest wzmocnieniem Kalmana. Określa ono stopień, w jakim z_t powinno zostać uwzględnione w nowym oszacowaniu pozycji. Równanie 8 oblicza x_t, dostosowując je proporcjonalnie do K_t i odchylenia z_t od przewidywanego pomiaru . Należy zauważyć, że pomiar czujnika z_t =[ z_t¹ z_t² …]^Todnosi się do współrzędnych zbioru obserwowanych punktów orientacyjnych, a nie do surowych odczytów czujnika, a model pomiaru czujnika h(⋅) podaje przewidywany pomiar z danej mapy topologicznej m i t jest Jakobianem h(⋅) obliczonym dla x_t-1. Na koniec, kowariancja P_t przekonania a posteriori bel(x_t) jest obliczana w Równaniu 9 poprzez dostosowanie do wzmocnienia informacji wynikającego z pomiarów czujnika.

Lokalizacja za pomocą filtra cząsteczkowego

W ostatnich latach obserwuje się rosnące zainteresowanie wykorzystaniem filtra cząsteczkowego nad EKF do lokalizacji robotów. To zwiększone zainteresowanie wynika prawdopodobnie z czterech powodów. Po pierwsze, surowe pomiary otoczenia z czujników są wykorzystywane w lokalizacji za pomocą filtra cząsteczkowego, gdzie lokalizacja EKF wymaga ekstrakcji cech. Po drugie, filtr cząsteczkowy jest bardziej odporny, ponieważ w przeciwieństwie do EKF nie zakłada rozkładu Gaussa dla przekonania a posteriori bel(x_t). Po trzecie, filtr cząsteczkowy jest w stanie odzyskać sprawność po awarii lokalizacji. Błąd lokalizacji występuje, gdy robot nagle straci ślad swojej pozycji podczas procesu lokalizacji. Błąd lokalizacji jest również znany jako problem porwania. Po czwarte, w przeciwieństwie do EKF nie ma potrzeby wyprowadzania skomplikowanych Jakobianów dla filtra cząsteczkowego. Intuicja stojąca za filtrem cząsteczkowym polega na reprezentowaniu przekonania a posteriori bel(x_t) przez skończony zbiór próbek M ważonych cząstek. Ten zbiór próbek jest losowany zgodnie z bel(x_t). Zbiór cząstek jest oznaczony przez



gdzie



Oznacza m-tą cząstkę. Tutaj x^[m]_t to zmienna losowa reprezentująca hipotetyczny stan, a w^[m]_t to wartość nieujemna zwana współczynnikiem ważności, która reprezentuje wagę każdej cząstki. Podobnie jak EKF, filtr cząstek składa się z etapów predykcji i aktualizacji. W kroku predykcji próbki cząstek są pobierane z modelu ruchu robota, aby reprezentować przewidywane przekonanie .Następnie cząstki są ważone zgodnie z pomiarami czujnika w kroku aktualizacji. Na koniec, jest przekształcany w późniejsze przekonanie bel(x_t) poprzez ponowne próbkowanie cząstek zgodnie z ich wagami. Tabela 1 przedstawia iterację rekurencyjnego algorytmu filtra cząstek do lokalizacji.



Danymi wejściowymi dla filtra cząstek są zbiór cząstek reprezentujący poprzednie przekonaniestanu ξ_t-1, ostatnie działania sterujące u_t i dane pomiarowe z_t. Wiersz 3 to krok predykcji, który generuje hipotetyczny stan x^[m]_t poprzez próbkowanie z modelu ruchu(x,sub>t|u_t,x^[m]_t-1) robota. Zbiór cząstek uzyskany po M iteracjach reprezentuje . Wiersz 4 oblicza w_t^[m] z modelu pomiaru czujnika. Współczynnik ważności uwzględnia niedopasowanie między l i bel(x_t). Na koniec proces ponownego próbkowania z wierszy 7 do 9 losuje M cząstek zastępczych z tymczasowego zbioru z prawdopodobieństwem proporcjonalnym do współczynników ważności. Rozkład jest przekształcany w bel(x_t) poprzez uwzględnienie współczynników ważności w procesie ponownego próbkowania.



Rysunek 4(a) do (d) przedstawia wynik implementacji robota lokalizującego się w korytarzu. Zbiór cząstek jest inicjowany do początkowej znanej pozycji robota pokazanej na rysunku 4(a). Cząstki są inicjowane równomiernie w okręgu o promieniu 100 mm, a początkowa pozycja robota jest przyjmowana jako środek. Orientacja cząstek jest również inicjowana jednolicie w zakresie ±5° względem początkowej orientacji robota. Ma to na celu wyeliminowanie ewentualnych błędów w oszacowaniu początkowej pozycji robota. Rysunki 4(b) do 4(d) pokazują, że błąd odometrii rośnie wraz ze wzrostem odległości pokonywanej przez robota. Robot myśli, że porusza się w przestrzeni zajętej, jeśli polegałby wyłącznie na odczytach odometrii, co jest oczywiście błędne. Oczywiste jest, że filtr cząsteczkowy daje bardziej racjonalne oszacowanie pozycji, ponieważ robot zawsze porusza się w wolnej przestrzeni. Wspomniano wcześniej, że filtr cząsteczkowy jest w stanie odzyskać sprawność po awarii lokalizacji. Przykładem awarii lokalizacji jest sytuacja, gdy robot jest popychany przez człowieka, co powoduje rozbieżność między rzeczywistą a szacowaną pozycją robota. Na szczęście problem można łatwo rozwiązać, obserwując całkowitą masę filtra po każdej iteracji. Błędy lokalizacji powodują gwałtowne spadki całkowitej masy cząstek. Cząstki są ponownie inicjowane jednolicie w wolnej przestrzeni po wykryciu gwałtownego spadku całkowitej masy. wagi cząstek. Cząstki ostatecznie zbiegną się do rzeczywistej pozycji robota. Filtr cząsteczkowy to potężny algorytm rozwiązujący problem lokalizacji. Należy jednak zauważyć, że liczba cząstek używanych do reprezentowania przekonań jest ważnym parametrem efektywności filtra cząsteczkowego w odzyskiwaniu danych po błędach lokalizacji. Do odzyskiwania danych po błędach lokalizacji w dużych środowiskach niezbędny jest duży rozmiar cząstek, a w wielu przypadkach maksymalna liczba cząstek jest ograniczona dostępnymi zasobami obliczeniowymi. Problem ten jest również znany jako klątwa wymiarowości.

TRENDY PRZYSZŁOŚCI

Chociaż algorytmy nawigacji, tworzenia map i lokalizacji są wdrażane z powodzeniem, skala i struktura środowisk, w których te algorytmy działają, są ograniczone. W związku z tym przyszłe wyzwania dla autonomii robotów mobilnych wiążą się z implementacją algorytmów w większej skali i bardziej złożonych środowiskach, takich jak miasta czy dżungle.

WNIOSKI

Aby osiągnąć pełną autonomię, robot mobilny musi posiadać trzy kompetencje: nawigację, tworzenie map i lokalizację. Na przestrzeni lat zaproponowano i wdrożono wiele algorytmów, które z powodzeniem wyposażyły roboty mobilne we wszystkie trzy kompetencje. Niektóre z kluczowych algorytmów, takie jak funkcja nawigacji, mapy drogowe, sztuczne pole potencjału, histogram pola wektorowego, nawigacja hybrydowa i zintegrowany algorytm nawigacji; siatka zajętości i mapowanie topologiczne; a także filtr Kalmana i filtr cząsteczkowy do lokalizacji, zostały omówione w Części I i II niniejszego artykułu.

WSTĘP

Kilka zagadnień uczenia bez nadzoru było od dziesięcioleci intensywnie badanych i znajdowało szerokie zastosowanie w literaturze z zakresu statystyki, przetwarzania sygnałów i uczenia maszynowego. Tematy te są ze sobą powiązane, a niektóre powiązania zostały częściowo omówione, ale nadal wymagają systematycznego przeglądu. Artykuł przedstawia ujednoliconą perspektywę poprzez ogólne ramy niezależnych podprzestrzeni, z różnymi tematami charakteryzującymi się różnicami w wyborze i łączeniu trzech składników. Co więcej, przegląd przeprowadzono poprzez trzy nurty badań. Jeden z nich obejmuje szeroko badane analizy głównych składowych (PCA) i analizy czynnikowej (FA), charakteryzujące się niezależnością drugiego rzędu. Drugi obejmuje badania nad niezależnością wyższego rzędu, charakteryzujące się analizą niezależnych składowych (ICA), binarną analizą głównych składowych i niegaussowską analizą głównych składowych. Trzeci to tzw. uczenie mieszane, które łączy poszczególne zadania w celu realizacji złożonego zadania. Obszerna literatura uniemożliwia przedstawienie pełnego przeglądu. Zamiast tego staramy się naszkicować plan działania dla każdego nurtu, zwracając uwagę na tematy, których brakuje w istniejących badaniach i podręcznikach, a które ograniczają się do wiedzy autorów.

OGÓLNE RAMY NIEZALEŻNYCH PODPRZESTRZENI

Wiele tematów uczenia się bez nadzoru charakteryzuje się sposobem jego obsługi w podstawowym zadaniu. Jak pokazano na rysunku (b),



każda próbka x jest rzutowana na na rozmaitość, a błąd użycia do reprezentacji x jest minimalizowany zbiorczo na zbiorze próbek. Jedną z szeroko badanych sytuacji jest to, że rozmaitość jest podprzestrzenią reprezentowaną przez współrzędne liniowe, np. rozpiętą przez trzy liniowe niezależne wektory bazowe a₁,a₂,a₃ jak pokazano na rysunku(a).



Zatem można przedstawić za pomocą jego rzutu y^(j) na każdy wektor bazowy, tj.



lub



Zazwyczaj błąd jest mierzony za pomocą normy kwadratowej, która jest minimalizowana, gdy e jest ortogonalne do 2 na zbiorze próbek lub jego wartości oczekiwanej E||e||² jest charakteryzowana przez te cechy podane na dole rysunku (a).



Ogólnie rzecz biorąc, zadanie składa się z trzech składników, jak pokazano na rysunku 2.



Po pierwsze, jak mierzy się błąd . Różne miary definiują różne projekcje. Norma kwadratowa d = ||e||² ma zastosowanie do ośrodka jednorodnego między x a


,rozpatrywana jest nieortogonalna, ale wciąż liniowa projekcja za pomocą d =||e||²_B=e^TΣ^-1_e z Σ^-1_e=B^TB, tak jakby e było najpierw odwzorowane na ośrodek jednorodny za pomocą odwzorowania liniowego e, a następnie mierzone za pomocą normy kwadratowej. Na dole rysunku (c) pokazano naturę tego Min||e||_B². Ponieważ założenia znacznie różnią się od założeń Min||e||², muszą być narzucone zewnętrznie. Drugim składnikiem jest układ współrzędnych, za pośrednictwem albo wektorów liniowych na rysunkach(a) i (c), albo zbioru krzywych na rozmaitości nieliniowej na rysunku(b). Ponadto istnieje trzeci składnik, który narzuca pewną strukturę, aby dodatkowo ograniczyć sposób, w jaki y jest rozłożone we współrzędnych, np. poprzez naturę d). Różnice w wyborze i łączeniu trzech składników prowadzą do różnych podejść. Używamy nazwy "niezależne podprzestrzenie" do określenia struktur, w których składowe y są wzajemnie niezależne, i uzyskujemy ogólne ramy do uwzględnienia kilku tematów uczenia bez nadzoru. Następnie podsumowujemy je za pomocą trzech nurtów badań, rozważając

o d =||e||²_B=e^TΣ^-1_e oraz dwa przypadki szczególne,
o trzy typy struktur niezależności i czy istnieje struktura czasowa między próbkami,
o wahająca się od jednego liniowego układu współrzędnych do wielu liniowych układów współrzędnych w różnych lokalizacjach, jak pokazano na rysunku 2



BADANIA WYBRANE PRZEZ NIEZALEŻNOŚĆ DRUGIEGO RZĘDU

Rozpoczynamy od rozważenia próbek o niezależnym i identycznym rozkładzie (i.i.d.) według współrzędnych liniowych i niezależnej struktury Gaussa) p(y^(j)_t | ì^(j) , przy czym miara projekcji zmienia się, jak pokazano w pierwszej kolumnie tabeli na rysunku 2. Spotykamy analizę czynnikową (FA) w ogólnym przypadku d = ||e||²_B=e^TB^TBe . Wszczególnym przypadku B =σ_eI, współrzędne liniowe rozpościerają główną podprzestrzeń danych. Dodatkowo narzucając A^TA = I i wymagając kolumn A podanych przez pierwsze m głównych składowych (PC), tj. wektorów własnych, które odpowiadają największym wartościom własnym Σ = (B^TB)^-1 .Staje się to równoważne z PCA. Ponadto, w zdegenerowanym przypadku e = 0, y = xW dekoreluje składowe y, np. wykonując wstępne wybielanie, jak w przypadku przetwarzania sygnałów. Podsumowujemy badania nad Mapą Drogową A. Pierwszy nurt powstał 100 lat temu. Pierwsze adaptacyjne uczenie się Reguła Oja znajduje pierwszy element (tj. wektor własny odpowiadający największej wartości własnej σ), bez jawnego szacowania σ. Rozszerzona o znajdowanie wielu elementów, jedna z metod charakteryzuje się asymetryczną lub sekwencyjną implementacją reguły pierwszego elementu, ale obarczona jest akumulacją błędów. . Inną metodą jest symetryczne znajdowanie wielu elementów, np. reguła podprzestrzeni Oja. Dalsze badania podsumowano w następujących gałęziach:

MCA, podprzestrzeń podwójna i dopasowanie TLS , sugeruje się rozpoznawanie wzorców dualnych, uwzględniając zarówno podprzestrzeń główną, jak i podprzestrzeń dopełniającą, a także wiele elementów i ich dopełniające odpowiedniki - składowe odpowiadające najmniejszym wartościom własnym Σ (tj. wektory wierszowe U na rysunku 2). Co więcej, pierwsza adaptacyjna reguła jest proponowana przez równanie (11a) w (Xu, Krzyzak&Oja, 1991) w celu uzyskania składowej odpowiadającej najmniejszej wartości własnej Σ, pod nazwą Minor Component Analysis (MCA), po raz pierwszy wymyślonej przez Xu, Oja&Suen (1992), i jest również używana do implementacji dopasowania krzywej najmniejszych kwadratów całkowitych (TLS). Następnie temat ten został wprowadzony do literatury przetwarzania sygnałów przez Gao, Ahmada i Swamy′ego (1992), co zostało zmotywowane wizytą Gao w biurze Xu, gdzie Xu przedstawił mu wynik Xu, Oja&Suen (1992). Następnie adaptacyjne uczenie się MCA do filtrowania TLS staje się popularnym tematem przetwarzania sygnałów. Zasugerowano również ,że implementację PCA lub MCA uzyskuje się poprzez zmianę znaku aktualizacji w powyższym równaniu (11a). Następnie podjęto wysiłki w celu zbadania istniejących reguł PCA pod kątem ich stabilności po takiej zmianie znaku. Zadania te zazwyczaj wymagają żmudnych analiz matematycznych stabilności równania różniczkowego zwyczajnego, np. Chen i Amari (2001). Alternatywnym sposobem jest przekształcenie optymalizacji kosztu PCA w stabilną optymalizację kosztu indukowanego dla MCA, np. koszt LMSER jest przekształcany w koszt dla podprzestrzeni rozpiętej przez wiele MC. Ogólna metoda jest dodatkowo podana przez równania (24-26) w (Xu, 2003), a następnie omówiona w (Xu, 2007a)

Uczenie się metodą LMSER i śledzenie podprzestrzeni

Nowa adaptacyjna reguła PCA została wyprowadzona z gradientu ∇E₂(W) dla rekonstrukcji metodą najmniejszego błędu średniokwadratowego (LMSER) , z pierwszym zaproponowanym dowodem globalnej zbieżności reguły podprzestrzeni Oja - zadania, które wcześniej uważano za trudne. Wykazano matematycznie i eksperymentalnie, że LMSER ulepsza regułę Oja poprzez dalsze badania porównawcze. Dwa lata później ta E₂(W) została wykorzystana do śledzenia podprzestrzeni sygnału za pomocą rekurencyjnej techniki najmniejszych kwadratów , a następnie przez inne metody w literaturze poświęconej przetwarzaniu sygnałów . Ponadto, PCA a analiza podprzestrzeni może być przeprowadzona za pomocą innych teorii lub kosztów. Właściwości algebraiczne i geometryczne zostały dalej przeanalizowane w oparciu o jedną z nich, mianowicie teorię względnej niepewności (RUT), autorstwa Fiori . Co więcej, kryterium NIC dla śledzenia podprzestrzeni jest w rzeczywistości szczególnym przypadkiem tej RUT, co można zaobserwować, porównując równanie (20) w (Miao i Hua, 1998) z równaniem ?e na końcu rozdz. III.B w (Xu, 1994a).

Podprzestrzeń główna a wieloelementowe

Reguła podprzestrzeni Oja nie znajduje prawdziwie wieloelementowych ze względu na nieoznaczoność rotacji. Co ciekawe, eksperymentalnie wykazano, że dodanie funkcji sigmoidalnej sprawia, że LMSER dobrze aproksymuje wieloelementowe . Pracując na Harvardzie późnym latem 1991 roku, Xu zapoznał się z Brockettem (1991) i w ten sposób rozszerzył schemat Brocketta dla macierzy ortogonalnych n×n na macierze ortogonalne n × n₁ z n > n₁, z czego dwie reguły uczenia dla prawdziwie wieloelementowych są uzyskiwane poprzez modyfikację reguły LMSER i reguły podprzestrzeni Oja. Te dwie reguły zostały zawarte jako równania (13) i (14) w pracy Xu (1993) opublikowanej w 1991 roku, które są niezależne i różnią się od reguł Oja (1992). Tanaka (2005) ujednolicił te reguły w jedno wyrażenie kontrolowane jednym parametrem, a badanie porównawcze wykazało, że równanie (14) w (Xu, 1993) okazało się najbardziej obiecujące.

Adaptacyjne, odporne PCA

W literaturze statystycznej zaproponowano odporne PCA w celu przeciwdziałania obserwacjom odstającym za pomocą odpornego estymatora dla Σ. Xu i Yuille (1992 i 1995) uogólnili reguły Oja, LMSER i MCA na odporne adaptacyjne uczenie się przez fizykę statystyczną, powiązane z M-estymatorami Hubera. Ponadto koszty PCA w (Xu, 1994b) zostały rozszerzone na odporne wersje . Następnie podjęto dalsze wysiłki, w tym wykorzystanie PCA w wizji komputerowej.W ostatniej dekadzie nastąpiło odrodzenie zainteresowania analizą składowych (FA). Nie tylko algorytm EM dla analizy składowych (FA) został wprowadzony do implementacji PCA, ale także adaptacyjny algorytm EM i inne postępy opracowano w celu wsparcia bayesowskiego uczenia się harmonii Ying Yang (BYY).

PODPRZESTRZENIE NIEZALEŻNOŚCI WYŻSZEGO RZĘDU

Zwracając uwagę na tabelę na rysunku 2, postępujemy tak, jak p(y_t^(j) |μ^(j) staje się niegaussowskie w dwóch ostatnich kolumnach. Zdegenerowany przypadek e = 0 prowadzi do problemu rozwiązania x = Ay z próbek x i ograniczenia niezależności



Jednym ze sposobów jest rozwiązywanie indukowanych nieliniowych równań algebraicznych. Innym sposobem jest analiza składowych niezależnych (ICA), którą omawia się w następujących czterech gałęziach:

o Poszukiwanie ekstremów kumulantów wyższego rzędu y.
o Wykorzystanie nieliniowego uczenia Hebba do usuwania zależności wyższego rzędu między składowymi y, z których w rzeczywistości wywodzą się badania ICA.
o Optymalizacja kosztu na podstawie



bezpośrednio. Równanie aktualizacji jest osiągane z kilku punktów widzenia, przy czym rzeczywiste różnice wynikają z wstępnego określenia nieliniowości f(y^(j)). Jedno działa, gdy wszystkie składowe źródłowe y* są subgaussowskie, a drugie działa, gdy wszystkie składowe źródłowe y* są supergaussowskie. Ten problem rozwiązuje się poprzez wspólne uczenie W i f(y^(j)) za pomocą modelu parametrycznego. Ponadto stwierdzono, że przybliżone oszacowanie każdego źródła jest już wystarczające, co uzasadnia tzw. hipotezę dopasowania jednego bitu, która niedawno została udowodniona matematycznie .

o Implementacja nieliniowego LMSER. Tutaj dodajemy wyjaśnienia dotyczące dwóch poprzednich nieporozumień. Jedno dotyczy pominięcia źródła nieliniowego LMSER. Zostało to już wyjaśnione w (Karhunen, Pajunen, &Oja, 1998; Hyvarinen, Karhunen i Oja, 2001; Plumbley i Oja, 2004), wyraźnie wskazując, że nieliniowa E₂(W) i jej adaptacyjna reguła gradientu zostały zaproponowane po raz pierwszy w (Xu, 1991&93). Drugie nieporozumienie dotyczy faktu, że ICA jest zazwyczaj postrzegana jako odpowiednik PCA. Jak stwierdzono w (Xu, 2001b&03) i zaobserwowano w tabeli na rysunku 2, ICA przy y = xW jest w rzeczywistości rozszerzeniem analizy dekorelacyjnej w dowolnych kombinacjach PC i MC. Odpowiednikiem MCA jest mniejsza ICA (M-ICA), a odpowiednikiem PCA jest główna ICA (P-ICA). W rzeczywistości pojęcie "główny" wyłania się z e_t = x_t - Ay ≠ 0. Jak pokazano w tabeli na rysunku 2 , gdy p(y_t^(j) |μ^(j) staje się niegaussowskie, FA rozszerza się do binarnego FA (NFA), jeśli y jest binarne, oraz do niegaussowskiego FA (NFA), jeśli y jest rzeczywiste, ale niegaussowskie. Podobnie jak w przypadku FA wykonującego PCA przy Σ_e = σ_e²I wykonaj P-ICA przy , zarówno BFA, jak i NFA stają się do Σ_e = σ_e²I. Obserwując pierwsze pole w tej kolumnie, dla e_t = x_t - Ay ≠ 0 musimy szukać odpowiedniego odwzorowania nieliniowego y = f(x). Zwykle nie ma ono rozwiązania analitycznego, ale wymaga kosztownych obliczeń w celu aproksymacji. Jak omówiono w (Xu, 2003), nieliniowy LMSER wykorzystuje nieliniowość sigmoidalną y_t^(j) = s(z_t^(j)), z=xW, aby uniknąć kosztów obliczeniowych i w przybliżeniu implementuje BFA dla równania Bernoulliego) p(y^(j)) z prawdopodobieństwem



oraz NFA dla p(y^(j)) z rozkładem pseudojednostajnym na (-∞, +∞), a także nieujemną ICA , gdy p(y^(j)) jest na [0, +∞). Jednak do tego przybliżenia potrzebna jest dalsza analiza ilościowa. Bez przybliżenia algorytm EM jest rozwijany dla uczenia metodą maksymalnego prawdopodobieństwa od 1997 roku, wciąż borykając się z wysokimi kosztami obliczeniowymi. Co ciekawe, dzięki nauce harmonii BYY udało się również osiągnąć dalsze postępy.

ROZSZERZENIA CZASOWE I LOKALIZOWANE

Rozważamy dalej próbki czasowe pokazane na dole prawej kolumny zarówno na Mapie A, jak i Mapie B, poprzez osadzenie struktury czasowej w p(y_t^(j) |μ^(j). Typowa struktura wykorzystuje



np. regresja liniowa



przekształcić model w rozszerzenia czasowe. Informacja jest przenoszona w czasie n na dwa sposoby. Pierwszym jest obliczenie μ^(j)_t za pomocą regresji, z nauką μ^(j)_t dokonaną poprzez gradient względem j_j za pomocą reguły łańcuchowej. Drugim sposobem jest obliczenie



i uzyskanie gradientu względem j_j. Następnie przechodzimy do wielu podprzestrzeni w różnych lokalizacjach, jak pokazano na rysunku 2. Badania podsumowano według jednego kluczowego punktu, tj. schematu p_l,t?, który przydziela próbkę x_t do różnych podprzestrzeni. To p_l,t? opiera się na dwóch kwestiach. Jedną z nich jest lokalna miara tego, jak l-ta podprzestrzeń jest odpowiednia do reprezentowania x_t. Drugą jest mechanizm, który podsumowuje lokalne miary podprzestrzeni, dając p_l,t?. Jednym z typowych mechanizmów jest ten, który pojawia się w algorytmie EM dla uczenia się metodą największej wiarygodności lub uczenia bayesowskiego, gdzie x_t jest ułamkowo przydzielane między podprzestrzenie proporcjonalnie do ich miar lokalnych. Innym typowym mechanizmem jest to, że x_t jest nieliniowo lokalizowane do jednego lub więcej zwycięzców poprzez konkurencję opartą na miarach lokalnych, np. jak w klasycznym uczeniu się konkurencyjnym i uczeniu się konkurencyjnym z karą dla rywala (RPCL). Schemat p_l,t? może również powstać w wyniku połączenia obu typów mechanizmów, na przykład w przypadku uczenia harmonicznego BYY.

TRENDY NA PRZYSZŁOŚĆ

Innym ważnym zadaniem jest określenie liczby k podprzestrzeni i wymiaru m_l każdej podprzestrzeni. Nazywa się to selekcją modelu i jest zazwyczaj realizowane w dwóch fazach. Najpierw rozpatruje się zbiór kandydatów poprzez enumerację k i m_l, z nieznanymi parametrami szacowanymi metodą uczenia metodą największej wiarygodności. Po drugie, najlepszy spośród kandydatów jest wybierany na podstawie jednego z kryteriów, takich jak AIC, CAIC, SIC/BIC/MDL, walidacja krzyżowa itp. Jednak ta dwufazowa implementacja jest bardzo rozbudowana obliczeniowo. Co więcej, wydajność znacznie się pogorszy, gdy wielkość próby będzie skończona, a k i m_l nie będą zbyt małe. Jednym z trendów jest umożliwienie automatycznego wyboru modelu podczas uczenia się, tj. w przypadku kandydata, dla którego k i m_l są początkowo wystarczająco duże, uczenie nie tylko określa nieznane parametry, ale także automatycznie zmniejsza k im_l do odpowiednich wartości. Dwoma takimi metodami są RPCL i uczenie harmoniczne BYY. Istnieją również otwarte kwestie dotyczące x = Ay + e, e ≠ 0, ze składowymi y wzajemnie niezależnymi w statystykach wyższego rzędu. Niektóre z nich wymieniono poniżej:

o Którą część nieznanych parametrów w równaniu x = Ay + e można wyznaczyć jednoznacznie? o W jakich warunkach niezależność



można zapewnić w teorii? Czy można to osiągnąć poprzez algorytm uczący się?

o W jakim sensie, zarówno zapewnienie



najlepszą rekonstrukcję x przez można osiągnąć jednocześnie? Jeśli nie, jaka jest najlepsza nieliniowa rekonstrukcja y = f(x) w odniesieniu do obu?



i e ≠ 0? o Czy taką najlepszą odpowiedź można uzyskać analitycznie, czy poprzez efektywne obliczenia?

WNIOSKI

Przeprowadzono obszerny przegląd badań trzech ściśle powiązanych ze sobą nurtów uczenia się bez nadzoru, z perspektywy systematycznej. Przedstawiono ogólne ramy niezależnych podprzestrzeni, z których podsumowano szereg tematów uczenia się poprzez różne cechy wyboru i łączenia trzech podstawowych składników.

WSTĘP

W ciągu ostatnich trzech dekad dziedzina nieliniowej charakterystyki sygnałów i nieliniowego przetwarzania sygnałów przyciągała coraz większą liczbę badaczy. Wynika to z faktu, że techniki liniowe mają pewne ograniczenia w niektórych obszarach przetwarzania sygnału. Wprowadzono wiele technik nieliniowych jako uzupełnienie klasycznych metod liniowych i jako alternatywę, gdy założenie liniowości jest niewłaściwe. Dwie z tych technik to statystyka wyższego rzędu (HOS) i teoria dynamiki nieliniowej (chaos). Znalazły one szerokie zastosowanie do charakteryzacji i analizy szeregów czasowych w kilku dziedzinach, zwłaszcza w sygnałach biomedycznych. Zarówno techniki HOS, jak i techniki chaosu przeszły podobną ewolucję. Po raz pierwszy zaczęto je badać około 1900 r.: metodę momentów (związaną z HOS) opracował Pearson, a w 1890 r. Henri Poincaré odkrył wrażliwą zależność od warunków początkowych (objaw chaosu) w szczególnym przypadku problemu trzech ciał. Obydwa podejścia zostały zastąpione technikami liniowymi aż do około 1960 roku, kiedy Lorenz przez przypadek ponownie odkrył układ chaotyczny, badając zachowanie mas powietrza. W międzyczasie grupa statystyków z Uniwersytetu Kalifornijskiego ponownie zaczęła badać zastosowanie technik HOS. Jednakże techniki te były ignorowane aż do 1980 roku, kiedy Mendel (Mendel, 1991) opracował techniki identyfikacji systemów w oparciu o HOS i Ruelle (Ruelle, 1979), Packard (Packard, 1980), Takens (Takens, 1981) i Casdagli (Casdagli, 1989) ustalili metody modelowania nieliniowych szeregów czasowych za pomocą teorii chaosu. Jednak dopiero niedawno zastosowanie HOS i chaosu w szeregach czasowych stało się możliwe dzięki większej mocy obliczeniowej komputerów i technologii cyfrowego przetwarzania sygnału (DSP). W artykule przedstawiono stan wiedzy na temat dwóch technik nieliniowych stosowanych w analizie szeregów czasowych: statystyki wyższego rzędu i teorii chaosu. Opisane zostaną niektóre pomiary oparte na technikach HOS i chaosie oraz przeanalizowane zostanie, w jaki sposób pomiary te charakteryzują różne zachowania sygnału. Zastosowanie pomiarów nieliniowych pozwala na bardziej realistyczną charakterystykę sygnałów i dlatego stanowi postęp w rozwoju systemów automatyki

TŁO

W cyfrowym przetwarzaniu sygnałów estymatory służą do charakteryzowania sygnałów i systemów. Estymatory te zwykle uzyskuje się za pomocą technik liniowych. Ich matematyczna prostota i istnienie jednoczącej teorii systemów liniowych ułatwiły ich obliczenia. Co więcej, techniki przetwarzania liniowego zapewniają zadowalającą wydajność w różnych zastosowaniach.Jednakże modele i techniki liniowe nie są w stanie rozwiązać problemów, takich jak nieliniowości spowodowane szumem w systemie produkcyjnym sygnału, nieliniowości systemowe w akwizycji, transmisji i percepcji sygnału cyfrowego, nieliniowości wprowadzone przez metodę przetwarzania i zachowanie dynamiki nieliniowej. Dlatego zastosowanie technik przetwarzania liniowego prowadzi do mniej realistycznej charakterystyki niektórych systemów i sygnałów. W wyniku niedociągnięć technik liniowych rewiduje się procedury analityczne i stosuje się techniki nieliniowe w estymatorach i modelach obliczeniowych oraz w charakteryzacji sygnałów, aby zwiększyć możliwości cyfrowego przetwarzania sygnałów. HOS to dziedzina statystycznego przetwarzania sygnałów, która stała się bardzo popularna w ciągu ostatnich 25 lat. Do tej pory prawie całe przetwarzanie sygnałów cyfrowych opierało się na statystykach drugiego rzędu (funkcja autokorelacji, widmo mocy). HOS wykorzystuje dodatkowe informacje, które można wykorzystać do uzyskania lepszych szacunków sytuacji hałaśliwej i nieliniowości. Teoria chaosu (nieliniowa teoria dynamiki) to długoterminowo nieprzewidywalne zachowanie w nieliniowym układzie system namiczny spowodowany wrażliwością na warunki początkowe. Dlatego nieregularności w sygnale mogą być spowodowane nie tylko przypadkowym sygnałem zewnętrznym, ale także chaotycznym zachowaniem. Obie techniki nieliniowe zostały wykorzystane w charakteryzacji sygnałów i opracowano liczne systemy automatycznej klasyfikacji wykorzystujące cechy HOS i chaos w wielu dziedzinach. Klasyfikacja tekstury (Coroyer, Declercq, Duvaut, 1997), przewidywanie zdarzeń sejsmicznych (Van Zyl, 2001), diagnostyka usterek w monitorowaniu stanu maszyn za pomocą sygnałów wibracyjnych (Samanta, Al.Balushi. & Al-Araimi, 2006), (Wang i Lin, 2003) oraz ekonomia (Hommes & Manzan, 2006) to tylko niektóre przykłady. Szczególnie ważne jest ich zastosowanie w sygnałach biomedycznych. Cechy nieliniowe okazały się przydatne w charakteryzowaniu sygnałów głosu, elektrokardiogramu (EKG) i elektroencefalogramu (EEG). Wdrożono automatyczne systemy klasyfikacji głosów patologicznych i zdrowych przy użyciu cech nieliniowych . Do wykrywania zmian elektrokardiograficznych wykorzystano charakterystykę nieliniową. Sygnał EKG , w ocenie chorób neurologicznych z wykorzystaniem sygnału EEG oraz w diagnostyce fonokardiogramu.

METODY NIELINIOWE: TEORIA CHAOSU I WYŻSZY PORZĄDEK STATYSTYKI DOTYCZĄCE SZEREGÓW CZASOWYCH

Statystyki wyższego rzędu

Statystyki wyższego rzędu, zwane kumulantami, i ich transformata Fouriera, zwane polispektrami, są rozszerzeniami miar drugiego rzędu (takich jak funkcja autokorelacji i widmo mocy). Niektóre zalety HOS w porównaniu ze statystykami drugiego rzędu to:

1. HOS dostarcza informacji o amplitudzie i fazie w dziedzinie widmowej, podczas gdy statystyki drugiego rzędu dostarczają jedynie informacji o amplitudzie. Dlatego sygnały fazowe inne niż minimalne i niektóre typy sprzężeń fazowych (związane z nieliniowościami) nie mogą być poprawnie zidentyfikowane za pomocą metody drugiego rzędu statystyki.
2. HOS są ślepi na procesy Gaussa, podczas gdy korelacja nie jest (Mendel, 1991). Dlatego kumulanty można stosować do określania poziomów szumu Gaussa w sygnale, oddzielania sygnałów niegaussowskich od szumu Gaussa, szacowania składowych harmonicznych lub zwiększania stosunku sygnału do szumu (SNR), gdy sygnały są zanieczyszczone z szumem Gaussa.
Miary drugiego rzędu działają prawidłowo, jeśli sygnał ma funkcję gęstości prawdopodobieństwa Gaussa, ale wiele sygnałów rzeczywistych nie jest gaussowskich. Dlatego HOS są potężnym narzędziem do pracy z procesami niegaussowskimi i nieliniowymi. Następnie przedstawiono pomiary statystyki wyższego rzędu i wyjaśniono ich przydatność w charakteryzowaniu niektórych zjawisk nieliniowych.

Moment trzeciego rzędu: skośność

Skośność jest momentem trzeciego rzędu i miarą asymetrii w rozkładzie prawdopodobieństwa. Pomiar ten umożliwia rozróżnienie różnych rodzajów rozkładu danych, ponieważ ich wartość zmienia się w zależności od asymetrii rozkładu. Skośność rozkładu normalnego wynosi zero (dane symetryczne względem średniej), dodatnia skośność odpowiada rozkładowi z dłuższym prawym ogonem, a ujemna skośność rozkładowi z dłuższym lewym ogonem. W większości przypadków zakłada się rozkład normalny, ale punkty danych zwykle nie są idealnie symetryczne. Skośność odzwierciedla dodatnie lub ujemne odchylenia od średniej i zapewnia bardziej realistyczną charakterystykę zbioru danych.

Moment czwartego rzędu: Kurtoza

Kurtoza jest momentem czwartego rzędu i miarą tego, czy dane w rozkładzie prawdopodobieństwa osiągnęły szczyt lub płaska w stosunku do rozkładu normalnego. Kurtoza jest miarą koncentracji danych na temat średniej, wyższa kurtoza oznacza, że większa wariancja wynika z rzadkich ekstremalnych odchyleń.

Kumulanty wyższego rzędu

Momenty wyższego rzędu są naturalnym uogólnieniem autokorelacji, natomiast kumulanty są nieliniowymi kombinacjami momentów. Kumulantą drugiego rzędu jest funkcja autokorelacji. Kumulanty wyższego rzędu można postrzegać jako miarę gaussjalności procesu losowego, ponieważ kumulanty wyższe niżdrugiego rzędu wynoszą zero w procesie gaussowskim.

Bispektrum

Bispektrum jest transformatą Fouriera kumulanty trzeciego rzędu. Bispektrum stacjonarnego procesu Gaussa z zerowymi ośrodkami są równe zeru. Bispektrum sygnału plus szum Gaussa jest takie samo jak widmo sygnału, podczas gdy widmo mocy sygnałuplus szum Gaussa bardzo różni się od widma mocy samego sygnału. Dlatego poprzez bispektrum szum Gaussa możebyć oddzielone od szumu niegaussowskiego i można poprawić stosunek sygnału do szumu. Z drugiej strony, kwadratowe sprzęganie fazowe może zostać wykryte i za pomocą bispektrum nie można zidentyfikować układów fazy minimalnej.

Dwuspójność

Ściśle powiązany z bispektrum jest miara spójności trzeciego rzędu, czyli bikoherencja. Bikoherencja to znormalizowane bispektrum. Dwuspójność jest ograniczona pomiędzy wartościami 0 i 1i służy do wykrywania kwadratowego sprzężenia fazowego z powodu liniowości drugiego rzędu. Sprzężenie fazowe pomiędzy liniową kombinacją składowych częstotliwości ?1 i ?2 istnieje, jeśli bikoherencja ma wartość równą jedności dla pary częstotliwości (ω₁, ω₂).

Teoria chaosu

Teoria chaosu pomaga nam zrozumieć i zinterpretować obserwacje ze złożonych deterministycznych układów dynamicznych i może być wykorzystana do przewidywania i kontrolowania szeregów czasowych . Do czasu pojawienia się teorii chaosu wszelkie nieregularne zachowania interpretowano jako zachowania stochastyczne i dlatego nieprzewidywalny. Dzięki teorii chaosu niekoniecznie jest to prawdą. Na przykład systemy stochastyczne i chaotyczne mają bogate szerokopasmowe widma mocy i zmienne widma fazowe. Zatem, aby rozróżnić systemy stochastyczne i chaotyczne, teoria chaosu jest nowym, potężnym narzędziem. Deterministyczny układ dynamiczny opisuje ewolucję czasową układu w pewnej przestrzeni fazowej (m wymiarowa przestrzeń wektorowa), gdzie określony jest stanprzez wektor . Ewolucję tę można wyrazić za pomocą równań różniczkowych zwyczajnych :



lub w czasie dyskretnym t = nΔt według map:



Sekwencje punktów które rozwiązują równania układu, nazywane są trajektoriami. Warunki początkowe to odpowiednio. Obszar przestrzeni fazowej, w którym wszystkie trajektorie powstały w zakresie warunków początkowych, zbiegają się po czasie przejścia, nazywa się atraktorem. Przykład chaotycznego atraktora z oscylatora Colpittsa przedstawiono na rysunku 1.



W większości przypadków musimy scharakteryzować układy nieliniowe, dla których równania i modele są nieznane. Znane są jednak niektóre pomiary systemu. Istnieją pewne techniki uzyskiwania przestrzeni fazowej i atraktora z sygnału wyjściowego (techniki osadzania). W ten sposób z atraktora uzyskuje się pewne wielkości, takie jak wykładniki Lapunowa, wymiar korelacji i entropia Kołmogorowa-Synaju. Wielkości te umożliwiają pomiar stopnia nieliniowości układu. Pomiary te są niezmienne przy płynnych transformacjach, a zatem niezależne od procedury osadzania.

Techniki osadzania

Twierdzenie Takensa o osadzaniu (Takens, 1981) stwierdza, że osadzanie istnieje, jeśli wymiar (m) zrekonstruowanej przestrzeni fazowej jest taki, że m>2D+1 (D jest wymiarem atraktora). Istnieją dwie główne metody rekonstrukcji atraktora z szeregu czasowego: metoda opóźnień (Kantz i Schreiber, 1997) oraz analiza głównych składowych (Broomhead i King, 1986). Najbardziej popularna jest ta pierwsza metoda: rekonstrukcję opóźnienia w wymiarach m tworzą wektory s_n podane jako (Kantz i Schreiber, 1997),

s_n = [s(n),s(n-T),…,s(n-(m-1)/T] gdzie s(n) to zmierzony sygnał skalarny, m to wymiar osadzania zrekonstruowanej przestrzeni fazowej, a T to opóźnienie czasowe. Twierdzenie Takensa jest ściśle twierdzeniem o istnieniu i nie sugeruje, jak znaleźć wymiar osadzania (m) i opóźnienie czasowe (T). Jako estymator pierwszego rzędu funkcji autokorelacji lub jej zaniku zaproponowano pierwsze zero funkcji autokorelacji e 1. Pierwsze minimum funkcji informacji wzajemnej (Fraser i Swinney, 1986) jest kolejnym estymatorem T, który uwzględnia korelacje nieliniowe.Metoda fałszywych sąsiadów (Kennel, Brown i Abarbanel, 1992) oraz metoda fałszywych nici są proponowanymi metodami szacowania wymiaru osadzania (m). To drugie jest ulepszeniem fałszu metody sąsiadów.

Chaotyczne pomiary

W kolejnych akapitach zostaną opisane niektóre chaotyczne pomiary.

Wykładniki Lapunowa

Wykładniki Lapunowa charakteryzują szybkość separacji dwóch punktów w przestrzeni fazowej, początkowo oddalonych o niewielką odległość. Istnieje tyle wykładników Lapunowa, ile m (wymiar przestrzeni fazowej). Maksymalny wykładnik Lapunowa (MLE) jest największym i określa przewidywalność układu dynamicznego. Dodatni MLE oznacza rozbieżność pobliskich trajektorii, czyli chaos. Po opis matematyczny odsyłamy czytelnika do (Kantz i Schreiber, 1997). Zaimplementowano kilka algorytmów obliczania wykładników Lapunowa z szeregów czasowych . LE jest przydatny do scharakteryzowania różnych rodzajów zachowania sygnału lub systemu. Ujemny MLE jest wskaźnikiem stabilnego punktu stałego (systemu rozpraszającego lub niezachowawczego), dodatni MLE jest wskaźnikiem nieregularnego (chaotycznego) zachowania, zerowy MLE jest wskaźnikiem układu konserwatywnego (takiego jak oscylator harmoniczny), a nieskończony MLE jest wskaźnikiem szumu.

Entropia Kołmogorowa-Sinai

Entropia Kołmogorowa-Sinai (KS) określa ilościowo utratę informacji w miarę ewolucji systemu i jest kolejną miarą związaną z nieprzewidywalnością systemu. W regularnym i przewidywalnym systemie H_KS = 0, tj. pobliskie punkty są ściśle zgrupowane w jakimś innym małym obszarze przestrzeni fazowej i nie ma zmiany informacji. W procesie losowym H_KS = ∞ ze względu na to, że po krótkim czasie wszystkie obszary przestrzeni fazowej stają się możliwe. W układach chaotycznych 0 < H_KS < ∞ wskazuje, że pobliskie punkty w przestrzeni fazowej rozchodzą się wykładniczo. Dlatego też, zgodnie z wartościami entropii KS, można scharakteryzować różne typy układów: układy regularne, chaotyczne i szumowe.

Wymiar korelacji

Wymiar korelacji (Grassberger i Procaccia, 1983) określa ilościowo złożoność zrekonstruowanego atraktora. Jest to geometryczny pomiar czułej zależności od warunków początkowych, ponieważ w ruchu chaotycznym atraktor zwykle wykazuje bardzo skomplikowane i geometria fraktalna. W chaotycznym systemie deterministycznym wymiar korelacji osiąga wartość skończoną, natomiast w procesie losowym nie zbiega się do wartości. Estymatorem największej wiarygodności pozwalającym uzyskać optymalne wartości wymiaru korelacji jest estymator Takensa-Theilera (Theiler, 1988). Wymiar korelacji pozwala na odróżnienie procesu losowego od ruchu chaotycznego. Liczba niecałkowita (fraktal). Wartość wymiaru korelacji jest zwykle oznaką chaosu, natomiast wartość całkowita jest oznaką prawidłowego zachowania. Ponadto wymiar korelacji jest oszacowaniem liczby stopni swobody układu.

PRZYSZŁE TENDENCJE

W systemach automatycznego rozpoznawania konieczne jest scharakteryzowanie sekwencji danych i obiektów (głosów, dźwięków, twarzy, dłoni itp.), aby uzyskać dobrze opisaną przestrzeń cech. Posiadanie cech różnicujących doprowadzi później do pomyślnego procesu klasyfikacji. Jednak znalezienie cech różnicujących nie zawsze jest łatwe. Techniki nieliniowe to nowatorskie narzędzia umożliwiające scharakteryzowanie szeregów czasowych i przezwyciężenie pewnych wcześniejszych problemów związanych z technikami liniowymi. Dowodem na to jest rozwój kilku automatycznych systemów klasyfikacji wykorzystujących cechy nieliniowe.

WNIOSEK

W tym artykule pokazaliśmy stan wiedzy w zakresie dwóch najnowszych technik nieliniowych: statystyki wyższego rzędu i teorii chaosu. Główną kwestią jest fakt, że wielu sygnałów w prawdziwym życiu nie można odpowiednio modelować za pomocą samego przybliżenia liniowego. Niedawno, rozwój pakietów do obliczania miar chaotycznych (pakiet TISEAN) i HOS (zestaw narzędzi HOSA dla Matlaba) ze zbiorów danych umożliwił zastosowanie tych technik do zbiorów danych. Dzięki tym technikom możliwe jest obecnie wyodrębnienie nowych cech, które wcześniej były ignorowane w analizie liniowej. Dlatego zastosowanie technik nieliniowych prowadzi do bardziej realistycznej charakterystyki sygnałów i systemów. Te nowe podejścia do analizy i charakteryzacji sygnałów dostarczają nowych narzędzi do lepszej charakteryzacji sygnałów i stanowią poprzedni krok w celu stworzenia nowych, dokładniejszych i wydajniejszych automatycznych systemów w systemach rozpoznawania wzorców, takich jak rozpoznawanie głosu i twarzy.

WSTĘP

Weryfikacja tożsamości staje się kluczowym czynnikiem w naszym niezwykle połączonym społeczeństwie. Pytania typu: "Czy naprawdę jest tą osobą, za którą się podaje?", "Czy ta osoba jest upoważniona do korzystania z tego obiektu?" są rutynowo przedstawiane w różnych scenariuszach, począwszy od wydania prawa jazdy po uzyskanie wjazdu do kraju. Konieczność stosowania niezawodnych technik uwierzytelniania użytkowników wzrosła w następstwie zwiększonych obaw dotyczących bezpieczeństwa i szybkiego postępu w sieciach, komunikacji i mobilności. Systemy biometryczne, określane jako nauka mająca na celu rozpoznawanie jednostki na podstawie jej cech fizycznych lub behawioralnych, zaczynają zyskiwać akceptację jako uprawniona metoda ustalania tożsamości jednostki. Obecnie systemy biometryczne są stosowane w różnych zastosowaniach komercyjnych, cywilnych i kryminalistycznych w celu ustalenia tożsamości. W szczególności w pracy przedstawiono niechętny do współpracy system identyfikacji oparty na biometrii twarzy.

TŁO

W jaki sposób pomiary biologiczne kwalifikują się jako biometryczne? Jako cechę biometryczną można zastosować dowolną ludzką cechę fizjologiczną i/lub behawioralną, o ile spełnia ona następujące wymagania : uniwersalność, odrębność, trwałość, kolekcjonowalność. Wybór identyfikatorów biometrycznych ma zasadniczy wpływ na wydajność systemu. Wybór ten zależy w dużej mierze od zamierzonego zastosowania systemu. Obecnie do najczęściej stosowanych identyfikatorów biometrycznych zalicza się odciski palców geometrię dłoni , tęczówkę , twarz, itp. Większość systemów biometrycznych wymaga współpracy ze strony użytkowników w celu uzyskania ich danych biometrycznych. Identyfikacja twarzy nie wymaga jednak tego warunku do swojego zastosowania, chociaż można ją zastosować. To jest dlatego jest to jego główna przewaga nad innymi systemami biometrycznymi. Identyfikacja twarzy ludzkiej jest dziedziną szeroko badaną, gdyż koszt obliczeniowy nie okazał się wadą, ze względu na rosnące znaczenie tego rodzaju identyfikacji biometrycznej w bezpieczeństwie dostępu do miejsc takich jak lotniska, metro, pociągi i dworce autobusowe. Na proces identyfikacji twarzy składają się dwie istotne metody: detekcja (jednostka ze zbioru) i identyfikacja (czy dana osoba jest tym, za kogo się podaje). Wykrywanie twarzy polega na zlokalizowaniu ludzkiej twarzy na obrazie zarejestrowanym przez kamerę wideo, pobraniu jej i odizolowaniu od innych obiektów uchwyconych na obrazie. Identyfikacja polega na porównaniu przechwyconej twarzy z innymi twarzami, które zostały zapisane i zapisane w bazie danych. Podstawowa technologia identyfikacji cech twarzy obejmuje cechy własne (metryki twarzy) lub twarze własne. W ramach tego typu badań można znaleźć wiele różnych źródeł (dyskretna transformata kosinusowa (DCT), transformata Karhunena-Loeve′a (KL), analiza składowych niezależnych (ICA), analiza składowych głównych (PCA) itp.). Największą zaletą systemu identyfikacji twarzy jest jego brak współpracy, gdyż jest to system, który może działać niezależnie od współpracy użytkownika.

SYSTEM IDENTYFIKACJI TWARZY

W artykule przedstawiono dwa główne procesy związane z identyfikacją twarzy: wykrywanie twarzy i identyfikacja twarzy. Istnieją jednak również inne aspekty systemu identyfikacji twarzy, które należy wziąć pod uwagę. W module wykrywania twarzy pokazywane jest przechwytywanie twarzy, właśnie wtedy, gdy aparat robi zdjęcie lub kadruje. Akwizycję obrazu można przeprowadzić przy użyciu obrazów RGB, obrazów w podczerwieni (IR) i innych formatów; ostatnio wykorzystuje się także obrazy termowizyjne. Wybór formatu obrazu zależy od jego zastosowania, warunków oświetleniowych, lokalizacji (system wewnętrzny lub zewnętrzny) oraz stopnia bezpieczeństwa. W module identyfikacji twarzy znajduje się baza danych z informacjami o użytkowniku, które należy zlokalizować; dlatego należy przeprowadzić klasyfikację nadzorowaną. Podmoduł parametryzacji wyodrębnia cechy użytkownika, a system klasyfikacji generuje model w celu odróżnienia naszego użytkownika/użytkowników od pozostałych osób (rysunek 1).



Wykrywanie twarzy

Wyzwania związane z wykrywaniem twarzy można przypisać następującym czynnikom: poza, obecność lub brak elementów strukturalnych, wyraz twarzy, okluzja, orientacja obrazu, warunki obrazowania. Istnieje wiele ściśle powiązanych problemów z szacunkiemdo wykrywania twarzy. Lokalizacja twarzy ma na celu określenie położenia obrazu pojedynczej twarzy; jest to uproszczony problem wykrywania przy założeniu, że obraz wejściowy zawiera tylko jedną twarz . Celem wykrywania cech twarzy jest wykrycie obecność i położenie cech, takich jak oczy, nos, nozdrza, brwi, usta, usta, uszy itp., przy założeniu, że na obrazie jest tylko jedna twarz . Rozpoznawanie twarzy lub identyfikacja twarzy porównuje obraz wejściowy z bazą danych i zgłasza dopasowanie, jeśli zostanie znalezione . Celem uwierzytelniania twarzy jest weryfikacja tożsamości osoby na obrazie wejściowym , podczas gdy metody śledzenia twarzy w sposób ciągły szacują lokalizację i ewentualnie orientację twarzy w sekwencji obrazów w czasie rzeczywistym (rysunek 2).



Wprowadzono kilka systemów wykrywania twarzy. Istnieje wiele technik wykrywania twarzy na podstawie pojedynczego obrazu. Techniki wykrywania twarzy na podstawie pojedynczego obrazu podzielono na trzy kategorie.

o System oparty na wiedzy: Podejście to polega na wykorzystaniu reguł dotyczących ludzkich cech twarzy do wykrywania twarzy. Ludzkie cechy twarzy, takie jak dwoje oczu, które są względem siebie symetryczne, nos i usta oraz inne cechy odległości, reprezentują ten zestaw cech. Po wykryciu cech przeprowadzany jest proces weryfikacji w celu ograniczenia liczby fałszywych detekcji. To podejście jest dobre w przypadku obrazów z przodu, jak pokazano na rysunku 3.



Trudność polega na przełożeniu ludzkiej wiedzy na znane zasady i wykryciu twarzy w różnych pozach. Ponadto otoczenie może również stanowić problem. Na przykład zmiany w źródłach światła mogą dodać lub usunąć cienie asa. Dlatego przy projektowaniu systemu wykrywania twarzy należy wziąć pod uwagę wiele zmiennych. Z tych powodów w systemie niewspółpracującym technika ta jest niezmienna.
o System oparty na obrazie: w tym podejściu używany jest wstępnie zdefiniowany standardowy wzór twarzy w celu dopasowania segmentów obrazu w celu ustalenia, czy są to twarze, czy nie. Wykorzystuje algorytmy szkoleniowe do klasyfikowania regionów na klasy twarzowe i nietwarzowe. Techniki oparte na obrazach polegają na skanowaniu okien w wielu rozdzielczościach w celu wykrycia twarzy, dlatego techniki te charakteryzują się dużą szybkością wykrywania, ale są wolniejsze niż techniki oparte na cechach. Twarze własne i sieci neuronowe są przykładami technik opartych na obrazie. Podejście to ma tę zaletę, że jest proste w zastosowaniu, ale nie radzi sobie skutecznie ze zmianami skali, pozycji i kształtu
o System oparty na cechach: Podejście to polega na wyodrębnieniu rysów twarzy, na które nie mają wpływu zmiany warunków oświetleniowych, poza i/lub inne czynniki. Metody te są klasyfikowane według wyodrębnionych cech. Techniki oparte na cechach polegają na wyprowadzaniu i analizie cech w celu uzyskania wymaganej wiedzy o twarzach. Cechami mogą być kolor skóry, kształt twarzy lub cechy twarzy, takie jak oczy, nos itp. Metody oparte na cechach są preferowane w systemach czasu rzeczywistego, w których skanowanie okien w wielu rozdzielczościach stosowane w metodach opartych na obrazie nie ma zastosowania. Kolor skóry mężczyzny to skuteczna funkcja używana do rozpoznawania twarzy, ponieważ chociaż różni ludzie mają różne kolory skóry, kilka badań wykazało, że podstawowa różnica opiera się na ich intensywności, a nie na chrominancji. Twarze ludzkie mają specjalną teksturę, dzięki której można je oddzielić od różnych obiektów Metoda cech twarzy polega na wykrywaniu cech twarzy

Identyfikacja twarzy w Transform DomainSystems

Wykryte twarze zawsze mają zmienne warunki (oświetlenie, wyraz, obrót, przesunięcie itp.), dlatego obrazy użyte do uczenia mogą wykazywać pewne zmiany w porównaniu z obrazami z wykrywania twarzy. Korzystanie z funkcji lub systemów opartych na wiedzy jest wadą ze względu na dużą zmienność danych wynikającą ze zmiennych warunków. Dlatego też transformacja systemów domen jest dobrym celem, ponieważ grupują informacje i przyczyniają się do większej dyskryminacji w identyfikacji twarzy. Analiza domeny transformacji jest powszechnie stosowaną techniką przetwarzania obrazu i parametryzacji. W ostatnich latach wykonano pewne prace w celu wydobycia aby przekształcać cechy domeny w celu identyfikacji obrazu. Li i inni wyodrębnilicechy zakresu Fouriera i kąta w celu identyfikacji obrazu odcisku dłoni. Lai i inni wykorzystują holistyczne niezmiennicze cechy Fouriera do rozpoznawania obrazu twarzy . Niektórzy badacze wykorzystują inną strukturę widmową generowaną w wyniku rozkładu wartości osobliwych (SVD) . Jednakże Tian i in. wskazują, że ta funkcja nie zawiera odpowiednich informacji do rozpoznawania twarzy . Hafed i Levine (2001) wyodrębniają dyskretną transformatę kosinusową (DCT) do rozpoznawania twarzy. Zwracają uwagę, że DCT uzyskuje niemal optymalną wydajność transformacji Karhunena - Loeve′a (KL) w informacjach o kompresji twarzy . Wydajność DCT jest lepsza od dyskretnej transformaty Fouriera (FT) i innych konwencjonalnych transformacji. Dzięki ręcznemu wyborowi pasm częstotliwości DCT, metoda ich rozpoznawania pozwala uzyskać efekt rozpoznawania podobny do metody Eigenface , która opiera się na transformacji KL. Niemniej jednak ich metoda nie może zapewnić racjonalnej reguły ani strategii wyboru pasma. Nie może też przewyższać klasycznej metody Eigenface. Ponadto zaproponowano pewne rozszerzone metody dyskryminacji. Zhang i inni przedstawiają podwójną metodę rozpoznawania twarzy w przestrzeni własnej. W. Malina (2001) zaproponował w swojej pracy kilka nowych zasad dyskryminacji opartych na kryterium Fishera. Yang wykorzystuje jądro analizy głównych składowych (PCA) do ekstrakcji i rozpoznawania cech twarzy, podczas gdy Bartlett i inni (2002) stosują niezależną analizę składowych (ICA) w rozpoznawaniu twarzy. Yang pokazuje jednak, że zarówno jądra ICA, jak i PCA wymagają znacznie więcej czasu obliczeniowego niż PCA. Ponadto, gdy stosuje się odległość euklidesową, nie ma znaczącej różnicy w skuteczności klasyfikacji PCA i ICA . Jing i inni (2003) przedstawili klasyfikację metody kombinacji sortowników do rozpoznawania twarzy. Artykuł ten nie analizuje i nie porównuje tych rozszerzonych metod dyskryminacji, ale ogranicza się do porównania głównych metod dyskryminacji liniowej, w tym metody Eigenface, metody Fisherface, DLDA i dyskryminowanej powierzchni falkowej. Transformacja KL jest optymalną transformacją służącą do usuwania korelacji statystycznej. Spośród transformacji dyskretnych DCT zbliża się do transformacji KL (Hu, Worrall, Sadka i Kondoz, 2001). Innymi słowy, DCT ma silną zdolność usuwania korelacji i kompresji obrazów. Co więcej, DCT można wykorzystać poprzez szybką transformatę Fouriera (FFT), podczas gdy nie ma algorytmu szybkiej realizacji dla transformacji KL. Dlatego nasze podejście w wystarczającym stopniu wykorzystuje te korzystne właściwości DCT. Poniższa tabela przedstawia różne systemy oparte na różnych metodach rozpoznawania twarzy wraz z odpowiadającymi im współczynnikami rozpoznawania. Wykorzystywane bazy danych to ORL [baza danych ORL], Yale [baza danych Yale], AR-Face [baza danych AR] i FERET [baza danych FERET].

PRZYSZŁE TENDENCJE

Ostatnio zaproponowano liczne metody lokalizowania lub wykrywania twarzy, które łączą kilka cech twarzy. Większość z nich korzysta z globalnych cech, takich jak kolor, rozmiar i kształt skóry, aby znaleźć kandydatów na twarz, a następnie zweryfikować tych kandydatów przy użyciu różnych metod lokalnej parametryzacji. Wyzwaniem jest osiągnięcie niezmienności przechwycone obrazy z warunków (światło, kształty…) i zmian pozycji (obroty, skale…). Tworzenie i rozwój nowych metod opartych na systemie dziedzin transformacji zapewni solidne cechy umożliwiające osiągnięcie tej niezmienności. Jeśli chodzi o identyfikację twarzy, w tym systemie można zastosować techniki 3D, ale w zastosowaniach czasu rzeczywistego główną wadą są koszty obliczeniowe. Przebudowa twarzy za pomocą technik 3D pozwala uzyskać więcej informacji i dowolnych funkcji wydobycia. Co więcej, system ten zachowuje jakość braku współpracy. W przyszłości możliwe będzie wykorzystanie systemów multimodalnych o innych cechach biometrycznych wygenerować silniejszy i solidniejszy system.

WNIOSEK

Rozpoznawanie twarzy jest trudnym i interesującym problemem. Jednakże można to również uznać za część szerszej próby rozwiązania jednego z największych wyzwań stojących przed wizją komputerową, czyli rozpoznawania obiektów.W szczególności identyfikacja twarzy staje się bardzo ważnym systemem biometrycznym w walce o ograniczenie globalnego terroryzmu. Przeprowadzono już wiele badań w tym zakresie, a mając na uwadze zagrożenie bezpieczeństwa, przed jakim stoi obecnie świat, niewątpliwie w przyszłości pojawi się znacznie więcej publikacji na temat identyfikacji twarzy.

WSTĘP.

Prawie wszystkie roboty autonomiczne muszą nawigować. Nawigację definiujemy podobnie jak Franz i Mallot (2000): "Nawigacja to proces wyznaczania i utrzymywania kursu lub trajektorii do lokalizacji docelowej" Dopuszczamy, że ta definicja może być bardziej restrykcyjna, niż są do tego przyzwyczajeni niektórzy czytelnicy - nie obejmuje na przykład problemów takich jak unikanie przeszkód i śledzenie pozycji - ale odpowiada naszym tutaj celom. Większość algorytmów opublikowanych w literaturze robotyki lokalizuje w celu nawigacji . Oznacza to, że określają własne położenie i położenie celu w odpowiednim układzie współrzędnych. Podejście to jest problematyczne z kilku powodów. Lokalizacja wymaga mapy dostępnych punktów orientacyjnych (tj. listy lokalizacji punktów orientacyjnych w odpowiednim układzie współrzędnych) oraz opisu tych punktów orientacyjnych. Na początku pracy operator dostarczał robotowi mapę jego otoczenia. Jednak ostatnio badacze opracowali jednoczesne nowe algorytmy lokalizacji i mapowania (SLAM), które pozwalają robotom uczyć się map środowiskowych podczas nawigacji . Oczywiście autonomiczne algorytmy SLAM muszą wybierać, które punkty orientacyjne mają zostać zmapowane i wykrywać te punkty orientacyjne z różnych pozycji i orientacji. Mając mapę, robot musi powiązać wykryte punkty orientacyjne z punktami na mapie. Ten problem skojarzenia danych jest trudny w zaśmieconym środowisku rzeczywistym i jest obszarem aktywnych badań. W tym rozdziale opisujemy alternatywne podejście do nawigacji, zwane wizualnym bazowaniem, które nie podejmuje wyraźnej próby lokalizacji, a zatem nie wymaga mapy punktów orientacyjnych. Istnieją zasadniczo dwa typy algorytmów naprowadzania wizualnego: oparte na cechach i oparte na obrazach. Algorytmy oparte na cechach, jak sama nazwa wskazuje, próbują wyodrębnić te same cechy z wielu obrazów i wykorzystać zmianę wyglądu odpowiednich obiektów do nawigacji. Zgodność funkcji jest - podobnie jak skojarzenie danych - trudnym, otwartym problemem w środowiskach rzeczywistych. Twierdzimy, że algorytmy naprowadzania oparte na obrazach, które dostarczają informacji nawigacyjnych w oparciu o porównania całego obrazu, są bardziej odpowiednie dla środowisk rzeczywistych we współczesnej robotyce.

TŁO

Algorytmy wizualnego naprowadzania nie podejmują prób lokalizacji w celu nawigacji. Dlatego nie jest wymagana żadna mapa. Zamiast tego obraz IS (z powodów historycznych zwykle nazywany migawką) jest rejestrowany w docelowej lokalizacji S = (x,sub>S, y_S). Należy zauważyć, że chociaż S definiuje się jako punkt na płaszczyźnie, większość algorytmów bazowania można łatwo rozszerzyć na trzy wymiary . Kiedy robot naprowadzający chce wrócić do S z pobliskiej pozycji C = (x_C, y_C), pobiera obraz i porównuje go z I_S. Wektor macierzysty H = S - C wynika z rozbieżności między I_S i I_C . Orientacja robota w punktach C i S jest często różna; w takim przypadku rozbieżność obrazu ma znaczenie tylko wtedy, gdy układ scalony zostanie obrócony w celu uwzględnienia tej różnicy. Algorytmy wizualnego naprowadzania różnią się sposobem obliczania tej rozbieżności. Wizualne naprowadzanie jest procesem iteracyjnym. Wektor początkowy H jest często niedokładny i prowadzi robota bliżej pozycji docelowej, ale nie bezpośrednio do niej. Jeżeli H nie dowiezie robota do celu, w nowym położeniu robota wykonywany jest kolejny obraz IC i proces się powtarza. Obrazy I_S i I_C są zazwyczaj obrazami panoramicznymi w skali szarości. Obrazy panoramiczne są przydatne, ponieważ dla danej lokalizacji (x, y) zawierają te same informacje o obrazie niezależnie od orientacji robota. Większość badaczy do tworzenia tych obrazów używa kamery obrazującej zwierciadło półkuliste, stożkowe lub paraboloidalne . Niektóre algorytmy naprowadzania wizualnego wyodrębniają cechy z I_S i I_C i wykorzystują je do obliczenia rozbieżności obrazu. Alternatywnie rozbieżność można obliczyć na podstawie całych obrazów, zasadniczo traktując każdy piksel jako realną cechę. Poniżej omówiono algorytmy wizualnego naprowadzania oparte na cechach i obrazie.

WIZUALNY DOMOWANIE OPARTE NA FUNKCJACH

Oparte na cechach metody wizualnego naprowadzania dzielą I_S i I_C na cechy i tło (problem ekstrakcji cech). Każda zidentyfikowana cecha na migawce jest następnie zwykle łączona z jedną cechą w I_C (problem zgodności). Wektor macierzysty jest wyznaczany - w zależności od algorytmu - ze zmiany położenia i/lub pozornej wielkości sparowanych obiektów. Ogólnie rzecz biorąc, aby algorytmy bazowania oparte na cechach działały poprawnie, muszą niezawodnie rozwiązywać problemy ekstrakcji cech i korespondencji. Model migawki (Cartwright i Collett (1983)) - pierwszy algorytm wizualnego naprowadzania, który pojawił się w literaturze i źródło terminu "migawka" opisującego obraz docelowy - dopasowuje każdą migawkę do aktualnej cechy znajdującej się najbliżej namiaru (po obróceniu obu obrazów do tej samej orientacji kompasu zewnętrznego). Elementy to czarne cylindry w skądinąd pustym środowisku. Z każdą parą cech powiązane są dwa wektory jednostkowe, jeden promieniowy, a drugi styczny. Wektor promieniowy jest równoległy do łożyska elementu migawki; wektor styczny jest prostopadły do wektora promieniowego. Kierunek wektora promieniowego wybiera się tak, aby przesunąć agenta w taki sposób, aby zmniejszyć rozbieżność w pozornym rozmiarze pomiędzy sparowanymi cechami. Kierunek wektora stycznego wybiera się tak, aby przesunąć czynnik w taki sposób, aby zmniejszyć rozbieżność w namiarie pomiędzy sparowanymi obiektami. Wektory promieniowe i styczne dla wszystkich par cech są uśredniane w celu uzyskania wektora naprowadzającego. Model migawkowy został opracowany w celu wyjaśnienia zachowania pszczół miodnych poszukujących gniazd, ale stał się inspiracją kilka algorytmów automatycznego naprowadzania wizualnego. Jednym z takich algorytmów jest model wektora średniego punktu orientacyjnego (ALV) . Model ALV, podobnie jak model migawki, wyodrębnia cechy zarówno z I_C, jak i I_S. Model ALV nie rozwiązuje jednak bezpośrednio problemu korespondencji. Zamiast tego, mając dane cechy wyodrębnione z IS, algorytm oblicza i przechowuje wektor jednostkowy ALV_S w kierunku średniego namiaru do wszystkich cech widzianych z S. W C algorytm wyodrębnia cechy z I_C i oblicza ich średni namiar zakodowany we wektorze jednostkowym _C. Wektor domowy H definiuje się jako ALV_C - ALV_S. Rysunek 1 ilustruje obliczenia wektora domu dla prostego środowiska z czterema łatwo rozpoznawalnymi punktami orientacyjnymi.



Kilka innych interesujących algorytmów bazowania opartych na funkcjach algorytmy można znaleźć w literaturze. Niestety ograniczenia przestrzenne uniemożliwiają nam ich tutaj przejrzenie. Godne uwagi są dwa algorytmy: wizualne naprowadzanie poprzez "surfowanie po epipolach" oraz model wektorów proporcjonalnych. Modele Snapshot i ALV zostały przetestowane przez ich twórców w środowiskach, w których cechy silnie kontrastują z tłem, a zatem są łatwe do wyodrębnienia. W jaki sposób ekstrakcja cech i zgodność są rozwiązywane w zagraconym środowisku w świecie rzeczywistym? Jedna z metod została opisana w: Gourichon (2002). Autorzy wykorzystują obrazy przekonwertowane do przestrzeni barw HSV (Barwa-Nasycenie), która według doniesień jest bardziej odporna na zmiany oświetlenia niż RGB. Cechy są definiowane jako obszary obrazu o w przybliżeniu jednakowych kolorach (identyfikowane przy użyciu kosztownej obliczeniowo techniki powiększania obszarów). Potencjalne pary cech są oceniane na podstawie ich różnicy w średnim odcieniu, średnim nasyceniu, średniej intensywności i łożysku. Algorytm wyszukuje zestaw par, które maksymalizują sumę poszczególnych dopasowań scores. Schemat parowania wymaga obliczeń wyniku parowania z częstotliwością O(n,sup>2) (gdzie n to liczba cech). Algorytm jest czasami oszukiwany przez cechy o podobnych kolorach (w szczególności przez sparowanie niebieskiego krzesła na zdjęciu z niebieskimi drzwiami na bieżącym zdjęciu). Gourichon i in. nie badali środowisk o zmiennych warunkach oświetleniowych. W literaturze pojawia się kilka innych metod ekstrakcji cech i algorytmów korespondencyjnych. Wiele z nich cierpi na te same problemy, co algorytm Gourichona opisany powyżej. Pojawienie się kilku konkurencyjnych algorytmów ekstrakcji cech i korespondencji w ostatnich publikacjach wskazuje, że są to otwarte i trudne problemy; dlatego też w tym rozdziale zalecamy bazowanie oparte na obrazach.

WIZUALNE DOMOWANIE OPARTE NA OBRAZIE

Algorytmy wizualnego naprowadzania oparte na funkcjach wymagają spójnego wyodrębniania cech i zgodności w różnych pozycjach oglądania. Obydwa te zjawiska stanowią wciąż otwarte problemy w zakresie widzenia komputerowego. Istniejące rozwiązania są często wymagające obliczeniowo. Algorytmy wizualnego naprowadzania oparte na obrazie całkowicie pozwalają uniknąć tych problemów. Wnioskują o rozbieżnościach obrazu na podstawie całych obrazów; żaden piksel nie jest pomijany. Wierzymy, że te algorytmy stanowią bardziej realną opcję dla robotyki działającej w świecie rzeczywistym. Do tej pory opublikowano trzy algorytmy wizualnego naprowadzania opartego na obrazie; opisujemy je poniżej. Wypaczenie obrazu Algorytm wypaczania obrazu zadaje następujące pytanie: Kiedy robot znajduje się w pozycji C w nieznanej orientacji, jaka zmiana orientacji i położenia jest wymagana, aby przekształcić I_C w I_S? Aby precyzyjnie odpowiedzieć na to pytanie, robot musi znać odległość do wszystkich obrazowanych obiektów w I_S. Nie mając tych informacji, algorytm wypaczania obrazu zakłada, że wszystkie obiekty znajdują się w równej (choć nieznanej) odległości od S. Algorytm wyszukuje wartości zmiany położenia i orientacji, co minimalizuje błąd średniokwadratowy pomiędzy przekształconym I_C i I_SS. Ponieważ funkcja błędu średniokwadratowego obfituje w lokalne minima, autorzy uciekają się do przeszukiwania metodą brute-force wszystkich dopuszczalnych wartości zmiany położenia i orientacji. Choć założenie równej odległości jest mało prawdopodobne, algorytm często daje całkiem dokładne wartości H. W przeciwieństwie do większości wizualnych schematów naprowadzania, zniekształcanie obrazu nie wymaga zewnętrznego odniesienia do kompasu. Niestety, poszukiwanie wektora naprowadzającego metodą brute-force i duża liczba transformacji układu scalonego przeprowadzonych podczas tego wyszukiwania sprawiają, że zniekształcanie obrazu jest dość kosztowne obliczeniowo.

Bazowanie za pomocą technik przepływu optycznego

Kiedy system obrazowania przesuwa się z S do C, obraz określonego punktu w przestrzeni przesuwa się z I_S(x,y) do I_C(x′,y′). Ruch ten nazywany jest przepływem optycznym i (x-x′, y-y′) jest tak zwanym wektorem przemieszczenia pikseli. Vardy i Möller (2005) pokazują, że wektor macierzysty H można wywnioskować z pojedynczego wektora przemieszczenia, o ile robot nawigacyjny jest ograniczony do poruszania się w jednej płaszczyźnie. W celu oszacowania można połączyć kilka zaszumionych wektorów przemieszczenia. H. Vardy i Möller (2005) opisują szereg metod, zaadaptowanych z literatury dotyczącej przepływu optycznego, w celu oszacowania wektora przemieszczenia. Jedna z najskuteczniejszych metod - BlockMatch - dzieli obraz migawki na kilka podobrazów o jednakowej wielkości. Następnie algorytm przeszukuje podzbiór układów scalonych metodą brute-force, aby znaleźć najlepsze dopasowanie dla każdego podobrazu. Wektor przemieszczenia jest obliczany od środka każdego podobrazu do środka pary dopasowań w I_C. Algorytm mniej wymagający obliczeniowo szacuje wektor przemieszczenia na podstawie gradientu intensywności w każdym pikselu w układzie scalonym. Gradient intensywności na konkretnym pikselu można łatwo obliczyć na podstawie intensywności otaczających ten piksel. Nie jest wymagane wyszukiwanie metodą brute-force. W testach porównawczych firmy Vardy & Möller wykazali, że ich metody oparte na przepływie optycznym działają niezmiennie lepiej niż zniekształcenie obrazu w kilku niezanieczyszczonych środowiskach wewnętrznych. Wadą metod naprowadzania z wykorzystaniem przepływu optycznego jest to, że robot może poruszać się w jednej płaszczyźnie. Autorzy nie podają sposobu na rozszerzenie swojego algorytmu na trójwymiarowe wizualne naprowadzanie. Surfowanie po powierzchni różnic Zeil i inni (2003) opisują właściwość scen naturalnychktóre można wykorzystać do wizualnego naprowadzania: jako odległość klideńska między S i C wzrasta, piksel-różnica średniokwadratowa (RMS) pomiędzy I_S a I_C rośnie płynnie i monotonicznie. Labrossei Mitchell również odkryli to zjawisko. Zeil zgłosił tojakowzrost sygnału RMS był zauważalny hałas do około trzech metrów od S na zewnątrz środowisko testowe; nazywają ten region zlewnią obszar. RMS, oceniany w lokalizacjach w podzbiorze płaszczyzna otaczająca S tworzy powierzchnię matematyczną, powierzchnia różnicy. Przykładowa powierzchnia różnicowa to pokazano na rysunku 2(a) (szczegóły w podpisie).Zeil opisuje prosty algorytm do użytku domowego powierzchnia różnicy RMS. Ich algorytm "Zaniedbany" algorytm kieruje robotem, aby poruszał się w bieżącym kierunku podczas okresowego próbkowania sygnału RMS. Kiedy bieżąca próbka jest większa niż poprzednia, robot ma się zatrzymać i obrócić o dziewięćdziesiąt stopni (zgodnie z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara, nie ma to znaczenia). Następnie powtarza proces w nowym kierunku. Agent zatrzymuje się, gdy sygnał RMS spadnie poniżej wcześniej określonego progu. Zbadaliśmy inspirowaną biologicznie metodę naprowadzania na powierzchnię, która w niektórych sytuacjach była skuteczniejsza niż "Run-Down". W przeciwieństwie do metod przepływu optycznego opisanych w poprzedniej sekcji, wizualne naprowadzanie poprzez optymalizację powierzchni różnicowej można łatwo rozszerzyć do trzech wymiarów . Niestety, gdy warunki oświetleniowe zmieniają się między przechwytywaniem IS i IC, minimum .Powierzchnia różnicowa RMS często nie pokrywa się z powierzchnią S, co uniemożliwia powrót do pozycji bazowej.

PRZYSZŁE TENDENCJE

Nie opublikowano jeszcze żadnej pracy porównującej skuteczność opisanych powyżej algorytmów naprowadzania opartych na obrazie. Wydawałoby się to logicznym kolejnym krokiem dla badaczy naprowadzania w oparciu o obrazy. Jak wspomnieliśmy w części zatytułowanej "Surfowanie po powierzchni różnic", powierzchnia różnic jest zakłócana przez zmiany oświetlenia pomiędzy ujęciami I_S i I_C. Problem ten oczywiście wymaga rozwiązania i jest przedmiotem naszych bieżących badań. Na koniec interesujące byłoby porównanie standardowych algorytmów nawigacji opartych na mapach z przedstawionymi tutaj metodami wizualnego naprowadzania opartego na obrazach.

WNIOSEK

Algorytmy wizualnego naprowadzania - w przeciwieństwie do większości algorytmów nawigacji spotykanych w literaturze robotyki - nie wymagają szczegółowej mapy swojego otoczenia. Dzieje się tak dlatego, że nie podejmują oni próby jednoznacznego wnioskowania o swoim położeniu względem celu. Algorytmy te zamiast tego wnioskują o wektor macierzysty na podstawie rozbieżności między przechowywanym obrazem migawki wykonanym w pozycji docelowej a obrazem zarejestrowanym w ich bieżącej lokalizacji. Przyjrzeliśmy się dwóm typom algorytmów naprowadzania wizualnego: opartym na cechach i obrazie. Argumentowaliśmy, że algorytmy oparte na obrazach są lepsze, ponieważ nie podejmują próby rozwiązania trudnych problemów spójnej ekstrakcji cech i zgodności - rozwiązań, których wymagają algorytmy oparte na cechach. Spośród trzech ocenionych algorytmów opartych na obrazach zniekształcenie obrazu prawdopodobnie nie jest możliwe w praktyce ze względu na wymagające obliczeniowo wyszukiwanie metodą brute-force. Konieczne jest określenie, który z dwóch pozostałych algorytmów opartych na obrazach jest bardziej skuteczny w przypadku samonaprowadzania robota w środowiskach rzeczywistych.

WSTĘP

Rozwój autonomicznych robotów mobilnych stale zyskuje na znaczeniu, szczególnie w wojsku do celów obserwacyjnych, a także w przemyśle do zadań inspekcyjnych i związanych z obsługą materiałów. Kolejnym rozwijającym się rynkiem o ogromnym potencjale są roboty mobilne do rozrywki. Podstawowym wymogiem dla autonomicznych robotów mobilnych w większości zastosowań jest możliwość nawigacji z punktu początkowego do określonego celu. Robot mobilny musi być w stanie wygenerować bezkolizyjną ścieżkę łączącą punkt początkowy z określonym celem. W tym artykule omówione zostaną niektóre kluczowe algorytmy nawigacji robotów mobilnych.

TŁO

Na przestrzeni lat opracowano wiele algorytmów autonomicznej nawigacji robotów mobilnych. Algorytmy te dzieli się na trzy różne kategorie: globalne planowanie ścieżki, lokalne metody nawigacji i metody hybrydowe, w zależności od rodzaju środowiska, w którym działa robot mobilny, oraz jego wiedzy o tym środowisku. W tym artykule omówiono niektóre kluczowe algorytmy nawigacji robota mobilnego. Omówione zostaną zalety i wady tych algorytmów. Omówione algorytmy obejmują funkcję nawigacyjną, mapy drogowe, histogram pola wektorowego, sztuczne pole potencjału, nawigację hybrydową oraz algorytm zintegrowany. Należy zauważyć, że wszystkie algorytmy nawigacyjne omówione w tym artykule zakładają, że robot działa w środowisku planarnym.

GLOBALNE PLANERY ŚCIEŻKI

Algorytmy globalnego planowania ścieżki odnoszą się do grupy algorytmów nawigacyjnych, które planują optymalną trasę od punktu początkowego do danego celu w znanym środowisku. Ta grupa algorytmów wymaga, aby środowisko było wolne od dynamicznych i nieprzewidzianych przeszkód. W tej sekcji omówione zostaną dwa kluczowe algorytmy globalnego planowania ścieżki: funkcje nawigacyjne i mapy drogowe.

Funkcje nawigacyjne

Najczęściej stosowanym algorytmem globalnego planowania ścieżki jest prawdopodobnie funkcja nawigacyjna obliczona na podstawie algorytmu "rozszerzenia frontu fali" ze względu na jej praktyczność, łatwość implementacji i solidność. Funkcja nawigacyjna N to odległość Manhattanu do celu z wolnej przestrzeni w otoczeniu. Algorytm wymaga, aby informacje o otoczeniu dostarczone robotowi były reprezentowane jako tablica komórek siatki. Funkcja nawigacji przypisuje wartość liczbową N do każdej komórki, przy czym komórka docelowa ma najniższą wartość, a pozostałe niezajęte komórki mają stopniowo wyższe wartości, tak aby najstromszy spadek z dowolnej komórki wyznaczał ścieżkę do celu. Wartość niezajętej komórki rośnie wraz z odległością od celu. Każda komórka siatki jest albo wolna, albo zajęta, oznaczona jako gC_free i gC_occupied. Najpierw wartość N jest ustawiana na "0" w komórce docelowej gC_goal. Następnie wartość N jest ustawiana na "1" dla każdego sąsiada 1 (definicja sąsiadów 1 znajduje się na rysunku )



gC_goal, który znajduje się w gC_free. Zakłada się, że odległość między dwoma sąsiadami 1-1 jest znormalizowana do 1. Ogólnie rzecz biorąc, wartość każdej komórki gC_free jest ustawiana na N+1 (np. "2") dla każdego nieprzetworzonego sąsiada 1-gCfree komórki siatki o wartości N (np. "1"). Powtarza się to, aż wszystkie komórki siatki zostaną przetworzone. Na koniec generowana jest ścieżka do celu, podążając za najstromszym spadkiem spośród wartości N. Aby zapobiec ocieraniu się ścieżki o przeszkody, komórki siatki, które znajdują się w odległości mniejszej niż bezpieczna odległość ? od przeszkód, są pomijane w obliczeniach funkcji nawigacyjnej. Rysunek 2 przedstawia ścieżkę wygenerowaną przez funkcję nawigacyjną.



Czarne komórki to przeszkody, a szare komórki to obszary niebezpieczne.

Mapy drogowe

Mapa drogowa to sieć jednowymiarowych krzywych, które odzwierciedlają łączność wolnej przestrzeni w środowisku . Po skonstruowaniu mapy drogowej jest ona wykorzystywana jako zbiór standardowych ścieżek. Planowanie ścieżki sprowadza się zatem do połączenia pozycji początkowej i docelowej z punktami na mapie drogowej. Zaproponowano różne metody oparte na tej ogólnej idei. Należą do nich graf widoczności , diagram Woronoja , siatka autostrad i sylwetka. Graf widoczności jest najprostszą formą mapy drogowej. Ten algorytm zakłada, że środowisko składa się wyłącznie z przeszkód wielokątnych. Węzły grafu widoczności obejmują punkt początkowy, cel i wszystkie wierzchołki przeszkód w środowisku. Krawędzie grafu to proste odcinki linii, które łączą dowolne dwa węzły w linii widzenia. Wreszcie, najkrótsza ścieżka od początku do celu może być uzyskana z grafu widoczności.

Zalety i wady

Zaletą funkcji nawigacyjnych, map drogowych i innych algorytmów globalnego planowania ścieżki jest to, że ciągła, bezkolizyjna ścieżka może zostać zawsze znaleziona poprzez analizę łączności wolnej przestrzeni. Algorytmy te wymagają jednak, aby środowisko było znane i statyczne. Wszelkie zmiany w środowisku mogą unieważnić wygenerowaną ścieżkę. W związku z tym funkcje nawigacyjne i inne algorytmy globalnego planowania ścieżki zazwyczaj nie nadają się do nawigacji w początkowo nieznanym środowisku oraz w środowiskach z dynamicznymi i nieprzewidzianymi przeszkodami.

METODY NAWIGACJI LOKALNEJ

W przeciwieństwie do globalnych planistów ścieżki, metody nawigacji lokalnej nie wymagają dostarczenia robotowi znanej mapy środowiska. Zamiast tego metody nawigacji lokalnej opierają się na bieżących i lokalnych informacjach z czujników, aby umożliwić robotowi mobilnemu nawigację online. W tej sekcji zostaną ocenione dwa kluczowe algorytmy nawigacji lokalnej: sztuczne pole potencjału i histogram pola wektorowego.

Sztuczne Pole Potencjału

Metoda sztucznego pola potencjału , po raz pierwszy wprowadzona przez Khatiba, jest prawdopodobnie najbardziej znanym algorytmem lokalnej nawigacji robotów mobilnych ze względu na swoją prostotę i skuteczność. Robot jest reprezentowany jako cząstka w przestrzeni konfiguracyjnej q poruszająca się pod wpływemsztucznego potencjału generowanego przez konfigurację celu qgoal i skalarną odległość do przeszkód. Zazwyczaj cel generuje atrakcyjny potencjał, taki jak



który ciągnie robota w kierunku celu, a każda przeszkoda i wytwarza potencjał odpychający, taki jak



która odpycha robota od przeszkody. W przypadku, gdy występuje więcej niż jedna przeszkoda, całkowita siła odpychająca jest obliczana jako suma wszystkich sił odpychających wytwarzanych przez przeszkody. K_g i K_o to odpowiednie zyski potencjału przyciągającego i odpychającego. d_i to skalarna odległość między robotem a przeszkodą i. Potencjał odpychający będzie miał wpływ na robota tylko wtedy, gdy przesunie się on na odległość mniejszą niż d₀. Oznacza to, że d₀


Rysunek 3 przedstawia siłę przyciągania





która powstaje z celu i siły odpychającej



generowany przez przeszkodę i. F_R jest wypadkową wszystkich sił odpychających i przyciągających. Należy zauważyć, że n oznacza całkowitą liczbę przeszkód, która jest mniejsza niż odległość do od robota. W każdym położeniu kierunek tej siły jest uważany za najbardziej obiecujący kierunek ruchu robota.



Histogram pola wektorowego

Metoda histogramu pola wektorowego wymaga, aby środowisko było reprezentowane przez teselację komórek siatki. Każda komórka siatki zawiera wartość liczbową z zakresu od 0 do 15. Wartość ta określa, czy środowisko reprezentowane przez daną komórkę siatki jest zajęte, czy nie. 0 oznacza absolutną pewność, że komórka nie jest zajęta, a 15 oznacza absolutną pewność, że komórka jest zajęta. Dwuetapowy proces redukcji danych jest przeprowadzany rekurencyjnie w celu obliczenia pożądanego ruchu robota w każdym momencie. W pierwszym etapie wartości wszystkich komórek siatki znajdujących się w pobliżu chwilowej pozycji robota są redukowane do jednowymiarowego histogramu biegunowego. Każdy przedział z histogramu biegunowego odpowiada kierunkowi widzianemu z bieżącej pozycji robota i zawiera wartość reprezentującą całkowitą sumę wartości komórek siatki wzdłuż tego kierunku. Wartości z histogramu biegunowego są również znane jako gęstość przeszkód biegunowych i reprezentują obecność przeszkód w odpowiednich kierunkach. W drugim etapie robot wybiera przedział o niskiej gęstości przeszkód biegunowych i kierunku najbliższym celu. Robot porusza się w kierunku reprezentowanym przez wybrany przedział, ponieważ ten kierunek jest wolny od przeszkód i przybliża robota do celu.

Zalety i wady

Zaletą sztucznego pola potencjału, histogramu pola wektorowego i innych metod nawigacji lokalnej jest to, że nie obejmują one wstępnego etapu przetwarzania mającego na celu uchwycenie łączności wolnej przestrzeni w zwięzłej reprezentacji. Dlatego nie jest wymagana wcześniejsza znajomość otoczenia. W dowolnym momencie ścieżka jest określana na podstawie bezpośredniego otoczenia robota. Pozwala to robotowi na omijanie wszelkich dynamicznych przeszkód w swoim otoczeniu. Główną wadą metod nawigacji lokalnej jest to, że są one zasadniczo metodami optymalizacji najstromszego zejścia. To sprawia, że robot mobilny jest podatny na minima lokalne . Minimum lokalne w metodzie pola potencjalnego występuje, gdy siły przyciągania i odpychania znoszą się wzajemnie. Robot zostanie unieruchomiony, gdy wpadnie w minimum lokalne i straci zdolność do osiągnięcia celu. Zaproponowano wiele metod rozwiązania problemu minimów lokalnych . Na przykład Liu Chengqing zaproponował metodę wirtualnych przeszkód, w której robot wykrywa minima lokalne i wypełnia obszar sztucznymi przeszkodami. W rezultacie metoda ta zamyka wszystkie wklęsłe przeszkody, unikając w ten sposób awarii minimów lokalnych. Inną metodę rozwiązania problemu minimów lokalnych zaproponował Jin-Oh Kim . Metoda ta wykorzystuje wolne funkcje harmoniczne minimów lokalnych oparte na dynamice płynów do budowania sztucznych potencjałów dla unikania przeszkód.

METODY HYBRYDOWE

Inna grupa algorytmów proponuje połączenie metod nawigacji lokalnej i globalnego planowania ścieżki. Algorytmy te mają na celu połączenie zalet metod lokalnych i globalnych, a także wyeliminowanie niektórych ich słabości. W tej sekcji omówione zostaną dwa kluczowe algorytmy metod hybrydowych: nawigacja hybrydowa i algorytm zintegrowany.

Nawigacja hybrydowa

Rysunek 4 przedstawia ilustrację algorytmu nawigacji hybrydowej .



Algorytm ten łączy funkcję nawigacji z metodą pola potencjalnego. Jego celem jest eliminacja błędów minimów lokalnych, a jednocześnie unikanie kolizji z przeszkodami dynamicznymi. Robot najpierw oblicza ścieżkę łączącą jego bieżącą pozycję z celem, korzystając z funkcji nawigacji. Następnie robot umieszcza okrąg o promieniu empirycznym, którego środek znajduje się w jego bieżącej pozycji. Komórka odpowiadająca przecięciu okręgu ze ścieżką funkcji nawigacji jest znana jako punkt przyciągania. Punkt przyciągania to komórka o najniższej wartości N, jeśli istnieje więcej niż jedno przecięcie. Robot zbliża się do punktu przyciągania, korzystając z metody pola potencjalnego, a okrąg porusza się wraz z robotem, co powoduje zmianę punktu przyciągania. W rezultacie robot zawsze podąża za dynamicznym punktem przyciągania, który będzie zmierzał w kierunku celu wzdłuż ścieżki wolnej od minimów lokalnych funkcji nawigacji. Promień okręgu jest zwiększany, aby przeciąć ścieżkę funkcji nawigacyjnej w przypadkach, gdy nie zostaną znalezione żadne przecięcia. Promień okręgu jest zmniejszany do wartości mniejszej niż odległość między robotem a jego celem, gdy odległość między robotem a jego celem staje się mniejsza niż promień okręgu. Ma to na celu zapewnienie, że wartość N następnego przecięcia będzie mniejsza niż bieżąca wartość N.

Algorytm zintegrowany

W ostatnich latach zaproponowano algorytm zintegrowany , który umożliwia robotowi mobilnemu planowanie ścieżek o swobodnych minimach lokalnych i unikanie kolizji z dynamicznymi przeszkodami w nieznanym środowisku. Algorytm ten modyfikuje metodę eksploracji opartą na granicach , pierwotnie wykorzystywaną do tworzenia map, w algorytm planowania ścieżki w nieznanym środowisku. Zmodyfikowana metoda eksploracji oparta na granicach jest następnie łączona z hybrydowym algorytmem nawigacji w jeden system. Rysunek 5 przedstawia przegląd algorytmu zintegrowanego.



Robot najpierw buduje mapę lokalną (szczegóły dotyczące tworzenia mapy znajdują się w Części II tego artykułu) swojego otoczenia. Następnie decyduje, czy cel jest osiągalny na podstawie pozyskanej mapy lokalnej. Cel jest osiągalny, jeśli znajduje się w wolnej przestrzeni, i nieosiągalny, jeśli znajduje się w nieznanej przestrzeni. Należy pamiętać, że nieznany region to część mapy, która nie została zbadana podczas procesu tworzenia mapy. Robot będzie podążał w kierunku celu, korzystając z hybrydowego algorytmu nawigacji, jeśli cel jest osiągalny, lub będzie podążał w kierunku podcelu i zbuduje kolejną mapę lokalną w podcelu, jeśli cel jest nieosiągalny. Mapa ta zostanie dodana do poprzednich map lokalnych, tworząc większą mapę otoczenia. Proces trwa, aż robot znajdzie cel w wolnej przestrzeni. Podcel jest obliczany w trzech krokach. Najpierw obliczana jest ścieżka łącząca bieżącą pozycję robota z celem, za pomocą funkcji nawigacji. Nieznane komórki są traktowane jako wolna przestrzeń w obliczeniach funkcji nawigacji. Następnie obliczane są wszystkie granice na mapie. Granica wolnej przestrzeni i nieznanego obszaru jest znana jako granica. Granica składa się z grupy sąsiadujących komórek granicznych. Komórka graniczna jest definiowana jako dowolna komórka gC_free na mapie z co najmniej dwiema nieznanymi komórkami gC_unknown jako jej bezpośrednim sąsiadem. Całkowita liczba komórek granicznych tworzących granicę musi być większa niż rozmiar robota, aby granica ta była ważna. Po trzecie, granica przecinająca ścieżkę funkcji nawigacyjnej zostanie wybrana, a jej centroid zostanie wybrany jako podcel.

Zalety i wady

Hybrydowy algorytm nawigacji ma tę zaletę, że eliminuje lokalne minima błędów i jednocześnie umożliwia unikanie kolizji z dynamicznymi przeszkodami. Wymaga on jednak pełnej znajomości środowiska, aby możliwe było znalezienie ścieżki funkcji nawigacyjnej do celu. Algorytm zawiedzie w całkowicie nieznanym środowisku. Nie posiada on również możliwości ponownego zaplanowania ścieżki funkcji nawigacyjnej podczas operacji. Dlatego wszelkie istotne zmiany w środowisku mogą spowodować awarię algorytmu. Zintegrowany algorytm ma zalety planowania lokalnych minimów swobodnych ścieżek i unikania kolizji z dynamicznymi przeszkodami w całkowicie nieznanym otoczeniu. Ponadto algorytm zapewnia robotowi mobilnemu wyższy poziom autonomii, ponieważ nie musi on polegać na ludziach w zakresie tworzenia mapy otoczenia. Jednak zalety te wiążą się z kompromisem w postaci żmudnych implementacji. Wynika to z faktu, że zintegrowany algorytm wymaga jednoczesnej implementacji zarówno hybrydowego algorytmu nawigacyjnego, jak i dobrego algorytmu mapowania.

TRENDY NA PRZYSZŁOŚĆ

Badacze zajmujący się nawigacją robotów mobilnych zazwyczaj zakładają, że czujniki pokładowe mają doskonałą zdolność wykrywania. W rzeczywistości czujniki te są zakłócone szumem, co zazwyczaj negatywnie wpływa na wydajnośćalgorytmów nawigacyjnych. Największym wyzwaniem dla solidnej implementacji algorytmów nawigacyjnych jest zatem zminimalizowanie negatywnych skutków spowodowanych niepewnością czujników.

WNIOSKI

Nawigacja robota mobilnego to coś więcej niż tylko planowanie trasy od punktu początkowego do określonego celu. Robot mobilny musi być w stanie dokładnie podążać zaplanowaną trasą i unikać wszelkich dynamicznych lub nieprzewidzianych przeszkód podczas podróży do celu. W tym artykule omówiono niektóre z kluczowych algorytmów, które umożliwiają robotowi mobilnemu nawigację. Algorytmy te obejmują funkcję nawigacji, mapy drogowe, sztuczne pole potencjału, histogram pola wektorowego, nawigację hybrydową i algorytm zintegrowany.

WSTĘP

Wykorzystanie mowy w interakcji człowiek-maszyna rośnie wraz ze wzrostem złożoności interfejsów komputerowych, ale także ich użyteczności. Interfejsy te wykorzystują informacje uzyskane od użytkownika poprzez analizę różnych modalności i wyświetlają konkretne odpowiedzi za pomocą różnych mediów. Początków systemów multimodalnych należy doszukiwać się w ich prekursorze, systemie "Put-That-There" , aplikacji opartej na rozpoznawaniu mowy i gestów. Wykorzystanie mowy jako jednej z tych modalności do otrzymywania poleceń od użytkowników i przekazywania informacji ustnych sprawia, że komunikacja człowiek-maszyna staje się bardziej naturalna. Coraz więcej aplikacji wykorzystuje konwersję mowy na tekst oraz animowane postacie z syntezą mowy. Jednym ze sposobów na zwiększenie naturalności tych interfejsów jest włączenie rozpoznawania stanów emocjonalnych użytkownika . Wymaga to zazwyczaj tworzenia baz danych mowy, prezentujących autentyczną treść emocjonalną, umożliwiającą solidną analizę. Cowie, Douglas-Cowie i Cox (2005) przedstawiają kilka baz danych pokazujących wzrost multimodalnych baz danych, a Ververidis i Kotropoulos (2006) opisują 64 bazy danych i ich zastosowanie. Podczas tworzenia tego rodzaju baz danych głównym problemem pojawiającym się jest naturalność wypowiedzi, która bezpośrednio zależy od metody użytej w nagraniach, zakładając, że muszą być one kontrolowane bez zakłócania autentyczności wypowiedzi. Campbell (2000) i Schröder (2004) proponują cztery różne źródła pozyskiwania mowy emocjonalnej, uporządkowane od mniejszej kontroli, ale większej autentyczności do większej kontroli, ale mniejszej autentyczności: i) naturalne zdarzenia, ii) wywoływanie autentycznych emocji w warunkach laboratoryjnych, iii) stymulowane emocje za pomocą przygotowanych tekstów oraz iv) mowa aktorska czytająca te same teksty z różnymi stanami emocjonalnymi, zwykle wykonywana przez aktorów. Z jednej strony korpusy zaprojektowane do syntezy mowy emocjonalnej opierają się na badaniach skoncentrowanych na słuchaczu, zgodnie z rozróżnieniem Schrödera (2004), ponieważ modelują parametry mowy w celu przekazania określonej emocji. Z drugiej strony, rozpoznawanie emocji implikuje badania skoncentrowane na mówcy, ponieważ są one powiązane ze stanem emocjonalnym mówcy i parametrami mowy. Walidacja korpusu użytego do syntezy obejmuje oba rodzaje badań: pierwsze, ponieważ będzie on wykorzystany do syntezy, i drugie, ponieważ rozpoznanie jest potrzebne do oceny jego treści. Najlepszym systemem walidacji jest selekcja prawidłowych wypowiedzi z korpusu przez słuchaczy. Jednak duży rozmiar korpusu sprawia, że proces ten jest nieopłacalny.

TŁO

Rozpoznawanie emocji od dawna stanowi interesujący obszar badań w zakresie interakcji człowiek-maszyna, co można zaobserwować w pracy Cowie . Przeprowadzono pewne badania mające na celu obserwację wpływu emocji na sygnały mowy, takie jak praca przedstawiona przez Rodrigueza i innych (1999). Jednak ostatnio, ze względu na rosnącą moc obliczeniową nowoczesnych komputerów, która umożliwia analizę ogromnych ilości danych w stosunkowo krótkich odstępach czasu, techniki uczenia maszynowego zostały wykorzystane do automatycznego rozpoznawania emocji za pomocą oznaczonych korpusów mowy ekspresywnej. Większość tych badań koncentrowała się na kilku algorytmach i niewielkich zestawach parametrów. Jednak w ostatnich pracach przeprowadzono bardziej wyczerpujące eksperymenty testujące różne techniki uczenia maszynowego i zestawy danych, jak opisano przez Oudeyera (2003). Wszystkie tego typu badania miały na celu osiągnięcie jak najwyższego wskaźnika rozpoznawalności, uzyskując w wielu przypadkach lepsze wyniki niż te uzyskane w testach subiektywnych , Planet, Morán i Formiga, 2006, Iriondo, Planet, Socoró i Alias, 2007). Niemniej jednak, analizując wyniki uzyskane z klasyfikacji obiektywnych i subiektywnych, można dostrzec wiele różnic i, o ile nam wiadomo, nie istnieją badania mające na celu naśladowanie tych subiektywnych kryteriów przed badaniami przeprowadzonymi przez Iriondo, Planet, Alias, Socoró i Martíneza (2007).

WALIDACJA KORPUSU MOWY EKSPRESYWNEJ POPRZEZ MAPOWANIE KRYTERIÓW SUBIEKTYWNYCH

Stworzenie korpusu mowy o autentycznej treści emocjonalnej jest jednym z najważniejszych wyzwań w badaniach nad mową ekspresywną. Po nagraniu korpusu wymagany jest proces walidacji, aby usunąć wypowiedzi, które wykazują wyraźne emocje.

Produkcja korpusu

Nagranie korpusu zostało przeprowadzone przez profesjonalną mówczynię. W środowisku naukowym panuje powszechna zgoda co do uzyskiwania mowy emocjonalnej za pomocą tej strategii w celach syntezy, choć inni autorzy opowiadają się za konstruowaniem ogromnych korpusów zebranych z nagrań z życia codziennego . Do projektowania tekstów semantycznie powiązanych z różnymi stylami ekspresji wykorzystaliśmy istniejącą bazę danych tekstowych reklam wyodrębnionych z gazet i czasopism. Na podstawie badania głosu w reklamie audiowizualnej wybrano pięć kategorii korpusu tekstowego i przypisano im najbardziej odpowiednie emocje/styl: Nowe technologie (neutralny-dojrzały), edukacja (radość-uniesienie), kosmetyka (styl zmysłowy-słodki), samochody (agresywny-twardy) i podróże (smutny-melancholijny). Zarejestrowana baza danych zawiera 4638 zdań i trwa 5 godzin i 12 minut. Z tych kategorii wybrano zbiór zdań za pomocą algorytmu zachłannego (François i Boëffard, 2002), który pozwolił nam na wyselekcjonowanie zdań zrównoważonych fonetycznie. Oprócz poszukiwania równowagi fonetycznej, odrzucono frazy zawierające słowa obce i skróty, ponieważ utrudniają one automatyczny proces transkrypcji i etykietowania fonetycznego. Korpus został podzielony na frazy, a następnie na fonemy, za pomocą procesu półautomatycznego opartego na wymuszonym dopasowaniu z ukrytymi modelami Markowa.

Analiza akustyczna

Cowie i inni (2001) pokazują, jak prozodyczne cechy mowy (częstotliwość podstawowa (F0), energia, czas trwania głosek i częstotliwość pauz) są powiązane z wokalną ekspresją emocji. Analiza F0 przeprowadzona w niniejszej pracy opiera się na wynikach algorytmu pitch marks opisanego przez Aliasa, Monzo i Socoró (2006). System ten może przypisywać znaczniki całemu sygnałowi, interpolując wartości z sąsiednich fonemów w segmentach bezdźwięcznych i pauzach. Energia jest mierzona w prostokątnych oknach o długości 20 ms i 50% nakładania, obliczając średnią energię w decybelach (dB) co 10 ms. Ponadto, parametry rytmu zostały uwzględnione za pomocą z-score jako sposobu analizy struktury czasowej mowy . Ponadto, dla każdej wypowiedzi brane są pod uwagę dwa parametry dotyczące liczby pauz w jednostce czasu i odsetka ciszy w odniesieniu do całkowitego czasu.

Test subiektywny

Test subiektywny pozwala na walidację ekspresywności korpusu mowy aktorskiej z punktu widzenia użytkownika. Niemniej jednak, dogłębna ocena całego korpusu byłaby bardzo żmudna ze względu na dużą liczbę elementów. Z tego powodu do tego testu wybrano tylko 10% wypowiedzi z korpusu. Test z wymuszoną odpowiedzią został zaprojektowany z wykorzystaniem platformy TRUE z pytaniem: Jaki stan emocjonalny rozpoznajesz w głosie mówcy w tym zdaniu? Możliwymi odpowiedziami są 5 stylów emocjonalnych korpusu oraz jedna dodatkowa opcja: Nie wiem/Inny (Nie wiem/Odpowiedź), aby zminimalizować stronniczość wyników spowodowaną mylącymi przypadkami. Dodanie tej opcji niesie ze sobą ryzyko, że niektórzy użytkownicy będą nadmiernie używać tej odpowiedzi, aby przyspieszyć zakończenie testu. Jednak w tym eksperymencie nie zaobserwowano takiego efektu. Oceniającymi było 30 ochotników o dość heterogenicznym profilu. Osiągnięta średnia dokładność klasyfikacji w teście subiektywnym wynosi 87%. Test ujawnia również, że styl smutny (SAD) jest najlepiej oceniany (średnio 98,5%). Drugim i trzecim najlepiej ocenianym stylem są styl zmysłowy (SEN) (87,2%) i styl neutralny (NEU) (86,1%), a następnie styl szczęśliwy (HAP) (81,9%) i styl agresywny (AGR) (81,6%). Style agresywny i styl szczęśliwy są często mylone. Co więcej, styl zmysłowy jest nieznacznie błędnie klasyfikowany jako smutny lub neutralny. Opcja Dk/A jest rzadko stosowana, chociaż jest bardziej obecna w stylach neutralnym i zmysłowym niż w pozostałych stylach. Aby stwierdzić, czy wypowiedzi nie są optymalnie wykonywane przez mówcę, na podstawie wyników testu subiektywnego opracowano dwie proste reguły poprzez empiryczne dostosowanie dwóch progów. Reguły te eliminują wypowiedzi, których odsetek identyfikacji jest niższy niż 50% lub których odsetek Dk/A jest większy niż 12%. Spośród 480 wypowiedzi testu subiektywnego 33 spełniają co najmniej jedną regułę. Analiza statystyczna, zbiory danych i klasyfikacja nadzorowana Iriondo, Planet, Socoró i Alías (2007) przedstawiają eksperyment rozpoznawania emocji, obejmujący różne zbiory danych i algorytmy. Eksperyment przeprowadzono na tym samym korpusie, który jest omawiany w niniejszym artykule. Każda wypowiedź jest definiowana przez 464 atrybuty reprezentujące charakterystykę sygnału mowy, ale ten pierwszy zbiór danych jest dzielony na różne podzbiory w celu zmniejszenia jego wymiarowości. Eksperymenty pokazują niemal takie same wyniki w pełnym zbiorze danych, jak i w zbiorze danych zredukowanym do 68 parametrów, dlatego w niniejszej pracy wykorzystano zredukowany zbiór danych. W tym zbiorze danych prozodia wypowiedzi jest reprezentowana przez wektory logarytmicznej wartości F0, energii w dB i znormalizowanych czasów trwania. Dla każdej sekwencji obliczana jest również pierwsza pochodna. Niektóre statystyki są uzyskiwane z tych sekwencji: średnia, wariancja, maksimum, minimum, rozstęp, skośność, kurtoza, kwartyle i rozstęp międzykwartylowy. W ten sposób oblicza się 68 parametrów dla wypowiedzi, biorąc pod uwagę oba parametry związane z pauzowaniem opisane wcześniej. W cytowanej pracy przetestowano dwanaście algorytmów uczenia maszynowego, biorąc pod uwagę różne zestawy danych. Wszystkie eksperymenty przeprowadzono z użyciem oprogramowania Weka za pomocą dziesięciokrotnej walidacji krzyżowej. Bardzo wysokie wskaźniki rozpoznawania uzyskano również w innych cytowanych wcześniej pracach: SMO (SVM firmy Weka) uzyskał najlepsze wyniki (~97%), następnie Naïve-Bayes (NB) z wynikiem 94,6% i J48 (Weka Decision Tree oparte na C4.5) z wynikiem 93,5%, biorąc pod uwagę średnią wszystkich wyników. Wniosek jest taki, że ogólnie rzecz biorąc, style opracowanego korpusu mowy można wyraźnie odróżnić. Co więcej, wyniki testu subiektywnego wykazały dobrą autentyczność treści mowy ekspresywnej. Jednakże, pójście o krok dalej i opracowanie metody walidacji każdej wypowiedzi korpusu według kryteriów subiektywnych, a nie tylko automatycznej klasyfikacji z przestrzeni atrybutów, jest uważane za konieczne.

Selekcja atrybutów oparta na subiektywizmie

Proponowane podejście do znalezienia optymalnego schematu klasyfikatora, który spełnia kryteria subiektywne, polega na opracowaniu metody selekcji atrybutów, kierując się wynikami uzyskanymi w teście subiektywnym. Po znalezieniu najlepszego schematu zostanie on zastosowany do całego korpusu w celu wygenerowania listy wypowiedzi kandydackich do usunięcia. Opracowano dwie metody selekcji atrybutów w celu określenia podzbioru atrybutów, który umożliwia lepsze odwzorowanie wyników testu subiektywnego. Jak wspomniano wcześniej, oryginalny zbiór zawiera 68 atrybutów na wypowiedź, więc wyczerpująca eksploracja podzbiorów nie jest możliwa i zostaną zastosowane zachłanne procedury wyszukiwania. Z jednej strony wybierany jest proces selekcji w przód (FW), który rozpoczyna się bez żadnego atrybutu i dodaje po jednym atrybucie na raz, a z drugiej strony rozważana jest technika eliminacji wstecznej (BW), która rozpoczyna się od pełnego zbioru i usuwa po jednym atrybucie na raz. Na każdym etapie klasyfikator jest testowany za pomocą 480 wypowiedzi branych pod uwagę w teście subiektywnym, uprzednio trenując go za pomocą pozostałych 4158 wypowiedzi. Błędnie sklasyfikowane przypadki biorą udział w procesie oceny danego podzbioru atrybutów. Nowością w tym procesie jest zastosowanie miary opartej na subiektywizmie do oceny oczekiwanej wydajności podzbioru w każdej iteracji. Miarą tą jest wynik F1 obliczony na podstawie precyzji i odtworzenia błędnie sklasyfikowanych wypowiedzi w porównaniu z 33 wypowiedziami odrzuconymi w teście subiektywnym.

Wyniki

Proces składa się z sześciu iteracji: po jednej na algorytm (SMO, NB i J48) i technikę selekcji atrybutów (FW i BW). Algorytm SMO uzyskuje praktycznie taki sam wynik F1 (∿ 0,50) zarówno w technice selekcji atrybutów FW, jak i BW. Wyniki dla obu NB są również podobne (F1 ≈ 0,43). Główną różnicą jest to, że J48 uzyskuje lepszy wynik F1 z procesem FW (0,45) niż z procesem BW (0,37). Co więcej, SMO-FW wydaje się być najbardziej stabilną konfiguracją, ponieważ osiąga prawie taki sam wynik (F1 = 0,49) z szerokim zakresem podzbiorów atrybutów (wyniki są bardzo podobne dla zakresu atrybutów od 18 do 35). Wyniki pokazują, że J48-FW ma najlepsze przywołanie (18/33), co implikuje największą liczbę zbieżności; jednak miara precyzji jest dość niska (18/51), co wskazuje na nadmierną liczbę ogólnych błędnych klasyfikacji.

PRZYSZŁE TRENDY

Przyszłe prace będą polegać na zastosowaniu tego automatycznego procesu w całym korpusie. Na przykład, dziesięciokrotna walidacja krzyżowa byłaby dobrą techniką obejmującą cały korpus. Błędnie sklasyfikowane wypowiedzi mogłyby zostać poddane selekcji. Pierwsze podejście polegałoby na uruchomieniu różnych klasyfikatorów i wybraniu ostatecznych kandydatów za pomocą techniki kumulacji . Ponadto ocenimy przydatność proponowanej metody, przeprowadzając modelowanie akustyczne wynikowej mowy emocjonalnej po selekcji, w odniesieniu do wyników uzyskanych dla całego korpusu. Niższy błąd estymacji prozodyki mógłby potwierdzić hipotezę, że wskazane jest wcześniejsze wyeliminowanie błędnych wypowiedzi z korpusu.

WNIOSKI

Niniejszy artykuł uwypukla potrzebę automatycznej walidacji korpusu mowy ekspresywnej ze względu na brak możliwości przeprowadzenia testu subiektywnego w dużym korpusie. Przedstawiono również podejście do osiągnięcia tego celu, polegające na przeprowadzeniu testu subiektywnego z udziałem 30 osób i około 10% wypowiedzi. Wynik tego testu wykazał, że niektóre wypowiedzi są postrzegane z odmienną lub ubogą treścią ekspresyjną w odniesieniu do ich etykietowania. Proponowana automatyczna klasyfikacja próbuje wyciągnąć wnioski z wyniku testu subiektywnego, aby uogólnić rozwiązanie na resztę korpusu, za pomocą odpowiedniej selekcji atrybutów przeprowadzonej dwiema różnymi strategiami (selekcja w przód i eliminacja w tył) z wykorzystaniem miary F1 obliczonej z uwzględnieniem błędnych klasyfikacji wynikających z testu subiektywnego jako odniesienia.

WSTĘP

Świat środowisk wirtualnych i technologii immersyjnych rozwija się dość dynamicznie. Wraz ze wzrostem zakresu i złożoności aplikacji rośnie również zapotrzebowanie na inteligentną interakcję. Stosunkowo proste obecnie środowiska projektu OZ zostały zastąpione przez wirtualne teatry , prototypy szkoleniowe Tactical Combat Air oraz symulatory kontroli lotu . Niniejszy artykuł przedstawia krótkie podsumowanie obecnych i przyszłych technologii oraz nowych zastosowań, które wymagają wykorzystania wiedzy specjalistycznej z zakresu sztucznej inteligencji w obszarze technologii immersyjnych i środowisk wirtualnych. Zastosowania te umieszczono w kontekście wcześniejszych projektów badawczych.

TŁO

Wizualizacja jest definiowana jako wykorzystanie komputerowych, interaktywnych, wizualnych reprezentacji danych w celu wzmocnienia procesów poznawczych. Często cytowany proces wizualizacji oparty na procesach, zaproponowany przez Upsona , przedstawiono na rysunku



Upson i jego współpracownicy definiują trzy procesy, obejmujące filtrowanie, mapowanie i renderowanie danych. Przedstawiony obraz pozwala użytkownikowi na wyciągnięcie wniosków i uzyskanie wglądu w dane. Proces filtrowania polega na tym, że interesujące dane są pozyskiwane z surowych danych wejściowych; na przykład interpolacja rozproszonych danych na regularną siatkę. Dane te są następnie mapowane na prymitywy geometryczne, które następnie mogą być renderowane i wyświetlane użytkownikowi jako obraz. Użytkownik może wówczas uzyskać lepsze zrozumienie i głębszy wgląd w oryginalne dane surowe. Rodzaj danych i obszar zastosowania mają duży wpływ na charakter procesu mapowania. Innymi słowy, wybór konkretnej techniki wizualizacji, której będziemy używać. Na przykład, jeśli dane składają się z jednowymiarowych danych skalarnych, do ich reprezentacji można użyć prostego wykresu liniowego. Jeśli przefiltrowane dane składają się z trójwymiarowych danych skalarnych, bardziej odpowiednia byłaby jakaś forma trójwymiarowych izopowierzchni lub technika bezpośredniego renderowania objętości. Poprzez różne specyfikacje i konceptualizacje powyższego potoku filtr-mapa, proponujemy ontologię opisującą relacje między typem danych a procesami mapowania, co ułatwia automatyczny wybór technik wizualizacji na podstawie surowego typu danych. Wraz ze wzrostem zaawansowania aplikacji, proces wizualizacji może wykorzystywać ontologię danych do sterowania postaciami i agentami sterowanymi przez AI, odpowiednimi dla danej aplikacji i danych. Punkt wyjścia do tego można dostrzec w obszarze wiarygodnych agentów , gdzie badania obejmują zagadnienia od animacji po modele emocji i poznania oraz adnotowane środowiska. Innowacyjne środowiska edukacyjne i animowane agenty pedagogiczne zapewniają dalsze obszary rozwoju, podobnie jak zastosowania przemysłowe, na przykład prototyp wirtualnego systemu szkoleniowego do frezowania z wykorzystaniem komputerowego sterowania numerycznego (CNC). Środowiska edukacyjne wykorzystujące wiele jsów w wirtualnej rzeczywistości obejmują Steve′a (Soar Training Expert for Virtual Environments), który wspiera proces uczenia się we współpracy z takimi instytucjami jak Lockheed Martin AI Center. SOAR był również wykorzystywany do symulacji treningowej w walce powietrznej (TacAir-Soar) . Ten autonomiczny system do modelowania taktycznej domeny powietrznej łączy obszary badań nad sztuczną inteligencją, obejmujące architektury poznawcze: reprezentację zachowań ludzkich (HBR) / siły generowane komputerowo (CGF). SOF-Soar: (Modelowanie Sił Operacji Specjalnych) wykorzystuje te same podstawowe ramy i metody generowania zachowań, oparte na modelu ludzkiego poznania Soar. Każda jednostka jest zdolna do autonomicznego, ukierunkowanego na cel podejmowania decyzji, planowania i reaktywnego zachowania w czasie rzeczywistym. Wraz z rozwojem świata mediów cyfrowych, nowe aplikacje będą czerpać ze świata Teatrów Wirtualnych , interaktywnych gier fabularnych i innych form rozrywki , aby wzbogacić wrażenia wizualne, zwłaszcza w przypadku wirtualnych światów z udziałem ludzkich artefaktów oraz dawnych i obecnych cywilizacji.

INTELIGENCJA ROJU DO WIZUALIZACJI

Zrozumienie zachowania czynników biologicznych w ich naturalnym środowisku ma ogromne znaczenie dla etologów i biologów. Miejsca, w których te stworzenia przemieszczają się w dużych ilościach, stanowią wyzwanie dla tradycyjnej wizualizacji. We współpracy z biologami morskimi stworzono trójwymiarowy model dużej liczby rojów kryla .



Model ten rozszerza klasyczne funkcje rojenia, takie jak separacja, wyrównanie i spójność, opisane przez Reynoldsa (1987). Wygenerowany model 3D umożliwia umieszczenie kamer na poszczególnych krylach w celu wygenerowania perspektywy roju. Nowe badania nad krylem antarktycznym ujawniają, że pochłaniają one i przenoszą więcej węgla z powierzchni Ziemi, niż wcześniej sądzono. Naukowcy z British Antarctic Survey (BAS) i Scarborough Centre of Coastal Studies na Uniwersytecie w Hull odkryli, że kryl antarktyczny zamiast robić to raz na 24 godziny, wykonuje "spadochron" z powierzchni oceanu do głębszych warstw kilka razy w ciągu nocy. W ten sposób, wydalając swoje odpady, wprowadza do głębin więcej węgla, niż wcześniej sądzono. Naszym celem było dostarczenie biologom morskim narzędzia wizualizacyjnego i statystycznego, które pozwoli im zmieniać szereg parametrów w środowisku morskim kryla i badać skutki tych zmian w czasie. Oprogramowanie może być również wykorzystywane jako narzędzie dydaktyczne na różnych poziomach nauczania. Biolog morski może modyfikować parametry dotyczące pola widzenia pojedynczego kryla, szybkości żerowania, unikania kolizji, szybkości wyczerpania, pragnienia pożywienia itp. Badacz może również modyfikować bardziej globalne parametry dotyczące prądów morskich, temperatury oraz ilości i gęstości glonów (pożywienia) itp. Po wykonaniu, biolog może wchodzić w interakcję z modelem, zmieniając trójwymiarowy punkt widzenia i modyfikując krok czasowy, który kontroluje prędkość działania modelu. Stany kryla są reprezentowane za pomocą różnych kolorów. Na przykład, czerwony kryl reprezentuje wygłodzonego, chorego kryla, zielony oznacza aktywnego i zdrowego, a niebieski reprezentuje okres trawienia, w którym aktywność kryla jest minimalna. Ostatnie postępy w technologii procesorów i grafiki oznaczają, że tego rodzaju symulacje są możliwe przy użyciu komputerów stacjonarnych o wysokiej wydajności. Biolodzy morscy są bardzo zainteresowani tym, jak drobne zmiany niektórych zmiennych, takich jak pole widzenia kryla, mogą mieć istotny wpływ na zachowanie stadne całego roju w czasie.

SYMULATOR PARALOTNIARSTWA

Wydział Informatyki Uniwersytetu w Hull opracował niedawno pierwszy na świecie symulator paralotniarstwa (SimVis, 2007). System zapewnia pilotowi paralotniarstwa immersyjne wrażenia z lotu w wirtualnej rzeczywistości



Z punktu widzenia użytkownika lata on prawdziwą paralotnią. Siedzi w prawdziwej uprzęży, a wszystkie fizyczne dane wejściowe użytkownika są takie same jak w rzeczywistości. Wizualizacja jest sterowana przez komputer i wyświetlana użytkownikowi za pomocą monitora zamontowanego na hełmie, śledzącego ruch głowy. Symulator dokładnie modeluje wiatry (w tym prądy termiczne i wstępujące), fotorealistyczny teren i inne elementy sterowane komputerowo przez pilotów AI. Rysunek przedstawia typowy widok z symulatora paralotniarstwa.



Po prawej stronie obrazu użytkownik widzi czterech pilotów paralotniarstwa krążących wokół komina termicznego. W interesie użytkownika leży lot w ten rejon, aby dzielić się wznoszeniem, nabieraniem wysokości, a tym samym czasem lotu. Ten prototyp jest rozwijany na wzór SOF-Soar: (Modelowanie Sił Operacji Specjalnych) . Wymaga on eksperckiego systemu nauczania obejmującego wiedzę doświadczonych pilotów. Podobnie jak niektóre wirtualne środowiska edukacyjne, musi on zbudować profil stażysty na podstawie domyślnego i dostosować się do potrzeb początkującego lotnika. Na przykład system może stworzyć pilota AI lecącego bezpośrednio nad użytkownikiem, zmuszając go do ćwiczenia zasad unikania kolizji. Jeśli piloci zderzą się w symulatorze, obaj piloci zostaną owinięci w osłony swojego samolotu i spadną na ziemię, gdzie zginą. W miarę jak wirtualny czas lotu się kumuluje, system musi dostosowywać się do zmieniającego się profilu użytkownika. System ekspercki może być użyty do zmuszenia użytkownika do wykonania pewnych manewrów lotniczych, które sprawdzą jego wiedzę na temat przepisów lotniczych CAA. Na przykład, system sztucznej inteligencji może uznać użytkownika za zaawansowanego pilota ze względu na jego doskonałe wykorzystanie prądów wstępujących termicznych itp. System opracowuje zatem sposób na postawienie naszego pilota w sytuacji, która wystawi na próbę jego umiejętności i zdolności, na przykład na wytyczenie kursu kolizyjnego z naszym pilotem, gdy ten leci wzdłuż krawędzi klifu. Jeśli nasz pilot jest nowicjuszem, system przedstawi prostsze wyzwania, takie jak podstawowe unikanie kolizji. Jest to zaawansowany projekt inżynierii wiedzy, który łączy tradycyjne obszary sztucznej inteligencji, takie jak inżynieria wiedzy, z nowszymi dziedzinami, takimi jak oparte na agentach architektury reaktywne i kognitywne oraz najnowocześniejsze technologie wizualizacji i immersji.

WNIOSKI

Niniejszy artykuł sugeruje, że kognitywistyka i sztuczna inteligencja odgrywają istotną rolę w nowych urządzeniach interfejsowych, które wymagają wiarygodnych agentów. W miarę jak środowiska wirtualne i technologie immersyjne stają się coraz bardziej zaawansowane, możliwości interaktywnych komponentów będą musiały stać się inteligentniejsze, wykorzystując sztuczne życie, sztuczną inteligencję i kognitywistykę. Będzie to obejmować symulację zachowań człowieka w interaktywnych światach, zarówno w modelowaniu sposobu manipulowania danymi i informacjami, jak i w wykorzystaniu urządzeń sprzętowych (takich jak paralotnia) w środowisku wirtualnym.

WSTĘP

Zarządzanie wiedzą (KM) to nowa dyscyplina, która zrodziła się z idei jawnego zarządzania całą istniejącą wiedzą danej organizacji (Wiig, 1995) (Wiig i in., 1997). Mówiąc dokładniej, KM polega na dostarczaniu zainteresowanym osobom właściwych informacji i wiedzy na najbardziej odpowiednim dla nich poziomie, w czasie i w sposób dla nich najbardziej odpowiedni; w ten sposób osoby te będą dysponować wszystkimi niezbędnymi elementami do wyboru najlepszej opcji w obliczu konkretnego problemu. Ponieważ wiedza, wraz z umiejętnością jej najlepszego zarządzania, stała się kluczowym czynnikiem wyróżniającym organizacje, pożądane jest określenie i opracowanie instrumentów wsparcia dla generowania takiej wartości w organizacjach. Sytuacja ta została powszechnie zaakceptowana przez wielu autorów. Powinny być dostępne narzędzia technologiczne, które zmniejszą dystans komunikacyjny i zapewnią wspólne środowisko, w którym wiedza będzie dostępna do przechowywania lub udostępniania. Ponieważ zarządzanie wiedzą (KM) jest bardzo młodą dyscypliną, istnieje niewiele komercyjnych narzędzi programowych, które zajmują się aspektami niezbędnymi dla tego podejścia. Większość narzędzi klasyfikowanych jako związane z zarządzaniem wiedzą to jedynie narzędzia do zarządzania dokumentami, co nie nadaje się do prawidłowego zarządzania wiedzą organizacji. Mając na uwadze ten problem, niniejsza praca podejmuje temat stworzenia narzędzia programowego wspomagającego zarządzanie wiedzą (KM) w oparciu o własną definicję zarządzania wiedzą (KM) oraz istniejące narzędzia. Aby to osiągnąć, w rozdziale 2 przedstawiono analizę rynku, którą przeprowadzono w celu zbadania istniejących narzędzi zarządzania wiedzą (KM), analizując nie tylko ich cechy, ale także przyszłe potrzeby pracowników wiedzy. W wyniku tego badania zidentyfikowano funkcjonalność, jaką powinno posiadać narzędzie wspomagające zarządzanie wiedzą (KM), oraz zaproponowano najlepsze podejście do tej funkcjonalności.

WSTĘP

Pierwszym krokiem w opracowaniu kompletnego narzędzia wspomagającego zarządzanie wiedzą (KM), zgodnego z obecnymi i przyszłymi potrzebami branży, jest przeprowadzenie badania istniejącego rynku. Po wstępnej identyfikacji cech, jakie powinno posiadać narzędzie wspomagające zarządzanie wiedzą (KM), analiza a posteriori ujawni, w jaki sposób badane narzędzia wspierają każdą z wcześniej zidentyfikowanych cech. Na koniec przeprowadzona zostanie ocena uzyskanych wyników.

Cechy, które należy uwzględnić

Wspomniana wcześniej definicja zarządzania wiedzą (KM) stanowiła podstawę do identyfikacji cech, które należy uwzględnić, biorąc pod uwagę różne aspekty, które narzędzie powinno wspierać. Narzędzie KM powinno wspierać następujące aspekty):

o Pamięć korporacyjna
o Żółte Strony
o Mechanizmy współpracy i komunikacji

1. Pamięć korporacyjna

Pamięć korporacyjna gromadzi wiedzę istniejącą w organizacji do dyspozycji jej pracowników (Stein, 1995) . Z tego powodu gromadzenie i upublicznianie odpowiedniej wiedzy jest równie ważne, jak zapewnienie odpowiednich mechanizmów umożliwiających jej prawidłową i łatwą lokalizację oraz odzyskiwanie.

2. Żółte Strony

Program zarządzania wiedzą (KM) nie powinien popełniać błędu polegającego na próbie uchwycenia i przedstawienia całej istniejącej wiedzy organizacji, ponieważ byłoby to niewykonalne; w tym sensie wiedza istotna dla funkcjonowania organizacji powinna być uwzględniona. Jednak brak upublicznienia całej wiedzy nie oznacza,że musi ona zostać wyeliminowana; z tego powodu ważne jest, aby określić, jaką wiedzę posiada każda osoba w organizacji, poprzez opracowanie Żółtych Stron. Te identyfikują i publikują dodatkowe źródła wiedzy, ludzkie i pozaludzkie, którymi dysponuje organizacja (Davenport i Prusak,2000).

3. Mechanizmy współpracy i komunikacji

W organizacjach wiedza jest współdzielona i dystrybuowana, niezależnie od automatyzacji procesu. Transfer wiedzy ma miejsce za każdym razem, gdy pracownik pyta współpracownika z sąsiedniego biura, jak wykonać dane zadanie. Te codzienne transfery wiedzy stanowią codzienną rutynę organizacji, ale ze względu na ich lokalny i fragmentaryczny charakter, należy ustanowić pewne systemy współpracy i komunikacji użytkowników. Odpowiednie narzędzie wspomagające zarządzanie wiedzą (KM) powinno zawierać mechanizmy gwarantujące efektywność współpracy i komunikacji, niezależnie od fizycznej lub czasowej lokalizacji rozmówców.

Przeanalizowane narzędzia

Po zidentyfikowaniu aspektów, które powinno uwzględniać narzędzie wspomagające zarządzanie wiedzą (KM), kolejnym krokiem jest analiza sposobu, w jaki uwzględniają je obecne narzędzia. W tym celu przeanalizowano główne, tzw. narzędzia wspomagające zarządzanie wiedzą (KM), które obecnie istnieją, odrzucając niektóre narzędzia, takie jak wyszukiwarki informacji czy proste aplikacje do zarządzania dokumentami, ponieważ oferują one jedynie częściowe rozwiązania.Analiza objęła trzynaście narzędzi (Tabela 1), z których każde spełniało co najmniej dwa z wcześniej wymienionych aspektów. Należy podkreślić, że wszystkie narzędzia implementują Pamięć Korporacyjną (Corporate Memory) jako magazyn dokumentów, a Żółte Strony (Yellow Pages) funkcjonują jako książka telefoniczna.

Ocena wyników

Po przeanalizowaniu narzędzi zauważono, że dla każdego rozpatrywanego aspektu istnieją pewne wspólne elementy. Mając na uwadze te elementy i aktualne potrzeby, tabela 2 przedstawia pożądane cechy, jakie powinno posiadać narzędzie wspomagające zarządzanie wiedzą (KM). Poniżej przedstawiono wnioski wyciągnięte po głębszym badaniu sposobu, w jaki analizowane narzędzia podchodzą do pożądanych cech. Po pierwsze, zauważono, że żadne z narzędzi sklasyfikowanych jako narzędzia KM nie posiada struktury niezbędnej do optymalnej identyfikacji, formalizacji i udostępniania odpowiedniej wiedzy, ponieważ realizują one wyłącznie zarządzanie dokumentacją, uzupełnione, w najlepszym przypadku, polami opisowymi, powiązaniem z drzewem treści lub linkami do innych powiązanych dokumentów. Fakt ten stwarza wiele problemów, zwłaszcza ze względu na dużą ilość danych, a także trudności w wyborze odpowiedniej wiedzy, której użytkownik może potrzebować w danym momencie. W związku z tym, jak już wcześniej wskazano, dla optymalnego wykorzystania wiedzy, powinna ona być w jakiś sposób ustrukturyzowana. Wsparcie komunikacji jest również bardzo ważne. Należy wówczas zdefiniować cechy narzędzia wspomagającego zarządzanie wiedzą (KM), a także opracować wytyczne dotyczące jego stosowania.

ZALECANE FUNKCJE

Podejście do każdej z wykrytych cech powinno zostać zainicjowane natychmiast po ustaleniu funkcjonalności narzędzia wspomagającego jawne zarządzanie wiedzą korporacyjną.

1. Pamięć korporacyjna: wiedza organizacji musi być w jakiś sposób fizycznie przechowywana za pośrednictwem Pamięci Korporacyjnej, aby mogła być odpowiednio udostępniana. Pamięć Korporacyjna to jawna, niezależna i trwała reprezentacja wiedzy , którą można uznać za repozytorium wiedzy osób pracujących w danej organizacji. Pamięć Korporacyjna powinna obejmować następujące aspekty:

1.1. Formalizacja wiedzy. Zanim wiedza zostanie włączona do Pamięci Korporacyjnej, musi zostać sformalizowana poprzez określenie nie tylko wiedzy istotnej, ale także atrybutów, które ją opisują. Dokonując tej formalizacji, należy pamiętać, że istnieją dwa rodzaje wiedzy: z jednej strony Pamięć Korporacyjna musi obejmować wiedzę potrzebną do opisu operacji związanych z realizacją zadania organizacyjnego. Z drugiej strony, konieczne jest uchwycenie wiedzy zdobytej przez jednostki w toku ich doświadczeń i życia. Ta wyraźnie heurystyczna wiedza jest znana jako Wyciągnięte Lekcje: zarówno pozytywne, jak i negatywne doświadczenia, które można wykorzystać do poprawy przyszłych wyników organizacji (Van Heijst, 1997), a tym samym dopracowania jej obecnej wiedzy.

a. Wiedza organizacyjna (Andrade i in., 2003b). System zarządzania wiedzą (KM) powinien uwzględniać różne rodzaje wiedzy podczas strukturyzacji wiedzy związanej z operacjami istniejącymi w organizacji:

o Wiedza strategiczna lub kontrolna: wskazuje nie tylko, co robić,ale także dlaczego, gdzie i kiedy. Z tego powodu należy zidentyfikować elementy funkcjonalnej dezintegracji każdej operacji.
o Wiedza taktyczna: określa, jak i w jakich okolicznościach zadania są wykonywane. Ten rodzaj wiedzy jest związany z procesem realizacji każdego ostatniego kroku strategicznego.

b. Wyciągnięte wnioski. Jest on związany z doświadczeniem i wiedzą, jaką posiadają jednostki w odniesieniu do swojego zadania. Daje osobie, która go posiada, możliwość udoskonalania zarówno procesów zachodzących w pracy, jak i już istniejącej wiedzy, aby zwiększyć wydajność. Natomiast w celu zachowania tego rodzaju wiedzy właściwe jest tworzenie systemów wyciągniętych wniosków.

1.2. Mechanizmy włączania. Wiedza może być włączana w sposób aktywny lub pasywny (Andrade i in., 2003c). Aktywne włączanie opiera się na istnieniu grupy KM odpowiedzialnej za dbanie o jakość wiedzy, która ma zostać włączona. Gwarantuje to jakość wiedzy włączonej do Pamięci Korporacyjnej, ale jednocześnie angażuje zasoby ludzkie. W przeciwieństwie do poprzedniego sposobu, w pasywnym włączaniu nie istnieje żadna grupa ds. oceny jakości, ponieważ to jednostka gotowa dzielić się wiedzą i doświadczeniem będzie odpowiedzialna za ocenę, czy propozycja spełnia minimalne wymagania jakości i trafności. Główną zaletą drugiego rozwiązania jest to, że nie angażuje ono dodatkowych zasobów. Mając na uwadze poprzednie rozważania, aktywne włączanie wiedzy jest preferowane, gdy tylko jest to możliwe, ponieważ w ten sposób gwarantowana jest jakość i trafność wiedzy.

1.3. Mechanizmy powiadamiania. Wszyscy członkowie organizacji powinni zostać poinformowani o wprowadzeniu nowej wiedzy, ponieważ umożliwia to udoskonalenie ich wiedzy. Krokiem poprzedzającym powiadomienie jest zdefiniowanie grupy osób, które zostaną poinformowane o pojawieniu się nowego elementu wiedzy. Istnieją dwie alternatywy (García i in., 2003): subskrypcja, w której każda osoba w organizacji może wykupić subskrypcję na określone, preferowane tematy, oraz rozpowszechnianie, w którym powiadomienia docierają do pracowników bez wcześniejszego zgłoszenia. W rozpowszechnianiu, wiadomości mogą być wysyłane do wszystkich członków organizacji, ale nie jest to zalecane, ponieważ odbiorca nie byłby w stanie rozpoznać, które z ogromnej liczby otrzymanych wiadomości mogą być dla niego interesujące. Inna możliwość rozpowszechniania polegałaby na tym, żejedna osoba lub grupa byłaby odpowiedzialna za określenie adresatów każdej wiadomości; ta ostatnia opcja jest dość wygodna dla członków organizacji, ale pochłania ogromne zasoby, które muszą zawierać wiele informacji dotyczących zainteresowań każdego z członków.

1.4. Mechanizmy lokalizacji. Narzędzie powinno być wyposażone w mechanizm wyszukiwania, aby osiągnąć maksymalny możliwy zysk z pozyskanej i włączonej wiedzy (Tiwana, 2000). Konieczne jest osiągnięcie równowagi między wydajnością a funkcjonalnością, ponieważ wystarczająca liczba opcji wyszukiwania powinna być dostępna bez zwiększania złożoności systemu. Z tego powodu sugerowane są następujące mechanizmy wyszukiwania: Wyszukiwanie hierarchiczne: to wyszukiwanie kataloguje wiedzę w ustalonej hierarchii, w taki sposób, że użytkownik może poruszać się po grupie linków w celu zawężenia wyszukiwania.

o Wyszukiwanie atrybutów: opiera się na specyfikacji terminów, którymiużytkownik jest zainteresowany, co skutkuje znalezieniem elementów wiedzy, które mogą odpowiadać tym terminom. Ten typ wyszukiwania zapewnia bardziej ogólne wyniki niż poprzedni.

2. Żółte Strony: system zarządzania wiedzą nie powinien próbować gromadzić i przyswajać całej wiedzy istniejącej w organizacji, ponieważ byłoby to niewykonalne. Dlatego Żółte Strony służą do uwzględniania nie tylko systemów przechowujących wiedzę, ale także osób posiadających dodatkową wiedzę. Ich opracowanie odbywa się po ustaleniu wiedzy posiadanej przez każdą osobę w organizacji lub przez inne podmioty zewnętrzne.

3. Mechanizmy współpracy i komunikacji: w organizacjach wiedza jest współdzielona i dystrybuowana niezależnie od tego, czy proces jest zautomatyzowany, czy nie. Technologia wspomaga wymianę wiedzy i pomysłów między członkami organizacji, ponieważ umożliwia dotarcie z najlepszą możliwą wiedzą do osoby, która jej potrzebuje. Wykryte mechanizmy współpracy i komunikacji to:

3.1 Komunikacja asynchroniczna. Nie wymaga jednoczesnego połączenia między końcami komunikacji. E-mail. Komunikator elektroniczny umożliwia wymianę tekstu i/lub dowolnego innego rodzaju dokumentów między dwoma lub kilkoma użytkownikami.

o Forum. Składa się ze strony internetowej, na której uczestnicy pozostawiają pytania, na które nie muszą odpowiadać w danym momencie. Pozostali uczestnicy pozostawiają odpowiedzi, które wraz z pytaniami są widoczne dla każdego, kto wejdzie na forum w dowolnym momencie.
o Skrzynka sugestii. Umożliwia wysyłanie sugestii lub komentarzy dotyczących dowolnego istotnego aspektu organizacji do odpowiedniej osoby lub działu.
o Tablica ogłoszeń. To wspólna przestrzeń, w której członkowie organizacji mogą publikować ogłoszenia istotne dla interesu publicznego.

3.2 Komunikacja synchroniczna. Ten rodzaj interaktywnej technologii opiera się na komunikacji w czasie rzeczywistym. Do najważniejszych systemów należą:

Czat. Oznacza komunikację między kilkoma osobami za pośrednictwem komputera, ponieważ wszystkie połączone osoby mogą śledzić komunikację, wyrażać opinie, wnosić pomysły, zadawać pytania lub odpowiadać na nie w dowolnym momencie.

o Tablica elektroniczna. Zapewnia członkom organizacji wspólną przestrzeń usprawniającą wymianę pomysłów, w której każdy rysuje lub pisze.

o Konferencja audio. Dwóch lub więcej użytkowników może korzystać z komunikacji głosowej w czasie rzeczywistym.

o Wideokonferencja. Dwóch lub więcej użytkowników może korzystać z komunikacji wizualnej w czasie rzeczywistym.

PRZYSZŁE TRENDY

Jak wspomniano wcześniej, obecnie nie istnieje narzędzie zarządzania wiedzą (KM), które mogłoby odpowiednio zaspokoić potrzeby organizacji. W niniejszej pracy podjęto ten problem, próbując określić funkcjonalność, jaką powinno zawierać każde z tych narzędzi. Jest to pierwszy krok, który należy uzupełnić kolejnymi pracami, ponieważ konieczne jest pogłębienie wiedzy i lepsze określenie sposobu podejścia do określonych aspektów i ich wdrożenia.

WNIOSKI

Wiedza, niezależnie od tego, czy jest zarządzana, czy nie, jest przekazywana w obrębie organizacji, chociaż jej istnienie nie oznacza jej odpowiedniego wykorzystania. Istnieje ogromna ilość wiedzy, do której dostęp jest niezwykle utrudniony; oznacza to, że istnieją elementy, z których nie uzyskuje się żadnych korzyści i które są tracone w organizacji. Zarządzanie wiedzą (KM) reprezentuje wysiłek na rzecz uchwycenia i czerpania korzyści ze zbiorowego doświadczenia organizacji poprzez udostępnienie go wszystkim jej członkom. Można jednak stwierdzić, że żadne z dostępnych obecnie narzędzi nie jest w stanie efektywnie realizować tego zadania, ponieważ, mimo że istnieją tzw. narzędzia zarządzania wiedzą (KM), służą one jedynie do przechowywania dokumentów i żadne z nich nie dokonuje strukturyzacji odpowiedniej wiedzy w celu jej optymalnego wykorzystania. Aby złagodzić te problemy, w niniejszej pracy zaproponowano podejście oparte na badaniu rynku. Opiera się ono również na definicji zarządzania wiedzą (KM), która wskazuje, jak należy podchodzić do zarządzania wiedzą i definiuje cechy, jakie powinno posiadać narzędzie, aby mogło ono pełnić rolę facylitatora adekwatnego i jasno określonego zarządzania wiedzą.