Abstract

This paper describes a quadruped mobile walking robot equipped with a IR range sensor and it show our attempt to solve the map building and path planning tasks in an unknown indoor environment. The encounter troubles forces us to changed the subject of this project. The new subject is to avoid contact with obstacles in unknown environment without concrete destination. This document describes troubles which were founded during realization of this project and it contain a describe of algorithm solving this task in real time. Algorithm is implemented in control unit of the robot without using any connection with exterior host computer ensure full autonomy of the robot.

1. Opis zadania

Początkowym zadaniem, które zamierzano zrealizować w ramach wykonanego projektu, było rozwiązanie problemu planowania bezkolizyjnej ścieżki robota. Ruch maszyny z punktu początkowego do punktu docelowego, przy jednoczesnym omijaniu przeszkód, miał być realizowany na podstawie dynamicznie budowanej mapy otoczenia. Informacje o otoczeniu pochodziły by z będącego na wyposażeniu robota, dalmierza działającego w paśmie podczerwonym ( PSD ).
Niestety, trudności napotkane w trakcie realizacji powyższego zadania wymusiły jego modyfikację. Realizowane zadanie zredukowano do problemu bezkolizyjnego poruszania się robota w nieznanym środowisku, bez ściśle określonego celu ( bez zadanego punktu docelowego ). Algorytm realizujący przedstawione zadanie zaimplementowano w jednostce sterującej robota, będącej jego integralną częścią. Wyeliminowało to konieczność zastosowania zewnętrznego systemu sterowania i kontroli, pozwalając na pełną autonomiczność wykorzystanej maszyny.
Poszczególne etapy realizacji zmodyfikowanego zadania opisano w dalszej części raportu.

2. Słów kilka o robocie

Wykorzystany w zadaniu robot został skonstruowany przez autorów niniejszego dokumentu, w ramach wcześniej realizowanych kursów uczelnianych. Każda z nóg tej czteronożnej maszyny kroczącej ma 3 stopnie swobody. Układ napędowy robota stanowi 12 serwomechanizmów zamocowanych w przegubach poszczególnych nóg.
Konstrukcję robota wykonano z poddanych obróbce prefabrykowanych kształtowników aluminiowych oraz szkła akrylowego.
Układ sterowania robota stanowią dwa mikrokontrolery firmy Atmel z rodziny AtMega. Jednostkę główną odpowiedzialną za obliczanie kinematyki odwrotnej oraz obsługę czujników, oparto o układ AtMega644. Kontroler serwomechanizmów komunikujący się z jednostką główną przy wykorzystaniu interfejsu SPI zrealizowano na układzie AtMega8.
Układ sterowania zasilany jest z akumulatora polimerowego za pośrednictwem przetwornicy.
Na chwilę obecną robot wyposażony jest w czujnik odległości IR firmy SHARP oraz w 3 osiowy akcelerometr.

Opisanego powyżej robota przedstawia poniższa fotografia.

Rys. 1. Czteronożny robot kroczący.

3. Realizacja zadania

Poszczególne etapy realizacji zadania przedstawiono poniżej. Podzielono je na dwie części.
W punkcie 3.1 wymieniono i krótko scharakteryzowano zadania, które nie są związane bezpośrednio z problemem bezkolizyjnego poruszania się w nieznanym środowisku. Były one jednak niezbędne do tego aby zadanie właściwe mogło być zrealizowane. Wszystkie z wymienionych w tym punkcie rozwiązań opracowano na potrzeby projektu, którego dotyczy niniejszy raport.
W punkcie 3.2 zawarto opis algorytmu realizującego główny cel projektu - bezkolizyjne poruszanie się robota w nieznanym środowisku.

3.1. Zadania poboczne

• opracowanie algorytmu chodu robota - bezwzględnym wymaganiem umożliwiającym realizację zadania głównego było opracowanie bardziej zaawansowanego algorytmu chodu robota ( etap prac prowadzonych w ramach poprzednio realizowanych kursów zakończył się na opracowaniu prymitywnego algorytmu pozwalającego robotowi na względnie stabilne poruszanie się do przodu ).
  Opracowany algorytm zapewnia w pełni stabilne poruszanie się robota. Zaprogramowane sekwencje umożliwiają robotowi poruszanie się do przodu, skręcanie w lewo i w prawo. Na chwilę obecną robot nie potrafi chodzić do tyłu.
  Sterowanie chodem robota polega na generowaniu odpowiednich sekwencji sygnałów sterujących, zależnych od aktualnie wykonywanego rodzaju przemieszczenia ( ruch w przód, obrót ). Wartości tych sygnałów obliczane są w oparciu o wyniki zwracane jako rezultat rozwiązania odwrotnego zadania kinematyki. Zależności opisujące odwrotne zadanie kinematyki dla omawianego robota, zostały wcześniej wyznaczone i zaimplementowane.
  
  
