Исследование алгоритмов принятия решений и обучение в программировании робототехнических устройств

Содержание

Введение

. Анализ моделей и методов реализации интеллектуальных игр в системе человек-робот

.1 Выбор алгоритма игры

.2 Передача данных игрового состояния

. Разработка архитектуры программного комплекса

. Разработка структур данных и знаний

.1 Язык программирования

.2 Структуры данных

.3 Среда разработки Choreographe

. Разработка алгоритмов

.1 Алгоритмы модуля распознавания

.2 Алгоритмы модуля обработки данных

.3 Алгоритмы функций модуля игры

.4 Алгоритмы выбора хода

.5 Алгоритм преобразования и вывода данных

. Разработка и реализация программных модулей

.1 Разработка модуля распознавания

.2 Разработка модуля обработки данных

.3 Разработка модуля игры

.4 Разработка модуля выбора хода

. Экспериментальное тестирование и отладка программных модулей

.1 Тестирование программного комплекса

.2 Поиск ошибок

.3 Редактирование и исправление ошибок

. Оценка качества разработанного продукта

Заключение

Список использованных источников

Приложение

Введение

Целью данного дипломного проекта является исследование алгоритмов принятия решений и обучение в программировании робототехнических устройств, а также введение материала по обучению в дисциплине «Интеллектуальные информационные системы» по направлению 09.03.02 и 09.04.02.

Частью предмета интеллектуальные информационные системы является искусственный интеллект(ИИ). ИИ - это одно из направлений информатики, целью которого является разработка аппаратно-программных средств, позволяющих пользователю-непрограммисту ставить и решать свои, традиционно считающиеся интеллектуальными задачи, общаясь с ЭВМ на ограниченном подмножестве естественного языка[1].

Основная задача - это обучить антропоморфного робота NAO Evolution V5 играть в интеллектуальную игру "Шашки“ и сделать этот процесс не отличимым от игры с обычным игроком.

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

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

В следующем части ведётся разработка структур данных и знаний. Это часть состоит из описания типов данных, используемых в программном обеспечении и из описания знаний необходимых для выполнения работы.

Указываются и рассматриваются материалы, применяемые при разработке программного комплекса.

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

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

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

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

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

Игра будет приближена к игре с реальным игроком. За исключением выполнения хода роботом. Выполненный ход будет сообщён пользователю по средствам голосовых команд. Для использования разрабатываемого программного комплекса также будет разработана документация со скриншотами и подробным описанием. Процесс настройки системы будет простым и доступным для любого человека.

1. Анализ моделей и методов реализации интеллектуальных игр в системе человек-робот

Для рассмотрения этого вопроса, необходимо изучить некоторые определения и понятия.

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

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

При реализации интеллектуальных игр в модели человек-робот требуется решить две задачи:

)        нахождение алгоритма, по которому совершаются ходы в игре;

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

1.1 Выбор алгоритма игры

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

Одним из существующих видов алгоритмов является метод построения игрового дерева. Рассмотрение данного алгоритма можно начать с более простой игры “Крестики-Нулики”.

Деревьями решений можно представить практически любую игру. Узлом игры является её состояние в данный момент времени до выполнения следующего хода и после выполнения предыдущего. Отдельная ветвь игрового дерева решений является последовательностью ходов игрока. Главная задача данного алгоритма найти оптимальный и лучший путь от корня до листа.

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

Каждый узел имеет H ответвлений, при условии, что игрок имеет H возможных ходов. Начальное состояние игры представляется пустым полем и в игровом дереве представлено корневым узлом. Ход первого игрока способен выпасть на любой из девяти возможных вариантов. Каждый возможный ход представлен ветвью, выходящей из корневого узла. Второму игроку для выполнения хода нолика остаётся восемь вариантов. Первые два хода представлены игровым деревом на рисунке 1.1

Рисунок 1.1. Дерево решений

Число возможных состояний в конце игр составит 362800 узлов. Но в действительности число возможных состояний игры будет приблизительно составлять 250000. Это связано с правилами игры. При победе одного из игроков продолжение ветки останавливается и текущее состояние является листом дерева.

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

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

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

)        выигрыш - 4;

)        не ясная ситуация -3;

)        ничья - 2;

)        проигрыш - 1.

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

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

)        победа игрока;

)        игра приходит к ничьей;

)        превышение допустимой глубины рекурсии.

В первом случае оппонент получает 1 балл, во второй ситуации 2 балла и в третьем случае игровому полю присваивается неопределенное значение, и противник получает 3 балла. Максимальный уровень глубины рекурсии устанавливается в целях сокращения вычислительных ресурсов. Необходимость возникает в шахматах, где количество узлов огромное.

