Ćwiczenie 2: Podstawowe algorytmy
planowania ścieżki

Planowanie ruchu jest czynnością, która decyduje jaki rodzaj działania ma

być podjęty w danej sytuacji (w której znajduje się np. robot), aby osiągnąć
zaplanowaną konfigurację końcową. Proces planowania związany jest także z
podejmowaniem oraz rozstrzyganiem wielu decyzji, m.in. którą ścieżkę wy-
brać, jakie informacje o środowisku wykorzystać w danej chwili.

Pomimo iż, planowanie w sytuacji, gdy znane są wszystkie informacje na

temat stanu środowiska zostały dokładnie zbadane, to w przypadku robota
mobilnego informacje i wiesza na temat otoczenia jest najczęściej wybiórcza i
niepewna. W tym przypadku należy analizować i realizować równolegle wiele
zadań ( planowanie ruchu, omijanie przeszkód, itd.)

Jedną z podstawowych funkcji sterowników robotów mobilnych, które

działają w częściowo lub zupełnie nieznanym otoczeniu dynamicznym, jest
wykrywanie oraz unikanie kolizji z przeszkodami lokalnymi. Aby zapobiec
kolizji, w algorytmach wykorzystuje się dane pomiarowe z sensorów, a także
docelową oraz aktualną pozycję względem docelowej w celu modyfikacji tra-
jektorii ruchu robota. Wykorzystywane algorytmy zapobiegania kolizji mu-
szą być efektywne obliczeniowo, projektowany ruch powinien być możliwie
płynny, a robot powinien musi podążać do określonego celu uwględniając
swoje ograniczenia fizyczne.

0.1. Wiadomości wprowadzające

Podstawowy problem planowania ścieżki związany jest z wyznaczeniem

krzywej geometrycznej przejścia pomiędzy początkową, a zadaną docelową
pozycją robota w takim sposób, aby nie występowały kolizje z przeszkodami.
Planowany ruch nie może także ograniczać kinematycznie i dynamicznie ro-
bota, tzn. wybrana ścieżka musi być możliwa do zrealizowania.

Planowanie ruchu robotów jest uzależnione od rodzaju robotów mobilnych

(wyróżnia się roboty holonomiczne i nieholonomiczne).

Przy planowaniu ścieżki w przypadku rzeczywistych robotów mobilnych

najczęściej przyjmuje się, że robot jest holonomiczny. Odnosi się to zwłasz-
cza do przypadku robotów z napędem różnicowym (ponieważ mogą obracać
się one praktycznie w miejscu). Ścieżka robota holonomicznego jest łatwo
odtwarzalna, gdy orientacja robota nie jest krytyczna. Dodatkowo, przy pro-
jektowaniu i symulacji ścieżki przyjmuje się, że robot jest punktem material-
nym, który porusza się w przestrzeni o przeszkodach, które są powiększone
o promień okręgu opisanego na danym robocie.

Metody planowania ścieżki można podzielić na:

2

Ćwiczenie 2: Podstawowe algorytmy planowania ścieżki

— globalne - całkowita ścieżka obliczana jest w procesie iteracyjnym. Me-

