Określanie pozycji robotów mobilnych z wykorzystaniem skanerów laserowych LRF

System składa się z punktów orientacyjnych oraz laserowego skanera do pomiaru odległości o nazwie Pos-URG. Punkty orientacyjne rozmieszczone zostały losowo i rzadko, a ich pozycja i sposób ułożenia są w trakcie działania systemowi znane. Pos-URG przechowuje mapę danych, która składa się z informacji o pozycji oraz relacji między punktami orientacyjnymi - informacje te posortowane zostały rosnąco w zależności od odległości pomiędzy punktami.

Rys. 1. Zasada przetwarzania czujnika

Rys. 2. Sposób wyświetlania danych przez Pos-URG

W momencie znalezienia wielu punktów orientacyjnych, są one porównywane z danymi z mapy. Przeszukiwanie jest wykonywane nie tylko z wykorzystaniem informacji o położeniu i ustawieniu danego punktu orientacyjnego, ale także na podstawie relacji pomiędzy poszczególnymi obiektami. Pozycja i ułożenie urządzenia Pos-URG jest obliczana z przekształcenia współrzędnych czujnika w stosunku do współrzędnych mapy. Najważniejszą cechą charakterystyczną opisywanej metody przeszukiwania jest krótki czas obliczeniowy, który pozwala na jej wykorzystanie względnie taniego mikroprocesora.

JAK OKREŚLAĆ POZYCJĘ?

Znajomość pozycji robota jest w przypadku robotów mobilnych zagadnieniem fundamentalnym, przy czym istnieją dwie zasadnicze metody jej określania. Pierwsza polega na oszacowaniu pozycji absolutnej w każdym miejscu, a druga na korygowaniu skumulowanej odometrii. W obu przypadkach kluczową rolę odgrywają zewnętrzne czujniki (np. opisany dalej czujnik Sokuiki, kamera wizyjna lub GPS) oraz czujniki wewnętrzne (np. żyroskop, enkodery na kołach).

a) Informacja o pozycji i orientacji wierzchołka każdego punktu orientacyjnego	b) Informacja o zależności każdego punktu orientacyjnego z punktu widzenia krawędzi
Rys. 3. Zawartość mapy danych

W warunkach zewnętrznych najczęściej jest wykorzystywany GPS, ze względu na możliwość określenia pozycji absolutnej, a inne metody wymagają zbyt dużej mocy obliczeniowej do samopozycjonowania robota mobilnego. Jednakże korzystanie z systemu nawigacji GPS jest bardzo utrudnione w pomieszczeniach. Obecnie trwają intensywne prace nad wynalezieniem wewnętrznego GPS-u, ale jego dokładność jest niewystarczająca do zastosowania w robotyce mobilnej. Jednym ze znanych systemów pozycjonowania opartych o LRF jest NAV200 firmy Sick.

System ten składa się ze skanera laserowego i obiektu odbijającego, a własną pozycję określa poprzez porównywanie pozycji obiektów odbijających z ich wstępnie zapamiętaną pozycją. Jednakże koszty oraz rozmiary tych skanerów nie są odpowiednie dla małych robotów mobilnych.

OPIS ROZWIĄZANIA

Proponowany system pozycjonowania składa się z czujnika Sokuiki Pos-URG będącego jednym z produkowanych przez firmę Hokuyo Automatic skanerów LRF oraz wielu obiektów odbijających promienie zlokalizowanych w środowisku pomiarowym. Te ostatnie rozmieszczone zostały losowo w charakterze punktów orientacyjnych, a następnie w Pos-URG zarejestrowano w postaci mapy danych ich pozycje, sposoby ustawienia, odległości pomiędzy nimi oraz wektory usytuowania.

a) Wykrywanie punktów orientacyjnych w rzeczywistym środowisku (pokazano obszar skanowania czujnika)	b) Pozycja każdego punku orientacyjnego została zapisana w Pos-URG, jako punkt mapa
Rys. 4. Przykład środowiska wyszukiwania

Pos-URG wraz z robotem mobilnym porusza się w przestrzeni i dokonuje pomiarów. W momencie wykrycia wielu punktów orientacyjnych mapa jest przeszukiwana w celu znalezienia odpowiedników w pamięci. Następnie obliczana jest pozycja i usytuowanie czujnika na podstawie transformacji współrzędnych ze współrzędnych otrzymanych w wyniku pomiaru na współrzędne mapy (rys. 1). Dane zostały zarejestrowane w mapie w postaci struktury drzewa i każdy rekord zawiera pozycję punktu orientacyjnego oraz relację pomiędzy poszczególnymi punktami.

