Перемещение робота в нужную точку векторной карты
|
Это незавершённая статья по робототехнике. Вы можете помочь проекту, исправив и дополнив её. |
Классическая постановка задачи поиска пути на карте
При решении этой задачи обычно считается, что робот может поворачиваться в нужную сторону вокруг своей оси на месте (танковый поворот) и этим временем поворота обычно пренебрегают. Сама постановка классической задачи перемещения робота в нужную точку карты обычно формулируется следующим образом:
Дано: Карта с указанными, текущее положение робота и конечное положение, в которое нам нужно попасть.
Требуется: Составить маршрут (ломаную от текущей точки до нужной), позволяющий избегажать всех препятствий и приводящий в нужную точку карты за приемлимое или оптимальное время.
При этом под "положением робота" могут пониматься как "координаты робота", так и пара "координаты робота + направление робота".
Решение классической задачи поиска пути на карте
Наиболее простой подход - составить граф допустимых путей, вершинами которого будут точки карты, а ребрами - доступная возможность проехать из 1 точку в другую напрямую, избежав препятствия. В случае растровой карты за вершины графа принимаются центры клеток, а за ребра - возможность проехать в соседние клетки. В случае же векторной карты, понятно, что вообще таких точек на карте бесконечное множество, но мы можем выбрать конечное число точек на карте, чтобы незначительно ограничить свои возможности и уже на этих точках искать оптимальный маршрут. (Подробнее о построении графа допустимых путей смотрите на странице Построение графа допустимых путей для векторной карты). Обязательное условие - в список вершина этого графа должны входить точки старта и финиши (где мы сейчас находимся и куда нам нужно попасть).
Когда граф допустимых путей построен поиск пути на карте сводится к задаче поиска пути во взвешенном графе. А для этого есть очень эффективный "алгоритм Дейкстры".
Суть алгоритма сводится к тому, что в нем создается очередь вершин графа в которые мы уже нашли путь из точки старта, но которые мы еще не "обработали". При этом очередь упорядочена по длине пути из стартовой вершнины до вершины лежащей в очереди.
