А. А. ГРИДНЕВ
Научный руководитель – Е. В. ЧЕПИН, к. т.н., доцент
Национальный исследовательский ядерный университет «МИФИ»
ПОИСК ПУТИ В НЕИЗВЕСТНОМ ЛАБИРИНТЕ НА
ОСНОВЕ МОДИФИЦИРОВАННОГО АЛГОРИТМА A*
В статье описываются особенности решения задачи поиска пути в неизвестном лабиринте колёсным роботом на основе модификации алгоритма A*.
Задача поиска пути в лабиринте является одной из распространённых конкурсных задач для робототехники. В этом году . ру» сформулировал её так: робот находится в лабиринте, известны GPS координаты начальной и конечной позиции, на роботе есть GPS-приёмник, робот должен добраться из начальной точки в конечную точку за минимальное время. Для обнаружения стен у робота имеется ультразвуковой дальномер.
Использование алгоритмов одной руки бессмысленно, так как они накладывают ограничение на лабиринт. Одним из возможных решений является использование алгоритма A* [1] для поиска пути. Для этого в оперативной памяти создаётся карта лабиринта в виде матрицы узлов, которые либо проходимы (нет препятствий), либо непроходимы (есть препятствие). Карта динамически обновляется: при обнаружении стен они добавляются на карту, и происходит перерасчёт маршрута. По полученному маршруту робот ведётся к точке назначения.
Обнаружение стены может быть в двух случаях: робот едет и робот поворачивается. В случае, когда робот едет, необходимо нанести стену на карту и пересчитать маршрут, если он проходил через то место, на котором образовалась стена. В случае, когда робот поворачивается, наилучшим вариантом является продолжение поворота, пока обнаруживается стена, и только после это пересчитать маршрут. Это позволит избежать лишних пересчётов маршрута и колебаний робота (поворота налево-направо, пока не будет найден конец стены).
Алгоритм A* отличается от других алгоритмов поиска путей на графе тем, что порядок обхода вершин в нём определяется эвристической функцией – суммой стоимости достижения рассматриваемой вершины из начальной и эвристической оценки расстояния от рассматриваемой вершины до конечной вершины. В случае с картой лабиринта граф вырождается в матрицу узлов, в которой эвристическая оценка расстояния от рассматриваемого узла до конечного узла может быть рассчитана, как евклидово расстояние или манхэттенское расстояние (расстояние городских кварталов).
Традиционная реализация алгоритма A* имеет узкое место – реализация открытого списка, в котором элементы в памяти выделяются и освобождаются динамически. Таким образом, на каждой итерации алгоритма происходит один вызов функции освобождения памяти (извлечение первого элемента списка) и до восьми (максимально число не посещённых соседей) вызовов выделения памяти. Также вызовы этих функций предполагают реализацию менеджера памяти, если его нет (например, в микроконтроллерах).
Чтобы избежать использования динамической памяти, есть вариант реализации открытого списка на массиве узлов, при котором в каждом узле есть возможность указать координаты следующего узла в открытом списке или его отсутствие [2]. Таким образом, в структуру узла включаются дополнительные переменные, что требует больший объём оперативной памяти, но в текущее время она не является проблемой.
При поиске маршрута может случиться так, что из двух коротких маршрутов будет выбран кратчайший, в котором так много поворотом, что в реальности быстрее было бы проследовать по более длинному маршруту, но с меньшим количеством поворотов. Для решения этой проблемы достаточно в стоимость перехода в соседний узел вложить стоимость поворота.
Для того чтобы из полученного из алгоритма A*пути в лабиринте, который представлен списком соседних узлов, получить пригодный для навигации в лабиринте список путевых точек, необходимо выпрямление пути. Самый простой способ – проверка линейной проходимости из одной точки в другую и удаление лишних точек. Для этого подходит алгоритм Брезенхэма [3], который используется для построения линий в компьютерной графике.
Список литературы
Introduction to A* // URL: http://theory. stanford. edu/~amitp/GameProgramming/AStarComparison. html (дата обращения: 29.11.2015) Toward More Realistic Pathfinding // URL: http://www. /view/feature/3096/toward_more_realistic_pathfinding. php (дата обращения: 29.11.2015) The Bresenham Line-Drawing Algorithm // URL: http://www. cs. helsinki. fi/group/goa/mallinnus/lines/bresenh. html (дата обращения: 29.11.2015)
