Робототехніка · складські парки роботів («товар до людини»)
Менше роботів, вища продуктивність
Сотні складських роботів, чий рух планується наживо у вашому браузері. Знайдіть розмір парку, з якого додавання роботів починає знижувати продуктивність.
Огляд
Планувальник руху для складських роботів, що працюють за принципом «товар до людини», просто у вашому браузері. До 400 змодельованих роботів на сітці безперервно отримують нові завдання: забрати мобільний стелаж, привезти його до однієї з 16 станцій комплектації, зачекати, поки з нього відберуть товар, а потім забрати наступний. Зіткнення виключені за побудовою, а в 4 775 запусках із фіксованим seed не сталося жодного взаємного блокування. Додавайте роботів, доки продуктивність не перестане зростати, потім розмітьте односторонні проходи — планувальник враховує їх як ваги, а не як обов’язкові правила, — і дивіться, як зміщується вершина кривої.
На нашому складі з цим планувальником і середнім часом відбору 6 секунд продуктивність сягає максимуму — близько 5 134 подач стелажів на годину. Вершина пласка: за будь-якої кількості від 196 до 235 роботів результат у межах 0,5 % від найкращого, а згладжена крива досягає піку на 214. Далі кожен робот знижує продуктивність, і дедалі сильніше: близько 1 подачі на годину за кожного робота одразу після вершини, близько 4 на робота в районі 250 і близько 7 на робота поблизу 400. За 400 роботів склад видає на 20,5 % менше, ніж у найкращій точці, а 48 % роботів у русі не ближчі до своєї цілі, ніж 8 секунд тому.
Розмітьте проходи як односторонні — як побажання, а не правила, — і той самий склад досягає максимуму 6 439 подач стелажів на годину з 191 роботом: продуктивність на 25,4 % вища, а роботів на 23 менше. Базовий варіант — двосторонній рух в однополосних проходах, якого реальні планування складів уникають, тож виграш очікуваний. Цікаво інше — де він закінчується. Коли відбір сповільнюється до 24 секунд на стелаж, межу задають станції, і розмітка змінює продуктивність щонайбільше на 2,5 % у будь-який бік.
Ці числа стосуються сіткової моделі з цим планувальником. Роботи рухаються синхронно, на одну клітинку розміром 1 метр за секунду, можуть їхати впритул один за одним і не витрачають часу на розгін чи поворот. Блоки зберігання суцільні (роботи ніколи не проїжджають під ними), повернення стелажа на місце об’єднано з наступним рейсом по стелаж, а станції не мають смуг для черги. За найкращого розміру парку склад заповнений приблизно на 40 % — набагато щільніше, ніж працював би реальний парк. Ці числа залежать від руху впритул: з варіантом планувальника, що тримає дистанцію (жоден робот не може заїхати в клітинку в ту саму секунду, коли її залишає інший), найкращим із розмірів парку, які ми запускали, було 80 роботів — близько 1 880 подач на годину, а за 160 роботів настає повний затор (по 10 запусків із фіксованим seed на точку). У реальних парках затори виникають раніше, а інший планувальник змістив би вершину.
Що ми створили
- Планувальник для групи роботів із безперервним надходженням завдань (lifelong) на основі PIBT (успадкування пріоритетів із поверненням, Okumura та ін.), реалізований за статтею. Він працює у Web Worker у вашому браузері, і той самий код планувальника виконав усі симуляції, на яких ґрунтуються основні числа цієї сторінки.
- М’які односторонні проходи: розмічені напрямки перетворюються на ваги на неорієнтованій сітці. Рух проти напрямку коштує 3 кроки замість 1, тож роботи все одно їдуть проти нього, коли об’їзд був би довшим або коли місце потрібне іншому роботу. Редактор карти відхиляє будь-яку зміну — блокування чи розблокування клітинки, — після якої якийсь коридор опинився б поза всіма циклами: саме цієї умови потребує доведення досяжності в PIBT. Це перевіряє пошук мостів у графі.
- Синхронне виконання з випадковими затримками. Щосекунди, перш ніж будь-хто рушить, 1 % запланованих переміщень випадково затримується, а роботи, що стоять у черзі за затриманим роботом, затримуються разом із ним, тож жоден робот ніколи не опиняється в зайнятій клітинці. Незалежний валідатор перевіряє кожен крок.
- Станції комплектації, де час відбору для кожного стелажа вибирається випадково (гамма-розподіл). В інтерактивній візуалізації середнє значення можна перемикати між 3, 6, 12 і 24 секундами.
- Перебір із 4 740 годинних запусків із фіксованим seed: від 20 до 400 роботів на основному складі, а також більший склад для перевірки. Кожна точка має довірчі смуги 95 %, а вершина — бутстреп-інтервал.
Стек технологій
JavaScript (ES-модулі) у Web Worker · three.js · Node.js worker threads для переборів · Python і NumPy для статистики
Цифри
| Показник | Як ми це виміряли |
|---|---|
| 5 134 на годину | Вершина кривої пропускної здатності: двосторонні проходи, середній час відбору 6 s. Один стелаж, поданий на станцію комплектації, — це одна подача; один крок сітки вважається однією секундою. Це максимум згладженої кривої (LOESS), побудованої за 1 400 годинними запусками з фіксованим seed з кількістю роботів від 20 до 400 (інтервал 95 %: від 5 130 до 5 139). |
| Від 196 до 235 роботів | Пласка вершина: будь-який розмір парку в цьому діапазоні дає результат у межах 0,5 % від найкращого. Згладжена крива досягає піку на 214 роботах (бутстреп-інтервал від 213 до 216); за іншої ширини згладжування ця точка зміщується в межах від 212 до 216. |
| −1 → −7 на робота | Скільки коштує кожен доданий робот, за апроксимаційною кривою, з бутстреп-інтервалами 95 %:
|
| −20,5 % | Пропускна здатність за 400 роботів (4 080 на годину) порівняно з вершиною, за тією самою апроксимаційною кривою. |
| +25,4 % | Виграш у вершині завдяки розміченим одностороннім проходам: 6 439 на годину з 191 роботом. Виміряно ще на 1 400 запусках із фіксованим seed на тому самому складі з тими самими налаштуваннями; бутстреп-інтервал 95 % — від 25,3 % до 25,5 %. |
| У межах 2,5 % | За часу відбору 24 s склади з розміткою і без неї відрізняються не більш ніж на 2,5 % за будь-якого розміру парку (по 10 запусків із фіксованим seed на точку). 16 станцій обмежують продуктивність до 2 400 на годину. |
| 35 % → 48 % | Частка роботів у русі, які не ближчі до своєї цілі, ніж 8 s тому, за 214 і за 400 роботів (двосторонні проходи, по 10 годинних запусків із фіксованим seed). Це сірі клітинки у фільмі та в інтерактивній візуалізації. |
| 0 зіткнень | У 4 775 запусках із фіксованим seed (21,2 мільйона змодельованих кроків, із випадковою затримкою від 0 до 5 % запланованих переміщень) незалежний валідатор на жодному кроці не виявив двох роботів в одній клітинці, обміну місцями чи перестрибування. Планувальник і правило виконання виключають це за побудовою. |
| 0 взаємних блокувань у 4 775 запусках | Спостережено, а не доведено. Після 10-хвилинного прогріву в жодному запуску не було 5-хвилинного відрізка без завершеного відбору. За часу відбору 6 s жоден робот у русі не стояв на місці довше ніж 111 s. За часу відбору 24 s найгірший випадок — 316 s: робот чекав у черзі до зайнятої станції. Серед 4 775 запусків — 35 запусків по 10 змодельованих годин кожен із 400 роботами. |
| 0,11 ms | Середній час планування одного кроку для 400 роботів (Node.js на ноутбуці Apple M1 Pro, під час перебору). Той самий код у настільному Chrome на цьому ноутбуці витрачав від 0,13 до 0,4 ms на крок. |
Кадри
Спробуйте наживо
Інтерактивна візуалізація, що працює у вашому браузері. Нічого не завантажується, доки ви її не відкриєте.
