roboforum.ru

Технический форум по робототехнике.

Нахождение маршрута движения методом градиентных полей.

Автомат, адаптивный автомат ... разум

Нахождение маршрута движения методом градиентных полей.

Сообщение setar » 12 окт 2004, 18:32

Этот метод описывает методы нахождения оптимального маршрута на заранее известной карте.

Свободный перевод материала :
( не пиняйте на корявость - редактирование машинного перевода)
http://www.gamedev.net/reference/articl ... le1125.asp


Что такое - поле потенциала?
Прежде, чем начать, мы должны договориться о некоторых определениях. Мы будем говорить о 'модуле' размера пиксел, который может свободно маневрировать во всех 8 направлениях со скоростью одного пикселя в среде. Эта среда ? 2х мерная карта, которая была разделена на квадраты, размером один пиксель каждый. В этом примере мы возьмем 100*100 квадратов и назовем это 'сеткой'. Границы - стены, через которые нельзя проникнуть и есть несколько 'объектов' на карте, которых нужно избежать. В теории, эти объекты могут иметь любую форму, но мы сосредоточимся на прямоугольниках.

Теперь, что мы еще должны делать - определить поле потенциала. В сущности, Вы можете думать об этом как о большой матрице. Каждый пиксель в 'сетке' представлен в матрице номером, говоря кое-что о состоянии. Так как наша окончательная цель состоит в том, чтобы найти путь от нашего стартового местоположения до нашего места назначения, логично предположить, что мы собираемся управлять и использовать эти числа как решающий фактор, чтобы двигаться по сетке.
В примерах ниже мы будем всегда пробовать понижать, насколько возможно, 'потенциал' нашего места назначения, и использовать мексимально высокий потенциал при создании стартового местоположения. Тогда мы можем,  двигаться от пикселя до пикселя в сетке, перемещаясь только на те пикселы, которые имеют более низкий потенциал, чем тот, который наш модуль находится в данный момент. Чтобы избегать врезаться в препятствия, мы дадим им очень высокое потенциальное значение (выше чем самый высокий доступный пиксель в сетке), так что наш модуль никогда не будет соблазняться перемещаться на них.
Вложения
1.gif
На картинке Вы видите поле потенциала, обозначенное цветом. В этом случае более низкий потенциал означает более темный зеленый. Модуль - синий пиксель в верхнем левом угле. Наша цель - красный пиксель в более низком правом угле. Препятствия показаны белым
1.gif (10.13 КиБ) Просмотров: 7146
Последний раз редактировалось setar 12 окт 2004, 18:42, всего редактировалось 1 раз.
Аватара пользователя
setar
Site Admin
 
Сообщения: 10984
Зарегистрирован: 04 окт 2004, 12:58
Откуда: St.Petersburg
Skype: taranenko.sergey
ФИО: Сергей Тараненко

Сообщение setar » 12 окт 2004, 18:37

Методика 1: линейный градиент
Теперь рассмотрим несколько методов. Каждый будет немного более сложным чем предыдущий, решая проблемы от предыдущей методики, но к сожалению создавая новые.
Мы начинаем простой метод.
Вычисляем расстояние каждого пикселя до места назначения и даем это расстояние как 'потенциальное' значение к тому пикселю. Пожалуйста обратите внимание, что в этом случае Вы не должны заботиться о препятствиях (только дать им очень высокое значение). Как только это сделано, мы применяем этот алгоритм: "Проверьте все соседние пиксели текущего пикселя и выберите пиксель с самым низким потенциальным значением. Двигайтесь в этот пиксель и продолжайте, пока Вы не достигаете вашей цели или застряните."
Этот алгоритм работает весьма хорошо, если Вы имеете немного объектов в сетке, но часто, модуль застрянет позади объекта и не имеет возможности  вернуться на правильный  путь.

