Аннотация 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
В настоящее время тема робототехники и, в частности, движения в среде с препятствиями является актуальной и используемой во многих сферах жизни. Мобильный робот - это робот, который может самостоятельно передвигаться в пространстве. Есть три больших класса мобильных роботов: первый - это наземные роботы, второй - воздушные, третий - морские. Для все них актуальны задачи построения траектории обхода препятствий и построения путь до цели.
Задачи нахождения кратчайшего пути всегда были актуальны. Правильно построенный маршрут позволяет быстро выполнить поставленные задачи с наименьшей затратой ресурсов. Самой известной задачей на оптимизацию пути остается задача коммивояжёра. Не смотря на простоту формулировки задачи, нахождение действительно оптимального пути является достаточно сложной задачей. Учитывая эти свойства, начиная со второй половины XX века исследование задачи коммивояжёра имеет не столько практический смысл, сколько теоретический - используется в качестве модели для разработки новых алгоритмов оптимизации.
Для постройки пути в первую очередь следует определить при каких ограничениях будет работать мобильный робот: определить возможность перемещения только по определённым строго заданным дорогам или перемещения по всей карте местности. Учитывая кинематические особенности робота, которые также будут накладывать свои ограничения на постройку пути, условия окружающей среды могут вносить существенную роль.
При перемещении из точки А в точку Б в большинстве случаев можно будет построить несколько вариантов пути. Выбор наилучшего пути можно осуществлять автоматически при помощи разных алгоритмов. Нам нужно лишь учитывать выгоду прохождения через определённые участки пути. Выгодность пути может быть выражена из множества факторов. Зная необходимые критерии, алгоритм может найти и выбрать наилучший маршрут.
Предметом исследования стали способы решения задачи о нахождении кратчайшего пути.
Поставленной целью в рамках данной работы является создание программы нахождения кратчайшего пути.
В качестве исследуемого алгоритма был использован алгоритм А*. Алгоритм A* - это мощный алгоритм с широким спектром применения. Это самый популярный способ для нахождения кратчайшего пути, так как система реализации чрезвычайно гибкая. Сегодня этот алгоритм применяют в различных областях от машинного обучения до беспилотных автомобилей.
В ходе работы были рассмотрены методы решения задачи нахождения кратчайшего пути. Описаны необходимые задачи для построения пути мобильным роботом.
Для построения путей был выбран алгоритм А*. Алгоритм был реализован на языке Python в среде разработки PyCham при помощи библиотеки pygame. Были проведены сравнения работы алгоритма при трех разных эвристиках: расстояния Чебышева, Манхэттенского расстояния и расстояния евклидовой прямой. Сравнивалась работа алгоритма на картах с различными условиями проходимости: на карте с постоянной проходимостью, на карте с препятствиями и на карте с различной степенью проходимости. В сравнении полученных результатах учитывалось количество посещенных клеток и количество клеток для постройки пути от точки старта до целевой точки. Не зависимо от выбранной эвристики, алгоритм строил маршрут с одинаковым количеством клеток, но траектория могла сильно отличаться в зависимости от выбранной функции. По проведенным испытаниям было обнаружено, что при определенных условиях функция, показывающая худшие результаты способна находить путь до цели с наименьшим количеством посещенных клеток и, наоборот, функции, показывающей лучшие результаты, требовалось большее количество посещенных клеток. Данное поведение алгоритма объясняется порядком обхода клеток в очереди.
