Modification of the hopfield neural network model for solving the task of optimal task allocation in a group of mobile robots

Толық мәтін

Введение. Мобильные автономные системы для решения различного типа задач стали одним из признаков современности. Разработкой данных систем занимаются коллективы различных стран. Использование мобильных роботов является обоснованным в различных ситуациях, связанных с автоматизацией производственных процессов, автоматической доставкой товаров, управлением складами, применением в экстремальных средах (космической и подводной, атомная энергетика, спасательные операции, охрана и безопасность и т.д.). В результате мобильные роботы выполняют широкий спектр задач как в качестве автономного объекта [1], так и в составе связанных групп роботов [2–4].

В последнее время одним из активно развивающихся направлений групповой робототехники является синтез алгоритмов управления группой роботов, которые выполняют общую поставленную задачу. При этом рассматривается два типа групп роботов – управляемые командами из центра связи [5] и работающие как замкнутая система [6]. Эффективность применения групп напрямую зависит от времени автономной работы мобильных роботов, что накладывает ограничения на их массогабаритные, энергетические, статические и динамические функциональные характеристики. Кроме технических проблем реализации необходимы методики управления и планирования, реализующие концепцию единой энергетики группы и поддерживающие механизмы перераспределения энергии и контроля решаемых задач. Данные методики вносят коррективы в работу всех уровней управления, в том числе и стратегического, где решаются задачи планирования деятельности группы. При этом задача генерации алгоритма управления группой роботов является сложной и актуальной проблемой, решение которой проводят с помощью различных методов теории управления [7–13]. В общем случае распределение задач проводится в рабочем пространстве с произвольным числом заданий и роботов, в качестве объекта применения алгоритмов распределения выступают гетерогенные группы роботов, а сама проблема рассматривается как сложная комбинаторная задача.

Среди подходов решения исследуемой проблемы следует отметить алгоритмы централизованного распределения задач [7], мультиагентные алгоритмы управления, использующие нечеткую логику [8], алгоритмы динамического программирования [9], потенциальные поля [10] и когнитивно-адаптивные методы [11]. Также показывают свою эффективность эволюционные подходы на основе генетических и муравьиных алгоритмов [12].

В работе [13] показано, что проблема распределения в группе с произвольным числом роботов и заданий на поле в общем случае является NP-полной задачей, при решении которой применяется аппарат нейронных сетей. Так, в [14–18] рассмотрены различные оптимизационные задачи данного типа и поиск методов их приближенного решения с помощью нейросетей. В отличие от генетических или муравьиных алгоритмов нейросетевой подход считается более предпочтительным в тех случаях, когда важна скорость алгоритма поиска, а само решение может быть не обязательно самым оптимальным.

Ранее в работе [19] авторами была показана применимость нейросетевого подхода при решении задач распределения, имеющих низкую размерность и ограниченное число заданий и роботов в группе. Однако решения задачи с учетом допустимости произвольного числа роботов и заданий, а также метаоптимизации параметров нейросети, влияющих на качество и скорость решения оптимизационной задачи, ранее не проводились. Целью данной работы является развитие использования аппарата нейронной сети Хопфилда для решения оптимизационной задачи распределения заданий в группе мобильных роботов. Также будет показано, что при решении задачи большой размерности существенное влияние как на результат решения, так и на время расчета оказывает выбор свободных параметров настройки нейронной сети.

1. Постановка задачи. Приведем состав исходных данных и модель рабочего пространства с произвольным числом заданий и числом мобильных роботов в группе. На дискретном рабочем пространстве N × N в узловых точках размещаются n роботов и m заданий. Точками расположения роботов и заданий являются соответственно координаты (x_i, y_i, $i\in \overline{\mathrm{1,}n}$) и ($x_j^{*}$, $y_j^{*}$, $j\in \overline{\mathrm{1,}m}$). Необходимо распределить задачи между роботами таким образом, чтобы были выполнены все задания. В результате распределения каждый робот должен решить k заданий, $k\in \overline{\mathrm{0,}m}$. В каждой точке в один и тот же момент времени может находиться только одно задание и/или один робот.

