Специалисты-математики из Федерального исследовательского центра «Информатика и управление» РАН совместно с коллегами из РФ и Израиля разработали алгоритм CCBS для прокладывания траекторий одновременного движения большого количества роботов. Внедрение этой технологии позволит избежать столкновений машин друг с другом или с людьми.

По данным Российского научного фонда, в результате экспериментальной проверки алгоритма выяснилось, что он значительно превосходит по эффективности уже существующие разработки. В частности, на выполнение миссии с задействованием новой технологии ушло на 20% меньше времени. Представители центра проинформировали о том, что на самом деле создан оптимальный и полный алгоритм планирования траекторий для целых групп агентов, который по всем параметрам превосходит мировые аналоги.

Значительная часть существующих разработок базируется на определённых упрощениях и допущениях, однако для того, чтобы сформировать реальный порядок движения робототехнического устройства, потребуется задействование мощностей квантового компьютера или же развитой нейронной сети. В связи с этим создателям алгоритмов приходилось идти на некоторые хитрости, которые позволили существенно упростить расчёты.

К примеру, такому явлению, как время, в существующих наработках присвоен вовсе не непрерывный, а дискретный характер. Эту величину учёные разбили на промежутки, затрачиваемые на процесс выполнения задач роботом. Если машина закончит свои действия раньше, чем планировалось, она по факту будет простаивать в ожидании следующего шага времени, однако это снижает показатель эффективности устройства. Кроме того, непосредственно траектория движения в традиционных программах представляется как перемещение в одну из сторон по горизонтали или вертикали, без возможности проделывания пути по диагонали или же вообще в произвольном направлении.

Новый же алгоритм CCBS позволяет задавать путь любого типа вне зависимости от конструкции робота. Программа базируется на выявлении потенциальных рисков столкновений, а также на обнаружении небезопасных интервалов во время движения. Таким образом, разработчики методики попросту вычислили промежутки времени, в течение которых устройству нельзя совершать любые действия, поскольку они могут привести к опасному контакту с другими объектами. Программа определяет такие моменты, после чего строит оптимальный маршрут движения робота.