Перемещение робота в нужную точку векторной карты — различия между версиями

Материал из roboforum.ru Wiki
Перейти к: навигация, поиск
(Решение классической задачи поиска пути на карте)
(Решение классической задачи поиска пути на карте)
Строка 15: Строка 15:
 
== Решение классической задачи поиска пути на карте ==
 
== Решение классической задачи поиска пути на карте ==
  
Наиболее простой подход - составить граф допустимых путей, вершинами которого будут точки карты, а ребрами - доступная возможность проехать из 1 точку в другую напрямую, избежав препятствия. В случае растровой карты за вершины графа принимаются центры клеток, а за ребра - возможность проехать в соседние клетки. В случае же векторной карты, понятно, что вообще таких точек на карте бесконечное множество, но мы можем выбрать конечное число точек на карте, чтобы незначительно ограничить свои возможности и уже на этих точках искать оптимальный маршрут. (Подробнее о построении этого графа смотрите [[Построение графа допустимых путей для векторной карты]]). Обязательное условие - в список вершина этого графа должны входить точки старта и финиши (где мы сейчас находимся и куда нам нужно попасть).
+
Наиболее простой подход - составить граф допустимых путей, вершинами которого будут точки карты, а ребрами - доступная возможность проехать из 1 точку в другую напрямую, избежав препятствия. В случае растровой карты за вершины графа принимаются центры клеток, а за ребра - возможность проехать в соседние клетки. В случае же векторной карты, понятно, что вообще таких точек на карте бесконечное множество, но мы можем выбрать конечное число точек на карте, чтобы незначительно ограничить свои возможности и уже на этих точках искать оптимальный маршрут. (Подробнее о построении этого графа смотрите [[Построение графа допустимых путей для векторной карты]]). Обязательное условие - в список вершин этого графа должны входить точки старта и финиши (где мы сейчас находимся и куда нам нужно попасть).
  
  

Версия 07:41, 15 декабря 2007


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

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

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

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

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


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

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


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

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