Teoretyczne założenia rozwiązania problemu marszrutyzacji w automatycznych systemach intralogistycznych.
Marszrutyzacja w zautomatyzowanych, zintegrowanych systemach intralogistycznych – zarys problemu.
Złożone systemy intralogistyczne oparte o roboty (mobilne roboty AMR/AGV, zautomatyzowane rolotoki, układnice magazynowe, regały automatyczne) wymagają praktycznego rozwiązania bardzo ciekawego przypadku problemu klasy VRP (Vehicle Routing Problem) czyli po polsku problemu marszrutyzacji i to na dodatek w skomplikowanej wersji. Z matematycznego punktu widzenia jest to problem NP-trudny, a nawet NP-zupełny, co oznacza, że w praktyce nie da się go rozwiązać algorytmami dokładnymi. Tymczasem w sieciach opartych o roboty, nie są to jedyne problemy do rozwiązania, kiedy chcemy automatycznie rozwozić setki ładunków między kilkudziesięcioma punktami. Marszrutyzacja w systemach intralogistycznych – przyjrzyjmy się zatem temu zagadnieniu.
Przewieź ładunek XYZ z punktu A do punktu B.
Jeśli tak zdefiniujemy problem, będzie od łatwy do rozwiązania. Wystarczy, że operator wprowadzi te trzy informacje (co, skąd, dokąd), będziemy mieli zdefiniowane najprostsze zadanie logistyczne, które będzie mogło być wykonane czy to przez robota, czy przez człowieka. Ale…w praktyce wygląda to inaczej. Flota robotów ma sens wtedy, kiedy tych misji są setki w ciągu zmiany, a w systemie nie potrzebujemy człowieka. Zatem – na początek trzeba skądś załadować listę zadań. Skąd?
Na to pytanie dają na ogół systemy klasy MES lub ERP. W systemach tych funkcjonuje na ogół dokument nazywany planem produkcji oraz BOM – czyli dekompozycja planu produkcji na komponenty. Jeśli tylko mamy mapę punktów logistycznych oraz wiemy, skąd pobrać komponenty, da się z tego wygenerować taką listę. Jeśli jeszcze znamy takt linii produkcyjnych oraz przepustowość systemu da się nawet ułożyć z tego sensowny harmonogram.
Mamy więc listę zadań, co dalej?
Ścieżka krytyczna.
Zanim zadania logistyczne (nazywamy je misjami) zostaną zlecone do systemu zarządzającego flotą robotów, musi nastąpić priorytetyzacja misji wymagająca najczęściej analizy ścieżki krytycznej, zastosowania algorytmów inteligentnego komponowania misji (np. łączymy misje „tam” i „z powrotem”) a także bieżącego sprawdzania parametrów ograniczających (np. dostępność ładunku do transportu czy wolne miejsce w miejscu przeznaczenia).
Analiza ścieżki krytycznej (CPM) choć wzięła się z dziedziny zarządzania projektami, jak najbardziej ma zastosowanie w przypadku komponowania planu misji. Chodzi bowiem o takie kolejkowanie zadań logistycznych, aby wszystkie punkty logistyczne zostały zaopatrzone w określonych oknach czasowych przy jednoczesnej optymalizacji czasu przejazdu wszystkich robotów. Po co? Ano po to, żeby z jednej strony zmniejszać przebiegi robotów, a z drugiej utrzymywać jak najbardziej korzystny bilans energetyczny całego systemu.
Techniczne rozwiązanie problemu wyznaczania harmonogramu misji nie jest trywialne. Wymaga oczujnikowania punktów logistycznych (aby system „wiedział” czy miejsce jest wolne, czy zajęte), odczytu identyfikatorów ładunków (by robot „wiedział”, co wiezie), odczytu i aktualizacji oczekiwanych czasów realizacji zadań logistycznych oraz logiki, która nad tym wszystkim panuje. Co więcej, nie wystarczy tej ścieżki wyznaczyć raz np. na zmianę, gdyż wciąż pojawiają się w niej zakłócenia: niewykonane zadania logistyczne (np. brak ładunku w miejscu odbioru), misje zlecone ręcznie (np. zwrot odpadów z linii produkcyjnej) czy niedostępność systemu (np. awaria robota).
Problem uprzywilejowania.
W przestrzeni magazynu czy hali fabrycznej roboty mobilne muszą respektować zasady pierwszeństwa przejazdu. Na ogół człowiek ma priorytet (ze względu na bezpieczeństwo ludzi oraz przepisy), a priorytety między pojazdami ustalane są przez mechanizmy bezpieczeństwa. I można by było tu postawić kropkę, ale…
Jeśli do zagadnienia pierwszeństwa przejazdu podejdziemy w opisany wyżej sposób, może okazać się, że roboty zważające na wszystko i wszystkich jeżdżą powoli, co powoduje spadek wydajności systemu i tak się niestety dzieje w wielu przypadkach, co podnosi koszty (więcej robotów) oraz zniechęca (duży ruch i zajęte ciągi komunikacyjne). I tu można pokusić się o przynajmniej dwa usprawnienia. Po pierwsze, zarządzanie misjami przez oprogramowanie nadrzędne może (a nawet powinno!) zawierać algorytmy predykcyjne, które np. będą opóźniać misje, jeśli miałyby one doprowadzić do zatorów. Po drugie zaś, robot realizujący zadania na ścieżce krytycznej lub zadania opóźnione może np. emitować czerwone światło oraz dźwięk wskazując na uprzywilejowanie – tak jak karetka na sygnale zmusza innych uczestników ruchu do ustąpienia drogi. W przypadku floty robotów można także wysłać do pozostałych robotów w okolicy sygnał zatrzymania – i mamy to!
Respektowanie ograniczeń.
Żeby problem marszruty dodatkowo skomplikować, flota robotów musi brać pod uwagę cały szereg ograniczeń. Wymieńmy te najważniejsze:
- Prędkość – choć robot bez problemu rozpędza się do 5-7 km/h musi brać pod uwagę fizykę ładunku (ciężka i wysoka paleta może być niestabilna w zakrętach czy przy scenariuszu awaryjnego zatrzymania wskutek wtargnięcia w strefę bezpieczeństwa), szczególnie na zakrętach, wąskich przejazdach oraz w okolicy doków.
- Stan naładowania akumulatorów – aby utrzymać w długim okresie stabilną wydajność oraz sprawność techniczną akumulatorów, system musi przy komponowaniu misji monitorować stan naładowania każdego z robotów oraz optymalizować i aktualizować w sposób ciągły plan misji.
- Dostępność ładunku oraz informacja o wolnych dokach – przed wysłaniem robota z konkretną misją, system sprawdza, czy ładunek jest dostępny w punkcie poboru i czy w punkcie docelowym jest wolne miejsce. Ten drugi parametr musi być monitorowany ciągle aż do ukończenia misji.
- Strefy wyłączenia i reguły omijania – przy nawigacji SLAM (czyli swobodnej nawigacji w oparciu najczęściej o lasery lub lidary) roboty muszą na bieżąco analizować sytuację pod kątem przeszkód. W tym celu definiuje się reguły omijania przeszkód (np. liczba prób ominięcia, strona omijania) w odniesieniu do stref wyłączenia (na ogół robot porusza się w określonym korytarzu i nie wolno mu poza niego wyjeżdżać). Jeśli system nadrzędny dowie się o istnieniu „stałej” przeszkody, powinien automatycznie przemodelować mapę i uwzględniać zmienioną ścieżkę przy planowaniu i zlecaniu misji w przyszłości.
Aktualizacja planu misji po awarii.
Wszystko pięknie zaplanowane, roboty realizują plan misji, telemetria zapewnia prawidłowe dane…jest to oczywiście stan idealny, do którego należy dążyć i nawet mierzyć stopień jego realizacji. Życie jednak dyktuje różne scenariusze, których wynikiem jest zakłócenie lub zatrzymanie realizacji procesu. Może zepsuć się robot, może na ścieżce przejazdu pojawić się przeszkoda nie do ominięcia, może wydarzyć się ludzki błąd typu błędny ładunek czy niewłaściwie oznaczony nośnik logistyczny. O ile procedury przywracania systemu do działania można sobie dość łatwo wyobrazić (np. ręczne dostarczenie błędnie oznakowanej palety czy reset oprogramowania robota), to już aktualizacja planu misji nie jest taka łatwa i zwykle wymaga interwencji człowieka, który mając informacje z systemu a także z „realu”, w odpowiedni sposób reorganizuje misje i wznawia transport. Oczywiście wymaga to z jednej strony klarownych procedur, z drugiej algorytmów wspomagających rozwiązywanie problemów, a z trzeciej jeszcze – całodobowego wsparcia merytorycznego od dostawcy systemu.
Do napisania powyższego artykułu skłoniła mnie wnikliwa lektura specyfikacji oprogramowania konkurencyjnych wobec oferty ESS producentów i integratorów systemów intralogistycznych. Być może w praktyce są one w ten czy inny sposób realizowane, ale informacji na ten temat brak lub są one szczątkowe. Może to wynikać też z faktu, że na rynku jest bardzo niewiele działających produkcyjnie całkowicie automatycznych systemów tej klasy o większej od 3-4 liczbie współpracujących robotów. Oprogramowanie, ze względu na konieczność licznych interakcji z realnym otoczeniem, nie jest proste ani w budowie, ani we wdrożeniu – rzut oka na poniższą grafikę może dać pewne pojęcie
