Второй критерий – перекрытие (bridging): коробки верхнего слоя опираются не на одну, а на две (или больше) коробки нижнего слоя, делая их устойчивее. В противном случае может получиться шаткая башня.
Рис. 6. Пример гравитационной устойчивости коробок. Допустим, верхний стек с нижней поверхностью, представленной прямоугольником U1, опирается на три стека из предыдущего слоя, с верхними поверхностями L1, L2 и L3. Пересечения верхнего стека с этими опорами – прямоугольники I1, I2 и I3. Выпуклая оболочка этих опор – полигон ABCDE. Для устойчивости верхнего стека необходимо, чтобы центр прямоугольника U1 (обозначенный *) находился внутри полигона ABCDE
Оба эти фактора можно было рассчитать, если вычислить все пересечения между прямоугольниками, представляющими верхние коробки нижнего слоя, с прямоугольниками, представляющими нижние коробки верхнего слоя. Большинство этих пар прямоугольников не пересекаются даже частично. Но желательно, чтобы каждый прямоугольник верхнего слоя имел два, три или больше ненулевых пересечений с прямоугольниками нижнего – это дает хорошее перекрытие. А для простой гравитационной устойчивости необходимо, чтобы центр каждой коробки верхнего слоя лежал внутри выпуклой оболочки (convex hull), образованной из всех его пересечений с коробками нижнего слоя.
При этом приходилось на каждом шаге использовать более тонкие вычисления, чем формальные математические. Например, если центр верхней коробки располагался всего в 5 мм от края соответствующей выпуклой оболочки, вряд ли такую конфигурацию можно было считать устойчивой, учитывая, что робот кладет коробку не идеально, а с некоторой погрешностью и что масса в коробках не всегда распределена равномерно и симметрично. А если в 10 или в 20 мм – это можно считать надежным положением? Или, например, если верхняя коробка опирается на две из нижнего слоя, но пересечение с одной из них – узкая полоса в один сантиметр? Едва ли это будет хорошее перекрытие, во-первых, потому, что верхняя кромка нижней коробки необязательно образует жесткий угол, на который можно опереться, а во-вторых, верхняя коробка может быть уложена с отклонением на несколько сантиметров от запланированного положения. В этом случае нижние коробки, которые должны быть перекрыты верхней, на самом деле остаются не связанными друг с другом и могут стать основанием неустойчивых колонн.
Приходилось по нескольку раз в день изобретать методы, позволяющие не только учитывать строгие неравенства, но и опираться на размытую логику (fuzzy logic), с допусками и люфтами, с плавным переходом результата от нуля до единицы, так, чтобы можно было учитывать реалии физического мира, а не математических абстракций.
Одна только работа по вычислению устойчивости коробок и степени перекрытия между слоями, а также оптимальному выбору одной из четырех возможных симметрий в нормальных условиях требовала месяцев теоретического анализа и экспериментов, даже если опустить физические тесты. Мне удалось сделать эту функциональность, в основном сохранившуюся и в более поздних версиях рабочего кода, практически за неделю.
И так было на каждом шагу. Одной из важных проблем, с которыми я столкнулся, было планирование нескольких палет из одного заказа. Ситуация довольно типичная: в Ньюбурге львиная доля заказов из одного супермаркета составляла намного больше, чем одну палету, – как правило, от четырех до десяти. Но только часть из этого объема проходила через нашу автоматизированную систему – остальные палеты собирали традиционным способом вручную, в основном в ночную смену. Так что объем одного заказа для нашей системы мог, как правило, уложиться в две или три палеты.
Возникал вопрос: как разделить весь заказ на минимальное число палет (помимо труднейшей задачи построения каждой отдельной палеты)? В полнейшем цейтноте я разрабатывал алгоритм, способный делать это наилучшим образом. В результате я пошел по довольно наивному пути, не требующему большого объема дополнительного дизайна. У меня к этому времени уже достаточно хорошо работали все шаги построения слоев из стеков: отбор части заказа для слоя, вычисление наилучших коллекций стеков и их двумерная упаковка. Так по одной и той же схеме складывались слой за слоем, пока не исчерпывалось число оставшихся коробок, и последний слой был уже не плоским, а собранным из стеков разной высоты.
Собрав таким образом палету (зачастую многометровой высоты), я разделял ее на несколько: составлял комбинации слоев с общей высотой, равной максимально допустимой высоте палеты или чуть ниже, и общим весом, не превышающим максимальный (обычно мы использовали значение 1,5 т – средняя грузоподъемность вилочного погрузчика). Это напоминало поиск комбинаций прямоугольников для заполнения ряда в двумерной упаковке. В большинстве случаев можно было найти много комбинаций слоев в интервале их суммарной высоты. Мой алгоритм отбирал определенное число таких комбинаций и останавливался на той из них, которая оптимально совмещала товары близких категорий, то есть включала минимальное число групп товаров и в общем случае минимальную «энтропию» – смесь многих групп на одной палете.
Так я отбирал комбинацию слоев для одной палеты; затем процедура повторялась с оставшимися слоями для следующей, и так до конца. Последняя палета, как правило, была небольшого размера – в среднем в половину максимальной высоты.
Но и это было еще не последним шагом в алгоритме. После отбора слоев нужно было определить порядок их размещения на палете, от низа до верха.
В целом логика была достаточно естественной: снизу должны размещаться самые плотные слои, а сверху – самые легкие. Однако процедуру усложняла необходимость учитывать устойчивость каждой коробки и максимизацию перекрытия между слоями.
Кроме того, приходилось иметь дело с десятками особых случаев, требующих специальных процедур. Например, в заказе имеется одна большая (по всем измерениям) и тяжелая коробка. В нашей практике подобные упаковки с соками, сидром или даже столовым вином попадались регулярно. С огромной вероятностью такая коробка не попадет в стек с другими, так как слишком отличается от них по длине и ширине, или, если попадет, высота такого стека не обязательно окажется в числе отобранных интервалов высот. Если следовать обычной процедуре построения слоев, эта коробка всякий раз будет оказываться лишней и не войдет в данный слой палеты. В конце концов она попадет в самый верхний слой, приминая своим весом нижние коробки и располагая центр тяжести палеты слишком высоко. Чтобы этого избежать, мне пришлось придумывать вариацию алгоритма, при которой подобные коробки попадали бы в один из нижних слоев той же высоты, что и сама коробка, или один из возможных стеков с ее участием. Такие особые условия встречались на каждом шагу, и приходилось очень быстро – за день-два – изобретать учитывающие их логические разветвления.
В середине марта состоялись первые испытания моего алгоритма непосредственно в нашей системе в Ньюбурге, где палеты уже строили роботы, а не сотрудники. В общей сложности шесть человек из нашей лабы и «КейсПика» были задействованы в этих испытаниях в течение трех дней. Целью было подобрать довольно типичные комбинации, коробок, встречающиеся в наших заказах, в том числе очень непростые для алгоритма. Например, заказ, где много мелких коробок, или где перемешаны крупные и мелкие, или плоские и высокие. Или заказ, где фигурируют упаковки всего лишь нескольких размеров – например, 30 коробок одного товара, 25 – другого и 20 – третьего.
Тестировщики подбирали комбинации коробок; я же должен был прокрутить их через мой код и выдать план палеты (координаты и ориентацию каждой коробки) в формате, понятном софтверу робота, строящего палету. После этого план построения палеты загружался в чрево всей системы автоматизированного склада, чтобы дать команды конкретным ботам на разных ярусах стеллажей привезти коробки в определенной последовательности к вертикальному конвейеру MVC.
Как и ожидалось, испытания скакали по кочкам недоработок и непредвиденных осложнений. В ряде случаев палеты были запланированы с определенными товарами в количестве нескольких или даже десятка и более коробок. При построении выяснялось, что система не в состоянии доставить такое число коробок на палетизацию. Общее число доступных коробок данного товара во всей системе хранения было меньше, чем их число на палете, хотя при ее планировании мы исходили из количества, указанного в базе данных. В других случаях погрешности округления в моем алгоритме (программа роботов оперировала целыми миллиметрами) приводили к тому, что в планах палет соседние коробки имели крошечное, миллиметровое пересечение в пространстве, и робот выплевывал планы палет обратно, отказываясь строить их. Приходилось срочно поправлять детали алгоритма, корректировать базу данных всей системы и придумывать дополнительные трюки. Вся команда, участвующая в тестах, активно и грамотно помогала преодолевать трудности – варьировать список заказа на палету, хакать софт робота и делать другие срочные поправки.
И испытания двигались вперед. Каждый раз из ячейки палетизации на оборачивание стягивающей пленкой выходили палеты крепче и красивее тех, что делались по алгоритму «ТОПС Инжиниринг». В одном из тестов в качестве заказа использовалось множество самых мелких коробок в нашем наборе товаров. В результате запланированная палета включала более двухсот коробок – намного больше, чем любая собранная до сих пор. Слой за слоем жужжащий робот укладывал коробки на растущую палету. Из-за дефектов упаковок и небольших ошибок измерения проблемы копились по мере построения слоев: они становились все более неровными, отдельные коробки робот укладывал не вполне аккуратно, и те выпирали за периметр палеты. Но вот последняя коробка была уложена. Огромная палета начала двигаться к выходу по цепному конвейеру. Пленкой ее оборачивали в самом конце процесса, и само движение по конвейеру производило немалую вибрацию. С замиранием сердца я вместе со всеми окружающими смотрел, как в любой момент этого движения (оно занимало около 20 секунд) палета, построенная на грани устойчивости, могла рухнуть, разбросав коробки по всей ячейке и измазав ее подвижные части майонезом и томатным соусом из лопнувших упаковок. Но палета, дрожа и покачиваясь, прошла через два поворота конвейера до выхода из ячейки. Ни одна коробка не упала. С полдюжины техников, работающих на разных участках процесса, кучковались рядом и пристально следили за ней, некоторые – даже с открытыми ртами. Они никогда еще не видели такой высокой, плотной и стройной палеты, выходящей из нашей автоматизированной системы.