Do Projektu iAutomatyka dołączyli:

https://iautomatyka.pl/wp-content/uploads/2019/01/genetics.jpg

Wykorzystanie algorytmu genetycznego do optymalizacji pracy wiertarki przemysłowej

autor: Kasparski.

Powiedzieć, że jest się automatykiem to w zasadzie tak jakby nic nie powiedzieć, a już z pewnością nic konkretnego. Zawód ten nosi w sobie tak szerokie spektrum możliwości, że nie sposób scharakteryzować czym ten „prawdziwy” automatyk tak właściwie się zajmuje. Ciężko przecież porównać chociażby pracę inżyniera „systemowca”, skupiającego się na najdrobniejszych szczegółach dokumentacji technicznej ze specjalistami z utrzymania ruchu, czy z projektantami szaf sterowniczych. A to tylko wierzchołek góry lodowej! Co z inżynierami sprzedaży, „uruchomieniowcami”, serwisantami, projektantami, programistami, szkoleniowcami, robotykami, czy technologami? Każdy z nas mógłby z pewnością dopisać do tej listy kolejne przykłady pokazujące jak szerokim pojęciem jest zawód automatyk.

Niezależnie od tego jak wygląda nasza codzienna praca myślę, że wielu z nas zgodzi się ze stwierdzeniem, iż zadania przed którymi przychodzi nam stawać w pracy rzadko pokrywają się z materiałem wykładanym na uczelniach. W jednym z ostatnich projektów miałem jednak możliwość wykorzystania typowo akademickiej wiedzy w aplikacji przemysłowej. Projekt wydał mi się na tyle ciekawy, że skłonił mnie do opisania go w poniższym artykule.

Założenia projektu

Zadanie, którego się podjąłem polegało na zaprojektowaniu i zrealizowaniu systemu sterowania do zautomatyzowanej wiertarki przemysłowej. Maszyna, z którą miałem spędzić kilka najbliższych dni, została zaprojektowana do nawiercania dużych arkuszy blachy. Operator poprzez edycję receptury decydował o ilości nawiertów i ich rozmieszczeniu. Produkty końcowe były na tyle duże, że wykonanie pojedynczej sztuki mogło wymagać aż do 50 wywierconych otworów.  Głowica wiertarki została umieszczona na trójosiowym manipulatorze kartezjańskim wykonującym ruch w płaszczyźnie XYZ. Manipulator napędzany był przez serwosilniki, natomiast do przeniesienia napędu wykorzystano śruby kulowe. Sterowanie oparte zostało na jednym sterowniku PLC, trzech serwowzmacniaczach i panelu HMI – bez dostępu do systemu nadrzędnego. Głównym wyzwaniem okazało się stworzenie intuicyjnego interfejsu pozwalającego na swobodną edycję i wizualizację programu. Kluczowym czynnikiem z punktu widzenia wydajności maszyny było wyznaczenie trajektorii ruchu manipulatora. W przypadku 5, czy 6 punktów operator gołym okiem byłby w stanie stwierdzić jak najlepiej poprowadzić głowicę. Jednak dla większej ilości nawiertów sprawa przestaje być taka oczywista. W przypadku 30 czy 40 nierównomiernie rozłożonych otworów znalezienie najkrótszej drogi między nimi jest już nie lada wyzwaniem. Produkcja miała charakteryzować się dużą zmiennością co wymagało częstego przezbrajania maszyny pod nową recepturę. Z punktu widzenia klienta końcowego wydłużenie cyklu produkcji przekładało by się na realne straty finansowe, a ręczna optymalizacja trajektorii byłaby dodatkową bolączką wydłużającą czas generowania programu. W związku z wymienionymi wymaganiami ostatnim, a zarazem najciekawszym, etapem projektu było przygotowanie optymalizacji ścieżki ruchu manipulatora.


Optymalizacja

