Zezwala się na korzystanie z artykułu na warunkach licencji Creative Commons Uznanie autorstwa 3.0

Artykuł recenzowany nadesłany 09.12.2014 r., przyjęty do druku 08.04.2015 r.

DOI: 10.14313/PAR_216/57

Zmodyfikowana metoda pól potencjałowych do wyznaczania drogi robota mobilnego

Przemysław Oborski, Tomasz Fedorczyk

Politechnika Warszawska, Wydział Inżynierii Produkcji, ul. Narbutta 85, 02-524 Warszawa, Gmach Nowy Technologiczny

Streszczenie: Możliwość wykorzystania robotów mobilnych w przemyśle jest w dużej mierze zależna od zastosowania efektywnych systemów sterowania. Powinny one pozwalać na autonomiczne, bezpieczne i szybkie osiąganie planowanych punktów drogi. Jednym z podstawowych problemów jest wybór odpowiednich algorytmów doboru i optymalizacji ścieżki ruchu. Ich zadaniem jest bieżące wyliczanie przebiegu drogi, omijającej przeszkody, optymalnie prowadzącej robota do postawionego, często zmieniającego się celu. Istotnym problemem w wyznaczaniu ścieżki robota mobilnego jest złożoność optymalizacji. W podejściu globalnym istnieje możliwość optymalizacji całej ścieżki, jednak wymagana jest znajomość wszystkich przeszkód przed przystąpieniem do obliczeń. Uniemożliwia to bieżące reagowanie na ich zmiany. Wadą jest także wymagana duża moc obliczeniowa. Podejście lokalne pozwala na dynamiczne reagowanie na zmieniające się przeszkody i cele. Wyznaczanie drogi można zawęzić do ograniczonego obszaru wokół robota, co znacznie zmniejsza wymagania w zakresie przetwarzania danych. Wadą jednak jest brak możliwości globalnej optymalizacji. W  artykule przedstawiono wyniki badań symulacyjnych metody lokalnego planowania ścieżki robota w oparciu o wyliczanie pól potencjałowych. Opracowano uniwersalny algorytm wykorzystujący zmodyfikowaną metodę pól potencjałowych oraz zbudowano aplikację pozwalającą na wykonywanie badań symulacyjnych w oparciu o mapy otoczenia. Przy wykorzystaniu opracowanej aplikacji przeprowadzono badania symulacyjne zachowania się robotów mobilnych sterowanych różnymi algorytmami oraz poruszających się w różnych środowiskach.

Słowa kluczowe: roboty mobilne, planowanie ścieżki, algorytmy sterowania, sterowanie nadrzędne, badania symulacyjne

1. Wprowadzenie

Możliwości współczesnych robotów mobilnych decydują o ich coraz powszechniejszym wykorzystaniu w różnych obszarach. W szczególności interesujące jest zastosowanie robotów mobilnych w systemach produkcyjnych, w których mogą realizować funkcje transportowe, w obszarze dostaw materiałów, narzędzi i przyrządów na stanowiska robocze. Może pozwolić to istotnie ograniczyć koszty działania systemu [1]. Roboty mobilne mogą stanowić również sterowane wieloagentowo platformy transportowe przemieszczające montowane wyroby w liniach montażowych [2]. Jednym z kluczowych problemów jest zastosowanie odpowiednich efektywnych i bezpiecznych algorytmów sterowania bazujących na metodach planowania ścieżki [3]. W zależności od sposobu analizy dostępnej informacji o środowisku wokół robota, w czasie planowania trajektorii ruchu można wyróżnić trzy generalne metody planowania drogi [4].

Metody globalne – przed przystąpieniem do planowania system posiada informacje o rozkładzie wszystkich przeszkód. Umożliwia to określenie optymalnej drogi. Metody globalne wymagają większej mocy obliczeniowej, co może stanowić problem przy budowie robota mobilnego. Najczęściej zanim polecenie wykonania ruchu trafi do robota wstępnie obliczana jest cała ścieżka, która może być poddawana wielokryterialnej optymalizacji [5]. Istotną wadą tego typu metod jest mała odporność na zmianę warunków początkowych zadania, na przykład dynamicznie zmieniające się przeszkody, lub praca kilku robotów w tej samej przestrzeni. Wynika ona z nieuwzględniania dynamicznie pojawiających się przeszkód, co może skutkować występowaniem kolizji. Badania prowadzone są także nad zastosowaniem algorytmów sztucznej inteligencji umożliwiających optymalizację i reagowanie na zmiany otoczenia w trakcie ruchu [6]. Przykładami metod globalnych są metody:

– propagacji fali,

– diagramów Woronoja,

– grafu widoczności,

– algorytmy sztucznej inteligencji: genetyczne, sieci neuronowe, itd.

