Robotyka · Floty robotów magazynowych (goods-to-person)
Mniej robotów, większa wydajność
Setki robotów magazynowych planowanych na żywo w przeglądarce. Można sprawdzić, przy jakiej wielkości floty dokładanie robotów zaczyna obniżać wydajność.
Przegląd
Planer ruchu dla robotów magazynowych typu goods-to-person, działający w przeglądarce. Do 400 symulowanych robotów poruszających się po siatce nieustannie otrzymuje nowe zadania: pobrać regał magazynowy, dowieźć go do jednego z 16 stanowisk kompletacji, zaczekać na kompletację, a potem pobrać następny. Kolizje są wykluczone z samej konstrukcji, a w 4 775 przebiegach z ustalonym ziarnem nie wystąpiło żadne zakleszczenie. Można dodawać roboty, aż wydajność przestanie rosnąć, a potem oznaczyć alejki jako jednokierunkowe – planer traktuje to jako wagi, a nie wymuszone reguły – i obserwować, jak przesuwa się szczyt krzywej.
W naszej hali, z tym planerem i średnim czasem kompletacji 6 sekund, wydajność osiąga maksimum ok. 5 134 podstawień regałów na godzinę. Szczyt jest płaski: każda flota od 196 do 235 robotów mieści się w granicach 0,5% od najlepszego wyniku, a wygładzona krzywa osiąga maksimum przy 214. Dalej każdy robot obniża wydajność, i to coraz szybciej: tuż za szczytem o ok. 1 podstawienie na godzinę na każdego robota, w okolicy 250 robotów o ok. 4 na robota, a blisko 400 o ok. 7 na robota. Przy 400 robotach hala daje o 20,5% mniej niż w optimum, a 48% jadących robotów nie jest bliżej celu niż 8 sekund wcześniej.
Po oznaczeniu alejek jako jednokierunkowych – jako preferencji, a nie reguł – ta sama hala osiąga maksimum 6 439 podstawień regałów na godzinę przy 191 robotach: o 25,4% większa wydajność przy 23 robotach mniej. Punktem odniesienia jest ruch dwukierunkowy w jednopasowych alejkach, którego rzeczywiste układy magazynów unikają, więc zysk jest spodziewany. Ciekawe jest to, gdzie się kończy. Gdy kompletacja zwalnia do 24 sekund na regał, ograniczeniem stają się stanowiska, a oznaczenia zmieniają wydajność najwyżej o 2,5% w jedną lub drugą stronę.
Te liczby dotyczą modelu siatkowego z tym planerem. Roboty poruszają się synchronicznie, w takcie, o jedną komórkę o boku 1 metra na sekundę, mogą jechać jeden tuż za drugim i nie mają czasu przyspieszania ani obrotu. Bloki regałów są pełne (roboty nigdy pod nimi nie przejeżdżają), odwiezienie regału jest wliczone w pobranie następnego, a stanowiska nie mają pasów kolejkowych. Przy optymalnej wielkości floty hala jest zapełniona w ok. 40% – znacznie gęściej, niż pracowałaby rzeczywista flota. Wyniki zależą od tej jazdy jeden za drugim: w wariancie planera z zachowaniem odstępu (żaden robot nie może wjechać do komórki w tej samej sekundzie, w której opuszcza ją inny) najlepsza ze sprawdzonych wielkości floty to 80 robotów i ok. 1 880 na godzinę, a przy 160 robotach dochodzi już do całkowitego zatoru (10 przebiegów z ustalonym ziarnem na punkt). Rzeczywiste floty korkują się wcześniej, a inny planer przesunąłby szczyt.
Co zbudowaliśmy
- Planer ciągły (lifelong) dla wielu robotów oparty na PIBT (priority inheritance with backtracking – dziedziczenie priorytetów z nawrotami; Okumura i in.), zaimplementowany na podstawie artykułu. Działa w wątku Web Worker w przeglądarce, a ten sam kod planera wykonał wszystkie symulacje stojące za głównymi liczbami na tej stronie.
- Miękkie alejki jednokierunkowe: oznaczone kierunki stają się wagami na siatce nieskierowanej. Jazda pod prąd kosztuje 3 kroki zamiast 1, więc roboty nadal jadą pod prąd, gdy objazd byłby dłuższy albo gdy miejsca potrzebuje inny robot. Edytor mapy odrzuca każdą zmianę – zablokowanie lub odblokowanie komórki – po której jakiś korytarz nie leżałby na żadnej pętli: tego warunku wymaga dowód osiągalności PIBT. Sprawdza to algorytm wyszukiwania mostów.
- Wykonanie w takcie z losowymi wstrzymaniami. Co sekundę, zanim którykolwiek robot się ruszy, losowo wstrzymywany jest 1% zaplanowanych ruchów, a roboty ustawione w kolejce za wstrzymanym robotem są wstrzymywane razem z nim, więc żaden robot nigdy nie zostaje przesunięty na zajętą komórkę. Każdy krok sprawdza niezależny weryfikator.
- Stanowiska kompletacji z czasem kompletacji losowanym dla każdego regału (rozkład gamma). W widoku na żywo można przełączać średnią między 3, 6, 12 a 24 sekundami.
- Seria 4 740 jednogodzinnych przebiegów z ustalonym ziarnem: od 20 do 400 robotów w głównej hali oraz większa hala jako kontrola. Każdy punkt ma 95-procentowe pasma ufności, a szczyt – przedział bootstrapowy.
Technologie
JavaScript (moduły ES) w wątku Web Worker · three.js · Node.js worker threads do serii symulacji · Python i NumPy do statystyki
W liczbach
| Wartość | Jak to zmierzyliśmy |
|---|---|
| 5 134 na godzinę | Szczyt krzywej przepustowości: alejki dwukierunkowe, średni czas kompletacji 6 s. Jeden regał podstawiony na stanowisko kompletacji to jedno podstawienie; jeden krok na siatce liczy się jako jedna sekunda. To maksimum wygładzonej krzywej (LOESS) dopasowanej do 1 400 jednogodzinnych przebiegów z ustalonym ziarnem przy liczbie robotów od 20 do 400 (przedział 95%: od 5 130 do 5 139). |
| Od 196 do 235 robotów | Płaski szczyt: każda wielkość floty w tym zakresie mieści się w granicach 0,5% od najlepszego wyniku. Wygładzona krzywa osiąga maksimum przy 214 robotach (przedział bootstrapowy od 213 do 216); inne szerokości wygładzania przesuwają ten punkt między 212 a 216. |
| −1 → −7 na robota | Koszt każdego dodatkowego robota według dopasowanej krzywej, z 95-procentowymi przedziałami bootstrapowymi:
|
| −20,5% | Przepustowość przy 400 robotach (4 080 na godzinę) w porównaniu ze szczytem, na tej samej dopasowanej krzywej. |
| +25,4% | Zysk na szczycie dzięki oznaczonym alejkom jednokierunkowym: 6 439 na godzinę przy 191 robotach. Zmierzone na kolejnych 1 400 przebiegach z ustalonym ziarnem, z tą samą halą i ustawieniami; 95-procentowy przedział bootstrapowy wynosi od 25,3% do 25,5%. |
| W granicach 2,5% | Przy czasie kompletacji 24 s wyniki dla hali z oznaczeniami i bez nich różnią się najwyżej o 2,5% przy każdej wielkości floty (10 przebiegów z ustalonym ziarnem na punkt). Łącznie 16 stanowisk ogranicza wydajność do 2 400 na godzinę. |
| 35% → 48% | Odsetek jadących robotów, które nie są bliżej celu niż 8 s wcześniej, przy 214 i przy 400 robotach (alejki dwukierunkowe, po 10 jednogodzinnych przebiegów z ustalonym ziarnem). To szare pola w filmie i w widoku na żywo. |
| 0 kolizji | W 4 775 przebiegach z ustalonym ziarnem (21,2 mln symulowanych kroków, z losowym wstrzymywaniem od 0 do 5% zaplanowanych ruchów) niezależny weryfikator nie wykrył w żadnym kroku dwóch robotów w jednej komórce, zamiany miejsc ani przeskoku. Planer i reguła wykonania wykluczają to z samej konstrukcji. |
| 0 zakleszczeń w 4 775 przebiegach | Zaobserwowane, nie udowodnione. Po 10-minutowym okresie rozruchu w żadnym przebiegu nie wystąpił 5-minutowy odcinek bez zakończonej kompletacji. Przy czasie kompletacji 6 s żaden jadący robot nie stał dłużej niż 111 s. Przy czasie 24 s najgorszy wynik to 316 s – robot czekający w kolejce do zajętego stanowiska. Wśród 4 775 przebiegów jest 35 przebiegów po 10 symulowanych godzin przy 400 robotach. |
| 0,11 ms | Średni czas planowania na krok dla 400 robotów (Node.js na laptopie z Apple M1 Pro, w trakcie serii symulacji). Ten sam kod potrzebował od 0,13 do 0,4 ms na krok w desktopowym Chrome na tym samym laptopie. |
Kadry
Wypróbuj na żywo
Interaktywny widok działający w przeglądarce. Nic się nie wczytuje, dopóki nie zostanie otwarty.
