75131 P1080265

6. Programowana robotom przem>skjwych

W metodach globalnych zakłada się znajomość rozkładu wszystkich przeszkód przed przystąpieniem do planowania. Zaletą metod globalnych jest (możliwa) optymałność. jej ceną jest zwielokrotnienie nakładów obliczeniowych i mała odporność na zmiany warunków początkowych zadania, np. w wynika nieoczekiwanego pojawienia się przeszkód ruchomych. Ze względu na dużą czasochłonność metody globalne są stosowane w e wstępnym planowaniu ruchu.

Metody lokalne zapewniają głównie bezkolizyjność ruchu z ewentualną optymalizacją lokalnej jakości ruchu. Zaletą metod lokalnych jest bardzo szybkie planowanie radiu, nawet w trybie czasu rzeczywistego, a wiedza o przeszkodach może być ograniczona do bezpośredniego otoczenia robota. Zalicza sie do nich metod>^r:

-    pól potencjałowych.

-    elastycznej wstęgi.

Wyróżnia się również planowanie ruchu inspirowane biologicznie, wśród nich metodę ewolucyjną i wykorzystującą kolonie mrów ek jako medium poszukiwań. Godna uwagi jest również metoda symulowanego odprężenia, niemająca samodzielnego znaczenia, jednak nadająca się do wykorzystywania w wielu metodach planow^rania jako sposób opuszczania minimów lokalnych.

Jeżeli otoczenie robota jest stale i nie zmienia się, to stosuje się metody globalne do realizacji procesu planow ania ruchu. Gdy obszar roboczy' zmienia się w czasie rzeczywistym, np. ruchome przeszkody, wówczas istnieje konieczność stosowania metod lokalnych.

6.5.1. Metoda propagacji fali

W metodzie propagacji fali zakłada się, że robot mobilny porusza się na płaszczyźnie w dowolnym kierunku z jednakową łatwością, a więc jest holonomiczny. Dwuwymiarową przestrzeń konfiguracyjną robota dzieli się na elementarne komórki, zwykle tworzące jednorodną siatkę, przy czym każdej komórce przypisuje się znacznik waz wagę. Zajętym przez przeszkody elementom siatki przypisuje się wagę o wartości —1. W danym obszarze przestrzeni konfiguracyjnej zakłada się. że jest on spójny i ma skończoną liczbę komórek.

Algorytm implementujący metodę propagacji fali przebiega w dwóch fazach. W pierwszej następuje zapełnienie wagami wszystkich komórek wolnych i zajętych. Waga 0 jest przypisana komórce początkowej. Jeżeli sąsiednie komórki nie są zajęte, to im zostaje przypisana waga 1, a ich sąsiadom waga 2 itd.

W pierwszej fazie zostaje wygenerowana fala rozchodzącą się w przestrzeni konfiguracyjnej, a jej algorytm wygląda następująco — rys. 6.8:

Krok 1. Zadanej komórce początkowej nadać wagę 0 i ustalić wartość poszukiwanej wagi i - 0.

Krok 2. Przeglądając jednokrotnie wszystkie komórki przestrzeni konfiguracyjnej, wykryć te o wadze równej /.

• 3 Jeśli nie znaleziono komórek o takiej wadze. wykonuje się kolejny V¹ ‘ krok.

^4. Każdemu z sąsiadów znalezionej komórki, którego waga me została ^ uprzednio zdeterminowana przez nadanie statusu zajętej lub przypisanie wagi nieujemnej. nadaje się wagę i + 1. i- 5. Po przejrzeniu wszystkich komórek o wadze / zwiększyć wartość : o 1. ^ kontynuować od kroku 2.

rrr	-i	-1	-1	-1	1	-1	-1	-1	-1	-1;	-1	-1 -1 -1 -1	-1 -1	aĄ
|-i 4	4	4	4	4	4	5	6	7	8	3	1011 11 12 13		4 15	16-1
ft3	3	3	3	3	rt-						10	10 11 12 13	-^1 -1
i-i 2	2	2	2	2	i	-1	-i	-1	A	r	9	10 11 12 13	-1 -1	18-|
1-1 2	1	1 ;	1	2	t	-V	-1	7	7	8	9	10 1l(ji)l3	-15-1	1S-1
1-1 2	1	rsr	1		1	-1		_ |	i			h1 11 12 13	r. ; ,
				2			-1	o		-i.			“li -1
1-1 2	1	1:	1	2	3	4	5	6	7	-1	-1	-1 1212 13	-1 -1	^17r
I-1S2	2	2	2	2	3	4	5	6	7		Ld	-1 11 12 13		^16 E
I-i 3								6	7	8	9	10 11 12 13	14 15	16 -i
r^4	4	. 4	5	6	7	8	7	7	7	8	9	10 11 12 13	1415	16-1
Łl-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1 -1 -1 -1	-1 -1	-J

tłSBBCfc    _

Ilustracja działania algorytmu generującego falę rozchodzącą się w przestrzeni koefiasa-cjjnej

P?	-l|-1 -1 -1|	-^1| -lj	-1	-1	-1	J	-1	-1 -1 -1 -1	-1 -1	-1-1
-1 4	4 4 4 4 |	4 | 5	6	7	8	9 i-	I0 11 11 12 13 14 15			*£--1
-1 3	3 j 3 i 3 3 |	r^1r-^1	—1-	-1-			10 10 11 12 13		pT-1	17-1
-12	2 j 2 2 2	1 -ii	pL		-i-	i	9	10 11 12 13	-1 -1	18-i
-1 ^2	1 j 1 11 2	i|-t|	-1	7	7		-9-	10-44^2)13	-1! -1	19-i
I ^12	1 (eH.2	-i|-i	-1	6	7		~=%	-1 11 12 13	-1 -1	18-t
-ii 2	1 1 i 1>	[■3’|' 4			7	-it	--i	-1 12 12 13	-li -1	17-i
-r 2	2 | 2 j 2 2	3 4	5	6	7	m£		-1 1112 13	-1 -l	16-1
-13				6	7	8	9	10 11 12 13	14 15	•6-1
-1 4	4 4 5 6	7 8	i 7	7	7	8 |	9	10 11 12 13 14 15		16-1
i a-i -i -i -i -i 89$^		| -1 j -1	pf	-1	-1	-11	-1	-1 -1 -1 -1	-1 -1	-r|

**■²6.9

Wykład propagacji wstecznej wyznaczania tras>' od punktu celu do punktu stanu

1

   ” drugiej fazie algorytmu stosuje się propagację wsteczną, tzn. wyznacza

2

^0<1 P¹¹¹³^¹¹ celu do punktu startu. W przy kładzie pokazanym na rys. 6.9 _Q ^y^nanęj komórki celu o wadze 12 wyznacza się drogę optymalną do komorki ^Wadze równej 0, czyli inicjującej działanie pierwszej fazy. Droga jest wyzna-