• akwizycja i obróbka danych z dalmierza - realizacja tego zadania polegała na odpowiednim skonfigurowaniu jednostki centralnej, tak aby możliwa była detekcja sygnałów generowanych przez zastosowany czujnik odległości. Istotną kwestią którą rozwiązano na tym etapie, było określenie optymalnego czasu pomiaru, na który składał się czas potrzebny na ustalenie pozycji czujnika ( obrót o wyznaczony kąt ), oraz czas niezbędny na ustabilizowanie się odczytu ( problem wynikał z opóźnienia czujnika ). Z uwagi na ograniczenia wynikające ze sposobu sterowania serwomechanizmem odpowiedzialnym za obrót czujnika, zdecydowano że zakres obrotu wynosił będzie: +/- 30st.
  Pojedyncza seria pomiarowa składa się z 13-stu próbek. Pierwsza próbka pobierana jest dla skrajnego położenia czujnika. Każda kolejna pobierana jest po obrocie serwomechanizmu o 5st.
  Ograniczony zakres pomiarowy czujnika oraz niedokładności występujące przy pomiarze odległości większych niż 150cm, wymusiły nałożenie granicznej wartości maksymalnej zwracanego pomiaru, równej 150cm. Dane pozyskiwane z czujnika, wskazujące na większą odległość są interpretowane jako odległość 150cm.
  Kolejnym ograniczeniem jest istniejąca przed czujnikiem tzw. "martwa strefa" ( dla zastosowanego modelu: "martwa strefa" = ok. 20cm ). W uproszczeniu jej istnienie powoduje niejednoznaczność zwracanych wartości dla zakresów pomiaru od 0-20cm. Wartości pomiarowe z tego zakresu mogą być w niektórych sytuacjach interpretowane jako odległość 150cm w przypadku gdy przeszkoda może znajdować się np. w odległości 5cm od czujnika ( dokładniejsze zrozumienie problemu "martwej strefy" wymaga przeczytania dokumentacji czujnika, a w szczególności analizy jego charakterstyki - stosowny odnośnik: dokumentacja )
  Niestety dla tego modelu czujnika, rozwiązanie tego problemu nie jest możliwe. Jedynym wyjściem jest zastosowanie innego modelu sensora o mniejszym obszarze "martwej strefy".
  
  Przy wykorzystaniu prostych zależności trygonometrycznych, wstępnie przetworzonym danym przypisywane są współrzędne w układzie kartezjańskim. Punkt (0,0) tego układu utożsamiony jest z osią czujnika. Współrzędne kartezjańskie zapamiętywane są w pamieci RAM mikrokontrolera stanowiąc materiał do dalszej obróbki.
  Przykladowy pomiar przedstawiono na poniższym rysunku.

Rys. 2. Obraz otoczenia uzyskany po wykonaniu jednej serii pomiarowej.

3.2. Zadanie główne

W ramach realizacji głównego zadania niniejszego projektu opracowano i zaimplementowano algorytm umożliwiający bezkolizyjne poruszanie się robota w nieznanym środowisku. Opis algorytmu zamieszczono poniżej ( opis pozbawiony jest szczegółowych objaśnień algorytmu chodu robota - z punktu widzenia realizacji tematu niniejszego zadania, jest on mniej istotny ):

Krok 1.

W pierwszym kroku algorytmu, tuż po zresetowaniu jednostki centralnej, wykonywana jest pierwsza seria pomiarowa. Każda seria wykonywana jest po zakończeniu aktualnie realizowanej przez robota sekwencji ruchów. Innymi słowy, podczas wykonywania pomiaru robot jest nieruchomy ( dane zebrane podczas pomiaru wykonywanego w trakcie chodu robota byłyby bezużyteczne ze względu na przemieszczenia będące oczywistym wynikiem ruchu oraz znaczne błędy występujące w przypadku takiego pomiaru ).

Krok 2.

W drugim kroku algorytmu, po wcześniejszej obróbce danych pomiarowych ( opis w punkcie 3.1 ) następuje ich interpretacja. Ze wszystkich danych pomiarowych, wyselekcjonowane zostają te, których współrzędna X oddalona jest od środka układu wspołrzędnych o |30cm| ( | | - wartość bezwzględna ). Pozostałe dane nie są w tym kroku interpretowane. Innymi słowy, dalsza interpretacja dotyczy danych, które znajdują się w "korytarzu" o szerokości 60-ciu centymetrów - przybliżona szerokość robota ( z odpowiednim marginesem bezpieczeństwa ).
Następnie wśród wyselekcjonowanych danych pomiarowych wyszukana zostaje ta o najmniejszej wartości współrzędnej Y.
Jeśli znaleziona wartość Y jest większa od 39cm, następuje obliczenie ilości kroków, które robot może pokonać idąc w przód. Ilość krokow obliczana jest na podstawie następującej zależności:

