X Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

Автономное исследование лабиринта

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Козлов Л.А. 1

---

1МОУ - Гимназия №2 г. Раменское

Баранова Н.С. 1

---

1МОУ - Гимназия №2 г. Раменское

Работа в формате PDF

635.1 KB

Автор работы награжден дипломом победителя III степени

Диплом школьникаСвидетельство руководителя

1.Введение

Актуальность темы исследования проекта:

В современном мире всё большее количество работы люди автоматизируют, появляются производства, склады, лаборатории. Роботов используют в труднодоступных для человека местах. В процессе выполнения работы автономным робототехническим системам приходится «запоминать» или изучать маршруты, карту. (автоматизированные склады) Подобные упрощенные задания решаются в спортивной робототехнике. Одной из таких задач является прохождение автономным роботом лабиринта, поиск пути до финиша, поиск кратчайшего пути от координаты к координате.

Цель: Разработка алгоритма исследования лабиринта для соревнований по робототехнике.

Задачи:

Найти возможные виды представления лабиринта в программировании.

Найти разные способы прохождения лабиринта.

Найти возможные способы ориентирования движущегося объекта в симуляторе.

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

Разработать алгоритмы, позволяющие найти путь от начальной заданной координаты, к конечной заданной координате в неизвестном лабиринте (алгоритм исследования лабиринта)

Разработать алгоритмы, позволяющие преобразовать последовательность посещения клеток лабиринта в движение робота.

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

Лабиринт. Способы прохождения лабиринта.

Лабиринт издавна привлекал людей своей таинственностью. Один из первых лабиринтов описывает Геродот – это был египетский лабиринт, в котором около 5000 тысяч комнат. Позже лабиринты утратили свою мистику и стали объектами развлечения, превратившись в сады и парки в виде зеленых изгородей сложной конфигурации. Более сложной задачей является создание ИРС (интеллектуальных робототехнических систем) для прохождения и исследования лабиринтов.

Первый способ прохождения лабиринта знали ещё древние греки – правило «одной руки». Именно с этого способа юные робототехники начинают своё знакомство с алгоритмами прохождения лабиринта.

2.1. Правило правой и левой руки в лабиринте.

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

Плюсы этого алгоритма:

Прост в реализации.

Минусы этого алгоритма:

По такому алгоритму робот посетит все возможные тупики с правой стороны лабиринта.

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

Реализация:

def moveForward():

#move robot one square forward

def turnRight():

#turn robot right

def turnLeft():

#turn robot left

#front_value is distance from front sensor

#right_value is distance from right sensor

#wall_value is distance on sensors if there is a wall

while True:

if right_value > wall_value:

turnRight()

moveForward()

else:

if front_value > wall_value:

moveForward()

else:

turnLeft()

2.2. Регулятор ошибки правого или левого датчика расстояния, как метод прохождения лабиринта.

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

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

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

Плюсы алгоритма:

Позволяет очень быстро получить требуемый результат.

Низкий порог знаний для реализации.

Минусы алгоритма:

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

Псевдокод на языке программирования Python 3.6.

def turnLeft():

#turn robot left

p_koef = 1

d_koef = 10

target_value = 7

wall_value = 5

last_error = 0

#sensor_value is current value from sensor

#function motors allows to move motors

while True:

while front_value > wall_value:

error = target_value - sensor_value

P = p_koef * error

D = (error - last_error) * d_koef

correction = P + D

motors(speed + correction,speed - correction)

last_error = error

turnLeft()

Схема прохождения лабиринта роботом.

3.Методы нахождения кратчайшего пути в лабиринте.

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

3.1. Метод нахождения кратчайшего пути в лабиринте без циклов (метод сокрытия тупиков).

Начав изучать тему лабиринтов, я не знал ничего про теорию графов, поэтому использовал иной метод. Метод заключается в представлении лабиринта, как 5 матриц, в которых записаны состояния стенок лабиринта в каждой ячейке и состояние самой ячейки. Пусть матрица А – сохраняет состояния всех левых для нас стенок лабиринта, B – верхних стенок, C – правых, D – нижних, S – сохраняет состояния ячеек. Каждая ячейка лабиринта будет выглядеть так.