Optymalizacja – słowo klucz, które potrafi zjeżyć włos na głowie. Dla producenta maszyny, dopracowany algorytm optymalizacji jest cechą, która ma wyróżnić go na tle konkurencji. Czynnikiem, który sprawia, że to akurat jego produkt jest najlepszą ofertą na rynku. Po drugiej stronie barykady znajduje się automatyk. Pytanie, które powinien sobie zadać programista brzmi: Co to znaczy dopracowany? Czasami projekty potrafią się ciągnąć latami. Tworząc kolejne udoskonalenia, znajdując co raz to nowe przypadki, generuje się kod mogący przekraczać pojemność sterownika. To mniej więcej jak z aplikacjami Google’a. Jak długo można je udoskonalać? Odpowiedź brzmi: w nieskończoność.

W przypadku projektu wiertarki sytuacja wydawała się dosyć klarowana. Zadaniem było znalezienie najkrótszej drogi pomiędzy punktami, tak aby na koniec powrócić do miejsca startowego.

Można byłoby przyjąć, że najłatwiejszym sposobem na znalezienie najkrótszej drogi dla głowicy jest po prostu przeliczenie wszystkich możliwych rozwiązań i wybranie najlepszego z nich. Liczba permutacji, którą trzeba sprawdzić w takim przypadku wyrażona jest wzorem: ((n-1)!)/2, gdzie n to liczba punków do wywiercenia.  Przyjmując optymistyczną wersję, że PLC jest w stanie obliczyć jedno rozwiązanie w ciągu 0.01 ms to czas potrzebny na sprawdzenie wszystkich możliwych rozwiązań wyglądałby następująco:

Jak widać już na poziomie 12 punktów liczba kombinacji przekracza akceptowalne granice oczekiwania na wynik. Zgodnie z założeniami projektowymi na jeden arkusz blachy mogło przypadać do 50 punktów. Dlatego należało zastanowić się nad innym, mniej oczywistym rozwiązaniem.

Gdy spojrzymy na przedstawiony problem optymalizacji z dystansu – abstrahując od silników, napędów, sterowników i całej tej automatyki – to łatwiej będzie dostrzec, że zadanie z którym przychodzi nam się mierzyć jest klasycznym przypadkiem problemu komiwojażera (ang. travel salesman problem) przeniesionym na poziom maszyny przemysłowej! Zagadnienie to zostało szeroko opisane i  posiada wiele rozwiązań bazujących na metodach heurystycznych. Jednym z nich jest wykorzystanie algorytmu genetycznego.

Algorytm genetyczny

Algorytm genetyczny jest to rodzaj algorytmu przeszukującego przestrzeń alternatywnych rozwiązań problemu w celu wyszukania rozwiązań najlepszych. Może być wykorzystywany jako uniwersalne narzędzie do rozwiązywania problemów optymalizacji. Stosuje się go  w wielu sytuacjach, w których nie radzą sobie tradycyjne metody obliczeniowe. Należy pamiętać, że wynik jaki otrzymamy nie musi być najlepszym z możliwych rozwiązań, możemy otrzymać tzw. optimum lokalne – wynik akceptowalnie dobry. Nazwa oraz stosowana terminologia algorytmu genetycznego związana jest ze sposobem działania opartym o mechanizmy zbliżone do działania ewolucji biologicznej.

Tyle o definicji. Zapewniam, że brzmi to wszystko o wiele bardziej skomplikowanie niż w rzeczywistości wygląda. Działanie algorytmu jest dość intuicyjne, jego zastosowanie wymaga jednak zazwyczaj sporej mocy obliczeniowej i dużych zasobów pamięci. Czy da się go zaimplementować w maszynie przemysłowej opartej o kompaktowy sterownik PLC? Na to pytanie postaram się odpowiedzieć w dalszej części artykułu.

Ze względu na ograniczoną ilość pamięci sterownika wykorzystanie algorytmu genetycznego wymagało pewnych modyfikacji w stosunku do tego, co zwykle można znaleźć w literaturze. Schemat działania algorytmu przedstawia diagram nr 1.

Stworzenie populacji początkowej

Pierwszym krokiem jest stworzenie skończonej liczby rozwiązań początkowych. W terminologii przyjętej przez algorytm nazywamy ją populacją początkową. Na tym etapie musimy określić jaki obszar pamięci będzie zajmował pojedynczy osobnik (jedno rozwiązanie) oraz jaką liczbę osobników jesteśmy w stanie przechowywać w sterowniku w tym samym czasie. Z wytycznych projektu wynikało, że pojedynczy punkt musi zawierać informacje o współrzędnych X, Y oraz dane wynikające z technologii wiercenia. Po zsumowaniu okazało się, że jeden punkt (gen) zajmuje 6 rejestrów sterownika, czyli 12 bajtów. Zgodnie z założeniami początkowymi pojedynczy osobnik może składać się maksymalnie z 50 punktów, dlatego wymagał rezerwacji obszaru 300 rejestrów. Architektura sterownika pozwalała przeznaczyć na działanie algorytmu około 32 tysięcy rejestrów. Po przeliczeniu, stwierdziłem, że populacja początkowa mogła pomieścić około 100 osobników i taką też liczbę przyjąłem jako rozmiar populacji początkowej.

Istnieje wiele sposobów na wyznaczenie początkowych rozwiązań. Jedną z nich jest stworzenie osobników poprzez losowy przydział genów. Na tym etapie osobniki mogą być dalekie od poprawnego rozwiązania, w tym momencie ich jakość nie jest aż tak istotna. W naszym przypadku gen to pozycja wiertarki, a genotyp to zbiór wszystkich punktów tworzących osobnika. W zasadzie można by wyznaczyć 100% populacji początkowej w sposób losowy. Jeżeli jednak posiadamy rozwiązanie, które w jakimś stopniu jest zbliżone do rozwiązania optymalnego, to warto dołożyć go do puli początkowej. Pozwoli to zmniejszyć ilość iteracji potrzebnych do znalezienia akceptowalnego rozwiązania.

Po fazie testów zdecydowałem o dodaniu osobnika powstałego poprzez połączenie najbliższych sobie wolnych punktów. By mieć pewność, że wynik działania algorytmu nie będzie nigdy gorszy niż stan wejściowy, postanowiłem również dodać aktualnego osobnika (wprowadzonego przez operatora) do populacji początkowej. W rezultacie algorytm w sposób losowy tworzył 98 osobników początkowych, jednemu został przypisany stan obecny, a ostatni został stworzony poprzez wynik działania innego algorytmu.

Ocena i wybór najlepszych osobników

Największe szanse na przetrwanie i pomyślną reprodukcję mają osobniki najlepiej przystosowane. W analizowanym projekcie o wartości danego osobnika świadczyła długość trajektorii, którą tworzył. Po posortowaniu populacji po wyniku funkcji przystosowania połowa osobników uczestniczyła w trakcie krzyżowania, a druga połowa zostawała odrzucana jako nierokująca na przyszłość. Za funkcję przystosowania przyjąłem bloczek funkcyjny sumujący odległości między punktami.

Krzyżowanie

W wyniku krzyżowania dwóch osobników (rodziców) powstaje kolejny osobnik zaliczany do następnego pokolenia. Liczba pokoleń którą chcemy uzyskać jest zależna od ilości wykonanych iteracji.  Sam wybór rodziców jak i sposób krzyżowania mogą się różnić w zależności od wersji algorytmu. Kombinacji na wybór osobników do krzyżowania jest zapewne tyle co samych programistów. Można na przykład wybierać ich losowo, lub krzyżować tylko najlepszego osobnika z wszystkimi pozostałymi. W wyniku przeprowadzonych testów zdecydowałem się na krzyżowanie osobników 1 z 2, 2 z 3, 3 z 4… aż do 49 z 50. Zostawali oni zapisywani kolejno w miejsce starej, odrzuconej części populacji.