Każdy węzeł ma pozycję i usytuowanie, a każda krawędź odległość pomiędzy obiektami i orientację wektora. Koszt obliczeniowy przeszukiwania takiej struktury danych jest niski, zatem wymagania w stosunku do mocy procesora mogą być mniejsze. Dzięki temu proponowana metoda jest właściwa do zastosowań m.in. w kompaktowych czujnikach, a jednocześnie układ sterujący robotem jest uwolniony od obciążenia obliczeniowego. Na rysunku 2 przedstawiono okno interfejsu użytkownika systemu czujnika wyświetlające wynik pomiaru.

ALGORYTM PRZESZUKIWANIA

1. Mapa punktów orientacyjnych

Na rysunku 3 przedstawiono znaczenie każdego z elementów zapisanych w mapie danych. Dane węzła są następujące: (1) pozycja (współrzędne x, y), (2) usytuowanie (orientacja powierzchni odbijającej), (3) linia graniczna obszaru widzialnego (nachylenie a i przesunięcie b równania liniowego y = ax+b). Dane krawędzi to: (1) numer indeksu (liczba porządkowa), (2) odległość (pomiędzy sobą i rodzicem), (3) orientacja wektora (od punktu orientacyjnego rodzica do samego siebie).

a) Znaleziono Ma-2, który jest w odległości około l1 od Ma-1	b) Znaleziono Ma-3, który jest w odległości około l2 od Ma-2, w kierunku θ1 od segmentu Ma-1Ma-2	c) Własna pozycja jest szacowana poprzez dopasowanie wyniku
Rys. 5. Wyszukiwanie zakończone sukcesem

W momencie zarejestrowania w mapie N punktów orientacyjnych, wszystkie z nich mają N-1 zestawów wartości posortowanych rosnąco ze względu na wzajemną odległość. Pos-URG wystawia na wyjściu swoją pozycję i usytuowanie w tym samym układzie współrzędnych co mapa.

2. Algorytm przeszukiwania

Tabela 1. Specyfikacja czujnika Rapid-rURG

Przeszukiwanie i asocjacja znajdowanych punktów orientacyjnych wykonywana jest w kierunku zgodnym z ruchem skanera Pos-URG. Czujnik skanuje w kierunku od prawej do lewej strony, zatem pierwszy wykryty punkt orientacyjny jest oznaczany jako L₁, następny po lewej jako L₂, itd. Przykład skanowania pokazany jest na rysunku 4a, natomiast rysunek 4b pokazuje reprezentację wirtualnej mapy, na której są zlokalizowane punkty orientacyjne (linie ścian nie są przechowywane na mapie). Definiujemy powiązaną mapę M_a-i, w której został znaleziony element a oraz następnie element i powiązany z a.

Proponowany algorytm przeszukiwania jest następujący (rys. 5 i 6):

1. W momencie wykrycia n elementów zostają one podzielone na n klastrów i ponumerowane jako {L₁, L₂, …, L_n} (rys. 4a).
2. Kiedy n>1 to L₁ jest powiązane z jednym z punktów orientacyjnych w mapie M_1-1, inaczej przetwarzanie wraca do kroku poprzedniego (rys. 6a).
3. Obliczana jest odległość l₁ pomiędzy L₁ i L₂, następnie budowany jest obszar przeszukiwania o promieniu l₁ i marginesie zależnym od dokładności czujnika. Przy użyciu informacji o odległości krawędzi zachowanej na mapie, punkty orientacyjne znalezione w obszarze wyszukiwania są sortowane rosnąco zgodnie z ich odległością od krawędzi M_1-1. Jeżeli n=2, przetwarzanie przesuwa się do kroku 6 (rys. 5a).
4. Obliczana jest odległość l₂ i kąt Θ₁ pomiędzy L₂ i L₃, następnie tworzony obszar poszukiwań w odległości l₂ i pod kątem Θ₁ z użyciem marginesu dokładności czujnika jako promienia. Jeżeli w obszarze poszukiwań znajdzie się punkt orientacyjny, jest on wiązany z mapą M_1-3. Wykorzystuje się tutaj wektor orientacji krawędzi zapisanej jako dana w mapie (rys. 5b).
5. Jeżeli w procesie przeszukiwania zostaje wykryty M_1-n, oznacza to, że zakończyło się ono sukcesem. Inaczej przetwarzanie wraca do punktu drugiego (rys. 6b).
6. Obliczany jest parametr transformacji Helmerta z wykorzystaniem współrzędnych {M_1-1, M_1-2, …, M_1-n} i {L₁, L₂, …, L_n} za pomocą metody najmniejszych kwadratów. Docelowo obliczana jest najbardziej prawdopodobna pozycja i usytuowanie czujnika za pomocą transformacji Helmerta dla {0, 0} (rys. 5c).
7. Ważność uzyskanego wyniku jest potwierdzana poprzez relację pozycji czujnika i orientację powierzchni odbijającej (rys. 7a).
8. Przetwarzanie od kroku drugiego do siódmego wykonywane jest dla każdego punktu orientacyjnego w mapie.
9. W przypadku otrzymania kilku wyników, przyjmowany jest najbardziej prawdopodobny, oczywiście, jeżeli może zostać to stwierdzone na podstawie poprzednich danych (rys. 7b).