Metody lokalne – robot ma określone pole widzenia, na podstawie analizy którego może obliczyć zgodnie z odpowiednim algorytmem kolejny ruch. Zaletą metod lokalnych jest planowanie ruchu w czasie rzeczywistym. Umożliwia to bieżące uwzględnianie obiektów dynamicznie pojawiających się i zmieniających się w przestrzeni roboczej [7]. Metody te nie pozwalają na przeprowadzanie optymalizacji globalnych, jednak umożliwiają bezkolizyjne reagowanie na dynamiczne zmiany przestrzeni roboczej [8]. Ma to szczególne znaczenie w systemach produkcyjnych. Istotnym obszarem badań nad rozwojem metod lokalnych jest problem wygładzania obliczanej ścieżki [9]. Przykładami metod lokalnych są metody [10]:

– elastycznej wstęgi,

– pól potencjałowych,

– rodzina algorytmów bug.

Metody mieszane – robot wylicza wstępną ścieżkę prowadzącą do celu przy wykorzystaniu algorytmu globalnego, następnie na bieżąco dokonuje analizy lokalnej, której celem jest wykrycie dynamicznie zmieniających się przeszkód, w tym innych robotów. Przykładem tego typu metod może być algorytm sterowania robotem Boss zwycięzcą zawodów Urban Challenge w 2007 r. [11].

Algorytmy wyznaczania drogi bazujące na metodach globalnych stosowane są w przypadkach, gdy środowisko robocze, w którym porusza się robot jest stałe oraz istotne jest wyliczenie optymalnej ścieżki. Natomiast metody lokalne, wykorzystywane są w sytuacjach gdy występuje dynamiczna zmiana środowiska pracy. Rozwiązaniem eliminującym wady obydwu metod i jednocześnie łączącym ich zalety jest stosowanie algorytmów mieszanych. Wymagają one jednak budowy skomplikowanego wielomodułowego oprogramowania bazującego na szczegółowych rozwiązaniach algorytmów planowania dostosowanych do konkretnych przypadków sterowania [12]. Do ich rozwoju przyczyniły się zawody DARPA grand i urban challenge [13] oraz badania nad rozwojem autonomicznych samochodów Google’a [14].

2. Metoda pól potencjałowych

Metoda sztucznych pól potencjałowych (ang. Artificial Potential Fields) została wybrana do badań z uwagi na niskie wymagania obliczeniowe, mające istotne znaczenie przy budowie niewielkich robotów mobilnych [8]. Metoda pól potencjałowych określa przestrzeń stanu nad przestrzenią roboczą, a następnie kieruje robota przez wiele pośrednich pozycji, aż do miejsca docelowego (o ile jest ono dostępne dla robota) [15]. Jest to metoda lokalna, gdyż prowadzenie obiektu odbywa się na zasadzie poszukiwania odpowiedniego antygradientu przestrzeni stanu jedynie w najbliższym otoczeniu robota [4]. Metoda pół potencjałowych opiera się na założeniu, że ruch robota jest wypadkową działających na niego sił. Opiera się ona na dwóch rodzajach sił: siłach pochodzących od przeszkód i siłach pochodzących od celu. Pierwsze odpychają robota, powinny one mieć niewielką wartość, gdy robot jest z dala od przeszkody, a rosnąć praktycznie do nieskończoności przy przeszkodzie. Natomiast siły pochodzące od celu przyciągają robota do punktu końcowego [16]. W każdym punkcie przestrzeni ruchu wypadkowa siła wyznacza chwilowy kierunek przemieszczania się robota o małą, stałą odległość. Najważniejszym problemem metody pól potencjałowych jest możliwość wystąpienia minimów lokalnych pola potencjału. Każde minimum posiada wokół siebie pewien obszar, którego jest atraktorem. Jeśli robot wejdzie w obszar atrakcji minimum lokalnego, to niechybnie je osiągnie. W punkcie minimum lokalnego niemożliwe jest wyznaczenie kolejnego kierunku ruchu robota. Literatura podaje kilka sposobów rozwiązania lub ograniczenia problemu minimum lokalnego [17]. Polegają one na takim konstruowaniu funkcji pola potencjałowego, aby wynikowe pole nie posiadało minimów lokalnych, opracowaniu scenariuszy ruchu w sytuacjach, gdy robot utknie w minimum lokalnym, czy też narzucaniu robotowi ruchu wzdłuż przeszkody, aż do uzyskania pewności, że ją ominięto. Można również wykorzystać inne metody ucieczki z obszaru minimum lokalnego między innymi wykorzystujące technikę błądzenia losowego lub algorytm symulowanego odprężania polegający na rozpatrywaniu rozwiązań gorszych od optymalnego [18]. W wykonanych badaniach zastosowano własne oryginale rozwiązanie polegające na zwiększaniu potencjału pól, w których robot już był.

2.1. Podstawy fizyczne

Metoda pól potencjałowych opiera się na znanej w przyrodzie zasadzie naturalnego oddziaływania elektrostatycznego ładunków elektrycznych. Zachowanie to zostało opisane w 1785 r. przez Charlesa Coulomba. Zgodnie z nim, siła oddziaływania dwóch ładunków punktowych jest wprost proporcjonalna do wartości bezwzględnej wielkości ładunku każdego z nich oraz odwrotnie proporcjonalna do kwadratu odległości między nimi [18]. Wartość siły oddziaływania jest również zależna od ośrodka, w którym znajdują się ładunki. Zostało to opisane wzorem:

(1)

gdzie: F – siła oddziaływania dwóch ładunków punktowych,

q1 – wartość pierwszego ładunku, q2 – wartość drugiego ładunku,

r – odległość między ładunkami, k – współczynnik proporcjonalności, opisany jako:

(2)

gdzie: e – przenikalność elektryczna ośrodka.

Kierunek działania wektora siły jest zgodny z prostą przechodzącą przez obydwa ładunki, natomiast zwrot zależy od ich znaków. Jeżeli są jednoimienne, następuje ich wzajemne odpychanie, dla ładunków różnoimiennych następuje przyciąganie [19]. Ładunki elektryczne wytwarzają wokół siebie pole elektryczne, którego natężenie wyraża się przez:

(3)

gdzie: E – natężenie pola elektrycznego, Q – ładunek punktowy, r – odległość od ładunku Q, k – współczynnik proporcjonalności opisany powyżej.

Metoda pól potencjałowych jest superpozycją działających na robota sił, które pochodzą od przeszkód oraz punktu docelowego. Te od przeszkód odpychają go, a ich wartość rośnie wraz ze zbliżaniem się do przeszkody, aż do nieskończoności na jej polu. Siły pochodzące od punktu docelowego przyciągają robota. W związku z tym można zauważyć, że ładunki robota oraz przeszkody są jednoimienne, natomiast robota i punktu docelowego różnoimienne. Wartości potencjału na obszarze roboczym można traktować jako siatkę wysokości terenu. Wtedy robot może być traktowany jak kula, która toczy się po pochyłościach, zdążająca do najniższego punktu na siatce, w którym przestanie się poruszać.

2.2. Implementacja zmodyfikowanej metody

W ramach badania opracowano własną metodę planowania trajektorii ruchu robota bazującą na zmodyfikowanej metodzie pól potencjałowych. Przy implementacji metody jedną z najważniejszych rzeczy jest ustalenie zależności pomiędzy wzajemnymi oddziaływaniami obiektów w otoczeniu za pomocą równań bazujących na wzorach omówionych w punkcie 2.1. Zostały opracowane następujące zależności:

– potencjał rozpatrywanego dowolnego punktu w funkcji odległości od punktu docelowego:

(4)

– potencjał rozpatrywanego dowolnego punktu w funkcji odległości od przeszkody:

(5)

gdzie: E – potencjał punktu rozpatrywanego, kd – wzmocnienie oddziaływania punktu docelowego, kp – wzmocnienie oddziaływania przeszkody, dp – odległość pomiędzy punktem rozpatrywanym i przeszkodą, d – odległość pomiędzy punktem rozpatrywanym, a punktem docelowym, opisane dla punktów A i B w dwuwymiarowym układzie współrzędnych (x, y) jako:

(6)

Obliczenie superpozycji oddziaływań polega na dodaniu do siebie potencjału obiektów, które znajdują się w zasięgu oddziaływania na wybrany punkt.

Fizyczna implementacja metody wymaga uwzględnienia sposobu pozyskiwania informacji z otoczenia. W docelowym rozwiązaniu wiedza na temat otoczenia będzie uzyskiwana za pomocą czujników indukcyjnych lub optycznych umieszczonych na robocie mierzących odległość dp. Do celów badań w zbudowanej aplikacji symulacyjnej odległość dp wyliczana jest tak samo jak odległość d. W rzeczywistym układzie sterowania dodatkowo będzie musiał być uwzględniony kąt widzenia czujnika i czułość.

2.3. Algorytm planowania ścieżki

W implementacji algorytmu w aplikacji symulacyjnej do reprezentacji opisu otoczenia zostało zastosowane podejście rastrowe, wzorowane na rozwiązaniach stosowanych w grach komputerowych. Polega ono na podziale całej przestrzeni, w której działa robot, na komórki siatki o równych bokach. Każda komórka jednoznacznie określa obiekt jako fragment na niej występujący. Zmiany wielkości pojedynczego rastra decydują o dokładności opisu mapy, wpływają również na efektywność planowania drogi. Im większa gęstość rastrów, tym interpretacja mapy jest dokładniejsza, jednak wymaga większego nakładu obliczeń [4].

Opracowany algorytm, bazujący na interpretacji rastrowej oraz zmodyfikowanej metodzie pól potencjałowych, przebiega następująco:

1. Dla punktu docelowego oblicz jego oddziaływanie na poszczególne rastry według wzoru 4.

2. Dla każdej przeszkody oblicz jej oddziaływanie na sąsiednie rastry, określone przez obszar działania czujnika zgodnie ze wzorem 5.

3. Oblicz superpozycje dodając do siebie wartości rastrów z punktu 1 oraz punktu 2.

Dla tak utworzonej globalnej mapy potencjałów:

– szukaj wokół rastra, określającego aktualne położenie robota, współrzędnych rastra o najmniejszej wartości pola potencjałowego;

– przesuń robota do rastra określonego przez pobrane współrzędne;

– sprawdź, czy współrzędne aktualnego położenia robota są równe współrzędnym punktu docelowego. Jeśli tak zakończ działanie algorytmu, jeśli nie przejdź to podpunktu a).

W niektórych przypadkach przeszkody mogą układać się w półzamknięte przestrzenie stanowiące minimum lokalne. W takim przypadku, podobnie jak w przypadku szerokiej przeszkody, najmniejsza wartość potencjału występuje przed przeszkodą, a wokół tego minimum lokalnego znajdują się wartości większe, związane z oddalaniem się od punktu docelowego. Wówczas robot będzie dążył do tego minimum – sądząc, że jest to minimum globalne. Metoda pól potencjałowych w czystej postaci nie daje możliwości wyjścia robota z takiego położenia. Opracowując algorytm wyznaczania ścieżki odporny na problem minimów lokalnych, analizowano kilka rozwiązań podawanych w literaturze [8, 20, 21]. Jedną z metod jest ominięcie przeszkody poprzez poruszanie się wokół krawędzi przeszkody do czasu uzyskania pewności, że zostanie ona ominięta. Kolejnym sposobem jest tak zwane błądzenie losowe, czyli poruszanie się robota w losowo wybranym kierunku. Można również wyłączyć siłę przyciągania punktu docelowego do czasu, gdy robot oddali się od przeszkody. Jednakże wymienione metody nie zawsze działają efektywnie, przykładem może być ryzyko ponownego wejścia robota w obszar minimum lokalnego. Dodatkowo są skomplikowane z punktu widzenia implementacji, między innymi z powodu nieznajomości geometrii przeszkód [21]. W wyniku badań wybrano rozwiązanie polegające na dodawaniu odpowiednio dobranej stałej wartości pola potencjałowego do aktualnego położenia robota. Wartość stała oznaczana jako ka zapobiega ponownemu wchodzeniu robota na tę samą pozycję. Na potrzeby badania symulacyjnego wprowadzono również współczynnik czułości sensora, został on określony jako ks. W zbudowanym symulatorze jego wartość odzwierciedla liczbę rastrów „widzianych” przez robota. W rzeczywistym urządzeniu będzie to regulowana w zależności od potrzeb czułość czujnika. Przeszkody mogą być zmieniane dynamicznie, wówczas od nowa musi być liczona superpozycja i przekazywana do robota w formie nowej mapy.

3. Środowisko symulacyjne

W ramach badań opracowano środowisko symulacji, w którym można testować różne algorytmy planowania ścieżki robota mobilnego. Można również testować efektywność dobieranych współczynników i różnych rozmieszczeń obiektów wraz z jednoczesną wizualizacją i analizą wyników. Program został wydany na licencji GPL, pozwalającej użytkownikom na jego dowolną modyfikację. Aplikację napisano, wykorzystując język obiektowy C#. Dzięki kompilacji do kodu pośredniego (Common Intermediate Language) wykonywanego w środowisku uruchomieniowym .NET Framework jest on niezależny od platform sprzętowych.

Podstawowym oknem aplikacji pojawiającym się po jej uruchomieniu jest okno główne przedstawione na poniższym rysunku.

Rys. 1. Okno główne systemu symulacyjnego wraz z oznaczeniem podstawowych elementów

Fig. 1. Main window of a simulation system with marked control elements

Okno to służy do sterowania głównymi działaniami aplikacji, umożliwiając realizację następujących działań opisanych poniżej wraz z odniesieniem do ich lokalizacji:

[A] – wczytanie mapy – status,

[B] – tworzenie, wczytywanie i edycja mapy,

[C] – możliwość tworzenia arkuszy kalkulacyjnych w programie Excel opisujących mapę – pole wyboru,

[D] – ustawianie parametrów dla algorytmu wyznaczania drogi bazującego na zmodyfikowanej metodzie pól potencjałowych – umożliwia wpływanie na sterowanie ruchem robota,

[E] – start symulacji – przycisk startu.

Do przeprowadzania eksperymentów tworzy się mapy opisujące środowisko, w którym porusza się robot wraz z przeszkodami, które musi omijać. Po naciśnięciu przycisku „Create map” wyświetla się okno, służące do tworzenia mapy (rys. 2).

Rys. 2. Okno służące do tworzenia mapy środowiska ruchu robota

Fig. 2. A window for creation of a map of mobile robot operating area

Okno to umożliwia wprowadzanie następujących parametrów i działań:

[A] – wprowadzanie parametrów rozmiaru przestrzeni,

[B] – parametry dotyczące rozmiaru rysowanych obiektów: robota oraz przeszkody,

[C] – menu rozwijalne wyboru obiektów do rysowania i ich parametrów,

[D] – przyciski służące odpowiednio do: kasowania ustawień robota, punktu końcowego oraz całej mapy,

[E] – przycisk zapisu mapy,

[F] – pole wyboru tworzenia dodatkowych map, które są odzwierciedleniem zapisywanej mapy w skali określonej przez współczynniki widoczne po zaznaczeniu pola, określające kolejno: maksymalny współczynnik oraz pojedynczy krok zwiększania mapy,

