2 ноября в онлайн-режиме прошла очередная конференция для малого и среднего бизнеса DataStart, посвящённая науке о данных, машинному обучению и нейросетям. На её счету — уже 13 заседаний. С 2017 года формат мероприятия неоднократно менялся, из Санкт-Петербурга DataStart переехала в Москву, затем — в интернет, количество сессий в году варьировалось от одного до трёх, увеличивался охват тем...
Вот и Константин Яковлев заглянул на огонёк, чтобы поговорить о наболевшем. «Эффективные методы многоагентного планирования для задач автоматизированной логистики» (ссылка) — невероятно интересное, но и малоизвестное направление вне профессиональных кругов. Например, гигант e-коммерции Amazon буквально на днях выложил видео с андроидами: те, мол, сортируют посылки и тянут их на конвейер своими подобиями рук. Мечтать не вредно, но реальные склады пока могут рассчитывать лишь на услуги рельсовых роботов, которые перетаскивают товары из одного угла в другой. Сам Amazon уже пытается внедрять колёсных роботов Kiva Systems, но и там без помощи человека не обойтись. А уж для эффективного функционирования необходима крайне отлаженная программа.
Нужно выстроить систему многоагентного планирования путей так, чтобы любой мобильный агент как можно быстрее и безопаснее выстроил маршрут от начальной точки (условно говоря, зарядки) до конечной точки (злосчастной бандероли). Для чего исследователи придумали два способа: централизированный и децентрализированный. Центральный планировщик полностью контролирует подопечных, передаёт информацию о целях и решает, что делать остальным в любой неловкой ситуации. Имеющиеся у него данные позволяют оптимизировать решения и минимальное время выполнения. Что не приведёт к коллизиям и дедлокам, он молодец! Жаль, вычислительно неэффективен, и просчитать совокупность траектории на 1000-1000000 роботов в режиме реального времени он попусту не успевает.
В демократичном децентрализованном варианте каждый агент сам решает, куда ему податься, ориентируясь на локальное наблюдение. Да, траектории зачастую далеки от оптимальных, агенты петляют кругами, пихаются-толкаются в узком коридоре вместо того, чтобы выполнить задание, поскольку не обладают полнотой информации. Mission not possible? Но не зря же существуют различные техники обучения, в частности, обучение с подкреплением, которому 71 отдел посвятил столько трудов. На практике децентрализация работает гораздо эффективнее.
Тем не менее, нынче проблему на складах принято решать именно в централизованном режиме быстрыми алгоритмами приоритизированного планирования: роботам назначают приоритеты, в соответствии с которыми они и выдумывают траектории. Увы, несмотря на простоту, сей подход способен просчитать далеко не все ситуации, что Константин наглядно и продемонстрировал на графике столкновения двух «умных» погрузчиков, когда ни один из них не способен ни пройти кратчайшим путём, ни свернуть за угол, чтобы уступить дорогу. Хотя на автоматизированных складах подобная ситуация просчитывается сразу, и к точкам сортировки посылок можно подойти сразу с четырёх сторон, что отметает подобную ересь. Это — правильно сформированные структуры.
Автор упомянул и два других метода. В частности, конфликтно-ориентированный поиск — не столь популярный, но дающий гарантированно оптимальное решение. Он представляет собой двухуровневый алгоритм: на верхнем уровне идёт поиск конфликтов и наложение ограничений, на нижнем — планирование траекторий для одного-единственного агента в соответствии с ограничениями. Строят его до тех пор, пока не будет найден бесконфликтный маршрут. В итоге мы не потеряем альтернативу, но сильно потеряем во времени.
Второй, Lifelong MAPF, имеет ту же алгоритмическую составляющую, но при участии двух параметров: частота перепланирования и горизонт бесконфликтности. Они позволяют строить кратковременные планы, которые меняются каждые несколько минут в т. н. window (окне бесконфликтного планирования). По отдельной задумке, роботов вообще можно не сильно изводить составлением маршрутов, если в полу проделать кучу дырок и раздать задания типа «сортировка почтовых отправлений по городам». Скинул посылку в дырку — уже молодец!
Но мы лишь кратко изложили аж часовой доклад. Прослушать запись длинной и крайне увлекательной лекции Константина можно на самом сайте бесплатной конференции. Правда, за отдельную плату, поскольку «бесплатным» организаторы считают только прямой эфир. Можно воспользоваться опцией «получить записи выступлений четырёх спикеров прошлой конференции», а можно и поискать презентацию в ином формате в нашем безразмерном архиве, где найдётся всё!
Ссылки по теме: