Исследователи MIT разработали новый децентрализованный алгоритм планирования действий для группы роботов и представят его на Международной конференции по робототехнике и автоматизации в мае этого года.

Есть две категории алгоритмов для планирования команд роботов: децентрализованные и централизованные. В децентрализованных алгоритмах каждый робот делает индивидуальные решения на основе местных наблюдений. В централизованных алгоритмах один компьютер способен принимать решения для всей команды.

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

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

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

«Это действительно захватывающий результат, потому что он сочетает в себе очень много сложных задач. Группа роботов имеет локальную цель и должна действовать в формировании глобальной цели, двигаясь вперед. Теперь вы можете позволить им действовать в мире не только с неподвижными препятствиями, но и с неожиданными динамическими изменениями, и у вас есть гарантия, что они сохранят свои локальные и глобальные цели. Они, конечно, должны будут сделать некоторые отклонения, но они будут минимальны», - говорят ученые MIT.

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

Ученые Даниела Рас, Алонсо-Мора, и их команда открыли способ уменьшения вычислительной нагрузки с помощью согласованного планирования. Они в основном сосредоточены на установлении факта, что каждый робот на основе своих собственных наблюдений планирует двигаться в область свободную от препятствий и отправляет эту карту своим ближайшим соседям. Получив карту от соседа, робот определяет маршрут на основе своих собственных знаний, а затем передает эту информацию дальше.

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

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

Алгоритм предполагает, что движущиеся препятствия имеют постоянную скорость, которая не всегда присутствует в реальном мире. Для каждого робота займет всего секунду, чтобы обновить его карту максимальное число раз. Этот период времени является достаточно коротким, и за это время вряд ли могут произойти какие-то существенные изменения.

Основываясь на последней карте, каждый робот определяет траекторию, которая поможет максимально увеличить свою глобальную и местную цель.