[G] – obszar roboczy mapy.

Rysowanie obiektów na mapie odbywa się za pomocą myszki. Istotne dla aplikacji jest także okno symulatora wizualizujące ruch robota, które oprócz widoku mapy i drogi robota prezentuje aktualne wartości ruchu (rys. 3):

[A] – droga pokonana przez robota,

[B] – droga do celu liczona po linii prostej,

[C] – chwilowa prędkość robota.

Rys. 3. Okno symulatora służące do wizualizacji ruchu robota

Fig. 3. A window for visualization of a robot operation

Użytkownik ma kontrolę nad przebiegiem symulacji, może ją zastopować i wznowić oraz sterować prędkością poruszania się robota, a także zmieniać położenie celu.

4. Badania symulacyjne

Przeprowadzone badanie obejmowało wykonanie trzech różnych analiz zachowania się robota sterowanego algorytmem bazującym na zmodyfikowanej metodzie sztucznych pól potencjałowych. Ukazują one działanie metody w przypadku wybranych charakterystycznych konfiguracji przeszkód będących odzwierciedleniem problemów spotykanych w sterowaniu rzeczywistymi robotami w środowisku produkcyjnym. Dla każdego przypadku zostały przeprowadzone trzy badania wpływu poszczególnych parametrów metody pól potencjałowych na trajektorię ruchu robota: (1) Badanie wpływ przyrostu wartości potencjału dla aktualnego położenia robota na drogę robota. (2) Wpływ wzmocnienia potencjału punktu docelowego na drogę robota. (3) Wpływ wzmocnienia potencjału przeszkody na drogę robota. Kryterium optymalizacji była długość drogi przebywanej do osiągnięcia celu.

Rys. 4. Przykład omijania prostej przeszkody

Fig. 4. Example of pass by a simple barrier

4.1. Omijanie pojedynczej przeszkody

W przypadku nieskomplikowanego otoczenia robota składającego się z pojedynczej przeszkody, gdzie istnieje jedna optymalna droga jej ominięcia algorytm zmodyfikowanej metody pól potencjałowych działa bardzo dobrze.

Badanie 1) Wpływ przyrostu wartości potencjału dla aktualnego położenia robota na drogę robota dla stałych wartości kd = 60, kp = 20, ks = 2.

Wynik badania pokazuje, że wartość przyrostu potencjału nie wpływa na drogę pokonywaną przez robota, gdyż nie występują tutaj minima lokalne (rys. 5).

Rys. 5. Wpływ przyrostu wartości potencjału aktualnego położenia robota na jego drogę

Fig. 5. Influence of actual robot position potential on its route

Badanie 2) Wpływ wzmocnienia potencjału punktu docelowego na drogę robota – stałe wartości ka = 100, kp = 20, ks = 2.

Istnieje korelacja zmian wzmocnienia potencjałów punktu docelowego z drogą robota. Z wykresu 6a widać, że wraz ze zwiększeniem wzmocnienia potencjału punktu docelowego skokowo spada pokonywana droga, aż do osiągnięcia minimalnej wartości. Robot nigdy dwukrotnie nie znajdzie się na tym samym polu. Wzmocnienie potencjału punktu docelowego powinno być na tyle duże, by móc konsekwentnie przyciągać robota w swoim kierunku.

Badanie 3) Wpływ wzmocnienia potencjału przeszkody na drogę robota – stałe wartości ka = 100, kd = 60, ks = 2.

Wykres 6b pokazuje skokowe zwiększanie się przebytej drogi wraz ze wzrostem wzmocnienia oddziaływania przeszkody. Zbyt duży potencjał przeszkody w tym przypadku zbyt daleko odpycha robota, co skutkuje niepotrzebnym wydłużaniem się drogi. W tym przykładzie powinien być on na tyle mały, by nie odpychać zbyt daleko robota od przeszkody, gdy ten znajdzie się blisko niej.

6a)

6b)

Rys. 6. Wpływ wzmocnienia potencjału punktu docelowego na drogę robota (6a) oraz wpływ wzmocnienia potencjału przeszkody na drogę robota (6b)

Fig. 6. Influence on robot route: final point potential amplification (6a) and barrier potential amplification (6b)

4.2. Całkowite omijanie przeszkody

Podczas całkowitego omijania płaskiej przeszkody robot zachowuje się podobnie jak w poprzednim przypadku.

Badanie przeprowadzono, tak samo jak poprzednio, dla trzech przypadków: (1) Wpływ przyrostu wartości potencjału dla aktualnego położenia robota na drogę robota dla stałych wartości kd = 60, kp = 20, ks = 2. (2) Wpływ wzmocnienia potencjału punktu docelowego na drogę robota dla stałych wartości ka = 100, kp = 20, ks = 2. (3) Wpływ wzmocnienia potencjału przeszkody na drogę robota dla stałych wartości ka = 100, kd = 60, ks = 2.

