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

Старт в науке

Применение эволюционных алгоритмов для движения мобильного робота.

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

Мухаметов И.И. 1

---

1ГБОУ СОШ №5

Артемова Д.Т. 1

---

1ГБОУ СОШ №5

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

1.1 MB

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

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

Введение.

Актуальность данной темы: Эволюционные алгоритмы хорошо решают задачи, сложные для человека. Эти алгоритмы можно использовать в решении задач по робототехнике, например, таких как прокладывание маршрута, моделирование, процессов взаимодействия нескольких роботов. Мобильные роботы в идеале должны уверенно перемещаться в незнакомой и непредсказуемой обстановке. Для их оптимально быстрого и точного передвижения и применяются эволюционные алгоритмы. Разновидностью эволюционных алгоритмов являются генетические алгоритмы. Генетические алгоритмы могут применяться в системах ИИ ( искусственного интеллекта). Генетические алгоритмы могут использоваться для управления процессом, например на химическом заводе, или балансировании загрузки на многопроцессорном компьютере, поиска максимального отношения прочности/веса, или определять наименее расточительное размещение для нарезки форм из ткани. Например: израильская компания Schema разработала программный продукт Channeling для оптимизации работы сотовой связи путем выбора оптимальной частоты, на которой будет вестись разговор. В основе этого программного продукта и используются генетические алгоритмы.

Проблема. Автономные роботы – это роботы, которые выполняют поставленные задачи с высокой степенью самостоятельности. Их использование позволяет решать многие транспортные операции во многих сферах деятельности. Это и доставка грузов, агрономия, освоение космоса, выполнение работ, опасных для жизни человека ( взрывы на АЭС, завалы, пожары). Решение этой проблемы является основой дальнейших исследований. При планировании автономного перемещения я подразумеваю задачу, состоящую из двух пунктов: разработка пространства и планирование траектории движения. Робот должен определять, где он находится в данный момент, особенно при определении своего местоположения на карте. Выбор генетического алгоритма дает возможность учесть множество вариантов поведения робота и аспектов окружающей среды на этапе планирования пути. Решение этой проблемы является основой дальнейших исследований

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

Задачи исследования:

Рассмотреть особенности генетических алгоритмов, проанализировать их особенности.

2. Рассмотреть оптимальные способы планирования пути мобильного робота;

3. Составить алгоритмы прямолинейного движения и обхода препятствий роботом;

4. Сравнить результаты работы генетических алгоритмов;

5 . Выбрать оптимальный вариант генетического алгоритма.

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

Объект исследования: применение генетических алгоритмов для решения задачи планирования пути автономного робота.

Предмет исследования: применение генетических алгоритмов для оптимального планирования пути автономного робота.

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

Структура исследовательской работы: работа состоит из введения, 3 глав,

заключения, списка литературы, аннотации, ключевых слов.

Ключевые слова: эволюционные алгоритмы, генетический алгоритм.

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

В данной работе приводится:

-Разработка новых генетических алгоритмов, необходимых для решения конкретной задачи;

-Применение разработанного генетического алгоритма к решению задачи для более точного движения робота в пространстве. –

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

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

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

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

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

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

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

ТАКИМ ОБРАЗОМ, мобильный робот должен передвигаться по заданным траекториям, искать кратчайший маршрут. Приводится обзор видов мобильных роботов, рассматриваются различные алгоритмы поиска кратчайшего пути, алгоритмы обхода препятствий, а также способы локализации мобильного робота в пространстве.

Глава 1.

Многое из того, что нас окружает можно объяснить единственной теорией: теорией эволюции через наследственность, изменчивость и отбор.

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

История эволюционных вычислений началась с изучения различных моделей. Базовыми из них были генетические алгоритмы Голланда (Holland), опубликованные в начале 60-х годов после выхода в свет книги "Адаптация в естественных и искусственных системах" ("Adaptation in Natural and Artifical Systems", 1975). В 70-х годах Растригиным Л.А. был предложен ряд алгоритмов, в основе которых лежали идеи бионического поведения особей. Био́ника — прикладная наука, которая помогает человеку создавать интересные технические системы и технологические процессы на основе идей, найденных и заимствованных у природы.

Развитие этих идей нашло свое продолжение в работах Букатовой И.Л. по эволюционному моделированию, Цетлина М.Л., Неймарк Ю.И.. Большой вклад в развитие эволюционного программирования внесли Фогел (Fogel) и Уолш (Walsh). Каждая из этих "школ" взяла за основу идеи, существующие в природе, изменила и упростила их до такой степени, чтобы их можно было реализовать на компьютере.

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

