Robotika · skladové flotily (goods-to-person)
Menej robotov, vyšší výkon
Stovky skladových robotov plánovaných naživo vo vašom prehliadači. Nájdite veľkosť flotily, od ktorej ďalšie roboty začnú výkon znižovať.
Prehľad
Plánovač premávky skladových robotov typu goods-to-person, ktorý beží vo vašom prehliadači. Až 400 simulovaných robotov na mriežke nepretržite dostáva nové úlohy: vyzdvihnúť skladový regál, priviezť ho k jednej zo 16 vychystávacích staníc, počkať, kým sa z neho vychystá, a potom ísť po ďalší. Kolízie sú vylúčené už z princípu konštrukcie a v 4 775 behoch s pevným seedom nedošlo k žiadnemu uviaznutiu. Pridávajte roboty, kým výkon neprestane rásť, potom vyznačte jednosmerné uličky, ktoré plánovač zohľadňuje ako váhy, nie ako záväzné pravidlá, a sledujte, ako sa vrchol krivky posúva.
Na našej skladovej ploche s týmto plánovačom a priemerným časom vychystávania 6 sekúnd dosahuje výkon maximum približne 5 134 pristavení regálov za hodinu. Vrchol je plochý: kdekoľvek od 196 do 235 robotov je výkon v rozmedzí 0,5 % od najlepšieho a vyhladená krivka vrcholí pri 214. Za touto hranicou každý ďalší robot výkon znižuje, a to čoraz rýchlejšie: tesne za vrcholom približne o 1 pristavenie za hodinu na robota, okolo 250 robotov približne o 4 na robota a blízko 400 približne o 7 na robota. Pri 400 robotoch plocha dosahuje o 20,5 % menej než pri optime a 48 % robotov na ceste nie je o nič bližšie k cieľu než pred 8 sekundami.
Ak uličky vyznačíte ako jednosmerné, ako preferencie, nie ako pravidlá, tá istá plocha dosiahne maximum 6 439 pristavení regálov za hodinu so 191 robotmi: o 25,4 % vyšší výkon s o 23 robotmi menej. Východiskom je obojsmerná premávka v jednopruhových uličkách, ktorej sa skutočné dispozície vyhýbajú, takže zlepšenie sa dalo očakávať. Zaujímavé je, kde sa končí. Keď sa vychystávanie spomalí na 24 sekúnd na regál, limit určujú stanice a vyznačenie uličiek zmení výkon najviac o 2,5 % jedným či druhým smerom.
Tieto čísla platia pre mriežkový model s týmto plánovačom. Roboty sa pohybujú synchronizovane o jednu bunku s rozmerom 1 m za sekundu, môžu ísť tesne za sebou a nemajú žiadny čas na zrýchlenie ani otáčanie. Skladové bloky sú plné (roboty pod ne nikdy nevchádzajú), návrat regálu je zahrnutý do ďalšieho vyzdvihnutia a stanice nemajú pruhy na čakanie. Pri najlepšej veľkosti flotily je plocha zaplnená približne na 40 %, oveľa hustejšie, než by jazdila skutočná flotila. Čísla závisia práve od tohto jazdenia tesne za sebou: s variantom plánovača, ktorý drží odstup (žiadny robot nesmie vojsť do bunky v tej istej sekunde, keď ju iný opúšťa), najlepšia z vyskúšaných veľkostí flotily bola 80 robotov s výkonom približne 1 880 za hodinu a pri 160 robotoch premávka úplne uviazne (10 behov s pevným seedom na bod). Skutočné flotily sa zaseknú skôr a iný plánovač by vrchol posunul.
Čo sme vytvorili
- Plánovač pre viac robotov s nepretržitým prideľovaním úloh (lifelong) založený na PIBT (dedenie priorít so spätným navracaním, Okumura a kol.), implementovaný podľa pôvodného článku. Beží vo vlákne Web Worker vo vašom prehliadači a rovnaký kód plánovača bežal vo všetkých simuláciách, z ktorých pochádzajú hlavné čísla na tejto stránke.
- Mäkké jednosmerné uličky: vyznačené smery sa menia na váhy na neorientovanej mriežke. Jazda proti smeru stojí 3 kroky namiesto 1, takže roboty proti smeru stále pôjdu, keď by bola obchádzka dlhšia alebo keď priestor potrebuje iný robot. Editor mapy odmietne každú úpravu, či už zablokovanie, alebo uvoľnenie bunky, po ktorej by niektorá chodba neležala na žiadnej slučke: to je podmienka, ktorú vyžaduje dôkaz dosiahnuteľnosti v PIBT. Overuje ju algoritmus hľadania mostov.
- Synchronizované vykonávanie s náhodným zdržaním. Každú sekundu sa ešte pred pohybom náhodne zadrží 1 % plánovaných pohybov a roboty v rade za zadržaným robotom sa zadržia s ním, takže žiadny robot sa nikdy nepresunie do obsadenej bunky. Každý krok overuje nezávislý kontrolný program.
- Vychystávacie stanice s časom vychystávania náhodne generovaným pre každý regál (gama rozdelenie). V živom zobrazení môžete prepínať priemer medzi 3, 6, 12 a 24 sekundami.
- Séria 4 740 hodinových behov s pevným seedom: 20 až 400 robotov na hlavnej ploche a navyše väčšia plocha na kontrolu. Každý bod má 95 % pásmo spoľahlivosti a vrchol má bootstrapový interval.
Technológie
JavaScript (ES moduly) vo vlákne Web Worker · three.js · vlákna Node.js (worker threads) pre série behov · Python a NumPy pre štatistiku
Čísla
| Číslo | Ako sme ho zmerali |
|---|---|
| 5 134 za hodinu | Vrchol krivky priepustnosti: obojsmerné uličky, priemerný čas vychystávania 6 s. Jeden regál pristavený k vychystávacej stanici je jedno pristavenie; jeden krok na mriežke sa počíta ako jedna sekunda. Ide o maximum vyhladenej krivky (LOESS) preloženej cez 1 400 hodinových behov s pevným seedom pri 20 až 400 robotoch (95 % interval 5 130 až 5 139). |
| 196 až 235 robotov | Plochý vrchol: každá veľkosť flotily v tomto rozsahu je v rozmedzí 0,5 % od najlepšej. Vyhladená krivka vrcholí pri 214 robotoch (bootstrapový interval 213 až 216); iné šírky vyhladzovania posúvajú tento bod medzi 212 a 216. |
| −1 → −7 na robota | Koľko stojí každý pridaný robot, podľa preloženej krivky, s 95 % bootstrapovými intervalmi:
|
| −20,5 % | Priepustnosť pri 400 robotoch (4 080 za hodinu) v porovnaní s vrcholom, na tej istej preloženej krivke. |
| +25,4 % | Zlepšenie na vrchole vďaka vyznačeným jednosmerným uličkám: 6 439 za hodinu pri 191 robotoch. Zmerané na ďalších 1 400 behoch s pevným seedom s rovnakou plochou a nastaveniami; 95 % bootstrapový interval je 25,3 % až 25,5 %. |
| V rozmedzí 2,5 % | Pri čase vychystávania 24 s sa plochy s vyznačenými a nevyznačenými uličkami pri každej veľkosti flotily líšia najviac o 2,5 % (10 behov s pevným seedom na bod). Výkon obmedzuje 16 staníc na 2 400 za hodinu. |
| 35 % → 48 % | Podiel robotov na ceste, ktoré nie sú bližšie k cieľu než pred 8 s, pri 214 a pri 400 robotoch (obojsmerné uličky, vždy 10 hodinových behov s pevným seedom). Vo filme a v živom zobrazení sú to sivé políčka. |
| 0 kolízií | V 4 775 behoch s pevným seedom (21,2 milióna simulovaných krokov, s náhodným zadržaním 0 až 5 % plánovaných pohybov) nezávislý kontrolný program v žiadnom kroku nenašiel robota, ktorý by zdieľal bunku s iným, vymenil si s ním miesto alebo preskočil. Plánovač a pravidlo vykonávania to vylučujú už z princípu konštrukcie. |
| 0 uviaznutí v 4 775 behoch | Pozorované, nie dokázané. Po 10-minútovom nábehu nemal žiadny beh 5-minútový úsek bez dokončeného vychystania. Pri čase vychystávania 6 s nestál žiadny robot na ceste dlhšie než 111 s. Pri čase vychystávania 24 s bol najhorší prípad 316 s: robot čakajúci v rade pri obsadenej stanici. Medzi 4 775 behmi je aj 35 behov po 10 simulovaných hodín pri 400 robotoch. |
| 0,11 ms | Priemerný čas plánovania jedného kroku pre 400 robotov (Node.js na notebooku Apple M1 Pro, počas série behov). Ten istý kód potreboval v desktopovom Chrome na tom istom notebooku 0,13 až 0,4 ms na krok. |
Zábery
Vyskúšajte naživo
Interaktívne zobrazenie, ktoré beží vo vašom prehliadači. Kým ho neotvoríte, nič sa nenačíta.