W pierwszym przypadku podobnie jak poprzednio wartość przyrostu potencjału nie wpływa na drogę pokonywaną przez robota – nie występują minima lokalne. Z kolei w przypadku (2) i (3) otrzymane wykresy ruchu posiadają więcej skoków wartości drogi. Symulacja została przeprowadzona dla czułości sensora równej 2. W sytuacji, gdy wynosiłaby ona 1, wystąpiłoby tutaj minimum lokalne. Jednakże byłoby ono blisko poprawnej trajektorii ruchu robota i przy dodatniej wartości współczynnika ka nie stanowiłoby to problemu w ominięciu przeszkody.

Rys. 7. Przykład omijania prostej przeszkody

Fig. 7. Example of pass by a simple barrier

4.3. Rozległa przeszkoda z minimum lokalnym

Wystąpienie rozległej przeszkody z minimum lokalnym jest najtrudniejszym przypadkiem. Algorytm oparty o metodę pól potencjałowych w czystej postaci nie jest w stanie poradzić sobie z takim zadaniem.

Poddany badaniu algorytm pól potencjałowych zgodnie z wcześniejszym opisem został zmodyfikowany w celu umożliwienia rozwiązywania tego typu problemów. Poddana badaniu konfiguracja przeszkód zalicza się do najtrudniejszych przypadków ze względu na występowanie dwóch minimów lokalnych przed rozległymi przeszkodami – po stronie robota oraz po stronie punktu docelowego. Badanie przeprowadzono podobnie jak poprzednio dla trzech przypadków.

Rys. 8. Przykład omijania skomplikowanej konfiguracji przeszkód

Fig. 8. Example of passing a complicated barrier

Badanie 1) Wpływ przyrostu wartości potencjału dla aktualnego położenia robota na drogę robota dla stałych wartości kd = 60, kp = 20, ks = 2.

Przeprowadzone badanie symulacyjne pokazało, że dla bardzo małych wartości przyrostu potencjału aktualnego położenia robota, nie jest on w stanie znaleźć ścieżki prowadzącej do celu (rys. 9).

Rys. 9. Wpływ przyrostu wartości potencjału aktualnego położenia robota na jego drogę

Fig. 9. Influence of actual robot position potential on its route

Dopiero wraz ze wzrostem potencjału aktualnego położenia robota zaczyna on odnajdować drogę do celu. Jednak dla małych wartości potencjału jest ona bardzo długa. Jej skracanie następuje wraz ze wzrostem współczynnika wzmocnienia potencjału. Droga pokonywana przez robota znacznie maleje, przyjmując w przybliżeniu charakterystykę funkcji potęgowej o wykładniku ujemnym, aż do osiągnięcia minimalnej wartości. Jest to zgodne z logiką, gdyż wraz ze wzrostem potencjału odwiedzonych pól obiekt ma większą szansę, by ponownie nie znaleźć się na tym samym polu, na którym już był. Wynika to z działania zmodyfikowanego algorytmu pól potencjałowych zwiększającego wartość potencjału pól, na których robot był.

Badanie 2) Wpływ wzmocnienia potencjału punktu docelowego na drogę robota dla stałych wartości ka = 200, kp = 20, ks = 2.

Wraz ze zwiększaniem wzmocnienia oddziaływania punktu docelowego dystans pokonywany przez robota rośnie. Dzieje się tak dlatego, że cel coraz bardziej wciąga robota w obszar minima lokalnego. Ponadto wartości pól na mapie są większe, co skutkuje zmniejszeniem wpływu przyrostu wartości potencjału dla aktualnego położenia poruszającego się obiektu. Powoduje to więc działanie odwrotne do omówionego wcześniej współczynnika – badanego w poprzednim punkcie. Można również zauważyć, że wartości drogi nie zmieniają się płynnie. Występują odchylenia, które są spowodowane skomplikowaniem otoczenia robota (rys. 10).

Rys. 10. Wpływ przyrostu wartości potencjału punktu docelowego na drogę robota

Fig. 10. Influence of final point potential amplification on robot rote

Badanie 3) Wpływ wzmocnienia potencjału przeszkody na drogę robota dla stałych wartości ka = 200, kd = 60, ks = 2.

Najbardziej skomplikowany jest przebieg drogi w badaniu wpływu wzmocnienia potencjału przeszkody (rys. 11). Bezpośrednia analiza przebiegu symulacji i ruchu robota pokazuje, dlaczego tak się dzieje. Początkowy wzrost wartości drogi jest spowodowany coraz większymi trudnościami w pokonaniu końca – rogu przeszkody. Wartości pól w tym miejscu coraz bardziej rosną i obiekt musi dalej się oddalić, aby pokonać ten fragment. Następnie obserwujemy nagły spadek wartości drogi. Jest to uzasadnione tym, że robot wewnątrz zamkniętego obszaru przy przeszkodzie, nie zbliża się już do jej konturów. Porusza się bliżej środka, co znacznie zmniejsza pokonywany dystans.

Rys. 11. Wpływ przyrostu wartości potencjału przeszkody dla aktualnego położenia robota na jego drogę

Fig. 11. Influence of barrier potential amplification on mobile robot route