Największą korzyścią z zastosowania opisywanej metody jest małe zapotrzebowanie na moc obliczeniową procesora. Po zarejestrowaniu na mapie N punktów orientacyjnych i wykryciu ich w liczbie n, drugi krok jest przetwarzany maksymalnie Nx(N-1) razy. W większości przypadków jednak przeszukiwanie kończy się właśnie w takim czasie, ponieważ rzadkie i losowe usytuowanie elementów ogranicza możliwość stworzenia właściwych warunków do jego przeprowadzenia.

a) Mapa nie zawiera punktu orientacyjnego Mb-2, znajdującego się w odległości około l1 od Mb-1	b) Mapa nie zawiera punktu orientacyjnego Mc-3, który znajduje się w odległości około l2 od Mc-2, w kierunku θ1 od segmentu Mc-1Ma-2, ale zawiera Mc-2 znajdujące się w odległości około l1 od Mc-1
Rys. 6. Wyszukiwanie zakończone porażką

Proces przeszukiwania zostanie przerwany, jeżeli odległość pomiędzy każdym punktem orientacyjnym przewyższa maksymalny zakres Pos-URG. Większość iteracji przeszukiwania zostaje szybko przerwana z powodu istniejących ograniczeń. Jeżeli wyszukiwanie zakończy się powodzeniem, to następna iteracja zostaje ograniczona do bliskiego otoczenia poprzedniego punktu. W momencie inicjacji obszar poszukiwań ograniczany jest na podstawie pierwszego procesu.

3. Dowodzenie ważności danych

Rysunek 7 przedstawia sposób potwierdzania ważności danych realizowany w kroku siódmym algorytmu. Zgodnie z rysunku 7a, kiedy Pos-URG znajduje się z tyłu obiektu lub orientacja czujnika jest podobna do orientacji powierzchni odbijającej, obiekt nie może być wykryty. Proces przeszukiwania opisany w poprzedniej sekcji nie może wykluczyć takiego właśnie przypadku. Przewidziano zatem specjalną procedurę, tak aby móc go wykryć.

a) Określenie ważności na podstawie pozycji czujnika i punktów orientacyjnych	b) Określenie ważności na podstawie orientacji czujnika
Rys. 7. Określenie ważności obliczonej pozycji czujnika

Jak pokazano na rysunku 3a, na mapie danych zarejestrowana jest orientacja powierzchni odbijającej oraz nachylenie i przesunięcie równania liniowego opisującego tę powierzchnię. Aby zadecydować, czy obiekt może być wykryty, czy nie, należy odwołać się do opisanych powyżej danych, a także do pozycji i usytuowania samego czujnika. Kolejną niestandardową sytuacją jest przypadek, w którym przeszukiwanie dostarcza dwie pozycje w momencie wykrycia dwóch obiektów, tak jak na rysunku 7b.

Idąc dalej, pozycji może być nawet więcej. Rozwiązaniem jest wybór najbardziej prawdopodobnej opcji, opierając się o historię wcześniej zarejestrowanych wyników. Jeżeli pomimo zastosowania opisywanych procedur nie można określić unikalnego wyniku, wszystkie opcje są przyjmowane jako rozwiązanie, a następnie zawężane do jednego, w czasie, gdy czujnik kontynuuje ruch.