Методика 2: Заполнение местных минимумов
Как мы видели в первой методике можно застрять. Это случается, когда модуль находит местный минимум. В поле потенциала это представлено пикселем, который имеет соседей, которые являются или объектами или доступны, но имеют более высокое значение, не являясь местом назначения.
Улучшим наш алгоритм, используя поиск по первому наилучшему совпадению. Сделаем это, строя дерево с пикселями в сетке. Наш корень в дереве - стартовое местоположение. Этот корень имеет  8 направлений, в которых наш модуль может путешествовать, образуя ветви. Возьмем ветвь с самым низким значением и оценим все направления, в которые мы можем путешествовать отсюда, но не те, которые находятся уже в дереве. Тогда оцениваем все листья в дереве и повторяем процесс для нахождения самого низкого значения. Продолжаем процесс пока не дошли до нашего места назначения, или пока мы оценили все листья и не можем найти другой пиксель для движения (так случится, если недостижимо место назначения от нашего стартового местоположения). Если повезло, и путь определен, преодолеваем дерево от корня до выхода, содержащего наше место назначения.
Вложения
2.gif
Если Вы делаете графическое представление формирования дерева, Вы можете видеть, что местные минимумы заполняются, пока не переполнятся, и мы можем продолжить прямую строку к нашей цели. В изображении, члены дерева являются синими, а листья являются желт
2.gif (11.31 КиБ) Просмотров: 7337
Последний раз редактировалось setar 12 окт 2004, 18:40, всего редактировалось 1 раз.
Аватара пользователя
setar
Site Admin
 
Сообщения: 10984
Зарегистрирован: 04 окт 2004, 12:58
Откуда: St.Petersburg
Skype: taranenko.sergey
ФИО: Сергей Тараненко

Сообщение setar » 12 окт 2004, 18:40

Методика 3: лучше предотвратить...
Мы, возможно, нашли способ выйти из местных минимумов в нашем предыдущем решении, но было бы лучше, если мы могли бы только найти способ не иметь никаких местных минимумов вообще. Чтобы достигнуть этого, нужно изменить метод, которым формируется наше поле потенциала.
Вместо того, чтобы непосредственно вычислять расстояние между пикселем и место назначением, дадим месту назначения значение нуль и затем применим такой алгоритм: Каждый прямой (горизонтальный и вертикальный, но не диагональный) сосед места назначения получает значение 1, тогда их прямые соседи получают 2, и так далее...
Так как только наше место назначения имеет нулевое значение, и каждый другой пиксель всегда имеет соседа с более низким значением, задача будет решена, если путь существует. Этот метод также известен как расширение фронта импульса.
Вложения
3.gif
Если Вы смотрите на изображение, Вы обратите внимание, что местные минимумы теперь получают более высокое значение (обозначенные более ярким желтым), потому что это - более длинный путь вокруг объекта{цели}, чтобы добраться там чем в прямой строке. Путь,
3.gif (11.08 КиБ) Просмотров: 7594
Аватара пользователя
setar
Site Admin
 
Сообщения: 10984
Зарегистрирован: 04 окт 2004, 12:58
Откуда: St.Petersburg
Skype: taranenko.sergey
ФИО: Сергей Тараненко

Сообщение setar » 12 окт 2004, 18:43

Методика 4: Уйдите от граней
С тех пор как мы начали наше исследование поля потенциала, мы учились выходить из минимумов и даже запрещать их полностью. Но Вы заметите в последнем рисунке, что мы двигались опасно близко к краю объектов и стен. В среде, где мы могли бы только знать приблизительное местоположение объектов, будет лучше всего остаться как далеко от них насколько возможно, чтобы избежать столкновений.
Для этого мы должны расширить наш алгоритм от предыдущей методики. Вместо того, чтобы инициализировать один фронт импульса в место назначениее, мы теперь запустим фронт импульса в каждом пикселе, который находится на краю объекта. Каждый из этих 'пикселей края' получает уникальный идентификатор и дает этот идентификатор всем его прямым соседям. Когда два идентификатора, которые являются достаточно отличными, сталкиваются, мы нашли середину между двумя близкими объектами. Результатом будет своего рода диаграмма Voronoi между объектами, которые мы можем использовать как маршрут, чтобы передвигаться между объектами. Все, что мы тогда должны сделать - дать значения пикселям в сетке, которая не принадлежит этому маршруту так, чтобы наш модуль продвинулся на маршрут как можно скорее. Для этого мы можем использовать один из методов выше.
Вложения
4.gif
Изображение показывает фронтам импульса, исходящим из граней объектов{целей} и фиолетового маршрут точно в середине между несколькими объектами{целями}.
4.gif (14.9 КиБ) Просмотров: 7758
Аватара пользователя
setar
Site Admin
 