Виды алгоритмов

Эволюционные алгоритмы — направление в искусственном интеллекте (раздел эволюционного моделирования), которое использует и моделирует процессы естественного отбора.

-генетические алгоритмы — алгоритм поиска, используемый для решения задач путём случайного подбора, комбинирования искомых параметров;

-генетическое программирование — автоматическое создание или изменение программ с помощью генетических алгоритмов;

-эволюционное программирование — структура программы постоянна, изменяются только числовые значения;

-эволюционные стратегии — похожи на генетические алгоритмы, но в следующее поколение передаются только положительные мутации;

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

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

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

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

Схематичное описание функционирования генетического алгоритма :

Главным плюсом ГА является то, что они могут применяться даже там, где не существует никаких специальных методов. Сила генетического алгоритма — в его способности управлять одновременно многими параметрами.

Генетические алгоритмы применяются для решения следующих задач:

1.Оптимизация функций.

2.Оптимизация запросов в базах данных.

3.Настройка и обучение искусственной нейронной сети.

4.Составление расписаний.

5.Игровые стратегии.

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

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

ГЛАВА 2

Описание сборки робота-сортировщика.

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

Ниже приведена смета на комплектующие, необходимые для изготовления робота:

Всего: 2550 руб.

Также для сборки робота использовались имеющиеся детали:

-Платформа из оргстекла 2 шт., макетная плата, кнопка включения,

-крепёжные детали и провода.

Робот после сборки выглядит так:

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

Для движения робот оснащён двумя моторами постоянного тока, которые управляются специальной платой – драйвером. Эта плата принимает аналоговые и цифровые сигналы от платы Arduino и подаёт питание на моторы. При этом аналоговые контакты (пины E1 и E2) используются для управления скоростью моторов, а цифровые контакты (пины IN1 и IN3) используются для управления направлением вращения моторов. Для того чтобы ориентироваться в пространстве робот оснащается электронными органами чувств – датчиками. На нашем роботе установлено 2 датчика линии, с помощью которых робот может двигаться по заранее проложенной траектории (чёрная линия), например при движении со склада на пункт выдачи готовой продукции. Кроме этого у робота есть ультразвуковой датчик препятствия, который помогает роботу избегать столкновений с препятствиями и другими складскими роботами. Несколько роботов могут двигаться по одной и той же траектории, не мешая друг другу.

Для автономной работы роботу необходимо питание. Решено было использовать раздельное питание: 3 батарейки 18650 с напряжением 3.7V (для питания моторов) и батарейка типа «Крона» с напряжением 9V (для питания платы и датчиков). Для обнаружения объектов используется ещё один датчик линии. В дальнейшем планируется доработать конструкцию робота: присоединить манипулятор, который позволит захватывать объекты после их обнаружения.

Глава 3.

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

БЛОК-СХЕМА ЭВОЛЮЦИОННОГО АЛГОРИТМА

(НА ПРИМЕРЕ ДВИЖЕНИЯ В ЛАБИРИНТЕ)

НАЧАЛО

ВВОД ИСХОДНЫХ ДАННЫХ (РАЗМЕРЫ ПОЛЯ, РАЗМЕР ЯЧЕЙКИ, НАЧАЛЬНОЕ РАСПОЛОЖЕНИЕ РОБОТА, ПОРОГОВОЕ ЗНАЧЕНИЕ ДЛЯ ОСТАНОВКИ ПЕРЕД ПРЕПЯТСТВИЕМ, КРИТЕРИЙ ОЦЕНКИ МАРШРУТА, КРИТЕРИЙ ОСТАНОВА)

СОЗДАНИЕ НЕСКОЛЬКИХ МАРШРУТОВ (ПОПУЛЯЦИЯ)

ОСНОВНОЙ АЛГОРИТМ (ПРОХОЖДЕНИЕ ЛАБИРИНТА, ПОВТОРЯЕМ N РАЗ)

ОЦЕНКА РЕЗУЛЬТАТА (СЕЛЕКЦИЯ, ОТСЕВ)

СКРЕЩИВАНИЕ ЛУЧШИХ ВАРИАНТОВ

МУТАЦИЯ (ИЗМЕНЕНИЕ ПОТОМСТВА, НОВАЯ ПОПУЛЯЦИЯ)

ПРОВЕРКА КРИТЕРИЯ ОСТАНОВА

НЕТ

ДА

ВЫБОР ЛУЧШЕЙ ОСОБИ

НАЧАЛО

БЛОК-СХЕМА ОСНОВНОГО АЛГОРИТМА (ОБЪЕЗД ПРЕПЯТСТВИЯ)

