ИСПОЛЬЗОВАНИЕ НЕЙРОННЫХ СЕТЕЙ ДЛЯ РЕШЕНИЯ ИГРОВЫХ ЗАДАЧ НА ПРИМЕРЕ ЗАДАЧИ ПОИСКА ПУТИ В ЛАБИРИНТЕ
Авторы:
1.
Новосибирский государственный технический университет
2.
Новосибирский государственный технический университет
Тип:
Статья
Страницы:
с 33
по 42
Статус:
Опубликован
Получено:
05.10.2018
Одобрено:
25.10.2018
Опубликовано:
25.10.2018
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 681.513
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 681.513
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
Язык материала:
русский
Ключевые слова:
нейронные сети, структура нейронной сети, методы обучения, игровое дерево, поиск пути в лабиринте
Аннотация (русский):
Рассматривается решение игровых задач на примере задачи поиска пути в лабиринте при помощи нейронной сети. Такая задача может быть решена одним из существующих методов обучения с подтверждением, однако решения имеют несколько недостатков, к которым можно отнести, например, большое время обучения для «классического» метода обучения с подтверждением. Приводится анализ данных алгоритмов, в том числе метода обучения с подтверждением, основанного на использовании метода поиска Монте-Карло в игровом дереве. Рассматривается вариант постановки исходной задачи, в котором вместо всего поля лабиринта на нейронную сеть подается вход, состоящий только из одного значения - признака, обозначающего, что предыдущий шаг был успешный или тупиковый. Предлагается вариант решения поставленной задачи при помощи синтеза нейронной сети на основании предварительно синтезированного алгоритма. Получена нейронная сеть, построенная из неформального описания алгоритма, которая позволяет выполнять поиск пути в лабиринте. Основная идея, используемая при формировании нейронной сети, заключается в том, что найденный или исследуемый путь отмечается в нейронной сети весами единиц, тупиковый - отрицательными весами, а неисследованный - нулевыми. При попадании робота в тупик происходит перезапуск процесса поиска пути из начального состояния, а тупиковое состояние отмечается в лабиринте как недостижимое. Приведены несколько этапов процесса поиска пути в лабиринте, иллюстрирующих работу синтезированной нейронной сети. Приведен сравнительный анализ полученного решения и существующих методов обучения с подтверждением.
Рассматривается решение игровых задач на примере задачи поиска пути в лабиринте при помощи нейронной сети. Такая задача может быть решена одним из существующих методов обучения с подтверждением, однако решения имеют несколько недостатков, к которым можно отнести, например, большое время обучения для «классического» метода обучения с подтверждением. Приводится анализ данных алгоритмов, в том числе метода обучения с подтверждением, основанного на использовании метода поиска Монте-Карло в игровом дереве. Рассматривается вариант постановки исходной задачи, в котором вместо всего поля лабиринта на нейронную сеть подается вход, состоящий только из одного значения - признака, обозначающего, что предыдущий шаг был успешный или тупиковый. Предлагается вариант решения поставленной задачи при помощи синтеза нейронной сети на основании предварительно синтезированного алгоритма. Получена нейронная сеть, построенная из неформального описания алгоритма, которая позволяет выполнять поиск пути в лабиринте. Основная идея, используемая при формировании нейронной сети, заключается в том, что найденный или исследуемый путь отмечается в нейронной сети весами единиц, тупиковый - отрицательными весами, а неисследованный - нулевыми. При попадании робота в тупик происходит перезапуск процесса поиска пути из начального состояния, а тупиковое состояние отмечается в лабиринте как недостижимое. Приведены несколько этапов процесса поиска пути в лабиринте, иллюстрирующих работу синтезированной нейронной сети. Приведен сравнительный анализ полученного решения и существующих методов обучения с подтверждением.
Ключевые слова:
нейронные сети, структура нейронной сети, методы обучения, игровое дерево, поиск пути в лабиринте
нейронные сети, структура нейронной сети, методы обучения, игровое дерево, поиск пути в лабиринте
В настоящее время применение нейронных сетей не ограничивается только задачами классификации и кластеризации, распознавания образов [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 (дата обращения: 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 (дата обращения: 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 (дата обращения: 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 (дата обращения: 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. Воевода А. А., Романников Д. О. Синтез нейронной сети для решения логико-арифметических задач // Тр. СПИИРАН. 2017. Вып. 54. C. 205-223.
16. Романников Д. О. О преобразовании сети Петри в нейронную сеть // Сб. науч. тр. НГТУ. 2016. № 4 (86). С. 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 (дата обращения: 25.08.2018).