Сообщения: 10984
Зарегистрирован: 04 окт 2004, 12:58
Откуда: St.Petersburg
Skype: taranenko.sergey
ФИО: Сергей Тараненко

Сообщение setar » 12 окт 2004, 18:44

Заключение
Методы, описанные выше - интересная альтернатива для A* алгоритма, который, кажется, очень популярен в эти дни. Хотя поля потенциала требуют,  некоторых серьезных вычислений, их принцип можетбыть полезен, если Вы нуждаетесь быстро в изменяющихся  места назначения, потому что все, что нужно сделать - увеличить или уменьшить числа в некоторой области, чтобы делать это более (или менее) привлекательным  для модуля, чтобы следовать этим путем.
Аватара пользователя
setar
Site Admin
 
Сообщения: 10984
Зарегистрирован: 04 окт 2004, 12:58
Откуда: St.Petersburg
Skype: taranenko.sergey
ФИО: Сергей Тараненко

Сообщение =DeaD= » 12 окт 2004, 19:30

А можно просто использовать поиск в ширину на карте :)

Во всех этих алгоритмах плохо одно - у них всего 8 направлений максимум, т.е. все маршруты по большому счету будут неоптимальны.

Можно слегка переработать алгоритм и сделать его оптимальным для любого количества направлений, с ограничением, что узловые точки маршрута все-таки будут лежать в центрах "клеток".

Надо будет только специальным образом задать граф связей, но вычислений там потребуется видимо существенно больше, чтобы вытащить все вершины этого графа.
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Сообщение setar » 13 окт 2004, 10:26

=DeaD= писал(а):Во всех этих алгоритмах плохо одно - у них всего 8 направлений максимум, т.е. все маршруты по большому счету будут неоптимальны.

Регулируется шагом сетки, с уменьшением шага движения становятся более плавными.  К тому же никто не мешает сделать сглаживание траектории по трём точкам.
Аватара пользователя
setar
Site Admin
 
Сообщения: 10984
Зарегистрирован: 04 окт 2004, 12:58
Откуда: St.Petersburg
Skype: taranenko.sergey
ФИО: Сергей Тараненко

Сообщение =DeaD= » 13 окт 2004, 13:22

setar писал(а):
=DeaD= писал(а):Во всех этих алгоритмах плохо одно - у них всего 8 направлений максимум, т.е. все маршруты по большому счету будут неоптимальны.

Регулируется шагом сетки, с уменьшением шага движения становятся более плавными.  К тому же никто не мешает сделать сглаживание траектории по трём точкам.

Нет, именно 8 направлений, а не шаг сетки будут иметь значение, например без препятствий относительное перемещение (100,200) будет всегда состоять из двух кусков (100,100) и (0,100).

Сглаживание по трем точкам поможет в данном случае только в одной точке.

Хотя в принципе можно даже посчитать на сколько будет различаться оптимальный путь из А в Б в идеальном и 8-направленном методе. И это не шибко много, так что забудем.
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Сообщение setar » 13 окт 2004, 13:39

=DeaD= писал(а):Нет, именно 8 направлений, а не шаг сетки будут иметь значение, например без препятствий относительное перемещение (100,200) будет всегда состоять из двух кусков (100,100) и (0,100).

Ничего подобного ! невнимательное ознакомление с материалом.