Mechanizm krzyżowania polega na przekopiowaniu losowej części genotypu (zaczynając od miejsca wybranego przez generator liczb losowych) w losowe miejsce genotypu potomka. Następnie uzupełniano brakujące komórki genotypem drugiego rodzica, zachowując kolejność niepowtarzających się genów. Przykład krzyżowania dla 10 punktów przedstawiono na diagramie nr 2.

Po skrzyżowaniu ostatnich z osobników następowała ponownie ocena i wybór najlepszych 50 osobników.

Mutacje

Zadaniem mutacji jest wprowadzanie zmian w pojedynczych genach. Zmian, które nie mają szans zaistnieć np. podczas krzyżowania. Mechanizm działania jest bardzo prosty: zamieniamy ze sobą miejscami dwa losowe wybrane geny. Mutacja była przeprowadzana na 50 najlepszych osobnikach i zapisywana w miejsce gorszej części populacji.

Na koniec etapu mutacji ponownie następowała selekcja najlepiej przystosowanych osobników

Parametry algorytmu

Algorytm został zapisany w postaci bloczka funkcyjnego posiadającego 2 argumenty wejściowe. W zależności od stopnia skomplikowania receptury można manewrować liczbą iteracji oraz ilością mutacji genotypu na jedną iterację. Dzięki tym parametrom można dopasować czas trwania obliczeń do skomplikowania rozpatrywanego przypadku.

Watchdog i czas cyklu

Tworząc strukturę programu, musimy od samego początku uwzględniać ograniczenia sterowników PLC. Jednym z nich jest maksymalny czas cyklu sterownika zabezpieczany przez timer watchdog. W sterowniku, który wykorzystałem, maksymalna nastawa tego ważnego parametru wynosiła dwie sekundy. To zdecydowanie za mało by cały kod algorytmu zdążył się wykonać. Dlatego też podczas pisania należy dzielić program na krótkie sekcje, po których sterownik ma szansę zakończyć swój cykl. Należy również unikać stosowania pętli while i for, które zatrzymują skan przez dłuższy czas w jednym miejscu. Zamiast wyżej wymienionych pętli, można używać funkcji case i indeksów w postaci inkrementowanych rejestrów. Dzięki tym działaniom udało się utrzymać czas cyklu sterownika poniżej 20ms.

Prezentacja wyników

Poniżej zamieszczam przykładowe wyniki działania algorytmu.

Podsumowanie

Współczesne sterowniki PLC charakteryzują się na tyle wysokimi parametrami, że mogą z powodzeniem sięgać po rozwiązania zarezerwowane dotychczas dla świata IT. Dzięki przestrzeganiu kilku zasad prowadzania kodu, udało się uzyskać w pełni działający algorytm genetyczny na kompaktowym sterowniku przemysłowym. Czas potrzebny na wykonanie potrzebnych obliczeń różnił się w zależności od stopnia skomplikowania receptury i zadanych parametrów. W większości przepadków nie przekraczał 3 minut. Algorytm był uruchamiany sporadycznie, tylko podczas definiowania nowych receptur. Warto nadmienić fakt, że jego obliczenia nie wpływały na pracę całej maszyny – mógł być wykonywany w tle podczas gdy urządzenie pracowało z pełną wydajnością. Podobny mechanizm można wykorzystać w innych aplikacjach operujących na dużej ilości punków.

 

Artykuł został nagrodzony w Konkursie iAutomatyka –  edycja Styczeń 2019

Nagrodę Voucher na szkolenie Mitsubishi + gadżety firmowe dostarcza ambasador konkursu, firma Mitsubishi Electric

 

 



Utworzono: / Kategoria: , , , ,

Reklama

Newsletter

Zapisz się i jako pierwszy otrzymuj nowości!



PRZECZYTAJ RÓWNIEŻ



NAJNOWSZE PUBLIKACJE OD UŻYTKOWNIKÓW I FIRM

Reklama



POLECANE FIRMY I PRODUKTY