📄Работа №187033
Тема: Создание алгоритма нахождения кратчайшего пути
Характеристики работы
Тип работы
Дипломные работы, ВКР
Предмет
Робототехника
Объем:
42 листов
Год:
2022
Просмотров:
77
4400
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Аннотация 2
ВВЕДЕНИЕ 6
1 Поиск оптимального пути 8
1.1 Задача коммивояжера 8
1.2 Обзор алгоритмов поиска оптимального пути 9
1.3 Алгоритмы на графах 11
1.4 Построения пути мобильным роботом 12
2 Построения пути А* 13
2.1 Представления графа на карте 13
2.2 Эвристики для А* 14
2.3 Программная реализация алгоритма А* 18
2.4 Анализ работы алгоритма А* 19
ЗАКЛЮЧЕНИЕ 35
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ 36
Приложение А Код программы реализации алгоритма A* 37
ВВЕДЕНИЕ 6
1 Поиск оптимального пути 8
1.1 Задача коммивояжера 8
1.2 Обзор алгоритмов поиска оптимального пути 9
1.3 Алгоритмы на графах 11
1.4 Построения пути мобильным роботом 12
2 Построения пути А* 13
2.1 Представления графа на карте 13
2.2 Эвристики для А* 14
2.3 Программная реализация алгоритма А* 18
2.4 Анализ работы алгоритма А* 19
ЗАКЛЮЧЕНИЕ 35
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ 36
Приложение А Код программы реализации алгоритма A* 37
📖 Аннотация
Работа посвящена исследованию и реализации алгоритмов для нахождения кратчайшего пути, актуальных для задач автономной навигации мобильных роботов в средах с препятствиями. Проблема эффективного планирования траектории является ключевой для робототехники, поскольку от выбора оптимального маршрута напрямую зависят скорость выполнения задачи и расход ресурсов. В качестве методологической основы был выбран и детально проанализирован алгоритм A*, реализованный на языке Python с использованием библиотеки Pygame. В ходе исследования была разработана программа, позволившая провести сравнительный анализ работы алгоритма с тремя различными эвристическими функциями — Чебышева, Манхэттенского и Евклидова расстояния — на картах с разной структурой проходимости. Результаты показали, что, хотя итоговая длина построенного пути оставалась неизменной, выбор эвристики существенно влиял на траекторию и эффективность поиска, измеряемую количеством посещённых ячеек; было установлено, что в различных условиях эвристика, демонстрирующая худшие результаты в одних сценариях, может оказаться наиболее эффективной в других из-за особенностей порядка обхода. Практическая значимость работы заключается в возможности применения разработанного решения и полученных выводов для моделирования и оптимизации систем навигации наземных, воздушных и морских автономных аппаратов. Обзор литературы включает анализ классических задач оптимизации, таких как задача коммивояжёра, и современных подходов к планированию пути. Таким образом, исследование демонстрирует важность адаптивного выбора эвристической функции в алгоритме A* для повышения эффективности поиска пути в зависимости от конкретных условий окружающей среды.
📖 Введение
В настоящее время тема робототехники и, в частности, движения в среде с препятствиями является актуальной и используемой во многих сферах жизни. Мобильный робот - это робот, который может самостоятельно передвигаться в пространстве. Есть три больших класса мобильных роботов: первый - это наземные роботы, второй - воздушные, третий - морские. Для все них актуальны задачи построения траектории обхода препятствий и построения путь до цели.
Задачи нахождения кратчайшего пути всегда были актуальны. Правильно построенный маршрут позволяет быстро выполнить поставленные задачи с наименьшей затратой ресурсов. Самой известной задачей на оптимизацию пути остается задача коммивояжёра. Не смотря на простоту формулировки задачи, нахождение действительно оптимального пути является достаточно сложной задачей. Учитывая эти свойства, начиная со второй половины XX века исследование задачи коммивояжёра имеет не столько практический смысл, сколько теоретический - используется в качестве модели для разработки новых алгоритмов оптимизации.
Для постройки пути в первую очередь следует определить при каких ограничениях будет работать мобильный робот: определить возможность перемещения только по определённым строго заданным дорогам или перемещения по всей карте местности. Учитывая кинематические особенности робота, которые также будут накладывать свои ограничения на постройку пути, условия окружающей среды могут вносить существенную роль.
При перемещении из точки А в точку Б в большинстве случаев можно будет построить несколько вариантов пути. Выбор наилучшего пути можно осуществлять автоматически при помощи разных алгоритмов. Нам нужно лишь учитывать выгоду прохождения через определённые участки пути. Выгодность пути может быть выражена из множества факторов. Зная необходимые критерии, алгоритм может найти и выбрать наилучший маршрут.
Предметом исследования стали способы решения задачи о нахождении кратчайшего пути.
Поставленной целью в рамках данной работы является создание программы нахождения кратчайшего пути.
В качестве исследуемого алгоритма был использован алгоритм А*. Алгоритм A* - это мощный алгоритм с широким спектром применения. Это самый популярный способ для нахождения кратчайшего пути, так как система реализации чрезвычайно гибкая. Сегодня этот алгоритм применяют в различных областях от машинного обучения до беспилотных автомобилей.
Задачи нахождения кратчайшего пути всегда были актуальны. Правильно построенный маршрут позволяет быстро выполнить поставленные задачи с наименьшей затратой ресурсов. Самой известной задачей на оптимизацию пути остается задача коммивояжёра. Не смотря на простоту формулировки задачи, нахождение действительно оптимального пути является достаточно сложной задачей. Учитывая эти свойства, начиная со второй половины XX века исследование задачи коммивояжёра имеет не столько практический смысл, сколько теоретический - используется в качестве модели для разработки новых алгоритмов оптимизации.
Для постройки пути в первую очередь следует определить при каких ограничениях будет работать мобильный робот: определить возможность перемещения только по определённым строго заданным дорогам или перемещения по всей карте местности. Учитывая кинематические особенности робота, которые также будут накладывать свои ограничения на постройку пути, условия окружающей среды могут вносить существенную роль.
При перемещении из точки А в точку Б в большинстве случаев можно будет построить несколько вариантов пути. Выбор наилучшего пути можно осуществлять автоматически при помощи разных алгоритмов. Нам нужно лишь учитывать выгоду прохождения через определённые участки пути. Выгодность пути может быть выражена из множества факторов. Зная необходимые критерии, алгоритм может найти и выбрать наилучший маршрут.
Предметом исследования стали способы решения задачи о нахождении кратчайшего пути.
Поставленной целью в рамках данной работы является создание программы нахождения кратчайшего пути.
В качестве исследуемого алгоритма был использован алгоритм А*. Алгоритм A* - это мощный алгоритм с широким спектром применения. Это самый популярный способ для нахождения кратчайшего пути, так как система реализации чрезвычайно гибкая. Сегодня этот алгоритм применяют в различных областях от машинного обучения до беспилотных автомобилей.
✅ Заключение
В ходе работы были рассмотрены методы решения задачи нахождения кратчайшего пути. Описаны необходимые задачи для построения пути мобильным роботом.
Для построения путей был выбран алгоритм А*. Алгоритм был реализован на языке Python в среде разработки PyCham при помощи библиотеки pygame. Были проведены сравнения работы алгоритма при трех разных эвристиках: расстояния Чебышева, Манхэттенского расстояния и расстояния евклидовой прямой. Сравнивалась работа алгоритма на картах с различными условиями проходимости: на карте с постоянной проходимостью, на карте с препятствиями и на карте с различной степенью проходимости. В сравнении полученных результатах учитывалось количество посещенных клеток и количество клеток для постройки пути от точки старта до целевой точки. Не зависимо от выбранной эвристики, алгоритм строил маршрут с одинаковым количеством клеток, но траектория могла сильно отличаться в зависимости от выбранной функции. По проведенным испытаниям было обнаружено, что при определенных условиях функция, показывающая худшие результаты способна находить путь до цели с наименьшим количеством посещенных клеток и, наоборот, функции, показывающей лучшие результаты, требовалось большее количество посещенных клеток. Данное поведение алгоритма объясняется порядком обхода клеток в очереди.
Для построения путей был выбран алгоритм А*. Алгоритм был реализован на языке Python в среде разработки PyCham при помощи библиотеки pygame. Были проведены сравнения работы алгоритма при трех разных эвристиках: расстояния Чебышева, Манхэттенского расстояния и расстояния евклидовой прямой. Сравнивалась работа алгоритма на картах с различными условиями проходимости: на карте с постоянной проходимостью, на карте с препятствиями и на карте с различной степенью проходимости. В сравнении полученных результатах учитывалось количество посещенных клеток и количество клеток для постройки пути от точки старта до целевой точки. Не зависимо от выбранной эвристики, алгоритм строил маршрут с одинаковым количеством клеток, но траектория могла сильно отличаться в зависимости от выбранной функции. По проведенным испытаниям было обнаружено, что при определенных условиях функция, показывающая худшие результаты способна находить путь до цели с наименьшим количеством посещенных клеток и, наоборот, функции, показывающей лучшие результаты, требовалось большее количество посещенных клеток. Данное поведение алгоритма объясняется порядком обхода клеток в очереди.
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.