Если шаг сетки 1 и нужно сделать перемещение (100,200) то результатом будет прямая, точнее это будет массив узлов сетки максимально приближенный к прямой (насколько позволяет её шаг).
Аватара пользователя
setar
Site Admin
 
Сообщения: 10984
Зарегистрирован: 04 окт 2004, 12:58
Откуда: St.Petersburg
Skype: taranenko.sergey
ФИО: Сергей Тараненко

Сообщение =DeaD= » 13 окт 2004, 14:34

setar писал(а):Ничего подобного ! невнимательное ознакомление с материалом.

Если шаг сетки 1 и нужно сделать перемещение (100,200) то результатом будет прямая, точнее это будет массив узлов сетки максимально приближенный к прямой (насколько позволяет её шаг).


неа :)
Изображение
Тогда это что? тут видно что вместо прямой едем по ломаной в нижнем правом углу.

И вообще исходя из 8 направлений никак не может быть оптимальным именно приближенная к прямой ломанная. Она ничем не будет по расстоянию отличаться от ломанной из 2 кусков. Это практически очевидно :)
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Сообщение setar » 13 окт 2004, 14:43

=DeaD= писал(а):неа :)
Тогда это что? тут видно что вместо прямой едем по ломаной в нижнем правом углу.

И вообще исходя из 8 направлений никак не может быть оптимальным именно приближенная к прямой ломанная. Она ничем не будет по расстоянию отличаться от ломанной из 2 кусков. Это практически очевидно :)

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

совпадение прямой маршрута с одним из 8 направлений поиска решения в данном случае случайное и исходит от постановки задачи - левый верхний угол старт, и нижний правый финиш. Просто в данной задаче область координат квадратная, а была бы она прямоугольная, то маршрут бы пролегал по диагонали, отличающейся от 45%.
Аватара пользователя
setar
Site Admin
 
Сообщения: 10984
Зарегистрирован: 04 окт 2004, 12:58
Откуда: St.Petersburg
Skype: taranenko.sergey
ФИО: Сергей Тараненко

Сообщение =DeaD= » 13 окт 2004, 15:01

setar писал(а):немного не так.
...skipped...
совпадение прямой маршрута с одним из 8 направлений поиска решения в данном случае случайное и исходит от постановки задачи - левый верхний угол старт, и нижний правый финиш. Просто в данной задаче область координат квадратная, а была бы она прямоугольная, то маршрут бы пролегал по диагонали, отличающейся от 45%.

Это почему случайное? видно же, что с угла препятствия в правую нижнюю точку идти над по прямой, а не по ломаной.
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Сообщение setar » 13 окт 2004, 16:29

=DeaD= писал(а):Это почему случайное? видно же, что с угла препятствия в правую нижнюю точку идти над по прямой, а не по ломаной.

Это второй метод, градиент которого построен по прямой линии, следовательно оттимальным маршрутом всегда является прямая соединяющая старт и финиш. После исчезновения препятствия траектория стремится вернуться на исходную прямую.

Впрочем согласен, выглядит не красиво.

Рациональнее использовать последний метод.
Аватара пользователя
setar
Site Admin
 
Сообщения: 10984
Зарегистрирован: 04 окт 2004, 12:58
Откуда: St.Petersburg
Skype: taranenko.sergey
ФИО: Сергей Тараненко

Сообщение =DeaD= » 14 окт 2004, 17:45

setar писал(а):Рациональнее использовать последний метод.

А как он учитывает существование каких-то еще направлений, кроме этих 8-ми?
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Сообщение setar » 14 окт 2004, 17:59

=DeaD= писал(а):А как он учитывает существование каких-то еще направлений, кроме этих 8-ми?


вот тут Изображение
мы явно получаем маршрут движения отличный от фосьмилучевой схемы (движение осушествляется по фиолетовым дорожкам)
Аватара пользователя
setar
Site Admin
 
Сообщения: 10984
Зарегистрирован: 04 окт 2004, 12:58
Откуда: St.Petersburg
Skype: taranenko.sergey
ФИО: Сергей Тараненко

След.

Вернуться в Алгоритмы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2