toda globalna dotyczy minimalizacji funkcji błędu. W metodzie tej przyj-
muje się, że znany jest rozkład wszystkich przeszkód w środowisku robota.
Wykorzystywany jest wyidealizowany model robota i jego otoczenia. Pro-
blemem jest duża złożoność obliczeniowa oraz ze względu na pojawianie
się np. ruchomych przeszkód, mała odporność na zmianę warunków po-
czątkowych. W związku ze złożonością obliczeniową, metody globalne są
metodami wstępnego planowania ruchu (tzn. óff-line"). Oznacza to, że
cała ścieżka jest zaplanowana zanim zostanie ona przesładana do robota
w celu wykonania jej przez układ sterowania robota.

— lokalne - unikanie przeszkód, podążanie do celu, zakładając dostępność

informacji o przeszkodach w najbliższym otoczeniu robota. Metody lo-
kalne są zazwyczaj metodami on-line czyli planowanie odbywa się w cza-
sie rzeczywistym, ścieżka tworzona jest przyrostowo. Charakteryzuje je
szybkość działania, stosunkowo duża odporność na zmiany otoczenia (dy-
namiczne środowisko);

Algorytm jest zupełny, gdy znajdzie rozwiązanie, jeśli ono tylko istnieje.

Istnieją słabsze postacie zupełności: zupełność przy zadanej rozdzielczości
(dyskretyzacji przestrzeni poszukiwań) i zupełność probabilistyczna (praw-
dopodobieństwo znalezienia rozwiązania dąży do 1, gdy czas działania algo-
rytmu dąży do nieskończoność. Ze względu na zupełność algorytmów plano-
wania wyróżniamy:
— podejścia dokładne (deterministyczne) zupełne;
— podejścia przybliżone zupełność przy zadanej rozdzielczości;
— podejścia losowe zupełność probabilistyczna;
— podejścia heurystyczne niezupełne.

0.1.1. Lokalne metody planowania ruchu

Lokalne metody planowania ruchu opierają się zazwyczaj na modyfikacji

zadanej trajektorii bazując na bieżących odczytach z czujników

Algorytm BUG

Algorytm BUG jest jest chyba najprostszym algorytmem omijania prze-

szkód. Robot podążając do celu, gdy napotka przeszkodę podąża wzdłuż
jej brzegu. Istnieje wiele odmian algorytmu BUG. Robot, wykorzystujący
algorytm BUG1, najpierw objeżdża całą przeszkodę, a dopiero podczas dru-
giego okrążenia decyduje, w którym miejscu przestać podążać wzdłuż brze-
gów przeszkody. Obrazuje to rysunek 2.9.

Jest to bardzo niewydajny algorytm, ale gwarantuje, że robot dotrze do

celu, jeśli tylko ten jest osiągalny. W przypadku algorytmu BUG2 robot po-
dąża wzdłuż brzegów przeszkody, podobnie jak w przypadku BUG1, ale tylko
do momentu gdy jest w stanie bezpośrednio podążyć do wyznaczonego celu,
co przedstawia rysunek 2.10. W ogólności BUG2 będzie zapewniał krótsza
ścieżkę ruchu, ale nadal nie będzie ona optymalna (jeśli kryterium stanowi
długość ścieżki).

0.1. Wiadomości wprowadzające

3

VFH i jego odmiany

Algorytmy te należą do grupy metod planowania ruchu bazujących na wy-

znaczaniu kierunku. Dokładniejszy opis tych metod znajduje się w rozdziale
4.

1. Dynamiczne okno- Metoda dynamicznych okien, jest techniką unikania

kolizji uwzględniającą ograniczenia kinematyczne robota.W literaturze
zostały przedstawione dwa podejścia: metoda dynamicznych okien (po-
dejście lokalne) [5] zaproponowana przez Foxa, Burgarda i Thruna oraz
metoda dynamicznych okien (podejście globalne) [3] podana przez Brocka
i Khatiba. Podejście lokalne W algorytmie dynamicznych okien (podej-
ście lokalne) wartości sterujące robota (prędkość liniowa v oraz kątowa
w) otrzymuje się w wyniku przeszukiwania przestrzeni prędkości. Prze-
strzeń ta jest zbiorem wszystkich możliwych wartości (v,w), gdzie v to
prędkość liniowa robota, natomiast w to prędkość kątowa. W algorytmie
tym zakładamy, że robot porusza się po torze będącym łukiem okręgu.
Mając daną aktualną prędkość wyznaczamy najpierw wszystkie dyna-
miczne okna dla pary (v,w), które mogą być osiągnięte w następnej chwili
czasowej (uwzględniając dynamikę robota). Następnie zbiór uprzednio
wyznaczonych okien jest redukowany do takich, które zapewniają bez-
pieczne zatrzymanie się robota przed przeszkodą. Wybrane w ten sposób
pary prędkości (v,w) nazywamy dopuszczalnymi. Nowy kierunek i pręd-
kość jest wyznaczana przez minimalizację wskaźnika jakości dobieranego
jako liniowa zależność (z odpowiednimi wagami) pomiędzy: odległością
od przeszkody, która wynika z danej pary (v,w), orientację względem
celu (też wynikającym z danej pary (v,w)) oraz prędkością, z jaką będzie
możliwy ruch (preferuje się szybki ruch na wprost).

2. Podejście globalne Podejście globalne polega na rozszerzeniu wcześniej

omawianego wskaźnika o składnik odzwierciedlający odległość do celu.
Część ta wyznaczana jest w oparciu o algorytm propagacji fali NF1, który
przeszukuje siatę zajętości analizowanego obszaru. W praktyce podejście
to okazuje się bardzo wydajnym rozwiązaniem, pozwalającym na osią-
gnięcie czasu wyznaczania ścieżki rzędu kilkunastu milisekund.
Diagram sąsiedztwa- Metoda diagramów sąsiedztwa (Nearness Diagram
ND) wydobywa informacje o środowisku otaczającym robota w trzech
etapach: 1. Na podstawie dostępnych informacji z sensorów budowane są
dwa diagramy sąsiedztwa: PND diagram sąsiedztwa widziany względem
punktu centralnego, RND diagram sąsiedztwa widziany względem robota.
Punkt centralny w praktyce jest środkiem geometrycznym robota. Dia-
gram PND reprezentuje sąsiedztwo przeszkód do tego punktu. Natomiast
diagram RND reprezentuje sąsiedztwo przeszkód do granic korpusu ro-
bota. 2. Diagram PND jest analizowany pod kątem wolnych obszarów.
Następnie wybierany jest jeden z tych obszarów. 3. Diagram RND jest
analizowany w celu oceny bezpieczeństwa sytuacji, w której robot się
znajduje. Uzyskane w trakcie tych analiz informacje są wykorzystywane
do podjęcia decyzji o następnym ruchu, na podstawie pięciu praw, które
przekładają się na pięć ocen bezpieczeństwa sytuacji, w których robot
może się znaleźć. Szerszy opis algorytmu znajduje się w [8]. Podejście to

4

Ćwiczenie 2: Podstawowe algorytmy planowania ścieżki

zostało rozszerzone o cechy globalnych metod planowania ruchu (Global
Nearness Diagram GND). Rozszerzenie to jest analogiczne jak w przy-
padku globalnego podejścia w metodzie dynamicznych okien.

3. Algorytm CVM- Do grupy podejść bazujących na wyznaczaniu prędkości

zalicza się także metodę tzw. krzywizn i prędkości (Curvature Velocity
Method (CVM)). Zakłada się tutaj podobnie jak w technikach okna dy-
namicznego, że robot porusza się tylko po łukach okręgów o krzywiznach
c = wv . W podejściu tym możliwe jest uwzględnienie ograniczeń na
dopuszczalne prędkości i przyspieszenia. Dokładniejszy opis tych metod
znajduje się w rozdziale

0.1.2. Globalne metody planowania ruchu

Środowisko, w którym poruszają się roboty, może być modelowane w po-

staci map m. in. geometrycznych bądź topologicznych. Pierwszym krokiem
jakiegokolwiek algorytmu planowania ruchu jest odwzorowanie tego środo-
wiska w mapę odpowiednią dla wybranego algorytmu. Planery ruchu różnią
się pod względem tworzenia tej mapy. Można rozróżnić trzy główne strategie
tworzenia map: 1. mapy drogowe (z ang. road map) w efekcie otrzymujemy
opis otoczenia w postaci grafu określającego sieć możliwych ścieżek, czyli
mamy dyskretną przestrzeń stanu, 2. dekompozycja (podział) komórkowy
(z ang. cell decomposition) dzielimy przestrzeń roboczą na komórki, otrzy-
mujemy dyskretną przestrzeń stanu, 3. sztuczne pola potencjałowe (z ang.
artificial potential field) poprzez określenie funkcji matematycznej nad prze-
strzenią roboczą, otrzymujemy ciągłą przestrzeń stanu

Mapy Drogowe

W metodzie tej łączone są ze sobą wolne obszary wokół robota za po-

mocą krzywych bądź prostych, zwanych drogami. W efekcie otrzymujemy
opis otoczenia w postaci grafu określającego sieć możliwych ścieżek. W mo-
mencie, gdy ten graf zostanie skonstruowany, zostanie wykorzystany jako sieć
dróg (ścieżek) pomiędzy obszarami, w których robot może się poruszać. W
ten sposób planowanie ruchu robota mobilnego ogranicza się do dołączenia
punktu początkowego i końcowego do powstałej wcześniej sieci dróg, a na-
stępnie znalezienie odpowiedniej ścieżki pomiędzy wspomnianymi punktami.
Opis przestrzeni roboczej robota za pomocą map drogowych zależy od geo-
metrii przeszkód. Trudnością (lub wyzwaniem) w tym podejściu jest taka
konstrukcja zbioru dróg, aby robot poruszając się po nich mógł dostać się
do któregokolwiek miejsca w jego wolnej przestrzeni roboczej, minimalizując
przy tym liczbę wszystkich dróg w całym zbiorze. Poniżej przedstawiono dwa
algorytmy bazujące na metodzie map drogowych, tj. graf widoczności oraz
diagram Woronoia.

— Graf widoczności- Graf widoczności dla przestrzeni konfiguracyjnej C

zawiera krawędzie powstałe z połączenia wszystkich par wierzchołków
nawzajem widocznych (włączając w to punkt startowy jak i docelowy
jako wierzchołki). Linie proste (drogi) łączące te węzły stanowią najkrót-
sze odległości między nimi. Zadaniem planera jest znalezienie najkrótszej
ścieżki przejścia z punktu początkowego do docelowego wzdłuż wyznaczo-

0.1. Wiadomości wprowadzające

5

nych dróg za pomocą grafu widoczności (rysunek 2.1). Algorytm ten jest
powszechnie stosowany, ponieważ jego implementacja jest niezwykle pro-
sta. Wystarczy aby reprezentacja środowiska opisywała wszystkie obiekty
w nim znajdujące się jako wieloboki (wielościany). Jednakże algorytm
ten ma dwie poważne wady: 1. Liczba krawędzi i węzłów rośnie wraz ze
wzrostem liczby wieloboków (wielościanów) opisujących przeszkody. Za-
tem metoda jest bardzo szybka i wydajna w rzadkich (z niewielką liczbę
przeszkód) środowiskach, jednak może być bardzo wolna i niewydajna,
w porównaniu do innych metod, w środowisku o dużej liczbie przeszkód.
2. Znaleziona ścieżka ruchu może stykać się z przeszkodami (zwykle w
wierzchołkach lecz niekiedy także wzdłuż krawędzi). Można temu zapo-
biec przez poszerzenie przeszkód o promień okręgu opisanego na robocie.

— Diagram Woronoia- Porównując z grafem widoczności, metoda diagramu

Woronoia służy do planowanie skrajnie bezpiecznych ścieżek. W podejściu
tym jest maksymalizowana odległość pomiędzy robotem a przeszkodami
na mapie. Na mapie środowiska nanosi się krzywe równoodległe od prze-
szkód (rysunek 2.2). Kształt krzywych zależy od metryki przyjętej do
wyznaczania odległości. Na przecięciach krzywych są węzły tworzonego
grafu. Dodatkowe węzły to punkt początkowy i docelowy oraz dwa wę-
zły w grafie położone w miejscach najbliższych od wierzchołka począt-
kowego i docelowego. /Lukom grafu przypisywane są wagi równe długo-
ściom krzywej między węzłami (odległość ta jest zazwyczaj większa od
odległości euklidesowej między węzłami). Jeśli przeszkody w przestrzeni
konfiguracyjnej są wielobokami, to diagram Woronoia składa się jedynie
z odcinków prostych (metryka L1) lub odcinków prostych i fragmentów
parabol (metryka L2). Algorytm, który szuka najkrótszej ścieżki w diagra-
mie Woronoia jest taki sam jak w przypadku grafu widoczności, ponieważ
istnienie ścieżki w wolnym obszarze (graf widoczności) implikuje istnie-
nie takiej na diagramie Woronoia (obie metody są zupełne). Jednakże
ścieżka wyznaczona za pomocą tego algorytmu jest daleka od optymal-
nej (jeśli kryterium stanowi długość ścieżki). Algorytm ten ma istotną
słabość w przypadku robotów, w których stosuje się tylko czujniki odle-
głości krótkiego zasięgu. Ponieważ algorytm ten maksymalizuje dystans
pomiędzy robotem a obiektami, każdy czujnik krótkiego zasięgu na tym
robocie może pracować na granicy poprawności odczytów.W takim przy-
padku może wystąpić trudność w wyznaczeniu poprawnej ścieżki ruchu,
ponieważ przeszkody mogą znajdować się poza zasięgiem tych czujników
i niemożliwa będzie maksymalizacja odległości od nich (przeszkód).

Podział na komórki, dekompozycja komórkowa (cell
decomposition)

Idea kryjąca się za dekompozycją komórkową to podział obszaru na ko-

mórki wolne i zajęte przez przeszkody. Podstawowy algorytm planowaniu ru-
chu opierający się na dekompozycji komórek można opisać w następujący spo-
sób: Podziel obszar na proste, spójne obszary zwane komórkami. Określ, które
puste komórki są sąsiadujące i skonstruuj graf spójności między nimi. Znajdź
komórki zawierające punkt startowy oraz docelowy, a następnie znajdź połą-
czenie między nimi w grafie spójności. Wyznacz ścieżkę przechodzącą przez

6

Ćwiczenie 2: Podstawowe algorytmy planowania ścieżki

każdą komórkę w znalezionym połączeniu (np. przechodzącą przez środek
każdej komórki). W metodzie tej ważne jest położenie krawędzi pomiędzy
komórkami. Jeżeli granice te wynikają ze struktury środowiska, wtedy de-
kompozycja ta jest bezstratna i określana mianem dokładnego podziału na
komórki (z ang. exact cell decomposition). Jeśli jednak granice te nie zależą
od struktury środowiska, metodę tę nazywa się przybliżonym podziałem na
komórki (z ang. approximate cell decomposition).

— Dokładny podział na komórki (exact cell decomposition)- Rysunek 2.3

przedstawia dokładny podział na komórki, w przypadku gdy granice zo-
stały wyznaczone za pomocą trapezoidalnego podziału. W podziale tym
trzeba wyznaczyć nie przecinające się odcinki przez poprowadzenie przez
wszystkie wierzchołki przeszkód pionowych linii prostych. Linie prowa-
dzone są do pierwszej przeszkody. Na powstałych odcinkach (oczywiście
trzeba wyeliminować wszystkie te, które znajdują się w przestrzeni za-
bronionej) zaznaczamy punkty dzielące je na dwie równe części. Wyzna-
czamy również środki powstałych w ten sposób trapezów. Środki odcin-
ków i środki trapezów będą punktami składowymi powstałej mapy, na
której rozpina się graf (w przestrzeni dozwolonej) zawierający bezkoli-
zyjną ścieżkę robota. Do wyznaczenia granic pomiędzy komórkami można
zastosować także inne metody. Idea: podziel obszar F na zbiór K rozdziel-
nych komórek, których suma (w sensie mnogosciowym) dokładnie odwzo-
ruje obszar F . Własności komórek: Geometria komórek powinna być na
tyle prosta, aby w łatwy sposób można było wyznaczyć ścieżkę pomiędzy
dwoma dowolnymi komórkami. Powinno się dać łatwo sprawdzić, czy do-
wolne dwie komórki mają wspólną krawędź (bok). Powinno się dać łatwo
znaleźć fizyczną ścieżkę przechodzącą przez granicę dzielącą dwie sąsia-
dujące komórki. Komórki, które otrzymamy stosując powyższe zasady są
albo puste, albo zajęte. Zatem znalezienie ścieżki z punktu początkowego
do punktu docelowego, tak jak w przypadku algorytmów opierających
się na mapach drogowych, jest niczym innym jak znalezieniem ścieżki w
grafie. Kolejną wadą tego algorytmu (jak i w wielu innych) jest fakt, że
efektywność planowania ruchu zależy od gęstości (liczba) oraz złożoności
obiektów w środowisku, tak jak w przypadku algorytmów opierających
się na mapach drogowych. Zaleta w przypadku tego algorytmu polega
na tym samym co wada: w niezwykle rzadkim otoczeniu liczba komórek
będzie bardzo mała, niezależnie od geometrycznej wielkości środowiska.
W rzeczywistości, z powodu złożoności implementacji, dokładny podział
na komórki stosuje się stosunkowo rzadko w robotach mobilnych.

— Przybliżony podział na komórki (approximate cell decomposition)- W

przeciwieństwie do dokładnej dekompozycji komórkowej przybliżony po-
dział ma komórki jest jedną najczęściej stosowanych technik w zagad-
nieniu planowania ruchu robotów mobilnych. Częściowo dzieje się tak, z
powodu popularności reprezentacji środowiska w postaci siatki zajętości.
Komórki tej siatki mogą mieć stałą bądź zmienną szerokość. Idea: podziel
obszar F na zbiór K rozdzielnych się komórek, których suma (w sensie
mnogościowym) w przybliżony sposób odwzoruje obszar F , ponieważ
komórki częściowo zajęte są traktowane jako zajęte. Własności komórek:

0.1. Wiadomości wprowadzające

7

Komórki powinny mieć prosty kształt (np. kwadrat, sześciokąt foremny),
tak aby łatwo można było dokonać dekompozycji (inaczej niż w dokład-
nej dekompozycji komórek) oraz łatwo można było wyznaczyć ścieżkę
pomiędzy dwoma dowolnymi komórkami (tak samo jak dla dokładnej
dekompozycji komórek). Powinno się dać łatwo sprawdzić, czy dowolne
dwie komórki mają wspólną krawędź (tak samo jak dla dokładnej dekom-
pozycji komórek). Powinno się dać łatwo znaleźć fizyczną ścieżkę przecho-
dzącą przez granicę współdzieloną przez dwie sąsiadujące komórki (tak
samo jak dla dokładnej dekompozycji komórek). Na rysunku 2.4 pokazano
przykładowy podział na komórki o stałej szerokości. Szerokość komórek
może zależeć od kształtu i rozmiarów przeszkód, jednak jest stała dla
całej siatki zajętości. Na rysunku 2.5 pokazano natomiast przykładowy
podział na komórki o zmiennej szerokości. Zaletą podziału na komórki o
stałej szerokości jest stosunkowo mała złożoność obliczeniowa planowania
ścieżki (wykorzystując np.: algorytmy propagacji fali NF1, BFS, DFS czy
algorytm Dijkstry lub A ) oczywiście zależy od rozmiarów mapy. Jest to
algorytm pamięciochłonny. Dla dużych środowisk (nawet rzadkich) siatka
zajętości musi być reprezentowana w całości. W rzeczywistości, w związku
ze spadającymi cenami pamięci operacyjnej, ta niedogodność została w
ostatnich latach złagodzona.

Sztuczne pole potencjałowe

Metoda sztucznego pola potencjałowego tworzy pole, które kieruje robota

do celu poprzez wiele pośrednich pozycji. To podejście oryginalnie zostało za-
adaptowane w celu planowania ruchu manipulatorów, ale jest często używane
w, wielu odmianach, dla robotów mobilnych.

Podstawową ideą we wszystkich metodach opierających się na zasadzie

sztucznego pola potencjałowego, jest to, że robot jest przyciągany do celu,
w tym samym czasie będąc odpychanym od przeszkód. W przypadku poja-
wienia się nowej przeszkody wystarczy zaktualizować pole sztucznego poten-
cjału. W metodzie sztucznego pola potencjałowego traktuje się robota jako
punkt materialny poruszający się pod wpływem sztucznego pola potencjało-
wego U(q). Robot porusza się w polu sztucznych sił, tak jakby piłka staczała
się z góry. Cel (minimum globalne pola w całej przestrzeni) działa jako siła
przyciągająca robota, natomiast przeszkody (jako siła odpychająca). Super-
pozycja wszystkich sił oddziałuje na robota, który w większości przypadków
jest reprezentowany jako punkt w przestrzeni konfiguracyjnej. Takie sztuczne
pole potencjałowe gładko prowadzi robota do celu, jednocześnie zapewniając
mu bezpieczeństwo (unikanie przeszkód). Podstawowym problemem jest uni-
kanie lokalnych minimów sztucznego pola potencjałowego. Wypadkowa siła
może mieć wartoćć zero poza punktem docelowym. W najprostszym przy-
padku, robot jest punktem, jego orientacja Q jest zaniedbywana, a wynikowe
pole potencjałowe jest dwuwymiarowe (x, y). Mając różniczkowalną funkcję
U (q) sztucznego pola potencjałowego, możemy wyznaczyć sztuczną siłę dzia-
łająca w pozycji q = (x, y) Sztuczne pole potencjałowe (rysunek 2.6) U(q)
jest sumą pól: przyciągającego i odpychającego: U (q) = U att(q) + U rep(q).
Podobnie można rozdzielić się na część przyciągającą i odpychająca.

8

Ćwiczenie 2: Podstawowe algorytmy planowania ścieżki

0.1.3. Lokalne i globalne planowanie ścieżki

0.2. Zadania do wykonania

Zadanie 1- Uruchomienia symulatora Stage. Algorytm
probabilistycznych map drogowych

Aby rozpocząć pracę należy otworzyć okno terminala (Ctrl+Alt+T) i uru-

chomić środowisko poleceniem roscore. Następnie otwieramy nową zakładkę
terminala (Ctrl+Shift+T).
Na początu należy skonfigurować środowisko symulacyjne.
Należy przemieścić się do wskazanego katalogu lab_cw1/stage_lab/bitmaps.
W symulacji zakłada się znaną mapę otoczenia. Należy uruchomić serwer
mapy odnosząc się do pliku .yaml

rosrun map_server map_server map.yaml

Następnie należy zmodyfikować plik .world odpowiedzialny za wygląd

świata symulacji. Otwieramy nową zakładkę terminala i wpisujemy:

cd ..

gedit lab.world

W pliku lab.world należy odkomentować linię kodu, odpowiedzialną za

powstanie nowego robota (przez usunięcie w ostatnich liniach pliku). Na-
stępnie plik zapisać i uruchomić symulator stage:

rosrun stage stageros lab.world

Powinno otworzyć się nowe okno “Stage: lab.world”. W oknie tym możliwe

jest przesuwanie robotów za pomocą kursora, obracanie oraz przesuwanie
całej mapy. Po przyciśnięciu klawisza “D” widoczny jest obszar działania
skanera laserowego.

Można zauważyć, że robot_0 porusza się samodzielnie, próbując omijać

przeszkody. Spowodowane jest to wywołaniem prostego skryptu ctrl “wan-
der” (w pliku konfiguracyjnym lab.world).

Kolejnym etapem jest podgląd danych pochodzących ze środowiska sy-

mulacyjnego. W tym celu w nowym oknie terminala należy wpisać:

rosrun rviz rviz

Uruchomi się nowy program wizualizacyjny. W oknie programu, z lewej

strony na dole należy dodać pozycję LaserScan i wybrać jej temat (topic)
np. /robot_0/base_scan. W oknie wizualiacji powinien pojawić się obraz
wykrytych przeszkód. Przesuwając robot w symulacji, skan laserowy powi-
nien zmieniać się płynnie w oknie rviz.

Planowanie ścieżki ruchu robota z wykorzystaniem probabilistycznych

map drogowych.

0.3. Sprawozdanie

9

Zadanie 2- Algorytm sztucznych pól potencjałowych

Planowanie ścieżki ruchu robota z wykorzystaniem algorytmu sztucznych

pól potencjałowych.

Zadanie 3- Algorytm DWA

Planowanie ścieżki ruchu robota z wykorzystaniem algorytmu DWA.

Zadanie 4- Algorytm CVM

Planowanie ścieżki ruchu robota z wykorzystaniem algorytmu CVM.

Zadanie 5- Algorytm Dekompozycji komórek

Planowanie ścieżki ruchu robota z wykorzystaniem algorytmu dekompo-

zycji komórek.

0.3. Sprawozdanie

Sprawozdanie (jedno na zespół pracujący przy stanowisku) powinno za-

wierać:

— Krótki opis etapów uruchomienia symulacji w ROS (x pkt)
— Porównanie wykorzystanych algorytmów do planowania ścieżki robota i

uzyskanej mapy (x pkt)

— Spostrzeżenia dotyczące błędów powstających podczas planowania ścieżki

(x pkt)

0.4. Zalecana literatura

— Lit. Nawigacja robotów robotów mobilnych (Skrypt BS)
— Reprezentacja otoczenia robota mobilnego (Skrypt BS)
— Uniwersalna metoda planowania ścieżki w oparciu o robota mobilnego

(Rozprawa hab BS)