Dalszy nagły wzrost pokonywanej trasy jest spowodowany tym, że na rogu przeszkody robot ponownie wkracza w obszar minimum lokalnego i znowu musi pokonać długi dystans, aby się z niego wydostać. Gdy już wartości pól na rogach przeszkód wzrosną na tyle, że robot nie będzie w stanie tędy przejechać w stronę minimum lokalnego, obserwujemy ponowny spadek wartości pokonywanej trasy. Utrzymuje się ona już na stałym poziomie.

Dla przeprowadzonych badań założonym kryterium optymalizacyjnym była długość drogi do pokonania oraz czas potrzebny na przebycie ścieżki od punktu startowego do celu.

5. Podsumowanie

Celem badania było opracowanie efektywnego algorytmu planowania ścieżki robota mobilnego, który potrafi radzić sobie z omijaniem przeszkód oraz jest odporny na występowanie minimów lokalnych. W ramach badań opracowano własną metodę obliczania drogi będącą modyfikacją metody pół potencjałowych. Modyfikacja miała na celu wyeliminowanie podstawowej wady metody pól potencjałowych, którą jest brak możliwości rozwiązywania problemu minimów lokalnych. W oparciu o wypracowaną zmodyfikowaną metodę pół potencjałowych opracowano algorytm planowania ścieżki mogący znaleźć zastosowanie w budowie układów sterowania robotami przeznaczonymi do wykorzystania w systemach wytwarzania. W celu przeprowadzenia badań efektywności algorytmu zbudowano w języku programowania obiektowego C# własne środowisko symulacyjne. W oparciu o nie przeprowadzono badania opracowanej metody – potwierdziły one jej skuteczność. Zbudowane środowisko symulacyjne i zaproponowana metodyka badań, pozwolą w przyszłości na dobór optymalnych parametrów sterowania rzeczywistymi robotami mobilnymi za pomocą opracowanego algorytmu. Działanie przedstawionego sposobu określania trajektorii ruchu robota zależy od wielu czynników i dla każdego modelu otoczenia może być inne. W przypadku gdy nie występuje minimum lokalne, przemieszczenie obiektu przebiega w sposób płynny i zrozumiały z punktu widzenia zmiennych parametrów algorytmu. W przypadku skomplikowanego układu przeszkód formujących minimum lokalne oraz spowodowanego tym występowania miejscowego ekstremum funkcji potencjału niezbędne jest doświadczalne określenie optymalnych współczynników metody. Pozwoli to na uzyskanie najmniej kosztownej drogi. Przeprowadzone eksperymenty pokazały, że robot za każdym razem dojeżdżał do celu i nigdy nie zderzył się z przeszkodą, nawet kosztem większego nakładu przebytej drogi.

Dalsze badania będą skupiały się na opracowaniu dodatkowych modyfikacji algorytmu, których celem będzie automatyczna optymalizacja nastaw metody w celu minimalizacji drogi oraz ograniczenia rozrzutu wyników dla trudnych modeli otoczenia. Obecnie nastawy algorytmu muszą być dobierane ręcznie i sprawdzane eksperymentalnie. Dla każdego nowego rozkładu obiektów – przeszkód muszą być one dobierane osobno. W pierwszej kolejności należy ocenić, czy na badanym obszarze może wystąpić minimum lokalne. Przy pomocy opracowanego symulatora jest łatwo to ocenić przeprowadzając testy lub eksportując wartości mapy do plików i oceniając je.

Na użytek badania symulacyjnego czułość sensora jest określana w rastrach na początku symulacji. W związku z tym, że jest to metoda lokalna czułość sensora powinna ograniczać się jedynie do najbliższego otoczenia robota. W rzeczywistym układzie wartość współczynnika czułości sensora powinna być dobierana tak, aby po uzyskaniu informacji o przeszkodzie robot miał szansę zatrzymać się lub zmienić kierunek, uwzględniając bezwładność urządzenia i sprawność elementów realizacji ruchu.

Bibliografia

1. Sałaciński T. i inni, Optymalizacja produkcji w czasie kryzysu. Wyd. Wiedza i Praktyka, Warszawa, 2012.

2. Oborski P., Multiagent Shop Floor Control, “Advances in Manufacturing Science and Technology”, Vol. 34, No 3, 2010, 61–72.

3. Latombe J., Robot Motion Planning, Klouwer, Norwell, MA, 1991. DOI: 10.1007/978-1-4615-4022-9.

4. Honczarenko J., Roboty przemysłowe: budowa i zastosowanie, Wydawnictwa Naukowo-Techniczne, Warszawa, 2010.

5. Rashid A., Ali A., Frasca M., Fortuna L., Path planning with obstacle avoidance based on visibility binary tree algorithm, “Roboticsand Autonomous Systems”, 61, 2013, 1440–1449.

6. Qu H., Xing K., Alexander T., An improved genetic algorithm with co-evolutionary strategy for global path planning of multiple mobile robots, “Neurocomputing”, Vol. 120, 23 November 2013, 509–517. DOI: 10.1016/j.neucom.2013.04.020.

