Введение
Группы мобильных роботов применяются при обследовании территорий, поиске объектов, складской логистике и мониторинге опасных зон. По мере увеличения числа платформ централизованное планирование становится более требовательным к каналу связи и вычислительным ресурсам. Поэтому интерес представляют распределенные правила, при которых согласованное поведение возникает в результате взаимодействия соседних агентов. Подобную организацию демонстрируют стаи птиц, колонии муравьев и другие биологические системы [1, 2]. Природоподобность, однако, не гарантирует ни безопасность движения, ни оптимальность решения. Алгоритм, успешно описывающий коллективное движение, может давать столкновения в узком коридоре; метод поиска кратчайшего пути сам по себе не обеспечивает его безаварийного выполнения роботом. Для корректного сравнения необходимо различать уровень локального управления, уровень построения маршрутов и уровень назначения задач. Цель статьи – выявить преимущества, ограничения и области применения четырех распространенных природоподобных подходов и предложить единый протокол их испытаний. Работа носит обзорно-методический характер: численные показатели представлены как определения будущих измерений, а не как результаты якобы выполненных запусков. Материалы Пусть группа содержит N роботов, работающих в ограниченной двумерной области Ω с неподвижными препятствиями. Состояние i-го робота определяется положением pᵢ(t), ориентацией θᵢ(t) и линейной скоростью vᵢ(t). Для дифференциальной платформы простейшая кинематическая модель имеет вид: ẋᵢ = vᵢ cos θᵢ, ẏᵢ = vᵢ sin θᵢ, θ̇ᵢ = ωᵢ. (1) Здесь ωᵢ - угловая скорость. Ограничения |vᵢ| ≤ vₘₐₓ и |ωᵢ| ≤ ωₘₐₓ должны в одинаковой мере распространяться на все сопоставляемые методы. Робот i использует сведения только о тех соседях, которые находятся на расстоянии не более R; при этом передача сообщений может происходить с задержкой или прерываться. Такое задание условий позволяет, как представляется, отделить собственно алгоритмические свойства от искусственного преимущества, возникающего за счет доступа к глобальной информации. Существенное значение имеют три требования: безопасность с учетом радиуса корпуса и погрешности локализации, достижение цели за ограниченное время и устойчивость к выпадению отдельных участников. Дополнительно учитываются затраты на вычисления и сообщения - этот блок также включается в оценку методов. Указанные критерии способны входить в противоречие; например, увеличение дистанции безопасности уменьшает плотность построения и, в свою очередь, снижает пропускную способность узкого прохода. Модель К. Рейнольдса описывает согласованное движение через три локальных правила: разделение (предотвращение сближения), выравнивание скорости с соседями и стремление к центру локальной группы [3]. В системах мобильных роботов эти правила преобразуются в желаемый вектор движения, а затем - в допустимые команды vᵢ и ωᵢ. Обобщенная запись имеет вид: uᵢ = kₛ uᵢˢᵉᵖ + kₐ uᵢᵃˡⁱᵍⁿ + kc uᵢᶜᵒʰ + kg uᵢᵍᵒᵃˡ. (2) Коэффициенты k определяют приоритет соответствующего поведения, а последнее слагаемое добавляет движение к цели. Преимущество Boids состоит в простоте локальной реализации: робот не обязан знать полную карту группы. Однако исходная модель не содержит формального доказательства предотвращения столкновений. При чрезмерном усилении когезии группа уплотняется, а при сильном разделении может распадаться. Как показано в теоретической работе Р. Олфати-Сабера, условия устойчивого flocking требуют более аккуратного выбора взаимодействий и потенциалов [4]. Boids особенно уместен для совместного следования в открытом пространстве. В среде с препятствиями необходимы дополнительные правила обхода и механизм разрешения тупиков; иначе локальная реакция на соседей и стену может порождать колебания. Идея потенциальных полей состоит в представлении цели как области притяжения, а препятствий и других роботов – как источников отталкивания. Команда направления формируется по отрицательному градиенту суммарного потенциала. Подход был разработан для обхода препятствий в реальном времени [5] и естественным образом переносится на локальное взаимодействие нескольких платформ: Uᵢ(p) = Uᵢᵃᵗᵗ(p) + ∑ⱼ Uᵢⱼʳᵉᵖ(p), uᵢ = -∇Uᵢ(p). (3) Функции отталкивания обычно ограничиваются зоной чувствительности датчиков. При настройке метод остается понятным, вычислительно экономным и позволяет напрямую включать расстояния безопасности. Его принципиальная слабость - локальные минимумы: робот способен остановиться в точке, где суммарная сила обращается в нуль, хотя цель еще не достигнута. К числу других типичных проблем относят колебания в проходах и зависимость поведения от формы препятствий. Для сопоставления с Boids необходимо задавать одинаковые условия насыщения скорости и аварийного торможения. Допустимо применять потенциальное поле как слой обхода препятствий над групповым регулятором, однако такая схема - уже отдельный гибридный алгоритм. По этой причине в протоколе эксперимента она должна учитываться самостоятельно; иначе сравнение методов утрачивает корректность. Муравьиный алгоритм основан на косвенном обмене информацией посредством цифрового аналога феромонного следа. В исходной постановке М. Дориго и соавторов агенты вероятностно выбирают переходы на графе, а предпочтительные пути усиливаются обновлением следа [6]. Для группы мобильных роботов вершинами графа могут служить обследуемые участки, а ребрами - допустимые переходы; при таком представлении алгоритм выбирает маршруты или распределяет точки посещения. Pᵢⱼ =(τᵢⱼᵅ ηᵢⱼᵝ)/(∑_(k∈Aᵢ)▒(τᵢₖᵅ ηᵢₖᵝ) ) . (4) Здесь τᵢⱼ – интенсивность феромона, ηᵢⱼ – эвристическая привлекательность перехода, Aᵢ – множество допустимых последующих вершин, α и β – параметры. След обновляют с испарением, что позволяет постепенно ослаблять ранее выгодные, но устаревшие маршруты. В реальном робототехническом комплексе цифровой феромон требует хранения и обмена данными; его нельзя считать бесплатным и автоматически распределенным. Сильная сторона метода проявляется при многоточечном обходе и поиске маршрутов на графе. Слабая – задержка до получения качественного решения и необходимость отдельного низкоуровневого предотвращения столкновений. Поэтому сопоставлять муравьиную оптимизацию с Boids по мгновенной угловой скорости без общего исполнительного контроллера методически некорректно. Метод роя частиц (particle swarm optimization, PSO) использует популяцию поисковых решений, каждое из которых изменяется с учетом собственного лучшего положения и лучшего решения группы. Классическая работа Дж. Кеннеди и Р. Эберхарта посвящена численной оптимизации [7]. Применительно к мобильным роботам частица может кодировать набор промежуточных точек маршрута, параметры регулятора либо назначение задач, но не обязательно соответствует физическому роботу. zᵢ(t+1) = w zᵢ(t) + c₁r₁(bᵢ - xᵢ) + c₂r₂(g - xᵢ). (5) В уравнении (5) xᵢ и zᵢ – положение и скорость частицы в пространстве решений, bᵢ и g – лучшие найденные решения, w, c₁, c₂ – параметры, r₁ и r₂ – случайные коэффициенты. Поскольку координаты поисковой частицы не являются непосредственно физическими координатами платформы, результаты PSO следует оценивать по качеству планирования и времени вычисления, а движение – после преобразования найденного решения в траекторию. PSO удобен для непрерывной настройки параметров, но чувствителен к определению целевой функции и ограничениям допустимости. При динамических препятствиях старое лучшее решение может утратить актуальность. Для онлайн-применения важны ограничение количества итераций и повторное планирование. В качестве исследовательской среды можно использовать ARGoS – специализированный модульный симулятор групп роботов, описанный К. Пинчироли и соавторами [8]. Важно зафиксировать версию среды, модель платформы, частоту обновления управления и исходные конфигурации. Для общего сравнения предлагаются три сценария: движение группы к общей цели по свободной площадке; прохождение через коридор с препятствиями; распределенное посещение нескольких целевых участков при частичной потере связи. Поскольку четыре рассматриваемых подхода относятся к разным уровням управления, эксперимент следует строить по единой двухуровневой схеме. На верхнем уровне метод выбирает желаемое направление или маршрут; на нижнем уровне общий для всех методов преобразователь команд учитывает кинематику, насыщение приводов и экстренную остановку. Для ACO и PSO дополнительно фиксируется стоимость построения маршрута, а для Boids и потенциальных полей – стоимость локального пересчета управления. Отдельно можно сопоставить гибриды ACO + потенциальные поля и PSO + Boids. Начальные положения и цели должны быть одинаковыми в парных запусках. Предлагается использовать N = 10, 20 и 40 платформ, три уровня плотности препятствий, два радиуса связи и независимые серии случайных инициализаций. Каждому сочетанию условий целесообразно сопоставить не менее 30 запусков с опубликованными seed. Это проект эксперимента, а не сообщение о выполненной симуляции. Основные показатели определяются следующим образом: время завершения T фиксируют от старта до выполнения задания последним исправным роботом; если достигнут лимит времени, опыт маркируется как незавершенный. Длина пути L понимается как сумма перемещений всех роботов, а число столкновений C учитывает физический контакт; минимальный зазор dₘᵢₙ - это наименьшее расстояние между корпусами. Долю успешных испытаний S определяют отдельно от среднего времени, чтобы исключить искажение, возникающее из-за неуспешных прогонов. S = ((Nₛ)/Nᵣ) · 100 %, L = ∑ᵢ∑ₜ ‖pᵢ(t+Δt) - pᵢ(t)‖. (6) Здесь Nₛ - число успешных запусков, Nᵣ - общее число запусков. Дополнительно требуется учитывать число переданных сообщений B, среднее время процессорного расчета одного шага Q и показатель связности графа взаимодействий. Для многоточечной задачи, при этом, вводится доля охваченных участков K. При анализе целесообразно приводить медиану и межквартильный размах времени и длины пути, а для S - доверительный интервал доли. Таблица 1 – Критерии сопоставления подходов (качественная оценка по механизму работы) Подход Основная роль Преимущества Ключевое ограничение Boids Локальное согласование движения Простота и распределенность Не гарантирует отсутствие столкновений Потенциальные поля Локальный обход и движение к цели Малая вычислительная стоимость Локальные минимумы и осцилляции ACO Маршрутизация на графе Адаптивное накопление решений Обмен следами и время поиска PSO Оптимизация маршрутов и параметров Работа с непрерывными переменными Не является готовым контроллером движения Представленные оценки не образуют численного рейтинга: предпочтение зависит от геометрии среды и постановки задачи. Чтобы таблица не подменяла эксперимент, для каждого метода необходимо публиковать одинаковые определения успеха и отказа, полные параметры настройки, число попыток, вычислительные ресурсы и исходный код сценариев.
Обсуждение результатов сравнительного анализа
Локальные природоподобные правила привлекательны тем, что решение формируется на борту робота, а не требует непрерывного доступа к центральному вычислителю. Вместе с тем простота правил сама по себе не означает устойчивости при высокой плотности группы. Исследования коллективного движения показывают, что математические гарантии требуют конкретных предпосылок о структуре взаимодействий и выборе закона управления [4]. Вклад этого анализа состоит именно в выделении этих предпосылок, а не в объявлении одного алгоритма универсально лучшим. Если основная задача состоит в поддержании согласованного движения группы на открытой площадке, Boids представляется разумным базовым вариантом. При наличии многочисленных локальных препятствий потенциальные поля могут выступать простым реактивным дополнением, однако для них необходимы средства выхода из ловушек. Для обхода набора точек более ценен ACO - его преимущество относится прежде всего к организации маршрута, тогда как PSO естественнее применять для настройки непрерывных параметров планировщика или оптимизации маршрута с ограничениями. Эти выводы выступают аналитическими следствиями устройства методов, а не оценкой эмпирического превосходства по неизмеренным показателям. Отдельное значение имеет масштабируемость. С увеличением N локальные методы выигрывают по объему непосредственно обрабатываемой информации при фиксированном числе соседей, но в тесной геометрии возрастает вероятность конфликтов. Алгоритмы оптимизации, в свою очередь, способны учитывать глобальные затраты; однако при их использовании увеличиваются вычислительная стоимость и передача коллективного состояния - особенно при росте размера группы. Поэтому при переходе от десятка платформ к большим коллективам следует оценивать не только качество пути, но и фактическую нагрузку на сеть. Перспективной представляется иерархическая схема: ACO либо PSO назначает целевые участки и формирует ориентиры, Boids согласует перемещение группы, а локальный барьер безопасности или потенциальное поле предотвращает опасные сближения. Подобная архитектура не устраняет необходимости проверки устойчивости, поскольку взаимодействие ее уровней требует отдельной верификации. Кроме того, вмешательство общего слоя безопасности нужно протоколировать отдельно - иначе высокая успешность будет ошибочно приписана одному только природоподобному модулю.
Заключение
Сравнение показало, что природоподобные алгоритмы управления мобильными роботами решают неодинаковые задачи. Boids ориентирован на распределенное согласование движения, тогда как потенциальные поля предназначены для локального реактивного управления; ACO, в свою очередь, связан с дискретной маршрутизацией. PSO применяется к поиску решений в пространстве параметров и траекторий, поэтому их прямое ранжирование по одному показателю - без общей модели платформы - оказывается некорректным. Для воспроизводимого исследования предложены единая кинематическая модель, три сценария, ограничения связи и перечень показателей: успешность, время, длина пути, столкновения, минимальный зазор, обмен сообщениями и вычислительная нагрузка. Численные результаты могут быть получены после реализации сценариев в ARGoS и проведения повторных прогонов. Наиболее перспективным направлением, как представляется, остается оценка гибридных систем - с ясным разделением планирования, групповой координации и гарантированного локального обеспечения безопасности.