Рисунок 1.2. Игровое дерево решений в конце партии

Подход минимакса является не единственной стратегий для нахождения оптимального хода, так как обход огромных деревьев занял бы большое время, что не желательно в процессе игры. Для сокращения времени обработки можно использовать первый ход, выбранный экспертами. В результате совершённого действия время обхода уменьшиться в девять раз. С учётом того, что после хода игрока, совершается ход противника, то количество обрабатываемых узлов будет равно

Память, используемая для хранения одного хода, уменьшить длительность выполнения хода игрока в 72 раза.

В игре шашки количество состояний или узлов равняется 10²⁰. В 2007 все допустимые ходы были просчитаны суперкомпьютером. Отсюда следует, что человек никогда не выиграет у компьютера.

В игре шахматы данное число составляет 10⁴⁶. Для обхода данного количества узлов требуется астрономическое время даже для суперкомпьютера.

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

Возможные варианты развития игры можно представить в виде графа, где вершина графа - это состояние игры. Стратегия в глубину подразумевает поиск по направлению “вглубь” по графу. Стратегия в ширину рассматривает поиск по всем вершинам на одном уровне. Каждая из стратегий имеет своё преимущество. Если не ограничивать поиск, то алгоритмы затрачивают одинаковое количество ресурсов и можно выбрать любой. При ограничении по количеству уровней лучшим алгоритмом является поиск в ширину[3].

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

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

Любая стратегия основана на анализе происходящих событий и состояний игры. И каждая из этих стратегий имеет одну цель - победа.

Рассмотрим несколько стратегий игры на примере интеллектуальной игры “Шашки”.

Стратегия “Поддавки”.

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

Стратегия “В дамки”.

Совершение ходов, при которых игрок хочет, как можно раньше пройти в дамки.

Стратегия “Блокирование”.

Блокировка противника - это ситуация, при которой игрок имеет возможность сходить, а его противник нет.

Робота можно запрограммировать на выполнение любого алгоритма. При этом не требуется глубокий расчёт, но правило, чем глубже расчёт, тем лучше, здесь также действует.

1.2 Передача данных игрового состояния

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

Красные шашки игрока, синие шашки компьютера. Для выполнения хода игроку достаточно выбрать шашку и поле, куда необходимо переместить эту шашку. Остальные действия выполняет программа.

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

Рисунок 1.3. Игра “Шашки” на ПК, передача данных “Человек-программа”

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

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

В примере, представленном на рисунке 1.4 продемонстрированы передача данных “Человек-робот” с физическим взаимодействие. Данный робот был представлен компанией ЧТПЗ на конференции «Иннопроме-2015». Для реализации данной игры потребовались специальные металлические шашки. Такая форма и размер шашек удобна для манипулятора.

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

Рисунок 1.4. Передача данных “Человек-робот”

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

2. Разработка архитектуры программного комплекса

Для разработки интеллектуальной игры в системе “Человек-Робот” необходимо проанализировать и рассмотреть некоторые требования и ограничения. Разработка системы будет осуществляться на основе алгоритма стратегии выбора хода и передачи данных по типу “Человек-Робот”

В качестве интеллектуальной игры выбрана игра “Шашки”. Основная цель игры состоит в том, чтобы взять все шашки противника и не оставить ему вариантов для хода путём блокирования его шашек. Существует большое количество вариантов игры. 64 клеточные шашки можно разделить на русские, обратные русские, английские(чекерс), пул чекерс, бразильские, испанские, португальские, чешские и другие.

Также есть 80-ти клеточные и 100 клеточные шашки. Пример 100 клеточного поля представлен на рисунке 2.1

Рисунок 2.1. Стоклеточные шашки

Для проектирования игры воспользуемся 64 клеточным русскими шашками.

В качестве робота выбран антропоморфный робот NAO Evolution V5 французской компании Aldebaran Technologies. NAO Evolution V5 робот-андроид идеально подходит для исследовательских миссий, а также учебных целей и разработок в области ИИ(искусственный интеллект). Робот построен на производительной аппаратной платформе. Разнообразные типы датчиков и их количество позволят в полной степени получить информацию об окружении робота. Полные характеристики представлены в таблице 2.1

Таблица 2.1. Технические характеристики NAO V5

Процессор: Intel Atom 1.6 ГГц , ARM9 ОС: ОС NAOqi на ядре Linux Питание: 27,6 Вт/ч Время работы без подзарядки 1.5 часа