УДК 004.021:004.896

Введение

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

Задача планирования оптимального пути в общей постановке формулируется следующим образом. На карте местности необходимо определить маршрут движения от стартового множества точек к множеству конечных точек обладающий минимальными транспортными затратами. В такой постановке начальные и конечные точки заведомо не известны и определяются в процедуре расчета. В частной постановке возможны следующие варианты задач:

·                    проложить оптимальный маршрут от множества стартовых точек к заданной конечной точке;

·                    проложить оптимальный маршрут от множества стартовых точек к заданному множеству конечных точек;

·                    проложить оптимальный маршрут от заданной стартовой точки к заданной конечной точке;

·                    построить фронт транспортной доступности с заданным уровнем затрат по отношению к множеству стартовых точек.

Известный базовый алгоритм прокладки оптимальных маршрутов основан на методе динамического планирования Форда-Беллмана на взвешенных графах [0,2,3] (1956-1958 гг). В приложении к транспортной задаче на пересеченной местности вершинами графа являются центры элементарных участков карты, а дуги соответствуют переходам между центрами смежных участков. Для транспортной сети вершинами графа является узлы транспортной сети, а дуги соответствуют переходам между узлами. Множество алгоритмов предложенных в последующие годы (алгоритмы Дейкстры, Калаба, A-звезда и др.) в основном являются вариациями базового алгоритма для частных постановок, благодаря чему достигается более высокая вычислительная эффективность данных алгоритмов по сравнению с базовым алгоритмом.

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

В разделе 1 представлен алгоритм выбора маршрута при движении по пересеченной местности. В разделе 2 представлен модифицированный вариант для использования в транспортной сети. В разделе 3 обсуждается построение оптимальных и квазиоптимальных маршрутов при комбинированном движении по пересеченной местности и транспортной сети.

1. Алгоритм выбора оптимального маршрута на пересеченной местности

Модель местности

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

При переходе с данного участка на смежный участок будем считать, что переход осуществляется из центра одного участка в центр другого. Затраты на переход равны среднему значению затрат по двум смежным участкам:

                                                                                                                         (1)

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

                                                                 ,                                                             (2)

где  - число точек маршрута. При построении оптимального маршрута на каждом шаге необходимо выбирать направление дальнейшего движения. Результат выбора называется  шаговым управлением и обозначается . Управление всей операцией состоит из совокупности шаговых управлений:

                                                                                                                      (3)

Маршруты задаются координатами элементарных участков карты, поэтому шаговые управление и накопленные затраты для множества маршрутов представляются в виде матриц  и , а шаговое перемещение реализуется в пределах маски размером 3×3. Это позволяет интерпретировать матрицу накопленных затрат в виде полутонового изображения и использовать методы рекурсивной пространственной фильтрации для нахождения оптимальных маршрутов. Начальное заполнение матрицы накопленных затрат реализуется волновым алгоритмом с числом вычислительных операций пропорциональным числу элементов матричной карты. Начальное заполнение дает первую оценку оптимальных маршрутов, которая в ряде случаев уже является удовлетворительной.

Фильтрующий алгоритм

Принцип динамического планирования Беллмана можно выразить фразой: «любая часть оптимальной траектории оптимальна». В частности, для любой промежуточной точки оптимального маршрута минимальна сумма затрат от стартового множества до данной точки. На основе принципа Беллмана можно предложить следующий вариант алгоритма решения общей задачи оптимального планирования пути.

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

В предлагаемом алгоритме матрица накопленных затрат  и матрица направлений  интерпретируются как двумерные изображения. Значение каждого элемента матрицы соответствует уровню яркости изображения. Алгоритм построения веера оптимальных траекторий реализуется как многоступенчатый пространственный параметрический ранговый фильтр минимума с маской размером  (рис. 1). Фильтрация производится над матрицами накопленных затрат  и матрицей шаговых управлений . Матрица  определяет параметр фильтра для каждой точки (элемента) матриц  и .  Веер траекторий строится от множества стартовых точек и распространяется по всем направлениям карты. Эффект пространственной фильтрации матриц эквивалентен ослаблению дуг в алгоритме Форда-Белмана.

Рис. 1 Многоступенчатый фильтр оптимальных затрат

Размещение фильтрующей маски в точке с координатами  показано на рис. 2. Число ступеней фильтра заведомо не определено, каждая ступень улучшает предыдущее решение. Матрица затрат  содержит относительные затраты приведенные к диапазону  ( - минимальные затраты,  - максимальные затраты в пределах зоны). Непреодолимые области имеют значение . Матрица может иметь не обрабатываемые области, которые помечены символом NaN (символика Матлаб). Значения элемента матрицы  используется как параметр пространственного фильтра в точке . Матрица накопленных затрат   имеет размер матрицы  и содержит следующие области:

·                   необрабатываемая область – точки помечены символом NaN. При выполнении пространственной фильтрации эти точки пропускаются и не участвуют в обработке;

·                   стартовые точки (в пределе это может быть одна точка) определяют границу, от которой распространяется волновой процесс накопления затрат. В начальном состоянии стартовые точки заполняются соответствующими значениями из матрицы затрат ;

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

Рис. 2 Маска пространственного фильтра