ilość_kroków = ( minimalna_wartość_Y - margines_bezpieczeństwa )/ długość_elementarnego_kroku

Krok 3.

Krok trzeci wykonywany jest wyłącznie wtedy, gdy przeszkoda znajduje się na tyle blisko robota, że dalsze kontynuowanie ruchu w przód groziło by kolizją. W takim przypadku podejmowana jest decyzja o wykonaniu sekwencji ruchów powodujących elementarny obrót robota.
Kryterium określajace kierunek obrotu ( lewo/prawo ) jest następujące.

Wśród wszystkich danych pomiarowych wyszukiwane są dwie próbki:
- spośród wszystich próbek, których wartość współrzędnej X jest mniejsza od 0, wyszukiwana jest ta o najmniejszej wartości współrzędnej Y;
- spośród wszystkich próbek, których wartość współrzędnej X jest większa bądź równa 0, wyszukiwana jest ta o najmniejszej wartości współrzędnej Y;
( wyszukiwany jest najbliższy punkt przeszkody po lewej i prawej stronie robota - z dokładnością do punktu zerowego )

Następnie podejmowana jest decyzja. Jeśli najbliższą próbkę wykryto po lewej stronie robota, podejmowana jest decyzja o obrocie w prawo. Jeśli z kolei najbliższy punkt przeszkody wykryto po prawej stronie robota, wykonywany jest obrót w lewo.
Po wykonaniu obrotu następuje przejście do pierwszego kroku opisywanego algorytmu ( zapętlenie ).

4. Testy

Testowanie opracowanego algorytmu polegało na przeprowadzeniu serii eksperymentów, podczas których badano "zachowanie się" robota przy różnych konfiguracjach otoczenia ( zmieniano rodzaj i ułożenie przeszkód ). Przeprowadzone doświadczenia, jak i osobne badania jakości uzyskiwanych danych pomiarowych, pozwoliły na wyodrębnienie kilku najistotniejszych z zaobserwowanych problemów. Napotkane trudności, wraz z próbą wyjaśnienia ich przyczyn wymieniono poniżej.

• problem z pomiarem przemieszczenia robota
  Stanowił główną przyczynę modyfikacji tematu zadania projektowego. Problem polega na braku możliwości dokładnego pomiaru wartości przemieszczenia. Na chwilę obecną robot nie jest wyposarzony w zaawansowane czujniki pozwalające określić odelgłość jaką pokonał robot w rezultacie wykonania elementarnego ruchu ( krok w przód, obrót w lewo bądź w prawo ). Początkowo próbowano mierzyć pokonaną odległość na podstawie liczby wykonanych kroków ( po uprzednim zmierzeniu i przyjęciu stałej wartości jednego kroku ). Niestety taki sposób pomiaru przemieszczenia obarczony jest dużymi błędami, wykluczającymi jego zastosowanie w zadaniu planowania bezkolizyjnej ścieżki przeprowadzającej robota z punktu początkowego do docelowego.
  Po przyjęciu takiego sposobu pomiaru przemieszczenia, zbudowana mapa otoczenia byłaby całkowicie bezużyteczna. W trakcie wykonywania kolejnych kroków i detekcji kolejnych przeszkód, błędy by się kumulowały, co w rezultacie ( po przejściu kilku kroków ) doprowadziłoby do błędnego określenia odległości między przeszkodami ( mapa otoczenia zapamiętana w pamięci układu sterującego robota błędnie odzwierciedlałaby rzeczywiste środowisko co z kolei wymusiło by ciągły pomiar przestrzeni przed robotem. Zatem budowanie takiej mapy pozbawione jest sensu ).
  Przyczyną niedokładności występujących podczas przemieszczenia robota jest elastyczność każdego z 12-stu przegubów robota wynikająca z luzów występujących w zastosowanych serwomechanizmach oraz sposobu mocowania ogniw.
  Omawiany problem zobrazowano na poniższych rysunkach. Pierwszy przedstawia wynik pomiaru przeprowadzonego przed elementarnym przemieszczeniem ( obrót w lewo ). Drugi z kolei wykonany był po powrocie robota do punktu początkowego ( obrót w prawo ). Rysunki obrazują przemieszczenie układu odniesienia będącego wynikiem wykonania opisanej sekwencji ruchów.

  Rys. 3. Obraz otoczenia przed wykonaniem ruchu.

  Rys. 4. Obraz otoczenia po wykonaniu obrotu w lewo a następnie w prawo.

  UWAGA:
  Przeszkoda na rysunku 4 naniesiona została względem układu odniesienia z rysunku 3. Dzięki temu widoczne jest przesunięcie względem siebie obydwu układów odniesienia.
  
  
