Sudoku Hunter

В последнее время наш блог молчит и может показаться, что «Карандаш и Самоделкин» все, сдулись. На самом деле работа кипела, а отсутствие публикуемых материалов было связано с тем, что проекты раз за разом становятся все сложнее и требуют все больше времени на реализацию. Последние наши разработки были так или иначе связаны с нейросетями, поэтому логично было за это время подтянуть скиллы по этой теме, что и было сделано – был пройден ряд онлайн курсов по и даже пара оффлайновых, из которых особенно понравилась «Зимняя школа машинного обучения» (Machine Learning Winter School).

Проект, работа над которым шла больше 4 месяцев, мы назвали Sudoku Hunter. Изначально была идея собрать робота по мотивам NXTSudokuSolver, однако постепенно она трансформировалось в нечто иное, на наш взгляд не менее интересное.

Итак, Sudoku Hunter – это пистолет с EV3, веб-камерой и Raspberry Pi на борту, из которого можно «стрелять» по математическим головоломкам судоку, получая на экране EV3-блока их решение. В алгоритмической части используются технологии машинного зрения и машинного обучения, веб-технологии для создания отладочной видеоконсоли.

Если кто не помнит, судоку - головоломка на бумаге, игровое поле которой представляет собой квадрат размером 9×9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9), называемые подсказками. От игрока требуется заполнить свободные клетки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась бы только один раз.

Конструкция нашего робота не особенно замысловата, поэтому инструкцию по сборке мы решили не делать – вы легко соберете что-то подобное просто глядя на фото. Мы использовали следующие компоненты:

• Блок Lego Mindstroms EV3 и строительные детали из этого набора
• Raspberry Pi
• Веб-камера Sony Playstation Eye
• Wi-fi адаптер для связи EV3 с RPi
• Powerbank для питания RPi

Программ, которые необходимы для работы робота - несколько, все они написаны на Python:

• Программа для EV3 - отвечает за вывод информации на экран блока, связь с Raspberry Pi, передачу на RPi состояния датчика-кнопки
• Программа для Raspberry Pi - отвечает за обработку кадров с камеры, распознаванием цифр с использованием обученной нейросети, последующим решением распознанного судоку, связь с EV3, вывод вспомогательной и отладочной информации на веб-консоль,
• Программа для Raspberry Pi, предназначенная для создания дата сета для обучения нейронной сети.
• Программа для ПК, используется для создания и обучения нейросети на основе подготовленного дата сета

Основная программа для Raspberry Pi работает по следующему алгоритму: 

• Подключение библиотеки машинного зрения OpenCV

• Подключение библиотек машинного обучения keras(tensorflow), sklearn

Процесс 1:

• Взятие кадра с камеры

• Преобразование изображения из BGR в HSV 

• Наложение маски для фокусировки на значимых элементах изображения

• Запись результирующего кадра в объект в памяти

• Соединение с EV3 с помощью протокола socket 

• Основной цикл:

• Чтение кадра из объекта в памяти

• Поиск в изображении с наложенной маской объектов, напоминающих квадрат 

• Передача данных о предполагаемом расположении квадрата на EV3, для вывода на экран блока

• Приём данных с EV3 о состоянии кнопки 

• Если кнопка нажата:

Процесс 3:

• Запуск веб-сервера (используется модуль Flask)

• Соединение с Raspberry Pi с помощью протокола socket

• Получение данных о предполагаемом расположении квадрата 

• Подключение библиотеки машинного зрения OpenCV

• Подключение библиотек машинного обучения keras(tensorflow), sklearn

Процесс 1:

• Взятие кадра с камеры

• Преобразование изображения из BGR в HSV 

• Наложение маски для фокусировки на значимых элементах изображения

• Запись результирующего кадра в объект в памяти

• Соединение с EV3 с помощью протокола socket

• Чтение кадра из объекта в памяти

• Поиск в изображении с наложенной маской объектов, напоминающих квадрат 

• Передача данных о предполагаемом расположении квадрата на EV3, для вывода на экран блока

• Приём данных с EV3 о состоянии кнопки 

• Если кнопка нажата:

• Запуск веб-сервера (используется модуль Flask)

• Вывод информации на веб-сервер - видеоконсоль для удобства отладки

• Подключение библиотек машинного обучения 

• Загрузка дата сета изображений 

• Разбиение дата сета на учебные и тренировочные данные

• Создание нейронной сети с заданными параметрами 

• Обучение нейронной сети

• Сохранение модели 

Процесс 2:

• Изображение обрабатывается и судоку «нарезается» на 81 квадрат в каждом из которых одна клетка головоломки 
• Каждый из фрагментов проверяется на наличие в нём цифры и если цифра обнаружена, то клетка подаётся на распознавание нейронной сети 
• Распознанная цифра заноситься в массив. Когда массив заполнен всеми цифрами, он подаётся в алгоритм, решающий судоку 
• Массив содержащий решённую головоломку передаётся на EV3 для вывода на экран блока 

• Вывод информации на веб-сервер - видеоконсоль для удобства отладки

Программа на EV3 работает по следующему алгоритму:

• Вывод контура квадрата на экран для визуального контроля (размер квадрата, угол разворота, степень его трапециевидности)
• Передача состояния датчика-кнопки на Rpi
• Если от RPi получен массив данных с решенной головоломкой - вывод решённого судоку на экран блока

Программа создания дата сета для обучения нейронной сети на Raspberry Pi имеет следующий алгоритм:

Процесс 2: 

• Изображение обрабатывается и судоку «нарезается» на 81 квадрат в каждом из которых одна клетка головоломки 
• Каждый квадрат сохраняется в папку, формируя дата сет

Процесс 3:

Программа на ПК, предназначенная для создания и обучения нейросети на основе подготовленного дата сета работает так: 

Стандартный алгоритм обучения нейронной сети мы усовершенствовали путём запуска функции обучения не на заданное количество эпох, а по одной эпохе, с проверкой результата на проверочной выборке после каждой. Если результат ухудшается несколько эпох подряд — прекращаем обучения с ошибкой. Если результаты на тестовой выборке выше 95% - прекращаем обучения, проверяем модель на отдельной выборке (которую она ещё не видела ни при обучении, ни при проверках после каждой эпохи).

Исходные коды всех программ проекта мы выложили здесь: https://github.com/darkavengersmr/Sudoku-Hunter

Демонстрация работы робота:

PiTanks Online

Нам очень нравятся игры для программистов, такие как например Colobot и Ceebot. Писать код, загружать его в своего бота и запускать его для выполнения миссий - что может быть интереснее? Поддержка сетевого режима, когда другие игроки запускают своих прокачанных кодом ботов против твоего? Несомненно. Однако еще более интересным нам показалось самим разработать игру для программистов и поиграть в нее с друзьями.
Серверный игровой движок, многопоточность, асинхронный обмен данными, объекты и классы - все это мы приправим поддержкой дополненной реальности с использованием машинного зрения c OpenCV.

Приставка Pi в названии проекта "PiTanks Online" однозначно намекает на то, что в качестве серверной платформы мы использовали Raspberry Pi. Игровое поле в нашем проекте нарисовано от руки на листе бумаги.

На него смотрит веб-камера, установленная на подставке, собранной из LEGO Technic. В качестве рисованного поля может использоваться также маркерная доска.

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

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

Наши примеры ботов имеют следующие наборы "команд":

• forward() - бот смещается на 1 единицу дистанции вперед (в сторону, в которую он в данный момент развернут)
• backward() - бот смещается на 1 единицу дистанции назад
• right() - бот поворачивается на месте на 1 градус вправо
• left() - бот поворачивается на месте на 1 градус влево
• radar(a) - запросить данные с радара по направлению a (угла в градусах 0..359 от текущего направления бота). Функция возвращает кортеж из символа, обозначающего объект, который обнаружил радар (t - живой бот противника, w - стена или мертвый бот противника, n - "ничего нет") и числа - расстояния до обнаруженного объекта (0 в случае объекта "ничего нет") 
• fire() - бот производит выстрел, снаряд летит по направлению разворота бота
• energy() - возвращает количество доступных очков действий. Очки действий тратятся на движение, стрельбу и работу радара. Пополняются каждую секунду. Введены, чтобы никто из игроков не мог получить приоритета в обработке его бота сервером. 
• exit() - отключиться от сервера, выйти из боя

Каждая из функций forward, backward, left и right возвращает True или False давая понять боту, была ли отработана команда. Это может быть удобным, например для понимания не застрял ли бот при маневре, упершись в препятствие.

При желании можно не использовать готовые функции из примеров, а написать свои. Например, доработать функции поворота возможностью принимать параметр "угол поворота", а функции движения - параметр "дистанция". Логику управления ботом в целом можно накрутить довольно сложную. Вполне адекватно работают, например, ПИД-регуляторы по дальномерам ботов, можно использовать элементы SLAM для локализации на карте.

Написанный на Python бот может работать не только на ПК, подходит практически любое устройство с интерпретатором этого языка, например LEGO EV3, ESP8266 или смартфон:

Исходный код сервера и примеры ботов доступны по ссылке.