Матрица шаговых управлений  имеет размеры матрицы . Каждая ячейка  матрицы содержит структуру из двух координат. В процессе выполнения алгоритма в ячейках матрицы  устанавливаются значения координат, которые указывают на соседнею предшествующую точку оптимального маршрута. Можно сэкономить память, если вместо пары координат в ячейке   сохранять  кодовый номер направления на соседнюю точку. Таких направлений всего  8 (см. рис. 3).

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

Рис. 3 Возможные варианты шаговых управлений

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

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

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

Реализация алгоритма

Ступень 1. На первой ступени фильтрации алгоритм распространяется от стартовых точек в виде волны. Фронт волны строится следующим образом. Множество стартовых точек рассматривается как начальный фронт волны. Маска позиционируется в стартовую точку карты и в матрицах затрат ,  просматриваются все точки покрываемые маской. Точки, для которых значения в матрице  равны , а значения в матрице  конечны, переносятся в список граничных точек. Просматриваются все стартовые точки, и строится общий список. Далее список редактируется, из него удалятся повторяющиеся точки (редактирование может производиться и при смене позиции  маски). Логические условия построения нового  фронта имеют вид:

                                    (4)

где координаты   и  принадлежат полю движущейся маски,  - координаты точек текущего фронта волны. Фильтрация выполняется для всего списка граничных точек. С этой целью маска позиционируется центром в граничную точку  и  выполняется вычисление нового значения накопленных затрат по следующему правилу:

                                                                                        (5)

где = 0,±1 индексы маски с ненулевыми значениями элементов. Полагается, что . В центральных областях карты матрица фильтрующей маски имеет вид:

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

                                                                                  (6)

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

Ступень 2 и последующие. Последовательно просматриваются все точки карты, для которых  и выполняется коррекция значений матриц  и   следуя формулам (5) и (6). Фильтрация заканчивается, когда матрицы  двух смежных ступеней совпадают. Дополнительный эффект ускорения вычислений достигается за счет рекурсивного принципа фильтрации.

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

1) Стартовых точек несколько. Необходимо проложить маршрут от ближайшей стартовой точки к заданной конечной точке с координатами . В этом случае точки маршрута восстанавливаются по цепочке шаговых управлений:

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

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

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

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

2. Алгоритм оптимального движения в транспортной сети

Модель транспортной сети

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

Постановка задачи по прокладке маршрута в транспортной сети не отличается от задачи маршрутизации по пересеченной местности.

Рис. 4 Реализация оптимального маршрута движения по пересеченной местности

Описание алгоритма

Обозначим через  множество стартовых точек  и через   множество конечных точек. Для каждого узла сети введем понятие накопленных затрат. Накопленные затраты определяются минимальными суммарными затратами на перемещение из ближайшей стартовой точки в данную точку.

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

Реализация алгоритма

Взвешенный граф транспортной сети задается квадратной матрицей затрат . Размер матрицы определяется числом вершин в графе. Каждый элемент матрицы представляет собой затраты на перемещение между смежными вершинами. В общем случае матрица может быть не симметрична (). Если вершины не являются смежными, то значение элемента матрицы равно  . Кроме того элемент матрицы может иметь 0 если  или значение NaN (символика Матлаб) - такой сегмент не участвует в построении оптимального маршрута.

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

Ступень 1. На первой ступени алгоритма накопление затрат происходит в виде волны от стартовых точек. Фронт волны строится следующим образом. Множество стартовых точек рассматривается как начальный фронт волны. Алгоритм фокусируется  в стартовой точке, в матрице весов и массиве накопленных затрат  . Просматриваются все сегменты и узлы ближайшего окружения. Точки, для которых значения в массиве   равны , и при этом соответствующие значения в матрице сегментных затрат конечны, переносятся в список граничных точек. Просматриваются все стартовые точки, и строится общий список. Далее список редактируется, из него удалятся повторяющиеся точки. Логическая формула построения нового  фронта имеет вид.

                                                                             (7)

Фильтрация первой ступени[1]. Алгоритм фокусируется в граничную точку   и выполняется вычисление нового значения накопленных затрат  следуя правилу:

                                                                                                               (8)

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

                                                                                                          (9)

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

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

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

1) Стартовых точек несколько. Необходимо проложить маршрут от ближайшей стартовой точки   к заданной конечной точки . В этом случае узловые точки маршрута восстанавливаются по цепочке шаговых управлений: .

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

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

На рис. 5 слева приведена схема транспортной сети, соответствующей участку местности, приведенному справа.

Рис. 5 Реализация оптимального маршрута на транспортной сети

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На рис. 6 представлен маршрут, состоящий из двух частей – маршрута движения по транспортной сети и маршрута движения по пересеченной местности. Светлый маркер показывает начало движения, темный – финиш.

Рис. 6 Реализация комбинированного оптимального маршрута

Заключение

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

1.    Кофман А. Введение в прикладную комбинаторику.- М.: Наука, 1975.- 479.

2.    Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. – Ижевск НИЦ «Регулярная и хаотическая динамика», 2001.- 288с.

3.    Кормен, Томас X., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клиффорд. - Алгоритмы: построение и анализ, 2-е издание. : Пер. с англ. — М.: Издательский дом "Вильяме", 2005. — 1296 с.