USING NEURAL NETWORKS FOR SOLVING GAME TASKS ON THE EXAMPLE OF THE PROBLEM OF SEARCHING THE WAY IN THE LABYRINTH
Authors:
1.
Novosibirsk State Technical University
2.
Novosibirsk State Technical University
Type:
Article
Pages:
from 33
to 42
Status:
Published
Received:
05.10.2018
Accepted:
28.02.2020
Published:
25.10.2018
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 681.513
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 681.513
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
Language:
Russian
Keywords:
neural networks, structure of neural network, teaching methods, game tree, search for a path in a labyrinth
Abstract (English):
The article deals with the solution of game problems by the example of finding a path in a labyrinth with the help of a neural network. Such a task can be solved by one of the existing methods of training with confirmation, but the solutions have several drawbacks, which include, for example, a long learning time for the "classical" training method with confirmation. Analysis of these algorithms is presented, including a training method with confirmation based on Monte Carlo search method in the game tree. There has been described a variant of setting the initial problem, in which the input consisting of only one value - the sign indicating that the previous step was successful or deadlock - is delivered to the neural network, instead of the entire field of the labyrinth. A variant of solving the problem is posed by the synthesis of a neural network based on a preliminary synthesized algorithm. A neural network obtained is constructed from an informal description of the algorithm; it allows searching for a path in the labyrinth. The main idea used in the formation of a neural network is that the detected or explored path is marked in the neural network by the weights of the units, the dead-end path - by the negative weights, and the unexplored path - by the zero weights. When a robot occurs in a dead end, the process of finding the path is restarted from the initial state, and the dead end state is marked in the labyrinth as unattainable. Several stages of the path search process in the labyrinth illustrating the operation of the synthesized neural network are presented. There has been given a comparative analysis of the solution obtained and of the existing methods of training with confirmation.
The article deals with the solution of game problems by the example of finding a path in a labyrinth with the help of a neural network. Such a task can be solved by one of the existing methods of training with confirmation, but the solutions have several drawbacks, which include, for example, a long learning time for the "classical" training method with confirmation. Analysis of these algorithms is presented, including a training method with confirmation based on Monte Carlo search method in the game tree. There has been described a variant of setting the initial problem, in which the input consisting of only one value - the sign indicating that the previous step was successful or deadlock - is delivered to the neural network, instead of the entire field of the labyrinth. A variant of solving the problem is posed by the synthesis of a neural network based on a preliminary synthesized algorithm. A neural network obtained is constructed from an informal description of the algorithm; it allows searching for a path in the labyrinth. The main idea used in the formation of a neural network is that the detected or explored path is marked in the neural network by the weights of the units, the dead-end path - by the negative weights, and the unexplored path - by the zero weights. When a robot occurs in a dead end, the process of finding the path is restarted from the initial state, and the dead end state is marked in the labyrinth as unattainable. Several stages of the path search process in the labyrinth illustrating the operation of the synthesized neural network are presented. There has been given a comparative analysis of the solution obtained and of the existing methods of training with confirmation.
Keywords:
neural networks, structure of neural network, teaching methods, game tree, search for a path in a labyrinth
neural networks, structure of neural network, teaching methods, game tree, search for a path in a labyrinth
В настоящее время применение нейронных сетей не ограничивается только задачами классификации и кластеризации, распознавания образов [1, 2], речи [3, 4] и поиска аномалий [5]. Также нейронные сети могут применяться к задачам управления. В частности, рекуррентные сети применяются для создания системы управления магнитным подвесом [6], сети прямого распространения применяются (совместно с методами обучения с подтверждением) для управления «перевернутым маятником», также среди игровых задач можно выделить использование сверточных нейронных сетей для создания систем для игры в аркадные игры Altari [7] и ее дальнейшее развитие для игры в Го [8]. Апробация методов обучения с подтверждением на примерах решения игровых задач является общепринятой по причине ее одновременной сложности и схожести с большим количеством других задач, например, она может быть интерпретирована как задача управления движением робота-манипулятора для перемещения детали от начального положения к заданному (или другие подобные задачи). В классической постановке данная задача может быть решена при помощи использования одного из алгоритмов поиска пути в графе или его обхода в ширину [9]. В [8] приводится решение подобной задачи (в указанной статье решается другая задача, но общая механика, по мнению авторов, схожа и, следовательно, можно сделать утверждение о применимости данного алгоритма) на основе применения алгоритма Монте-Карло для оценки дерева (или графа) возможных перемещений. Также в [10] для задачи такого же класса применяется метод временной разницы (temporal difference). Однако методы в [7, 8] не лишены недостатков, к которым можно отнести то, что для систем, в которых награда (reward) может быть получена лишь по окончании эпизода, управление, формируемое нейронной сетью, не позволяет сделать заключение о ходах, ведущих к положительному завершению эпизода. Причем вышеописанное поведение будет иметь место до того, как в результате завершения эпизода будет получена положительная награда. Для этого на практике применяют либо произвольные шаги, выполняющиеся с заданной вероятностью, либо модель, обученную на предварительно подготовленных данных, которые содержат ведущие к положительному завершению эпизода пути [11, 12]. В методе Монте-Карло для оценки дерева (или графа) возможных перемещений [8] проблема первоначального поиска пути решена при помощи использования статистики по совершенным перемещениям в дереве и их оценки. Однако данное решение, помимо нейронной сети, содержит и другие программные элементы. В статье рассматривается применение аппарата нейронных сетей без использования других программных составляющих для решения игровых задач на примере поиска пути в лабиринте. Постановка задачи Рассматривается задача поиска пути в лабиринте. При этом можно выделить несколько взаимодействующих объектов: 1) среда - представляет собой поле, на котором в каждой клетке могут располагаться один из нескольких типов ячеек (0 - «проход», можно совершать перемещение; 1 - «стена», нельзя совершить перемещение; 2 - «робот», который совершает перемещение; 3 - точка, к которой необходимо прийти в лабиринте). В литературе рассматриваются разные варианты сред. Для рассматриваемых алгоритмов (см. следующий раздел) применяются среды, в которых каждое совершенное действие характеризуется кортежем {done, r}, в котором содержится информация о совершенном действии: done - признак завершения эпизода; r - полученная награда. Система управления принимает значение {-1, 1} для эпизода, завершенного «проигрышем» и «выигрышем» соответственно; 2) «система управления» - представляет собой программный комплекс, цель которого - сформировать сигнал передвижения на основании входных данных лабиринта. Также возможен вариант среды, которая возвращает только признак того, было ли предыдущее действие выполнено или нет. В рассматриваемом варианте лабиринта для действия передвижения выходной сигнал будет иметь значение «1», если передвижение не было выполнено, и значение «0», если передвижение было осуществлено. При решении будут рассмотрены несколько вариантов входных данных для системы управления: 1) на вход подается состояние лабиринта полностью; 2) на вход подается только признак того, был ли выполнен предыдущий ход успешно. При этом робот ориентируется только по сигналам от среды. Анализ существующих решений Среди существующих методов решения поставленной задачи, описание которых частично приведено во введении, следует рассмотреть [7] и [8]. Далее будет рассмотрено решение каждым из вышеуказанных методов. Алгоритм, основанный на использовании нейронной сети и обучении с подтверждением [7], для одного эпизода приведен на рис. 1. В алгоритме на рис. 1 в первой строке начинает выполняться алгоритм по поиску пути в среде. Он должен выполняться до тех пор, пока среда не вернет признак окончания эпизода. Переменная pi обозначает вероятность каждого из возможных ходов прийти к «победному» состоянию. Вероятности получены путем оценки нейронной сетью состояния si. В следующей строке выполняется определение действия с наибольшей вероятностью и далее исполнение его в среде, которая возвращает новое состояние, признак окончания эпизода и значение награды. Значение награды для текущего эпизода добавляется в массив к существующим, а затем составляется массив наград с учетом коэффициента gamma (со значением меньше единицы, чаще всего около 0,99), и последним действием выполняется вычисление стоимостной функции и один «шаг» обучения. Рис. 1. Алгоритм обучения с подкреплением [7] Существенным недостатком данного алгоритма является его попадание в локальные минимумы, что на практике решается добавлением действия, выбираемого случайным образом, которое срабатывает с некоторой вероятностью. Данный метод достаточно хорошо показал себя для сред, у которых за каждое действие можно получить награду, при этом существенной проблемой является то, что для сред, у которых награда выдается по окончании эпизода, произведение logs · rewards будет вырожденное до тех пор, пока система управления не завершит эпизод с положительной наградой, что требует либо предварительно обученной нейронной сети [11-14], либо ожидания существенного временного промежутка. Применение данного алгоритма к решению поставленной задачи не дало относительно положительного результата по той причине, что не удалось дождаться того момента, когда робот случайным образом найдет путь до выхода из лабиринта (применяемые на практике методы [12] авторы сознательно не применяли, т. к. основные идеи этих методов идут в разрез с основной идей метода на рис. 1). Значительно улучшенной идей является алгоритм, представленный в [8]. Его главное преимущество заключается в преодолении недостатка поиска последовательности действий до первого выигрыша в эпизоде путем использования Монте-Карло поиска в игровом дереве. Работа [8] не содержит детального алгоритма, а только лишь некоторое описание направления проведенных исследований. Наша интерпретация исходного описания алгоритма [8] приведена ниже. В алгоритме присутствуют три составляющие: нейронная сеть, игровое дерево действий из каждого достижимого состояния и нейронная сеть. Наша интерпретация данного алгоритма заключается в первоначальном вычислении действия, которое более вероятно ведет к победному состоянию, что может быть формально реализовано в виде функции на рис. 2. В данной функции выполняется выбор нового состояния из числа возможных при совершении одного из действий. Если встречается неисследованное состояние, то выполняется переход в него, иначе выбирается состояние с наибольшим рейтингом (на рис. 2 обозначен как utc) [8]. Также для каждого состояния при исполнении эпизода вычисляются вероятности выполнения каждого из действий и вероятность достижения победного состояния из текущего. Результатом исполнения функции является новое состояние, в которое переходит среда, а также действие, с помощью которого выполняется этот переход. Рис. 2. Часть алгоритма обучения с подкреплением [8]: функция выбора действия Вторая часть рассматриваемого алгоритма заключается в обновлении состояний игрового дерева и обучении используемой нейронной сети на состояниях из завершенных эпизодов (рис. 3). Рис. 3. Часть алгоритма обучения с подкреплением [8]: функции обновления состояний дерева и обучения сети Первая функция на рис. 3 выполняет обратный обход игрового дерева из конечного состояния до корня дерева, при этом обновляется информация о вероятности победы из каждого посещенного состояния. Во второй функции выполняется обучение используемой нейронной сети на примерах из исполненного эпизода: передаваемые в функцию значения p - это ожидаемое действие согласно игровому дереву; v - значение 1 при победном исходе эпизода; 0 - при остальных; s - исследованные в эпизоде состояния. Далее обучение выполняется согласно сумме двух представленных стоимостных функций. Применение данного алгоритма к решению поставленной задачи дало положительный результат: обучить систему «сеть» (собрать статистику для игрового дерева и обучить нейронную сеть) удалось менее чем за 5 000 эпизодов. При этом в качестве алгоритма обучения использовался метод стохастической оптимизации с шагом обучения lr = 0,01. Построение нейронной сети При постановке исходной задачи таким образом, что на вход нейронной сети поступает не полное изображение лабиринта, а только признак, был ли предыдущий шаг успешным или тупиковым, применение выше обсужденных алгоритмов не будет эффективным. При такой постановке задачи и основываясь на идеях о синтезе нейронных сетей, изложенных в [15-17], можно синтезировать нейронную сеть (рис. 4). Рис. 4. Синтезированная нейронная сеть: «А» - признак наличия нового состояния и отсутствия сигнала «тупика» На рис. 4 с целью компактного представления изображен пример нейронной сети для выбора пути между двумя направлениями (движение влево и вправо). При этом данная нейронная сеть может быть легко расширена на произвольное число последовательных выборов и произвольное число вариантов выбора. Нейронная сеть содержит три входа: на первый вход «Вход» подается всегда сигнал «единицы»; второй вход «Тупик» поступает из среды и показывает, был ли выполнен предыдущий шаг (значение сигнала «0») или он является тупиковым (значение сигнала «1»); третий вход «Новое состояние» является внутренним сигналом синтезированной нейронной сети и показывает необходимость добавления нового состояния (см. описание ниже). Основная идея предлагаемой нейронной сети заключается в том, что путь от начального состояния до конечного формируется в нейронной сети по аналогии с «прожиганием». В нейронной сети это отражается как изменение весов таким образом, что для путей, ведущих к тупиковым состояниям, задаются веса со значением «-1», а для путей, которые исследуются или ведут к правильным состояниям, задаются веса со значением «1» (изначально веса путей имеют значения «0»). Длина исследуемого пути определяется текущим активным нейроном (далее будем называть его состоянием) в нижней части нейронной сети (рис. 4). В начальном состоянии активным является первое состояние. При этом переход к следующему активному состоянию выполняется, если есть признак наличия нового состояния и отсутствия сигнала «тупика» (на рис. 4 обозначен как «А») и также сигнал единицы с предыдущего состояния. Изначально сигнал с входа, отмеченного как «вход», поступает на два нейрона, которые обозначают выбор перехода влево и вправо соответственно, со значением нуля (веса этих переходов инициализируются нулями). В нейроне «новое состояние» формируется значение для входа «Новое состояние» и имеет значение единицы, если отсутствуют входные сигналы единиц и есть хотя бы один сигнал нулевой. Это достигается с помощью нейронной сети (рис. 5), которую можно разделить на несколько частей: часть по определению того, что отсутствуют сигналы единицы, и часть по определению того, что присутствует сигнал нуля. Рис. 5. Часть нейронной сети по определению признака нового состояния: «А» - признак присутствия единиц; «Б» - признак присутствия нулей В приведенной выше нейронной сети часть по определению наличия сигналов со значением единиц реализуется так, что изначально сигналы поступают на нейроны с функцией активации «выпрямителя», что позволяет преобразовать сигналы с отрицательными значениями к нулевым. А далее они поступают на нейрон с функцией активации выпрямителя для суммирования. Данная часть схемы формирует сигнал единицы в случае, если на входе присутствует хотя бы один сигнал единицы, в противном случае - сигнал нуля («А» на рис. 5). Вторая часть нейронной сети используется для определения наличия перехода, который еще не был рассмотрен (для обозначения такого перехода используется вес со значением нуля). Первоначально каждый из входных сигналов поступает на нейрон с функцией активации, которая имеет значение При этом положительные значения и нулевые значения сигналов на выходе нейронов будут нулевыми, а отрицательные останутся отрицательными. Далее все выходные сигналы суммируются по модулю, что позволяет сформировать выход со значением единицы, если на входе присутствует хотя бы один сигнал со значением нуля, и иначе - сигнал со значением нуля («Б» на рис. 5). Стоит отметить, что эта часть нейронной сети также будет формировать сигнал единицы для случая, если входными сигналами являются не нули, а единицы. Данный недостаток решается тем, что на выходном нейроне рассматриваемой нейронной сети формируется сигнал единицы только для случая, когда выход «А» имеет значение нуля, а выход «Б» - значение единицы. При этом если на выходе «Б» сформировалась единица из-за входного сигнала единицы, то тогда на выходе «А» сформируется также сигнал единицы, что приведет к итоговому нулевому значению сигнала. После определения признака нового состояния формируются выходные сигналы управления. Если такой признак отсутствует, то выходные сигналы будут иметь значения нулей. Если признак формирования нового состояния имеет значение единицы, то формируется сигнал управления влево, если соответствующий выход не был отрицательным, в противном случае - сигнал управления вправо. При одновременном наличии входов «тупика» и состояния формируется признак изменения веса последнего нейрона с «1» на «-1» как вариант «обучения» сети избегать тупиковых направлений. Также при формировании признака «нет возможных вариантов» (срабатывает, если все сигналы имеют значение «-1») наступает окончание эпизода, и робот должен начинать поиск пути из начального положения. Результаты моделирования Были выполнены эксперименты по исследованию того, как работает синтезированная нейронная сеть. Программа для имитации среды, а также нейронная сеть реализованы на языке программирования Python 3.6, при этом для реализации нейронной сети использовалась библиотека PyTorch 0.4. Моделирование выполнялось на компьютере с процессором Intel Core i5 2.3 GHz с использованием операционной системы macOS 10.13.6. На рис. 6 представлены три этапа поиска пути в лабиринте. a б в Рис. 6. Этапы моделирования работы синтезированной нейронной сети: начальное состояние среды (а); промежуточное состояние среды (б); конечное состояние среды (робот нашел путь) (в) На рис. 6, а приведено начальное состояние среды и перемещаемого робота в ней, который изображен в виде стрелки (стрелка указывает направление предыдущего шага) в верхнем углу. Решеткой изображены стены в лабиринте, через которые робот не может пройти. Цель, к которой необходимо отыскать путь, обозначена буквой «G». При входе робота в тупик происходит перезапуск, и робот начинает поиск пути из начального положения, при этом место тупика в лабиринте помечается крестом, в который запрещен переход (на рис. 6, б приведено состояние после нескольких перезапусков). На рис. 6, в приведено состояние системы, в котором синтезированная нейронная сеть нашла путь в лабиринте. Заключение В статье представлен подход к синтезу нейронной сети при помощи ее построения на основе алгоритма для решения задачи поиска пути роботом в лабиринте. Само преобразование носит неформальный характер, а в результате преобразования формируется структура нейронной сети, которая в дальнейшем может быть обучена традиционным способом или при помощи расчета значений коэффициентов. Предложенная структура нейронной сети позволяет решить задачу поиска пути выхода из лабиринта при постановке задачи, в которой на вход нейронной сети поступает только признак успешного (или неуспешного) выполнения прошлого действия. При сравнении наиболее популярных алгоритмов обучения с подтверждением можно сделать вывод о том, что предлагаемая сеть является рекуррентной (вместо сверточных сетей или сетей прямого распространения), что является новизной при решении поставленной задачи. Другим преимуществом предлагаемого подхода является то, что синтезированную нейронную сеть можно обучить за меньшее число итераций обучения, что может являться важным для более сложных задач и нейронных сетей большего размера.
1. Krizhevsky A., Sutskever I., Hinton G. E. ImageNet Classification with Deep Convolutional Neural Networks // Proceedings of Neural Information Processing Systems (NIPS). 2012. P. 1097-1105.
2. Karpathy A., Fei-Fei L. Deep Visual-Semantic Alignments for Generating Image Descriptions // Proceedings of IEEE Transactions on Pattern Analysis and Machine Intelligence. 2016. V. 39. P. 664-676.
3. Graves A., Mohamed A., Hinton G. Speech recognition with deep recurrent neural networks // Proceedings of International Conference on Acoustics, Speech and Signal Processing (ICASSP). 2013. P. 6645-6649.
4. Deng L., Hinton G. E., Kingsbury B. New types of deep neural network learning for speech recognition and related applications: An overview // Proceedings of IEEE International Conference on Acoustic Speech and Signal (ICASSP 2013). 2013. P. 8599-8603.
5. Perera P., Patel V. M. Learning Deep Features for One-Class Classification // ArXiv e-prints. URL: https://arxiv.org/pdf/1801.05365.pdf (data obrascheniya: 25.08.2018).
6. Aliasghary M., Shoorehdeli M. A., Jalilvand A., Teshnehlab M. Magnetic levitation control based-on neural network and feedback error learning approach // 2008 IEEE 2nd International Power and Energy Conference. Johor Bahru, 2008. P. 1426-1430.
7. Mnih V., Kavukcuoglu K., Silver D., Graves A., Antonoglou I., Wierstra D., Riedmiller M. Playing Atari with Deep Reinforcement Learning // Proceedings of Neural Information Processing Systems (NIPS). Nevada, 2013. URL: https://www.cs.toronto.edu/~vmnih/docs /dqn.pdf (data obrascheniya: 25.08.2018).
8. Silver D., Schrittwieser J., Simonyan K., Antonoglou I., Huang A., Guez A., Hubert T., Baker L., Lai M., Bolton A., Chen Y., Lillicrap T., Hui F., Sifre L., van den Driessche G., Graepel T., Hassabis D. Mastering the game of Go without human knowledge // Nature. 2017. V. 550. P. 354-359.
9. Cormen T., Leiserson C., Rivest R., Stein C. Introduction to Algorithms, Third Edition // The MIT Press. 2009. P. 1109.
10. Penedones H., Vincent D., Maennel H., Gelly S., Mann T., Barreto A. Temporal Difference Learning with Neural Networks - Study of the Leakage Propagation Problem // ArXiv e-prints. URL: https://arxiv.org/pdf/1807.03064.pdf (data obrascheniya: 25.08.2018).
11. Gao Y., Xu G., Lin L. Reinforcement Learning from Imperfect Demonstrations // ArXiv e-prints. URL: https://arxiv.org/pdf/1802.05313.pdf (data obrascheniya: 25.08.2018).
12. Hester T., Vecerik M., Pietquin O., Lanctot M., Schaul T., Piot B., Horgan D., Quan J., Sendonaris A., Dulac-Arnold G., Osband I., Agapiou J., Leibo J. Z., Gruslys A. Learning from Demonstrations for Real World /Reinforcement Learning // Proceeding AAAI'16 Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. P. 2094-2100.
13. Bishop C. Pattern Recognition and Machine Learning (Information Science and Statistics). Springer, 2007. 738 p.
14. Goodfellow I., Bengio Y., Courville A. Deep Learning. MIT Press, 2016. 775 p.
15. Voevoda A. A., Romannikov D. O. Sintez neyronnoy seti dlya resheniya logiko-arifmeticheskih zadach // Tr. SPIIRAN. 2017. Vyp. 54. C. 205-223.
16. Romannikov D. O. O preobrazovanii seti Petri v neyronnuyu set' // Sb. nauch. tr. NGTU. 2016. № 4 (86). S. 98-103.
17. Voevoda A. A., Romannikov D. O. A Binary Array Asynchronous Sorting Algorithm with Using Petri Nets // Journal of Physics: Conference Series. 2017. V. 803. N. 1. P. 012178. URL: http://stacks.iop.org/1742-6596/803/i=1/a=012178 (data obrascheniya: 25.08.2018).