НАЧАЛО

СЧИТЫВАНИЕ ИСХОДНЫХ ДАННЫХ (РАЗМЕРЫ ПОЛЯ, РАЗМЕР ЯЧЕЙКИ, НАЧАЛЬНОЕ РАСПОЛОЖЕНИЕ РОБОТА, ПОРОГОВОЕ ЗНАЧЕНИЕ ДЛЯ ОСТАНОВКИ ПЕРЕД ПРЕПЯТСТВИЕМ, КРИТЕРИЙ ОЦЕНКИ МАРШРУТА)

ДВИЖЕНИЕ ВПЕРЕД

ДАТЧИК РАССТОЯНИЯ ПОКАЗЫВАЕТ < ПОРОГ

НЕТ

ДА

СЧИТАЕМ КОЛИЧЕСТВО ПРЕПЯТСТВИЙ НА ПУТИ i=i+1

ОСТАНОВКА РОБОТА

ВЫБОР ПУТИ ПО МАРШРУТУ

ПОВОРОТ ПО МАРШРУТУ (НАЛЕВО ИЛИ НАПРАВО НА 90 ГРАДУСОВ)

ВПЕРЕД НА РАССТОЯНИЕ 1 ЯЧЕЙКИ

ПОВОРОТ ПО МАРШРУТУ (НАЛЕВО ИЛИ НАПРАВО НА 90 ГРАДУСОВ)

ЗАДАЧА

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

Размеры лабиринта 4х10 ячеек.

Создание нескольких маршрутов (популяция):

2-3-4-3-2 2-3-4-3-4 2-3-2-3-2 2-3-2-3-4 2-3-2-1-2 2-1-2-3-2 2-1-2-3-4 2-1-2-1-2

1

2

3

4

5

6

7

8

9

10

1 2 3 4

На рисунке показана схема лабиринта, и пример прохождения его роботом по заданному маршруту (2-3-4-3-2). Результат прохождения – робот достиг 7 линии лабиринта, не добравшись до финиша.

Результаты прохождения лабиринта для других маршрутов:

2-3-4-3-4 5

2-3-2-3-2 3

2-3-2-3-4 5

2-3-2-1-2 3

2-1-2-3-2 7

2-1-2-3-4 9

2-1-2-1-2 7

Общая сумма: 46.

Отбор лучших:

2-3-4-3-2 7

2-1-2-3-2 7

2-1-2-3-4 9

2-1-2-1-2 7

Скрещивание и мутация:

2-1-2-4-3

2-1-2-4-2

2-1-2-4-1

2-3-4-2-3

2-3-4-2-1

2-3-4-2-4

2-3-4-1-3

2-3-4-1-2

Результаты прохождения лабиринта для полученных маршрутов:

2-1-2-4-3 10

2-1-2-4-2 10

2-1-2-4-1 10

2-3-4-2-3 7

2-3-4-2-1 7

2-3-4-2-4 9

2-3-4-1-3 5

2-3-4-1-2 5

Общая сумма: 63.

Отбор лучших:

2-1-2-4-3 10

2-1-2-4-2 10

2-1-2-4-1 10

2-3-4-2-4 9

Вывод:

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

Заключение.

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

Данное исследование включает следующие этапы:

а) составление маршрута робота;

б) изменение траектории движения робота;

в) планирование маршрута (выбор оптимального пути);

г) управление местоположением робота;

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

Список рекомендуемой литературы.

1.Бобровский С. Навигация мобильных роботов/Сергей Бобровский

2.Курейчик В.М. Генетические алгоритмы и их применение/В.М.Курейчик .– Таганрог: ТРТУ, 2002

3.Емельянов В.В. Теория и практика эволюционного моделирования/ В. В.Емельянов, В. В. Курейчик В. В., В. М. Курейчик. – М: Физматлит, 2003. – 432 c.

4. Управление роботами. Состояние и перспективы [Текст] : материалы ХХ общ. собрания академии навигации и управления движением, 26 октября 2005 г. С.-Петербург / редкол : П.К.Плотников (отв. ред.). - С.-Петербург: Электроприбор, 2008. - 20 с.

5. Мартыненко, Ю. Г.Управление движением мобильных колёсных роботов [Текст] / Ю.Г. Мартыненко - МГУ им. М.В. Ломоносова, 2005. - 29-80с.

6. Интеллектуальный мобильный робот [Электронный ресурс] / - Евстигнеев Д.В. - Режим доступа: www/ URL: http://robot-rad.narod.ru/index.html/ - 15.02.