August 20th, 2012

la

Статья в NY Times про нашу компанию

В субботу NY Times напечатала в разделе "Технологии" (но видную с заглавной страницы сайта) большую статью про новое поколение промышленных роботов: "Skilled Work, Without the Worker"

Там есть несколько параграфов, посвящённых роботам в логистике - на примере нашей компании Symbotic (под катом соответствующий отрывок из статьи).

В нашей автоматизированной системе, описанной в статье, есть два основных элемента которые мы регулярно показываем потенциальным заказчикам (и заезжим визитерам, вроде корреспондента NY Times). Первый - сами стеллажи с ящиками, которые кладутся на полки и убираются с полок множеством "ботов" - машинок, быстро бегающих по многоярусной структуре, жужжа и мигая зелёными огоньками. Высокая скорость им на самом деле не нужна - от этого у них большой расход энергии (требующий частую подзарядку, дорогие электромоторы и супер-конденсаторы вместо батареек), и высокий уровень вибрации, делающий сами стеллажи более дорогими и менее долговечными. Но посетители любят когда "машинки" быстро бегают, пусть даже вхолостую.

Но самая главная (и визуально выгодная) часть этой демонстрации - ячейка автоматической паллетизации: это место, где коробки, в определённом порядке, по конвейеру подходят к 6-осному роботу, который подхватывает их и кладёт на палету, как кирпичи на строящееся здание. Для робота положить коробку в заданное нужное место, с хорошей точностью - не проблема. Проблема в том что все "кирпичи" могут иметь разный размер (а так же массу, плотность, твёрдость), различающийся в диапазоне примерно в 10 раз, и придумать правильную кладку для них очень непросто.

Основным элементом этой ячейки, без которого вся эта процедура не имеет смысла, является мой математический алгоритм. Этот алгоритм решает задачу трёхмерной оптимальной упаковки (3d bin-packing problem), своего рода 3-мерный "Тетрис", только с непрерывным диапазоном размеров "кубиков". Я придумал этот алгоритм с нуля и совершенно неожиданно, за короткий срок, примерно полтора года назад. Это была вообще не моя работа, мой основной проект находился в совсем другой области, и сам я никогда не занимался такими задачами. Но подобной задачей вообще-то в мире занимаются немало людей - в академической науке (профессора математики и компьютерных наук со своими пост-доками и аспирантами), и в промышленности - целые коллективы математиков и программистов, в течении многих лет. На эту тему есть тысячи статей, патентов, множество софтверных продуктов, и т.д. Проблема упаковки очень актуальна как в логистике, так и в некототых других приложениях. Количество mixed-case pallets (паллет из смеси разных коробок), которые ежегодно перевозятся в мире со складов в магазины, исчисляется сотнями миллионов. Большинство из них собирается вручную - рабочими, которые берут ящики с полок и кладут на паллеты. Основная проблема, тормозящая переход к автоматизации этого процесса - именно алгоритмы упаковки. До последнего времени упаковки, созданные комьютерной программой, были хуже чем те, что тренированные рабочие делают "на глазок". Только в последние годы начали появляться автоматические системы, способные конкурировать с ручным трудом.

И мой алгоритм, по-видимому, делает это лучше всех в мире (точно не могу сказать, потому что немалая часть информации в этой области - в собственности больших компаний и тщательно охраняется). Фактически мой алгоритм закрыл проблему с точки зрения реальных логистических приложений. Его можно очень долго доводить, улучшать, оптимизировать множество параметров и т.д., но в обозримом будущем навряд ли получится создать алгоритм, радикально лучший чем мой. Когда я создал прототип, показавший его возможности, нашей компанией был срочно организован большой проект вокруг него, и в кратчайшие сроки, чуть более полугода, он был превращён в реальный рабочий продукт. В декабре 2010-го у меня ещё не было идеи этого в голове, а в октябре 2011-го роботы уже упаковывали сотни паллет в день в геометрические структуры, являющиеся результатом моего алгоритма - фантастической сложности, но и высочайшей эффективности. Всё, что связано с этим алгоритмом, у нас в компании проходит под официальным именем "KP" (т.е. мои инициалы). Основной критерий оптимальности - плотность упаковки (т.е. минимизация обьёма пустых мест). Но кроме этого - чуть ли не десяток других важных критериев (устойчивость, распределение массы, смежность продуктов одной категории, наконец, быстрота работы алгоритма, и ещё несколько параметров).

Сама ячейка автоматической паллетизации была создана ещё до моей идеи. Но до моего алгоритма наша корпорация рассчитывала на алгоритм упаковки созданный этой компанией, уже много лет специализирующейся на подобных комбинаторных задачах. Когда же дошло до реальной системы, они не смогли удовлетворить наши требования. Их паллеты получались уродливым, неустойчивым нагромождением ящиков. Эти паллеты было стыдно показывать нашим потенциальным заказчикам. Это не потому что они (компания, делающая этот алгоритм) тупые, а потому что задача, на самом деле, невероятно сложная. После того как мы поняли, что они не справляются, несмотря на постоянные мелкие улучшения, я стал думать над этой задачей, и скоро придумал этот "KP palletizing algorithm". Когда, после его воплощения, людям показывали рядом старые паллеты, и паллеты собранные по моему алгоритму, они начинали смеяться: разница между ними была примерно как между грудой камней и готическим собором.

Под катом - фото, два визитёра из потенциальных заказчиков (начальство одной сети супермаркетов из Голландии) радостно прыгают вокруг такой паллеты, (с наклейкой "KP pallet"):
Collapse )