У стенок есть три состояния: не изучена, изучена и стенка есть, изучена и стенки нет. У ячейки три состояния: не изучена, открыта, закрыта. Открытая ячейка означает, что робот может попасть в неё, закрытая запрещает перемещение в неё.

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

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

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

После ответов датчиков на первой клетке лабиринт примет такой вид.

При этом если в текущей клетке будет тупик, и мы «скажем» об этом программе, увидим следующий результат.

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

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

Основная программа выглядит так:

В функциях происходит смена состояний клеток и стенок в зависимости от текущего направления робота и его текущей клетки.

К минусам данного алгоритма можно отнести узконаправленность. Он будет работать только для нецикличных лабиринтов. Недостатками обладает сама прошивка leJos. Прошивка тратит около 40 секунд только на запуск программы. В соревнованиях, где время отсчитывается не время движения робота, а полное время с перезапусками программ это является недостатком.

Этот алгоритм был отработан на соревновании «Робофинист 2017». Основные проблемы возникли не с логикой, а с навигацией робота, но были быстро решены. Данное соревнование было проиграно по времени.

3.2. Метод нахождения кратчайшего пути в лабиринте без циклов (без использования двумерных массивов).

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

Так как Small basic не поддерживает многомерные массивы, алгоритм должен был использовать только одномерные массивы. В алгоритме перемещение робота было по правилу правой руки и параллельно записывалась информация о его перемещении в одномерный массив. 8 – проезд прямо, 6 – поворот направо, 4 – поворот налево, 5 записывалась в случае, если у робота в одной клетке было 2 и более вариантов перемещения. После финиша робота полученный одномерный массив оптимизировался по следующему принципу: если в массиве последовательно шли два поворота (44), значит робот попал в тупик и дальше едет его обратно, после того, как алгоритм нашел тупик, он удалял все проезды робота до моментов, когда он имел больше 2 вариантов перемещения.

Пример:

массив до оптимизации 856884488568

массив после оптимизации 85568

Последовательные элементы 55 показывают, что были удалены перемещения робота в тупике. После, если после 55 был поворот, то есть цифра 4 или 6, они тоже удалялись.

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

Плюсы алгоритма:

Для реализации достаточно одномерного массива.

Не требует специальных знаний.

Простота реализации алгоритма.

Минусы:

Отсутствие стабильности, при ошибке в перемещении на пути «туда», обратно робот может не вернуться.

3.3. Теория графов в исследовании лабиринтов.

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

Было найдено много информации по теории графов, поэтому новый алгоритм базировался на ней.

В основу лег алгоритм обхода графа в ширину. Поиск в ширину (обход в ширину, breadth-first search) — это один из основных алгоритмов на графах.

В результате поиска в ширину находится путь кратчайшей длины в

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

Псевдокод алгоритма BFS.

1. Поместить стартовую вершину в очередь

2. Пока очередь не пуста...

2.1.Извлечь из начала очереди вершину u и пометить её как посещенную

2.2.Найти все вершины смежные с текущей...

2.2.1.Если смежная вершина не посещена, то добавить её в конец очереди

Метод нахождения кратчайшего пути в графе BFS.

Функция BFS (вершина V)

{

помещаем в очередь вершину V

пока (очередь не пуста)

{

достаём вершину Tиз очереди;

перекрашиваем Tв чёрный;

если (T удовлетворяет условиям поиска) то

прерываем цикл с флагом успешного поиска;

запихиваем в очередь все белые вершины смежные с T;}

}

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

Программная реализация этой идеи заключается в следующем:

Нужно проинициализировать лабиринт, как будто в нем отсутствуют стенки, и он пустой.

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

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

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

4.Заключение.

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

Ход работы:

Анализ алгоритмов

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

Используемая литература

Обучающиеся ресурсы Университета Иннополис http://robolymp.ru/season-2020/training/resources/

Определение местоположения. Колотов А.В., Миклин А.А.

Счисление пути в задачах навигации. Колотов А.В., Миклин А.А., Томшин П.В., Киселев О.М.

Поиск и построение маршрута перемещения. Колотов А.В., Миклин А.А., Фадеев М.Ю., Козлов П.А.