7. Sabattini L., Secchi C., Fantuzzi C., Arbitrarily shaped formations of mobile robots: artificial potential fields and coordinate transformation, “Auton. Robot”, Vol. 30, No. 4, 2011, 385–397. DOI: 10.1007/s10514-011-9225-4.

8. Huang L., Velocity planning for a mobile robot to track a moving target — a potential field approach, “Robotics and Autonomous Systems”, Vol. 57, No. 1, 2009, 55–63. DOI: 10.1016/j.robot.2008.02.005.

9. Gao X., et al., A novel local path planning method considering both robot posture and path smoothness, “Robotics and Biomimetics (ROBIO), 2013 IEEE International Conference”, 172– 178. DOI: 10.1109/ROBIO.2013.6739454.

10. Buniyamin N., et al., A Simple Local Path Planning Algorithm for Autonomous Mobile Robots, “International Journal of Systems Applications, Engineering & Development”, Issue 2, Vol. 5, 2011, 151–159.

11. Urmson Ch., Baker Ch., Dolan J., Rybski P., Salesky B., Whittaker W., Ferguson D., Darms M., Autonomous Driving in Trafic: Boss and the Urban Challenge, “AI Magazine, Association for the Advancement of Artificial Intelligence”, summer 2009, 17–28.

12. Wei J., Dolan J.M., A multi-level collaborative driving framework for autonomous vehicles. [in:] “18th IEEE International Symposium on Robot and Human Interactive Communication”, September 2009, 40–45. DOI: 0.1109/ROMAN.2009.5326205.

13. Thrun S., Montemerlo M., Dahlkamp H., Stavens D., Aron A., Diebel J., Fong P., Gale J., Halpenny M., Hoffmann G., et al., The robot that won the DARPA grand challenge, “The 2005 DARPA Grand Challenge”, 2007, 1–43.

14. Seshanet J. et al., Efficient Route Finding and Sensors for Collision Detection in Google’s Driverless Car, “International Journal of Computer Science and Mobile Computing”,Vol. 3 Issue 12, December 2014, 70–78.

15. Koren Y., Borenstein J., Potential field methods and their inherent limitations for mobile robot navigation. [in:] “Proc. IEEE Conf. on Robotics and Auto.”, Sacramento, California, 1991, 1398–1404. DOI: 10.1109/ROBOT.1991.131810.

16. Dulęba I., Metody i algorytmy planowania ruchu robotów mobilnych i manipulacyjnych, Warszawa, Akademicka Oficyna Wydawnicza EXIT, 2001, 169–174.

17. Ge S.S., Cui Y.J., New potential functions for mobile robot path planning, “IEEE Transactions on Robotics and Automation”, Vol. 16, No. 5, 2000, 615–620. DOI: 10.1109/70.880813.

18. Huang L., Velocity planning for a mobile robot to track a moving target — a potential field approach, “Robotics and Autonomous Systems”, Vol. 57, No. 1, 2009, 55–63. DOI: 10.1016/j.robot.2008.02.005.

19. Purcell E., Elektryczność i magnetyzm, tłum. L. Łukaszuk, Wyd. II. Warszawa, Państwowe Wydawnictwo Naukowe, 1974.

20. Garbacz M., Zaczyk M., Metoda pól potencjałowych w nawi-gacji kołowego robota mobilnego, „AUTOMATYKA”, 2011, t. 15, z. 3.

21. Spong M., Hutchinson S., Vidyasagar M., Robot Modeling and Control, John Wiley & Sons, Hoboken, 2006.

Modified Potential Field Method for Mobile Robot Route Calculation

Abstract: The possibility of using mobile robots in industry is largely dependent on the application of the efficient control systems. They should be able to achieve planned road points autonomously, safety and fast. Selection of suitable algorithms for route calculation and optimization is one of the main problems. Their task is current calculation of the road, avoiding obstacles, making the leading robot achieve often changing goal. Complexity of the optimization of a mobile robot path is one of the main problems. There are two main approaches in the mobile robot path calculation: the global and local one. In the global approach it is possible to optimize the entire path. However, it requires knowledge of all the obstacles before starting calculation, so a dynamic response to changes is impossible. The disadvantage is also required significant computing power. The local approach allow for dynamic response to changing obstacles and goals. Searching of the path can be narrowed to a limited area around robot what greatly reduce the requirements with regard to the processing of data. However, disadvantage is the inability of global optimization. The article presents the results of research on new modified potential filed method development. On the base of it a universal control algorithm has been prepared. It was used for simulation based testing of the algorithm operation in various difficult conditions like local minimum.

Keywords: mobile robots path planning, shop floor control, control algorithms, simulation tests

dr inż. Przemysław Oborski

p.oborski@op.pl

Ekspert w zakresie systemów wytwarzania, sterowania nadrzędnego, integracji systemów sterowania i monitorowania oraz organizacji systemów produkcyjnych.

Tomasz Fedorczyk

fedorwwy123@wp.pl

Programista używający między innymi języka C#, Java; specjalista w zakresie instalacji i wdrażania urządzeń produkcyjnych.