Критерием оптимальности служит общая длина маршрута, которая складывается из пройденных расстояний каждого робота из группы:

$S_{\Sigma }=\sum _{i=1}^n{S}_i$, (1.1)

где S_i – длина маршрута, по которому прошел i-й робот в результате распределения задач в группе. Длина маршрута рассчитывается как сумма евклидовых расстояний, пройденных роботом:

$S_i=\sum _{j=1}^k\sqrt{{\left(x_j^{*}-x_{j-1}\right)}^2+{\left(y_j^{*}-y_{j-1}\right)}^2}$. (1.2)

2. Постановка задачи в виде TSP (travelling salesman problem, задача коммивояжера). Для эффективного синтеза алгоритмов управления группой роботов целесообразно представить всю группу роботов и задания на поле в виде вершин графа, что является необходимым и достаточным условием [13]. В качестве демонстрации процесса перехода от исходной задачи к TSP-задаче на графе рассмотрим частный случай, когда мобильная группа состоит из двух роботов (Р₁, Р₂) и необходимо выполнить четыре задания (З₁, З₂, З₃, З₄). Объекты размещаются на дискретном рабочем поле 10 × 10. Начальные координаты роботов и координаты заданий показаны в табл. 1, на рис. 1 – их графическое расположение на дискретном рабочем поле.

 

Таблица 1. Начальное расположение роботов и координаты заданий

Робот			Р1	Р2
Координаты			{4, 10}	{1, 7}
Задание	З1	З2	З3	З4
Координаты	{5, 8}	{1, 6}	{5, 4}	{2, 7}

 

Рис. 1. Графическое представление расположения роботов и задач на рабочем поле

 

Представим в виде графа дискретное рабочее поле с расположенными на нем объектами. Пусть A – множество неориентированных ребер, R и W – вершины, соответствующие координатам расположения роботов и заданий на рабочем поле. Введем обозначения: $G=\left\{\left.V,A\right\}\right.$ – смешанный граф, где $V=R\cup W$ – объединение непересекающихся множеств. При этом никакие две вершины подмножества R не смежны друг с другом, в графе G подграф W имеет пару различных смежных вершин, а каждое ребро является взвешенным направленным ребром.

Соответствующий начальному расположению роботов и координатам заданий граф приведен на рис. 2.

 

Рис. 2. Граф G_VRP для рассматриваемого примера

 

Решение NP-полных задач с помощью нейросетевых методов широко практикуется для задач TSP-класса [19]. Для преобразования исходной задачи к задаче TSP-класса введем фиктивные переходы между заданиями и работами на поле, а также между точками расположения роботов с нулевым весом. В конечной точке траектории i-го робота необходимо замкнуть его маршрут через фиктивный путь i+1 робота. При этом вершину маршрута последнего робота N необходимо замкнуть на вершину первого робота (N = 1). Это позволяет построить граф, содержащий гамильтонов цикл, являющийся одним из вероятных решений.

3. Использование сети Хопфилда для решения задачи. Нейронная сеть Хопфилда может быть применена в целочисленном программировании и комбинаторной оптимизации [19]. Основная проблема в этом случае состоит в подборе весов в функциях активации, обеспечивающих достижение состояния сходимости и исключение неверных решений. Функцией оптимизации модели Хопфилда является функционал энергии сети [20]:

$\left\{\begin{array}{l}{E}_1=A\sum _X\sum _i\sum _{j\ne i}{g}_{Xi}{g}_{Yi},\\ E_2=Â\sum _i\sum _X\sum _{X\ne Y}{g}_{Xi}{g}_{Yi},\\ E_3=C{\left(\sum _X\sum _i{g}_{Xi}-N\right)}^2,\\ E_4=D\sum _X\sum _{Y\ne X}\sum _i{d}_{XY}{g}_{Xi}\left(g_{Yi}+g_{Yi-1}\right),\end{array}\right.$ (3.1)

где g_Xi – двоичный параметр вершины X_i графа; d_XY – вес между вершинами X и Y; A, B, C, D – весовые коэффициенты.

Входной потенциал определяется через выражение

$u_{Xi}=-\frac{\partial E}{\partial u_{Xi}}$.

Модель нейродинамики

$\frac{d{u}_{Xi}}{dt}=-\frac{u_{Xi}}{\tau }-\left[\begin{array}{c}A\sum _{j\ne i}{g}_{Xi}+B\sum _{X\ne Y}{g}_{Yi}+\\ +C\left(\sum _X\sum _i{g}_{Xi}-N\right)+\\ +D\sum _Y{d}_{XY}\left(g_{Yi+1}+g_{Yi-1}\right)\end{array}\right]$,

где τ – числовой коэффициент. Процесс расчета итерационно повторяется. В матрице решений номер столбца является точкой маршрута, а номер строки – вершиной графа.

Общий алгоритм функции оптимизации при распределении задач в рабочем пространстве с произвольным числом заданий и числом мобильных роботов в группе показан на рис. 3.

 

Рис. 3. Блок-схема алгоритма оптимизации

 

4. Пример работы алгоритма. Рассмотрим результаты вычислительных экспериментов для частного случая расположения роботов и координат заданий (табл. 1), графическое расположение которых на рабочем поле представлено на рис. 1.

По формуле (1.1) инициализируются значения весов ребер графа, и в соответствии с алгоритмом оптимизации (рис. 3) строится граф, содержащий гамильтонов цикл (рис. 4). Для построения стратегии поведения производится обратное преобразование TSP-решения в маршруты движения роботов и их распределение по заданиям.

 

Рис. 4. Результат расчета стратегии поведения группы роботов

 

5. Анализ влияния свободных параметров на качество решения. Рассмотренный частный случай имеет низкую размерность и как результат приемлемое (близкое к оптимальному) решение получается без настройки свободных параметров сети. Используем предложенный подход для задач большей размерности (5 роботов, 15 заданий) и проведем оценку влияния основных параметров на качество и скорость решения оптимизационной задачи.

К основным параметрам сети отнесем: пороговый уровень потенциала (u₀); относительные веса слагаемых (A, B, C, D).

Метаоптимизацию параметров нейросети выполним по методике, содержащей следующие этапы:

1) выбор оптимального порогового уровня,

2) выбор набора относительных весов слагаемых A, B, C, D,

3) уточнение порогового уровня при выбранных весах слагаемых.

В качестве тестовой задачи используем задачу с размерностью поля 10х10 и числом объектов N = 20 (5 роботов, 15 заданий). Отображение исходных данных (гамильтонов цикл и стратегия поведения группы роботов) показано на рис. 5.

 

Рис. 5. Тестовая задача для размерности N = 20 (5 роботов, 15 заданий) и ее решение при начальных параметрах (u₀ = 0.2; A = B = D = 500; C = 200)

 

Этап 1. Пороговый уровень потенциала определяет, насколько плавный переход будет при расчете узлов сети Хопфилда.

Для анализа влияния параметра u₀ на качество решения проведен расчет тестовой задачи при разных его значениях. Всего выполнялось 250 запусков нейросети. На рис. 6 представлена зависимость минимума длительности маршрута для всех запусков по каждой точке.

 

Рис. 6. Зависимость минимальной длины маршрута от порогового уровня потенциала (250 запусков нейросети для каждой точки)

 

Получено, что минимум длины маршрутов наблюдается для u₀ ≈ 0.4.

Этап 2. Для быстрой сходимости веса A, B, C, D задаются в диапазоне 100–1000 единиц. Практические исследования показали, что при таких параметрах оптимизация наиболее эффективна. Проверим, какие параметры будут наиболее применимы для текущей размерности сетевой модели. Для этого проведем последовательную метаоптимизацию по весовым критериям. Ход оптимизации приведен в табл. 2 и на рис. 7.

 

Таблица 2. Последовательная метаоптимизация по весовым критериям

Итерация	Весовые коэффициенты				Длина маршрута, единицы расстояния (по 250 итерациям)
	A	B	C	D
1	100	500	200	500	585
2	500	500	200	500	435
3	1000	500	200	500	450
4	2000	500	200	500	484
5	5000	500	200	500	594
6	500	250	200	500	491
7	500	500	200	500	435
8	500	750	200	500	392
9	500	1000	200	500	340
10	500	2000	200	500	393
11	500	5000	200	500	621
12	500	1000	10	500	391
13	500	1000	100	500	334
14	500	1000	200	500	340
15	500	1000	500	500	398
16	500	1000	1000	500	450
17	500	1000	100	100	347
18	500	1000	100	200	303
19	500	1000	100	300	318
20	500	1000	100	500	334
21	500	1000	100	1000	671
22	500	1000	100	2000	804

 

Рис. 7. Метаоптимизация суммарной длины маршрута по весовым коэффициентам (250 запусков нейросети для каждой точки)

 

Результатом оптимизации являются следующие значения параметров: A = 500, B = 1000, C = 100, D = 200, которые позволяют получить длину маршрута в 303 единицы расстояния, что в 1.43 раза меньше исходной длины. Результат расчета задачи после второго этапа метаоптимизации показан на рис. 8.

 

Рис. 8. Тестовая задача и ее решение после этапа 2 метаоптимизации

 

Этап 3. Заключительным этапом является повторный подбор параметра порогового уровня потенциала. Результаты подбора представлены на рис. 9.

 

Рис. 9. Зависимость минимальной длины маршрута от порогового уровня потенциала на этапе 3 метаоптимизации (250 запусков нейросети для каждой точки)

 

Подбор уровня потенциала позволил снизить длину маршрута до 250 единиц расстояния. Результат решения тестовой задачи для этапа 3 рассмотрен на рис. 10. Как видно из рисунка, получено решение, которое наиболее оптимально.

 

Рис. 10. Тестовая задача и ее решение после этапа 3 метаоптимизации

 

Дополнительно приведем решение нескольких случайных задач такой же размерности (рис. 11).

 

Рис. 11. Примеры решения тестовых задач модифицированной нейросетью при различных начальных условиях (N = 20)

 

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

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

6. Результаты сравнения нейросетевого алгоритма с другими эвристическими алгоритмами оптимизации. Проведем сравнительный анализ эффективности разработанного нейросетевого алгоритма (НА) в сравнении с другими эвристическими методами оптимизации: генетическим алгоритмом (ГА) [21] и муравьиным алгоритмом (МА) [13]. Для каждого алгоритма выполнены адаптация под решаемую задачу и реализация в виде вычислительных моделей. Из-за разной сложности трех алгоритмов принято решение сравнить три модели в процессе однопараметрической оптимизации с поиском минимума функции евклидового расстояния по формуле (1.2) при фиксированном числе итераций (эпох) запуска алгоритма.

Предлагается провести серию вычислительных экспериментов на случайно сгенерированных полигонах. Под полигоном понимается рабочее поле заданных размеров с размещенным на нем определенным числом роботов и заданий. Всего предлагается использовать 100 различных полигонов (5 типов по 20 версий в каждом). Между собой типы полигонов отличаются размером рабочего поля, числом роботов и числом заданий (табл. 3).

 

Таблица 3. Типы полигона для решения задачи оптимизации

Тип полигона	Число роботов	Число заданий	Размер поля	Число полигонов
1	2	8	5x5	20
2	5	20	10x10	20
3	5	50	10x10	20
4	10	50	20x20	20
5	10	90	20х20	20

 

Примеры сгенерированных полигонов типов 1, 2, 4 и 5 представлены на рис. 12.

 

Рис. 12. Примеры полигонов типов 1, 2, 3, 4, 5

 

Для каждого полигона решается задача поиска квазиоптимального маршрута с точки зрения минимизации функции (1.2) тремя исследуемыми на эффективность алгоритмами. Максимальное число итераций (эпох, генераций, запусков) зафиксировано на уровне 500 для каждого алгоритма.

Результаты сравнительного эксперимента для всех типов полигонов сведены в табл. 4. Следует отметить, что НА использовался только на трех первых типах полигонов. На типе 4 и 5 полигонов ввиду большой размерности задачи время расчета с помощью нейросети превысило 1 ч, что неприемлемо при стандартном требовании к оперативности получения решения исходной задачи.

 

Таблица 4. Результаты экспериментов для тестовых полигонов (500 эпох каждого алгоритма)

Тип полигона	Алгоритм	Среднее время расчета, с	Средняя погрешность, %	Доля лучших решений, %
1	ГА	12.1	1.8	45
	МА	24.7	0.6	80
	НА	71.1	3.5	50
2	ГА	14.5	92.0	0
	МА	26.4	0.0	100
	НА	1076	27.7	0
3	ГА	17.2	230	0
	МА	28.9	0	100
	НА	9961	45	0
4	ГА	21.8	305	0
	МА	30.6	0	100
	НА	Время расчета неприемлемо
5	ГА	26.1	436	0
	МА	37.6	0	100
	НА	Время расчета неприемлемо

 

Представленные результаты эксперимента, оценка по уровню оптимизации (поиск пути с минимальной суммарной длиной маршрута группы роботов) позволили выделить наиболее эффективный алгоритм. Применение МА позволяет за приемлемое время получить решение, которое эффективнее (от 3 до 85%) решений, найденных с помощью НА и ГА. Показано, что НА и ГА при действующем ограничении на число эпох и низкой размерности задачи (порядка 10 объектов) позволяют найти лучшие решения, чем МА в 15–30% экспериментах. При высокой размерности задачи (25 объектов и более) МА в свою очередь обеспечивает поиск более эффективных решений, которые на 20–85% лучше (минимальная длина маршрута) решений, предлагаемых НА и ГА. Следует также отметить, что время расчета с помощью МА остается низким и стабильным для всех групп полигонов.

Таким образом, по результатам сравнения рассмотренных эвристических методов можно сделать вывод, что применение НА эффективно для задач распределения, поставленных для малых размерностей, с числом роботов в группе и заданий на рабочем поле не более 10. Для более сложных ситуаций должна быть проведена дальнейшая оптимизация процесса обучения нейронной сети, в первую очередь уменьшение размерности входных данных, количества нейронов в сети, одновременно с использованием аппроксимации матрицы весов A, B, C, D и более эффективных методов оптимизации, например стохастического градиентного спуска.

Заключение. Показано решение задачи построения стратегии управления группой мобильных роботов при выполнении произвольного числа заданий с помощью нейросети Хопфилда. Решение получено путем преобразования поставленной задачи к TSP-задаче, для чего введены фиктивные переходы между вершинами графа (заданиями и роботами на рабочем поле), а также между точками расположения роботов с нулевым весом.

Представлены результаты моделирования. В рассмотренном частном случае задачи с низкой размерностью (N = 6) близкое к оптимальному решение было получено без настройки свободных параметров сети. Для задач большей размерности (N = 20) показано, что существенное влияние как на результат решения, так и на время расчета оказывает выбор свободных параметров. Проведена оценка влияния основных параметров нейросети на качество и скорость решения оптимизационной задачи.

По результатам сравнения различных эвристических алгоритмов (НА, ГА и МА) показано, что НА может быть эффективно применен в задачах распределения с ограничениями по числу роботов в группе и заданий на рабочем поле (N ≤ 10).

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

Авторлар туралы

O. Darintsev

Mavlyutov Institute of Mechanics of the Ufa Federal Research Centre of the Russian Academy of Sciences; Ufa University of Science and Technology

Хат алмасуға жауапты Автор.
Email: ovd@uimech.org
Ресей, Ufa; Ufa

A. Migranov

Mavlyutov Institute of Mechanics of the Ufa Federal Research Centre of the Russian Academy of Sciences

Email: abm.imech.anrb@mail.ru
Ресей, Ufa

Әдебиет тізімі

Қосымша файлдар