Перемещение робота в нужную точку векторной карты — различия между версиями
=DeaD= (обсуждение | вклад) |
=DeaD= (обсуждение | вклад) |
||
| Строка 2: | Строка 2: | ||
{{robo-stub}} | {{robo-stub}} | ||
| − | + | == Классическая постановка задачи поиска пути на карте == | |
| − | + | При решении этой задачи обычно считается, что робот может поворачиваться в нужную сторону вокруг своей оси на месте (танковый поворот) и этим временем поворота обычно пренебрегают. Сама постановка классической задачи перемещения робота в нужную точку карты обычно формулируется следующим образом: | |
| − | '''Требуется:''' Составить маршрут ( | + | '''Дано:''' Карта с указанными, текущее положение робота и конечное положение, в которое нам нужно попасть. |
| + | |||
| + | '''Требуется:''' Составить маршрут (ломаную от текущей точки до нужной), позволяющий избегажать всех препятствий и приводящий в нужную точку карты за приемлимое или оптимальное время. | ||
При этом под "положением робота" могут пониматься как "координаты робота", так и пара "координаты робота + направление робота". | При этом под "положением робота" могут пониматься как "координаты робота", так и пара "координаты робота + направление робота". | ||
| − | Наиболее | + | |
| + | == Решение классической задачи поиска пути на карте == | ||
| + | |||
| + | Наиболее простой подход - составить граф допустимых путей, вершинами которого будут точки карты, а ребрами - доступная возможность проехать из 1 точку в другую напрямую, избежав препятствия. В случае растровой карты за вершины графа принимаются центры клеток, а за ребра - возможность проехать в соседние клетки. В случае же векторной карты, понятно, что вообще таких точек на карте бесконечное множество, но мы можем выбрать конечное число точек на карте, чтобы незначительно ограничить свои возможности и уже на этих точках искать оптимальный маршрут. (Подробнее о построении графа допустимых путей смотрите на странице [[Построение графа допустимых путей для векторной карты]]). Обязательное условие - в список вершина этого графа должны входить точки старта и финиши (где мы сейчас находимся и куда нам нужно попасть). | ||
| + | |||
| + | |||
| + | Когда граф допустимых путей построен поиск пути на карте сводится к задаче поиска пути во взвешенном графе. А для этого есть очень эффективный "алгоритм Дейкстры". | ||
| + | |||
| + | Суть алгоритма сводится к тому, что в нем создается очередь вершин графа в которые мы уже нашли путь из точки старта, но которые мы еще не "обработали". При этом очередь упорядочена по длине пути из стартовой вершнины до вершины лежащей в очереди. | ||
Версия 07:40, 15 декабря 2007
|
Это незавершённая статья по робототехнике. Вы можете помочь проекту, исправив и дополнив её. |
Классическая постановка задачи поиска пути на карте
При решении этой задачи обычно считается, что робот может поворачиваться в нужную сторону вокруг своей оси на месте (танковый поворот) и этим временем поворота обычно пренебрегают. Сама постановка классической задачи перемещения робота в нужную точку карты обычно формулируется следующим образом:
Дано: Карта с указанными, текущее положение робота и конечное положение, в которое нам нужно попасть.
Требуется: Составить маршрут (ломаную от текущей точки до нужной), позволяющий избегажать всех препятствий и приводящий в нужную точку карты за приемлимое или оптимальное время.
При этом под "положением робота" могут пониматься как "координаты робота", так и пара "координаты робота + направление робота".
Решение классической задачи поиска пути на карте
Наиболее простой подход - составить граф допустимых путей, вершинами которого будут точки карты, а ребрами - доступная возможность проехать из 1 точку в другую напрямую, избежав препятствия. В случае растровой карты за вершины графа принимаются центры клеток, а за ребра - возможность проехать в соседние клетки. В случае же векторной карты, понятно, что вообще таких точек на карте бесконечное множество, но мы можем выбрать конечное число точек на карте, чтобы незначительно ограничить свои возможности и уже на этих точках искать оптимальный маршрут. (Подробнее о построении графа допустимых путей смотрите на странице Построение графа допустимых путей для векторной карты). Обязательное условие - в список вершина этого графа должны входить точки старта и финиши (где мы сейчас находимся и куда нам нужно попасть).
Когда граф допустимых путей построен поиск пути на карте сводится к задаче поиска пути во взвешенном графе. А для этого есть очень эффективный "алгоритм Дейкстры".
Суть алгоритма сводится к тому, что в нем создается очередь вершин графа в которые мы уже нашли путь из точки старта, но которые мы еще не "обработали". При этом очередь упорядочена по длине пути из стартовой вершнины до вершины лежащей в очереди.
