Перемещение робота в нужную точку векторной карты

Материал из roboforum.ru Wiki
Перейти к: навигация, поиск


Классическая постановка задачи поиска пути на карте

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

Дано: Карта с указанными, текущее положение робота и конечное положение, в которое нам нужно попасть.

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

При этом под "положением робота" могут пониматься как "координаты робота", так и пара "координаты робота + направление робота".


Решение классической задачи поиска пути на карте

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


Когда граф допустимых путей построен поиск пути на карте сводится к задаче поиска пути во взвешенном графе. А для этого есть очень эффективный "алгоритм Дейкстры".

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