Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 1,279
A HYBRID NEURODYNAMIC ALGORITHM FOR TASK ALLOCATION IN GROUPS OF MOBILE ROBOTS UNDER OBSERVATION UNCERTAINTY WITH PARAMETRIC TUNING
Введение
В прикладных задачах при ограниченных вычислительных ресурсах бортовой системы управления распределение целей и координация перемещений в группах мобильных роботов выполняются в реальном времени на основе данных сенсорных систем [1, 2]. Ошибки в работе датчиков и динамические изменения внешней среды приводят к расхождению наблюдаемых и истинных координат. Это ухудшает качество распределения роботов по целям, увеличивает разброс результатов, а также может приводить к росту суммарной длины перемещений [3, 4].
Нейродинамические методы на основе сети Хопфилда применяются к комбинаторным задачам как методы минимизации энергетического функционала [5, 6]. Вместе с тем такие методы требуют точной настройки параметров [7, 8]. В задачах распределения целей между роботами по зашумленным наблюдениям классические схемы чувствительны к выбору параметров и нередко требуют ручного подбора. В результате ухудшается качество решений и возрастает их вариативность, особенно при увеличении размерности задачи [8–10]. В работах по динамическому распределению целей в условиях неопределенности используются обучаемые механизмы подстройки стратегий назначения, в частности метаобучение [11, 12]. Для децентрализованного назначения целей применяются модели на графовых нейронных сетях [13]. Подходы верхнего уровня реализуются на основе гиперэвристик и иерархических схем управления поиском [14].
В продолжение работ [10, 15] в данной статье рассматривается двухуровневая схема вычислений. Нейродинамическое ядро формирует решение для одношагового назначения на каждом цикле перепланирования, а верхний уровень настраивает параметры по выборке сценариев неопределенности для последующей работы в контуре управления.
Цель исследования – разработать двухуровневый алгоритм распределения целей между мобильными роботами при погрешностях измерения координат на основе нейродинамической модели с предварительной настройкой параметров.
Материалы и методы исследования
Рассматривается группа из m мобильных роботов и множество невыполненных целей Gk на каждом цикле перепланирования k. Под циклом перепланирования понимается один такт работы алгоритма, в котором по текущим наблюдениям формируется одношаговое назначение и обновляется множество невыполненных целей. Истинные координаты роботов rik и целей gjk принадлежат ℝ2. Алгоритму доступны наблюдаемые координаты 
, формируемые по данным измерений. Одношаговое распределение на каждом цикле описывается бинарной матрицей
при следующих ограничениях:
.
Допускается отсутствие назначений для части роботов и целей, что отражает реальную ситуацию простоя роботов и неполного покрытия задач на отдельных этапах. При этом число назначаемых пар на каждом цикле не превышает
.
Значение критерия оптимизации на каждом цикле определяется суммой попарных расстояний, вычисляемых по наблюдаемым координатам:
nk = |Gk|.
Показатель качества определяется выражением
где Tep – максимальное число циклов за прогон моделирования. Выбор Xk соответствует схеме скользящего горизонта. На каждом цикле распределение формируется по наблюдаемым координатам.
Неопределенность наблюдений задается аддитивным возмущением координат, что позволяет отдельно оценить влияние шумов измерения
,
где εr,ik и εg,jk – гауссовские двумерные векторы ошибок с нулевым средним и дисперсией σ2, то есть
εr,ik, εg,jk ~ Ɲ(0,σ2I2).
В вычислительных экспериментах параметр σ принимал значения
,
что соответствует набору значений дисперсии
.
Значение σ = 0 соответствует идеальным наблюдениям без искажений. Значения σ = 0,1_0,3 соответствуют слабому и умеренному уровню погрешностей измерения, а значения σ = 0,5 и σ = 0,8 – повышенному уровню зашумления, при котором ошибки наблюдений существенно влияют на формирование назначений в контуре перепланирования. Стохастическая компонента нейродинамического алгоритма описывается случайным процессом ξ. Целевым критерием служит значение 
, оцениваемое методом Монте-Карло по множеству реализаций неопределенности.
Для аналитического описания одношагового назначения используется релаксированная постановка с энергетической функцией E(X). На каждом цикле k вводится матрица состояний
.
В дальнейшем индекс k опускается и используются обозначения
, 
.
Энергетическая функция задается суммой целевого слагаемого, штрафных слагаемых, уℝчитывающих только нарушение ограничений «не более одного», а также слабого слагаемого, приближающего компоненты решения к значениям 0 и 1:
Выбранная форма энергетической функции допускает неполные назначения и не вводит штрафов за нулевые строки и столбцы, возникающие при простое роботов или при наличии невыполненных целей. Ограничения учитываются штрафными слагаемыми в энергетической функции. Данная постановка задает энергетический функционал одношагового назначения в явном виде. Основные вычислительные эксперименты выполнены на основе компактной вычислительной реализации нижнего уровня, а в открытом репозитории также приведена матричная реализация соответствующего энергетического функционала [16].
Динамика системы определяется потенциалами U = [uij] и сигмоидальной связью состояния с потенциалом
.
Далее запускается итерационный процесс t = 0,1,…,I–1 по правилу:
где μ > 0 – шаг, T > 0 – параметр температуры, ξij(t) – независимые случайные величины (например, Ɲ(0,1)), β ≥ 0 – интенсивность стохастической компоненты.
Производная имеет вид
где 
, 
, 1[∙] – индикатор условия (1 [истина] = 1, 1 [ложь] = 0).
При β = 0 динамика соответствует дискретному спуску по E при малом μ; при β > 0 реализуется стохастический эвристический поиск, для которого монотонность E не гарантируется. Остановка итерационного процесса определяется критерием
X(t + 1) – X(t)∞ ≤ εstop или t = I – 1.
Условия устойчивости и сходимости нейродинамики в данной работе могут быть описаны следующим образом. При β = 0 и достаточно малом шаге μ детерминированная часть итерационного процесса соответствует дискретному спуску по энергетической функции E(X), поэтому в этом случае можно ожидать невозрастания E(X) и перехода системы к стационарному состоянию. При β > 0 в уравнение обновления входит стохастическая компонента, поэтому монотонность E(X) уже не гарантируется, и алгоритм следует рассматривать как стохастическую эвристическую процедуру поиска. Полное формальное доказательство сходимости для модифицированной схемы с шумовой составляющей и последующим приведением решения к допустимому бинарному виду в настоящей работе не приводится. Вместе с тем на практике работоспособность вычислительной схемы обеспечивается ограниченностью значений состояний после сигмоидального преобразования и завершением итераций либо по критерию остановки, либо по достижении предельного числа итераций. В дальнейшем под сходимостью понимается достижение стационарного режима либо режима, при котором выполняется критерий остановки.
После остановки полученное решение приводится к допустимому бинарному виду, в результате чего формируется матрица назначения X, затем применяется пороговое правило отбора
: 
Далее, для каждого робота выбирается цель с максимальным значением xij среди еще не назначенных целей. В случае конфликта за одну цель предпочтение отдается роботу с меньшим dij, а при отсутствии кандидатов робот остается без назначения на цикле. Это правило гарантирует выполнение ограничений ≤ 1 по строкам и столбцам, не гарантируя достижения глобального оптимума.
Предложенная выше постановка определяет общий аналитический вид энергетического функционала и итерационной схемы одношагового назначения. В программной реализации нижнего уровня используется компактная вычислительная схема для выполнения основных серий вычислительных экспериментов. При этом на верхнем уровне настраивается не весь набор параметров общей аналитической записи E(X), а только реализованный в алгоритме вектор параметров θ = (α, bR, T, τ), непосредственно влияющий на формирование активного множества целей и последующее приведение решения к допустимому бинарному виду. Выбор вектора параметров осуществляется путем минимизации выборочной оценки:
где Ωtrain – обучающая выборка сценариев неопределенности, Strain = |Ωtrain| – число сценариев в этой выборке, а J(θ;ω) – значение критерия при фиксированных параметрах θ и фиксированном сценарии ω. Θ задает допустимые интервалы изменения настраиваемых параметров α, bR, T и τ:
, 
,
, 
.
Параметр α определяет масштаб весовых связей в нижнем уровне и тем самым влияет на чувствительность вычислительной схемы к различиям между конкурирующими вариантами назначения. Параметр bR задает положительное смещение для нейронов, соответствующих роботам, и препятствует вырождению решения в состояния с низкой активностью этих нейронов. Параметр T задает температуру в сигмоидальной функции активации: при меньших значениях T переходы становятся более резкими, а при больших – более сглаженными. Параметр τ задает порог отбора активных целей после завершения нейродинамики: увеличение τ уменьшает число целей, передаваемых на этап формирования допустимого назначения, а уменьшение τ расширяет множество рассматриваемых целей. Тем самым параметры α, bR и T определяют характер нейродинамического процесса, а параметр τ – правило формирования активного множества целей. Вычислительная трудоемкость одного цикла нижнего уровня определяется построением связей для текущего множества целей и выполнением ограниченного числа итераций нейродинамического обновления. Верхний уровень выполняется на этапе предварительной настройки, поэтому его вычислительные затраты не ограничивают работу алгоритма в реальном времени.
Результаты исследования и их обсуждение
Вычислительные эксперименты выполнены в MATLAB R2020a на имитационной модели распределения заданий на плоскости. Программная реализация размещена в открытом репозитории [16]. Расчеты выполнены на основе компактной вычислительной реализации нижнего уровня; в репозитории также приведена матричная реализация энергетического функционала. Для запуска скриптов использовался компьютер с процессором Intel Core i5 (4 ядра, 3,0 ГГц), объемом ОЗУ 8 ГБ и ОС Windows 10 (64-разрядной). В каждом прогоне моделирования координаты роботов и целей генерировались случайно в области [0;L]×[0;L], где L = 10; при этом m = 10; n = 30. Алгоритм функционировал по циклам: на каждом из них по наблюдаемым координатам 
формировалось одношаговое назначение «робот-цель», после чего назначенные цели считались выполненными, а координаты роботов обновлялись путем перемещения в соответствующую точку. Прогон моделирования завершался после выполнения всех целей либо по достижении заданного числа циклов Tep.
Для раздельной оценки влияния погрешностей измерения и качества распределения назначение целей роботам строилось по , а показатель качества вычислялся по фактической суммарной длине перемещений. Модель измерений задавалась в виде аддитивного гауссовского шума Ɲ(0,σ2I2) по каждой координате.
а) 
б) 
Рис. 1. Графики зависимостей J от σ (а); графики зависимостей времени tep от σ (б) Примечание: составлен авторами по результатам вычислительных экспериментов
а) 
б) 
Рис. 2. Графики J при разных m (а); графики времени tep при разных m (б) Примечание: составлен авторами по результатам вычислительных экспериментов
Сравниваются три варианта нейродинамического алгоритма: 1) классический [10]; 2) модифицированный с фиксированными параметрами; 3) гибридный, в котором параметры настраиваются методом случайного поиска. Для гибридного варианта рассматривалось 45 случайно сформированных наборов параметров, значения которых выбирались независимо по равномерному закону в пределах допустимых интервалов настройки. Для гибридного варианта настройка параметров выполнялась на обучающем наборе из 15 сформированных сценариев неопределенности. После завершения настройки сравнение вариантов проводилось на общих сериях независимых прогонов, сформированных по одинаковой схеме. В дальнейшем использовался набор параметров, для которого среднее значение критерия на обучающем наборе сценариев было минимальным.
Цель вычислительных испытаний – проверить процедуру назначения по зашумленным наблюдениям. Дополнительно показаны траектории, формируемые в процессе перепланирования. Качество распределения оценивается интегральным показателем, отражающим общую длину перемещений. Основными показателями служили математическое ожидание суммарной длины пути группы за прогон J и время одного прогона tep. Время измерялось с использованием функций tic/toc MATLAB. Для каждой точки параметров выполнялось K = 30 независимых прогонов, а 95 %-й доверительный интервал для среднего строился по нормальному приближению.
Чувствительность показателей к шуму наблюдений оценивалась по зависимостям J и tep при фиксированных настройках
(рис. 1).
Во всем рассмотренном диапазоне σ модифицированный алгоритм обеспечивает меньшие значения J по сравнению с классическим, при этом в ряде режимов наблюдается частичное перекрытие доверительных интервалов. Гибридный алгоритм по качеству сопоставим с модифицированным вариантом с фиксированными параметрами, при этом наблюдаемые различия в большинстве случаев укладываются в доверительные интервалы. Время tep при рассматриваемых размерах задач имеет миллисекундный порядок, а его изменение при росте σ не является определяющим на фоне ограничения числа итераций нейродинамики (не более 250 итераций), рис. 1, б.
В следующем эксперименте исследовалась масштабируемость при росте числа роботов m и пропорциональном увеличении числа целей n, где n ≡ nk = |Gk| для рассматриваемого цикла, m ∈ {5,10,15,20}, n = γm, γ = 3. Уровень шумов фиксировался на значениях σ = 0.30 и β = 0.10, при этом для каждого m выполнялось K = 30 прогонов на одинаковых наборах сценариев. На рис. 2, а, показан близкий к линейному рост J при увеличении масштаба задачи, при этом модифицированный алгоритм обеспечивает меньшие значения J, чем классический. На рис. 2, б, показано, что время tep остается малым и в целом увеличивается при росте m, что соответствует росту размерности задачи и объема вычислений нижнего уровня при построении решения на каждом цикле перепланирования.
Для иллюстрации работы алгоритма в контуре перепланирования выполнен дополнительный эксперимент с построением траекторий перемещений роботов по циклам. Рассматривалась группа из m = 10 роботов и множество n = 30 целей в квадратной области [0;10]×[0;10]. Уровень шума наблюдений задавался значением σ = 0.3, параметр стохастической компоненты нейродинамики β = 0.1. В данном эксперименте использовался гибридный вариант алгоритма (метанастройка параметров), при этом для рассматриваемого режима неопределенности были автоматически подобраны параметры нейродинамического ядра α = 0.0787, bR = 0.5366, T = 1.2267, τ = 0.4578.
Алгоритм функционировал в режиме одношагового назначения на цикле: на каждом цикле перепланирования формировалось множество пар «робот-цель», после чего роботы перемещались к назначенным целям, а выполненные цели удалялись из множества невыполненных. Поскольку m = 10 и n = 30, эпизод в данном прогоне завершился за три цикла перепланирования (K = 3) при полном выполнении целей. Траектории роботов показаны на рис. 3. По результатам прогона суммарная фактическая длина перемещений составила Ltotal = 81.46 усл. ед. (таблица), время вычисления одного прогона имело миллисекундный порядок, признак завершения = 1 (все цели выполнены).
Циклы перепланирования
|
Цикл k |
Число назначений |
∑L(k), усл. ед. |
|
|
10 |
22,04 |
6,89 |
|
|
2 |
10 |
29,82 |
8,70 |
|
3 |
10 |
29,60 |
8,73 |
|
Итого |
30 |
81,46 |
- |
, усл. ед.Примечание: составлена авторами по результатам вычислительных экспериментов.
Рис. 3. Траектории роботов (гибридный метод) Примечание: составлен авторами по результатам вычислительных экспериментов
Графическая визуализация подтверждает, что решения формируются последовательно по циклам перепланирования: на каждом шаге выбираются цели для всех роботов, после чего система переходит к следующему циклу уже с обновленными позициями и уменьшенным множеством целей.
Заключение
Рассмотрена задача одношагового распределения пар «робот-цель» в группе мобильных роботов при наличии погрешностей наблюдений. Использована двухуровневая схема вычислений, в которой на нижнем уровне решение формируется нейродинамической процедурой с последующим построением допустимого бинарного назначения. На верхнем уровне выполняется параметрическая настройка по выборке сценариев неопределенности с последующей фиксацией найденных параметров для использования в контуре перепланирования.
В последующих работах предполагается учесть кинематические и динамические ограничения в критериях оптимизации и рассмотреть постановки задачи с динамическими и статическими препятствиями. Также планируется выполнить более подробный анализ кинематики и визуализацию траекторий, получаемых в процессе перепланирования.
Conflict of interest
Financing
Библиографическая ссылка
Мигранов А. Б. ГИБРИДНЫЙ НЕЙРОДИНАМИЧЕСКИЙ АЛГОРИТМ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ В ГРУППАХ МОБИЛЬНЫХ РОБОТОВ ПРИ НЕОПРЕДЕЛЕННОСТИ НАБЛЮДЕНИЙ И ПАРАМЕТРИЧЕСКОЙ НАСТРОЙКЕ // Современные наукоемкие технологии. 2026. № 4. С. 76-84;URL: https://top-technologies.ru/en/article/view?id=40731 (дата обращения: 10.05.2026).
DOI: https://doi.org/10.17513/snt.40731