Алгоритм планирования пути на местности

 

Значение соответствующего элемента массива шаговых управлений устанавливается по позиции точки минимума в выражении (5):

  (6)

 

 

Когда все точки текущего фронта пройдены, строится новый фронт по вышерассмотренному алгоритму. Итерационный процесс первой ступени заканчивается, когда новый фронт не содержит ни одной точки. После выполнения первой ступени все точки массива накопленных затрат Q, которые были равны ∞, получают конечное положительное значение.

 

Ступень 2 и последующие.

Последовательно просматриваются все точки зоны, для которых q(i) ≠ NaN и выполняется коррекция значений, массивов Q и C, следуя выражениям (5) и (6). Фильтрация заканчивается либо когда массивы двух смежных ступеней совпадают, либо после выполнения заданного числа ступеней фильтрации.

 

Построение оптимального маршрута.

При построении маршрута возможны следующие варианты:

1. Стартовых точек несколько. Необходимо  проложить маршрут от ближайшей стартовой точки

 заданной конечной точке В этом случае узловые точки маршрута восстанавливаются по цепочке шаговых управлений:

 

 

2. Конечная узловая точка не  задана, но определено множество, которому она принадлежит. В этом  случае на заданном множестве  необходимо найти узловую точку, в которой q(ik )→ min и далее повторить алгоритм пункта 1.

 

3. Если заданы начальная и  конечная узловые точки, то алгоритм  формирования массива накопленных  затрат необходимо выполнить  для начального фронта, состоящего  из одной стартовой точки.

 

Построение фронта транспортной доступности.

Фронт транспортной доступности представляет собой линию (изохрону), в каждую точку которой можно попасть из стартовой точки примерно при одном и том же уровне затрат L . В массиве накопленных затрат Q ищутся точки, удовлетворяющие условию: q(i) ≈ L . Степень приближения должна быть задана (например, в процентах от уровня L ). Узловым точкам изохроны соответствуют координаты (xi , yi ). По этим координатам можно приближенно построить фронт транспортной доступности, соединив их отрезками прямых линий.

 

 

3. Алгоритм прокладки  оптимального маршрута при комбинированном  движении

 

Комбинированное движение состоит из этапа движения по транспортной сети с использованием транспортных средств и этапа движения по пересеченной местности.

 

3.1. Построение первого  приближения

 

1. С помощью волнового алгоритма  определяются достижимые затраты  на перемещение из стартового  узла во все узлы транспортной  сети.

2. Узлы транспортной сети рассматриваются  как стартовые точки для оптимального  алгоритма движения по пересеченной  местности, причем для стартовых  точек задается начальный уровень  затрат, полученный при расчете  движения по транспортной сети.

3. С помощью волнового алгоритма  рассчитывается оптимальный маршрут движения по пересеченной местности от множества стартовых точек.

4. Выделяется оптимальная стартовая  точка (узел транспортной сети, принадлежащий  оптимальному маршруту).

Точность первого приближения определяется максимальным расстоянием между оптимальной стартовой точкой и смежными с ней узлами.

 

3.2. Уточнение решения

 

1. Сегменты транспортной сети, инцидентные  оптимальной стартовой точке, детализируются  дополнительным числом узлов.

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

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

4. С помощью волнового алгоритма  рассчитывается оптимальный маршрут  движения по пересеченной местности  от множества стартовых точек.

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

6. При необходимости построения  точного маршрута выполняются  этапы фильтрации в алгоритме  движения по пересеченной местности.

 

Заключение

Представленные алгоритмы покрывают практически значимые варианты прокладки оптимальных маршрутов. Быстродействие алгоритмов зависит от требуемой точности построения маршрута. Для построения квазиоптимальных решений достаточно ограничиться волновым алгоритмом. В этом случае вычислительные затраты минимальны и пропорциональны числу узлов транспортного графа. Дополнительные этапы фильтрации

(ослабления дуг) обеспечивают улучшение  решений в пределе до оптимального, при этом

вычислительная эффективность интегрального алгоритма будет не хуже базового алгоритма Форда-Беллмана. Число дополнительных этапов фильтрации зависит от сложности транспортного графа. Поэтому для конкретной задачи использование предложенных алгоритмов может оказаться значительно более эффективным, чем использование базового алгоритма.

 

 

 

Алгоритм HGA*

 

Алгоритм HGA* (Hierarchical A* for MT-Graphs) использует совершенно другой подход к решению задачи планирования — иерархический. Задача рекурсивно разбивается на иерархическую сеть подзадач, решение которых считается известным. Алгоритм использует графы специальной структуры — метрические, топологические (МТ-графы). МТ-граф — это неупорядоченная пара: MT-Gr=<A,d>, где А — множество клеток, представляющее матрицу

   

d – метрика на множестве .

 

Клетку МТ-графа будем называть проходимой, если aij=0; непроходимой, если aij=1.

Графически МТ-граф можно представить в виде таблицы, содержащей m строк и n столбцов. Ячейки таблицы соответствуют клеткам aij, проходимым и непроходимым. Упорядоченную пару клеток МТ-графа <aij, akl> назовем секцией. Секция считается проходимой, если прямая, проходящая через клетки секции не содержит непроходимых клеток.

Частичным путем из начальной клетки в целевую будем называть последовательность клеток МТ-графа PP = {ai0,j0, ai1,j1, ai2,j2,...,ain,jn}. При этом если каждая из секций <ai0,j0, ai1,j1>, <ai1,j1, ai2,j2>,…, <ain-1,jn-1, ain,jn> является проходимой, то такой путь будем называть допустимым, иначе — недопустимым. Клетки, входящие в частичный путь будем называть опорными. Таким образом, задача поиска пути на МТ-графе сводится к построению допустимого частичного пути. Другими словами, для решения задачи необходимо выделить

множество клеток, называемых опорными, между которыми может быть построен путь любыми стандартными средствами, например путем построения дискретной прямой по

алгоритму Брезенхема.

 

Благодаря такому подходу работы, алгоритм HGA* позволяет построить «приближенное» решение за конечный промежуток времени и постепенно улучшать его при наличии временных и вычислительный ресурсов.

 

Выводы

Результаты проведенных вычислительных экспериментов подтверждают целесообразность иерархического подхода в решении задачи планирования траектории, а так же показывают эффективность алгоритма HGA* и его превосходство над существующими аналогами.

 

Список используемой литературы:

 

Статья журнала «Искусственный интеллект» 3’2008

 А.Ю. Дорогов, В.Ю. Лесных, И.В. Раков, Г.С. Титов Санкт-Петербургский государственный электротехнический университет, Россия «Алгоритмы оптимального движения

мобильных объектов по пересеченной местности и транспортной сети»

 

Информационно-телекоммуникационные технологии и матмоделирование — 2012