• "martwa strefa" zastosowanego czujnika
  Wyjaśnienie problemu martwej strefy zawarto w punkcie 3.2. W tym miejscu przedstawiono zaobserwowane podczas przeprowadzania eksperymentów problemy, których przyczyną jest wspomniana wada zastosowanego czujnika odległości.
  Podczas eksperymentów kilkukrotnie zdarzyło się, że robot zahaczył którąś z nóg o znajdującą się bardzo blisko niego przeszkodę. To, że robot znalazł się tak blisko przeszkody ( mimo przewidzianego marginesu bezpieczeństwa ) było konsekwencją podjęcia w poprzednim kroku działania algorytmu, decyzji o wykonaniu elementarnego obrotu w prawo bądź w lewo. Wykonany po obrocie pomiar, z uwagi na obecność przeszkody w odległości mniejszej niż 20cm (ok. 15cm) nie odzwierceidlał rzeczywistego stanu otoczenia. Konsekwencją błędnej oceny stanu otoczenia było przeważnie podjęcie decyzji o wykonaniu obliczonej ilości kroków w przód co skutkowało kolizją robota ze znajdującą się przed nim przeszkodą ( kolizja polegała zazwyczaj na zahaczeniu przeszkody którąś przednich nóg robota ).
  Jak wspomniano wcześniej jedynym rozwiązaniem opisanego problemu jest wymiana czujnika na model o mniejszym obszarze "martwej strefy" bądź zwilokrotnienie ilości czujników w robocie.
  
  
• ograniczenia wynikające ze specyfiki chodu
  Podczas przeprowadzania eksperymentów kilkukrotnie miały miejsce sytuacje, w których robot nie podjął decyzji o przejściu pomiędzy dwoma przeszkodami, mimo tego, że odległość między nimi była wystarczająco duża. Problem nie wynika z błędnego działania algorytmu. Wręcz przeciwnie. Jego przyczyną jest "kwantyzacja" chodu. Robot może przemieszczać się o wielokrotność ściśle określonych, elementarnych ruchów ( pojedynczy krok w przód, obrót w lewo, obrót w prawo ). W opisanych wyżej sytuacjach niemożliwe było ( z uwagi na aktualne ustawienie będące konsekwencją poprzednich ruchów ) takie ustawienie robota, aby zdołał on przejść korytarzem wyznaczonym przez dwie przeszkody.
  Rozwiązaniem powyższej trudności może być opracowanie bardziej skomplikowanych algorytmów odpowiedzialnych za obrót robota, zmniejszających kwant ruchu. Z uwagi na specyfikę konstrukcji rozwiązanie tego problemu jest zagadnieniem niezwykle złożonym.

5.Kierunki rozwoju

Dalsze etapy prac nad nawigacją omawianego robota będą koncentrowały się na wyposażeniu go w odpowiednie układy umożliwiające dokładniejszy pomiar przemieszczenia robota. W ramach rozwiązania problemu samolokalizacji planuje się w przyszłości wzbogacenie robota o układ modułów GPS pozwalających na dokładne zlokalizowanie robota w przestrzeni zadaniowej.
Po opracowaniu układu zapewniającego duży stopień dokładności określania pozycji robota, planowana jest kontynuacja prac nad jego nawigacją.

6. Źródła

• http://www.datasheetcatalog.org/datasheets2/66/66516_1.pdf
  - dokumentacja użytego dalmierza
  
  
• http://www.ecse.monash.edu.au/centres/irrc/LKPubs/IJRR99map/MAPJNL3.html
  - budowanie mapy otoczenia z użyciem sonaru
  
  
• http://cml.mit.edu/~jleonard/pubs/ldw_iros_1991.pdf
  - budowanie mapy i lokalizacja dla autonomicznego robota mobilnego
  
  
• http://www.robotfrontier.com/papers/icra98.pdf
  - budowanie mapy z ciągłą lokalizacją
  
  
• http://www.math.kth.se/~hu/papers/iros36.pdf
  - planowanie trasy i nawigacja robota mobilnego w nieznanym otoczeniu
  
  
• http://www.morpha.de/download/publications/IPA_Eurobot01_IPA_final.pdf
  - elastyczne planowanie trasy dla nieholoniczmego robota mobilnego
  
  
• http://robotics.stanford.edu/~latombe/cs326/2000/visibility-graph-voronoi.ppt
  - graf widocznoóci i graf Voronoia