Алгоритмы оптимального движения мобильных объектов по пересеченной местности и транспортной сети
Исследованы алгоритмы построения оптимальных и квазиоптимальных маршрутов движения мобильных объектов по пересеченной местности и транспортной сети. Рассмотрены алгоритмы для комбинированных вариантов движения. Эффективность предложенных алгоритмов не хуже базового алгоритма Форда- Беллмана и зав...
Gespeichert in:
| Datum: | 2008 |
|---|---|
| Hauptverfasser: | , , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут проблем штучного інтелекту МОН України та НАН України
2008
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/7052 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Алгоритмы оптимального движения мобильных объектов по пересеченной местности и транспортной сети / А.Ю. Дорогов, В.Ю. Лесных, И.В. Раков, Г.С. Титов // Штучний інтелект. — 2008. — № 3. — С. 419-427. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-7052 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-70522025-02-23T18:50:35Z Алгоритмы оптимального движения мобильных объектов по пересеченной местности и транспортной сети Алгоритми оптимального руху мобільних об’єктів по пересіченій місцевості і транспортній мережі Дорогов, А.Ю. Лесных, В.Ю. Раков, И.В. Титов, Г.С. Управление и информационное обеспечение мехатронных и робототехнических систем Исследованы алгоритмы построения оптимальных и квазиоптимальных маршрутов движения мобильных объектов по пересеченной местности и транспортной сети. Рассмотрены алгоритмы для комбинированных вариантов движения. Эффективность предложенных алгоритмов не хуже базового алгоритма Форда- Беллмана и зависит от сложности транспортного графа. Для построения квазиоптимальных решений предложен волновой алгоритм с вычислительной эффективностью, пропорциональной числу узлов транспортного графа. Досліджено алгоритми побудови оптимальних і квазіоптимальних маршрутів руху мобільних об’єктів по пересіченій місцевості і транспортній мережі. Розглянуто алгоритми для комбінованих варіантів руху. Ефективність запропонованих алгоритмів не гірше базового алгоритму Форда-Беллмана і залежить від складності транспортного графа. Для побудови квазіоптимальних рішень запропоновано хвильовий алгоритм з обчислювальною ефективністю, пропорційною числу вузлів транспортного графа. 2008 Article Алгоритмы оптимального движения мобильных объектов по пересеченной местности и транспортной сети / А.Ю. Дорогов, В.Ю. Лесных, И.В. Раков, Г.С. Титов // Штучний інтелект. — 2008. — № 3. — С. 419-427. — Бібліогр.: 3 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/7052 629.3.072.1:004.896 ru application/pdf Інститут проблем штучного інтелекту МОН України та НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Управление и информационное обеспечение мехатронных и робототехнических систем Управление и информационное обеспечение мехатронных и робототехнических систем |
| spellingShingle |
Управление и информационное обеспечение мехатронных и робототехнических систем Управление и информационное обеспечение мехатронных и робототехнических систем Дорогов, А.Ю. Лесных, В.Ю. Раков, И.В. Титов, Г.С. Алгоритмы оптимального движения мобильных объектов по пересеченной местности и транспортной сети |
| description |
Исследованы алгоритмы построения оптимальных и квазиоптимальных маршрутов движения мобильных
объектов по пересеченной местности и транспортной сети. Рассмотрены алгоритмы для комбинированных
вариантов движения. Эффективность предложенных алгоритмов не хуже базового алгоритма Форда-
Беллмана и зависит от сложности транспортного графа. Для построения квазиоптимальных решений
предложен волновой алгоритм с вычислительной эффективностью, пропорциональной числу узлов
транспортного графа. |
| format |
Article |
| author |
Дорогов, А.Ю. Лесных, В.Ю. Раков, И.В. Титов, Г.С. |
| author_facet |
Дорогов, А.Ю. Лесных, В.Ю. Раков, И.В. Титов, Г.С. |
| author_sort |
Дорогов, А.Ю. |
| title |
Алгоритмы оптимального движения мобильных объектов по пересеченной местности и транспортной сети |
| title_short |
Алгоритмы оптимального движения мобильных объектов по пересеченной местности и транспортной сети |
| title_full |
Алгоритмы оптимального движения мобильных объектов по пересеченной местности и транспортной сети |
| title_fullStr |
Алгоритмы оптимального движения мобильных объектов по пересеченной местности и транспортной сети |
| title_full_unstemmed |
Алгоритмы оптимального движения мобильных объектов по пересеченной местности и транспортной сети |
| title_sort |
алгоритмы оптимального движения мобильных объектов по пересеченной местности и транспортной сети |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| publishDate |
2008 |
| topic_facet |
Управление и информационное обеспечение мехатронных и робототехнических систем |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/7052 |
| citation_txt |
Алгоритмы оптимального движения мобильных объектов по пересеченной местности и транспортной сети / А.Ю. Дорогов, В.Ю. Лесных, И.В. Раков, Г.С. Титов // Штучний інтелект. — 2008. — № 3. — С. 419-427. — Бібліогр.: 3 назв. — рос. |
| work_keys_str_mv |
AT dorogovaû algoritmyoptimalʹnogodviženiâmobilʹnyhobʺektovpoperesečennojmestnostiitransportnojseti AT lesnyhvû algoritmyoptimalʹnogodviženiâmobilʹnyhobʺektovpoperesečennojmestnostiitransportnojseti AT rakoviv algoritmyoptimalʹnogodviženiâmobilʹnyhobʺektovpoperesečennojmestnostiitransportnojseti AT titovgs algoritmyoptimalʹnogodviženiâmobilʹnyhobʺektovpoperesečennojmestnostiitransportnojseti AT dorogovaû algoritmioptimalʹnogoruhumobílʹnihobêktívpoperesíčeníjmíscevostíítransportníjmereží AT lesnyhvû algoritmioptimalʹnogoruhumobílʹnihobêktívpoperesíčeníjmíscevostíítransportníjmereží AT rakoviv algoritmioptimalʹnogoruhumobílʹnihobêktívpoperesíčeníjmíscevostíítransportníjmereží AT titovgs algoritmioptimalʹnogoruhumobílʹnihobêktívpoperesíčeníjmíscevostíítransportníjmereží |
| first_indexed |
2025-11-24T11:52:13Z |
| last_indexed |
2025-11-24T11:52:13Z |
| _version_ |
1849672475698266112 |
| fulltext |
«Штучний інтелект» 3’2008 419
6Д
УДК 629.3.072.1:004.896
А.Ю. Дорогов, В.Ю. Лесных, И.В. Раков, Г.С. Титов
Санкт-Петербургский государственный электротехнический университет, Россия
vaksa2006@yandex.ru
Алгоритмы оптимального движения
мобильных объектов по пересеченной
местности и транспортной сети
Исследованы алгоритмы построения оптимальных и квазиоптимальных маршрутов движения мобильных
объектов по пересеченной местности и транспортной сети. Рассмотрены алгоритмы для комбинированных
вариантов движения. Эффективность предложенных алгоритмов не хуже базового алгоритма Форда-
Беллмана и зависит от сложности транспортного графа. Для построения квазиоптимальных решений
предложен волновой алгоритм с вычислительной эффективностью, пропорциональной числу узлов
транспортного графа.
Введение
Задача нахождения оптимальных путей по уровню транспортных затрат актуальна
для ряда технических приложений. В частности, к ним относятся: оценка транспортной
доступности для территориально-распределенных систем охраны, планирование оптималь-
ных маршрутов движения робототехнических систем на пересеченной местности, модели-
рование прокладки маршрутов в тренажерах мобильных систем и компьютерных играх.
Задача планирования оптимального пути в общей постановке формулируется
следующим образом. На карте местности необходимо определить маршрут движения от
стартового множества точек к множеству конечных точек, обладающий минимальными
транспортными затратами. В такой постановке начальные и конечные точки заведомо
не известны и определяются в процедуре расчета. В частной постановке возможны
следующие варианты задач:
− проложить оптимальный маршрут от множества стартовых точек к заданной ко-
нечной точке;
− проложить оптимальный маршрут от множества стартовых точек к заданному
множеству конечных точек;
− проложить оптимальный маршрут от заданной стартовой точки к заданной
конечной точке;
− построить фронт транспортной доступности с заданным уровнем затрат по отно-
шению к множеству стартовых точек.
Известный базовый алгоритм прокладки оптимальных маршрутов основан
на методе динамического планирования Форда-Беллмана на взвешенных графах
(1956 – 1958 гг.) [1-3]. В приложении к транспортной задаче на пересеченной
местности вершинами графа являются центры элементарных участков карты, а дуги
соответствуют переходам между центрами смежных участков. Для транспортной
сети вершинами графа являются узлы транспортной сети, а дуги соответствуют
переходам между узлами. Множество алгоритмов, предложенных в последующие
годы (алгоритмы Дейкстры, Калаба, A-звезда и др.), в основном являются вариа-
Дорогов А.Ю., Лесных В.Ю., Раков И.В., Титов Г.С.
«Искусственный интеллект» 3’2008 420
6Д
циями базового алгоритма для частных постановок, благодаря чему достигается
более высокая вычислительная эффективность данных алгоритмов по сравнению с
базовым алгоритмом.
В настоящей работе рассматривается алгоритм оптимального планирования
маршрутов в общей постановке. В отличие от алгоритма Форда-Беллмана маршрут
строится в виде последовательно улучшаемых решений, причем на первом этапе для
прокладки маршрута используется волновой алгоритм с вычислительной слож-
ностью, пропорциональной числу узлов. На последующих этапах маршрут уточ-
няется за счет последовательного ослабления дуг. Алгоритм завершается при
стабилизации накопленных затрат для узлов графа. В целом вычислительная
сложность алгоритма не превышает вычислительной сложности алгоритма Форда-
Беллмана, однако возможность построения приближенных решений позволяет
существенно сократить число вычислительных операций в тех случаях, когда в
конкретной задаче требования к точности решений можно понизить.
В разделе 1 представлен алгоритм выбора маршрута при движении по пересечен-
ной местности. В разделе 2 представлен модифицированный вариант для использования
в транспортной сети. В разделе 3 обсуждается построение оптимальных и квазиоп-
тимальных маршрутов при комбинированном движении по пересеченной местности
и транспортной сети.
1. Алгоритм выбора оптимального маршрута
на пересеченной местности
1.1. Модель местности
Карта местности представлена в виде матрицы ( )xyzZ ,= , где каждый элемент
определяет максимальные затраты на преодоление участка с координатами ( )xy, .
Участок местности, соответствующий элементу матрицы, считается квадратом со
стороной d , правильно ориентированным вдоль координатных осей. Под коорди-
натами участка понимаются матричные индексы: y – номер строки матрицы, x –
номер столбца. Максимальные затраты соответствуют пересечению участка по
диагонали. Полагается, что затраты при пересечении вдоль любой координатной оси
в 2 раз меньше максимальных.
При переходе с данного участка на смежный участок будем считать, что
переход осуществляется из центра одного участка в центр другого. Затраты на
переход равны среднему значению затрат по двум смежным участкам:
( ) 22112 zzz += .
Затраты на маршруте определяются суммой затрат по всем переходам между
точками маршрута:
∑
−
=
+=
1
1
1,
N
i
iizQ ,
где N – число точек маршрута. При построении оптимального маршрута на каждом
шаге необходимо выбирать направление дальнейшего движения. Результат выбора
называется шаговым управлением и обозначается kc . Управление всей операцией
состоит из совокупности шаговых управлений:
( )121 ,, −= mcccC … .
Маршруты задаются координатами элементарных участков карты, поэтому
шаговые управления и накопленные затраты для множества маршрутов представ-
ляются в виде матриц ( )xycC ,= и ( )xyqQ ,= , а шаговое перемещение реализуется в
Алгоритмы оптимального движения мобильных объектов...
«Штучний інтелект» 3’2008 421
6Д
пределах маски размером 3 × 3. Это позволяет интерпретировать матрицу накоплен-
ных затрат в виде полутонового изображения и использовать методы рекурсивной
пространственной фильтрации для нахождения оптимальных маршрутов. Начальное
заполнение матрицы накопленных затрат реализуется волновым алгоритмом с
числом вычислительных операций, пропорциональным числу элементов матричной
карты. Начальное заполнение дает первую оценку оптимальных маршрутов, которая
в ряде случаев уже является удовлетворительной.
1.2. Фильтрующий алгоритм
Принцип динамического планирования Беллмана можно выразить фразой: «любая
часть оптимальной траектории оптимальна». В частности, для любой промежуточной
точки оптимального маршрута минимальна сумма затрат от стартового множества
до данной точки. На основе принципа Беллмана можно предложить следующий
вариант алгоритма решения общей задачи оптимального планирования пути.
Начиная от точек стартового множества, строится веер оптимальных траекторий
до тех пор, пока некоторая оптимальная траектория не достигнет какой-либо конечной
точки. На каждом шаге алгоритма запоминается оптимальное направление перехода в
текущую точку (шаговое управление на предшествующем шаге), что позволяет при
достижении конечной точки восстановить весь оптимальный маршрут.
В предлагаемом алгоритме матрица накопленных затрат Q и матрица направ-
лений C интерпретируются как двумерные изображения. Значение каждого элемента
матрицы соответствует уровню яркости изображения. Алгоритм построения веера
оптимальных траекторий реализуется как многоступенчатый пространственный пара-
метрический ранговый фильтр минимума с маской размером 33× (рис. 1).
Фильтрация производится над матрицами накопленных затрат ( )xyqQ ,= и
матрицей шаговых управлений ( )xycC ,= . Матрица ( )xyzZ ,= определяет параметр
фильтра для каждой точки (элемента) матриц Q и C . Веер траекторий строится от
QS (x,y) FQ FQ FQ FQ
CS (x,y) FC FC FC FC
Q(x,y)
C(x,y)
Рисунок 1 – Многоступенчатый фильтр оптимальных затрат
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( )1,1,11,1
1,,1,
1,1,11,1
+++−+
+−
+−−−−
xyxyxy
xyxyxy
xyxyxy
Рисунок 2 – Маска пространственного фильтра
Дорогов А.Ю., Лесных В.Ю., Раков И.В., Титов Г.С.
«Искусственный интеллект» 3’2008 422
6Д
множества стартовых точек и распространяется по всем направлениям карты.
Эффект пространственной фильтрации матриц эквивалентен ослаблению дуг в
алгоритме Форда-Беллмана.
Размещение фильтрующей маски в точке с координатами ( )xy, показано на
рис. 2. Число ступеней фильтра заведомо не определено, каждая ступень улучшает
предыдущее решение. Матрица затрат Z содержит относительные затраты, при-
веденные к диапазону [ ]1,0 ( 0 – минимальные затраты, 1 – максимальные затраты в
пределах зоны). Непреодолимые области имеют значение ∞ . Матрица может иметь
необрабатываемые области, которые помечены символом NaN (символика Матлаб).
Значение элемента матрицы ( )xyz , используется как параметр пространственного
фильтра в точке ( )xy, . Матрица накопленных затрат ( )xyqQ ,= имеет размер мат-
рицы Z и содержит следующие области:
− необрабатываемая область – точки помечены символом NaN. При выполнении
пространственной фильтрации эти точки пропускаются и не участвуют в обработке;
− стартовые точки (в пределе это может быть одна точка) определяют границу, от
которой распространяется волновой процесс накопления затрат. В начальном сос-
тоянии стартовые точки заполняются соответствующими значениями из матрицы
затратZ ;
− точки, до которых волновой фронт еще не дошел – имеют значение ∞ . В про-
цессе выполнения алгоритма значение этих точек изменяется и в конце первой
ступени алгоритма содержит оценку минимальных затрат на движение от множества
стартовых точек к данной точке.
Матрица шаговых управлений ( )xycC ,= имеет размеры матрицы Z . Каждая
ячейка матрицы содержит структуру из двух координат. В процессе выполнения
алгоритма в ячейках матрицы C устанавливаются значения координат, которые
указывают на соседнюю предшествующую точку оптимального маршрута. Можно
сэкономить память, если вместо пары координат в ячейке ( )xyc , сохранять кодовый
номер направления на соседнюю точку. Таких направлений всего 8 (рис. 3).
При пространственной фильтрации в классическом варианте маска последо-
вательно перемещается вдоль строк и столбцов изображения, формируя новые
значения яркости. Однако в данном случае на первой ступени фильтрации такая
реализация оказывается неэффективной, поскольку большинство точек матрицы Q
(имеющих бесконечные значения) не граничат со стартовыми точками и поэтому не
изменяют свое значение, но, тем не менее, будут просматриваться сканирующей
маской.
Поэтому на первой ступени фильтрации маска перемещается только вдоль
границы, отделяющей настоящее и прошлое движение от будущего. Вначале граница
Рисунок 3 – Возможные варианты шаговых управлений
Алгоритмы оптимального движения мобильных объектов...
«Штучний інтелект» 3’2008 423
6Д
охватывает только стартовые точки, а затем, по мере построения веера оптимальных
траекторий, она распространяется в виде волны по всей плоскости матрицы Q .
При движении маски вдоль границы только часть точек, покрываемых маской,
может быть использована для вычисления накопленных затрат. Это означает, что в
процессе вычисления шаговых управлений будут пропущены некоторые направле-
ния из-за того, что будущее движение нам пока не известно. После первой ступени
фильтрации будут получены оценки накопленных затрат для всех точек матрицы Q
(оценки первого приближения). При этом в матрице направлений ( )xyC , все эле-
менты будут содержать направления маршрута первого приближения.
Последующие ступени фильтрации позволяют уточнить первое приближение.
Поскольку после первой ступени матрицы Q и C полностью определены, то на
последующих ступенях фильтрации сканирование маской выполняется последова-
тельно по строкам и столбцам, при этом фильтр маски использует все восемь
возможных шаговых управлений (рис. 3).
1.3. Реализация алгоритма
Ступень 1. На первой ступени фильтрации алгоритм распространяется от стар-
товых точек в виде волны. Фронт волны строится следующим образом. Множество
стартовых точек рассматривается как начальный фронт волны. Маска позицио-
нируется в стартовую точку карты и в матрицах затрат Z , Q просматриваются все
точки, покрываемые маской. Точки, для которых значения в матрице Z равны ∞ , а
значения в матрице Q конечны, переносятся в список граничных точек. Просматри-
ваются все стартовые точки и строится общий список. Далее список редактируется,
из него удалятся повторяющиеся точки (редактирование может производиться и при
смене позиции маски). Логические условия построения нового фронта имеют вид:
( ) ( ) ( ) ( ){ }* *, , если , & , , & ,y x Front q y x z y x NaN q y x∈ = ∞ ≠ ∞ ≠ ≠ ∞ (1)
где координаты y и x принадлежат полю движущейся маски, ** , xy – координаты
точек текущего фронта волны. Фильтрация выполняется для всего списка граничных
точек. С этой целью маска позиционируется центром в граничную точку ( )xy, и
выполняется вычисление нового значения накопленных затрат по следующему
правилу:
( ) ( ) ( )( )xyzixjyqxyq jiji
,,min,
,
+++= , (2)
где ij, = 0, ±1 – индексы маски с ненулевыми значениями элементов. Полагается,
что ( ) 0,00 =xyz . В центральных областях карты матрица фильтрующей маски имеет
вид:
=
111
111
111
Maska .
Матрица маски наполняется нулями при пересечении границы карты. Значение
соответствующего элемента матрицы шаговых управлений устанавливается по пози-
ции точки минимума в выражении (2):
( ) ( ) ( )( )xyzixjyqxyc jiji
,,minarg,
,
+++= . (3)
Дорогов А.Ю., Лесных В.Ю., Раков И.В., Титов Г.С.
«Искусственный интеллект» 3’2008 424
6Д
Полученный фронт используется для построения нового списка граничных
точек. Процедура волновой фильтрации повторяется для нового списка граничных
точек. Итерационный процесс заканчивается, когда новый фронт не содержит ни
одной точки. После выполнения первой ступени все точки матрицы накопленных
затрат, которые были равны ∞ , получают конечное положительное значение.
Ступень 2 и последующие. Последовательно просматриваются все точки карты,
для которых ( ) NaNxyq ≠, и выполняется коррекция значений матриц Q и ,C
следуя формулам (2) и (3). Фильтрация заканчивается, когда матрицы Q двух смеж-
ных ступеней совпадают. Дополнительный эффект ускорения вычислений дости-
гается за счет рекурсивного принципа фильтрации.
Построение оптимального маршрута. При построении маршрута возможны
следующие варианты:
1. Стартовых точек несколько. Необходимо проложить маршрут от ближайшей
стартовой точки к заданной конечной точке с координатами ( )kk xy , . В этом случае
точки маршрута восстанавливаются по цепочке шаговых управлений:
( ) ( ) ..,,., 11 yxycyxxycx kkkkkk == −−
2. Конечная точка не задана, но определено множество, которому она принад-
лежит. В этом случае на заданном множестве необходимо найти точку, в которой
( ) min, →xyq и далее повторить алгоритм пункта 1.
3. Если заданы начальная и конечная точки, то алгоритм необходимо выпол-
нить для начального фронта, состоящего из одной стартовой точки.
Построение фронта транспортной доступности. В матрице накопленных
затрат ищутся точки, удовлетворяющие условию: ( ), ,q y x L≈ где L – уровень затрат
на линии фронта. Степень приближения может быть задана, например, в процентах
от уровня L .
2. Алгоритм оптимального движения в транспортной сети
2.1. Модель транспортной сети
Транспортная сеть (рис. 4) представляется топологической моделью в виде
взвешенного графа G. Ребра графа соответствуют однородным сегментам транспортной
сети, а узлы – точкам ветвления или иным точкам интереса (стартовым точкам, конечным
точкам, точкам сети, ближайшим к заданному объекту и т.д.). Каждому ребру графа
поставлено в соответствие значение временных затрат на преодоление сегмента.
Сегментные затраты определяются геометрической длиной сегмента и средней ско-
ростью движения объекта вдоль сегмента.
Постановка задачи по прокладке маршрута в транспортной сети не отличается
от задачи маршрутизации по пересеченной местности.
2.2. Описание алгоритма
Обозначим через S множество стартовых точек и через E множество конеч-
ных точек. Для каждого узла сети введем понятие накопленных затрат. Накопленные
затраты определяются минимальными суммарными затратами на перемещение из
ближайшей стартовой точки в данную точку.
Начиная от точек стартового множества, строится веер оптимальных траекто-
рий до тех пор, пока некоторая оптимальная траектория не достигнет какой-либо
конечной точки. В каждой узловой точке производится вычисление минимальных
Алгоритмы оптимального движения мобильных объектов...
«Штучний інтелект» 3’2008 425
6Д
накопленных затрат по отношению к ближайшей стартовой точке. Кроме того
запоминается сегмент оптимального маршрута (оптимальное шаговое управление на
предшествующем шаге), что позволяет при достижении конечной точки восстано-
вить весь оптимальный маршрут.
2.3. Реализация алгоритма
Взвешенный граф транспортной сети задается квадратной матрицей затрат
( )jizZ ,= . Размер матрицы определяется числом вершин в графе. Каждый элемент
матрицы представляет собой затраты на перемещение между смежными вершинами.
В общем случае матрица может быть не симметрична ( ( ) ( )ijzjiz ,, ≠ ). Если вершины
не являются смежными, то значение элемента матрицы равно ∞ . Кроме того
элемент матрицы может иметь 0, если ji = или значение NaN (символика Матлаб) –
такой сегмент не участвует в построении оптимального маршрута.
Накопленные затраты сохраняются в массиве Q . Каждый элемент массива
соответствует вершине графа. Первоначально всем элементам массива Q присваи-
вается значение ∞ . Элементу массива Q присваивается значение NaN, если все
сегменты окружения для соответствующей вершины графа имеют значение NaN.
Ступень 1. На первой ступени алгоритма накопление затрат происходит в виде
волны от стартовых точек. Фронт волны строится следующим образом. Множество
стартовых точек рассматривается как начальный фронт волны. Алгоритм фокуси-
руется в стартовой точке, в матрице весов Z и массиве накопленных затрат Q .
Просматриваются все сегменты и узлы ближайшего окружения. Точки, для которых
значения в массиве Q равны ∞ , и при этом соответствующие значения в матрице
сегментных затрат Z конечны, переносятся в список граничных точек. Просмат-
риваются все стартовые точки и строится общий список. Далее список редакти-
руется, из него удалятся повторяющиеся точки. Логическая формула построения
нового фронта имеет вид:
( ) ( ){ }NaNjiziqFronti ,,&если ∞≠∞=∈ . (4)
Фильтрация первой ступени1. Алгоритм фокусируется в граничную точку i и
выполняется вычисление нового значения накопленных затрат, следуя правилу:
( )
( )
( )( )ji
iqj
zjqiq +=
−∈ 1
min . (5)
1 Применительно к графам используется терминология «ослабление дуг».
Рисунок 4 – Транспортная сеть
Дорогов А.Ю., Лесных В.Ю., Раков И.В., Титов Г.С.
«Искусственный интеллект» 3’2008 426
6Д
Значение соответствующего элемента массива шаговых управлений устанавли-
вается по позиции точки минимума в выражении (5):
( )
( )
( )( )ji
iqj
zjqic +=
−∈ 1
minarg . (6)
Когда все точки текущего фронта пройдены, строится новый фронт по выше-
рассмотренному алгоритму. Итерационный процесс первой ступени заканчивается,
когда новый фронт не содержит ни одной точки. После выполнения первой ступени
все точки массива накопленных затрат Q , которые были равны ∞ , получают
конечное положительное значение.
Ступень 2 и последующие. Последовательно просматриваются все точки зоны, для
которых ( ) NaNiq ≠ и выполняется коррекция значений, массивов Q и ,C следуя
выражениям (5) и (6). Фильтрация заканчивается либо когда массивы двух смежных
ступеней совпадают, либо после выполнения заданного числа ступеней фильтрации.
Построение оптимального маршрута. При построении маршрута возможны
следующие варианты:
1. Стартовых точек несколько. Необходимо проложить маршрут от ближайшей
стартовой точки
1is к заданной конечной точке
kie . В этом случае узловые точки
маршрута восстанавливаются по цепочке шаговых управлений: ( )1k ki c i− = .
2. Конечная узловая точка не задана, но определено множество, которому она при-
надлежит. В этом случае на заданном множестве необходимо найти узловую точку, в
которой ( ) min→kiq и далее повторить алгоритм пункта 1.
3. Если заданы начальная и конечная узловые точки, то алгоритм формирования
массива накопленных затрат необходимо выполнить для начального фронта,
состоящего из одной стартовой точки.
Построение фронта транспортной доступности.
Фронт транспортной доступности представляет собой линию (изохрону), в каждую
точку которой можно попасть из стартовой точки примерно при одном и том же уровне
затрат L . В массиве накопленных затрат Q ищутся точки, удовлетворяющие условию:
( ) Liq ≈ . Степень приближения должна быть задана (например, в процентах от уровня L ).
Узловым точкам изохроны соответствуют координаты ( )ii yx , . По этим координатам
можно приближенно построить фронт транспортной доступности, соединив их отрезками
прямых линий.
3. Алгоритм прокладки оптимального маршрута
при комбинированном движении
Комбинированное движение состоит из этапа движения по транспортной сети с
использованием транспортных средств и этапа движения по пересеченной местности.
3.1. Построение первого приближения
1. С помощью волнового алгоритма определяются достижимые затраты на
перемещение из стартового узла во все узлы транспортной сети.
2. Узлы транспортной сети рассматриваются как стартовые точки для оптималь-
ного алгоритма движения по пересеченной местности, причем для стартовых точек зада-
ется начальный уровень затрат, полученный при расчете движения по транспортной сети.
3. С помощью волнового алгоритма рассчитывается оптимальный маршрут
движения по пересеченной местности от множества стартовых точек.
Алгоритмы оптимального движения мобильных объектов...
«Штучний інтелект» 3’2008 427
6Д
4. Выделяется оптимальная стартовая точка (узел транспортной сети, принадле-
жащий оптимальному маршруту).
Точность первого приближения определяется максимальным расстоянием между
оптимальной стартовой точкой и смежными с ней узлами.
3.2. Уточнение решения
1. Сегменты транспортной сети, инцидентные оптимальной стартовой точке,
детализируются дополнительным числом узлов.
2. С помощью волнового алгоритма определяются достижимые затраты на
перемещение из стартового узла к вновь образованным дополнительным узлам
транспортной сети. С помощью этапов фильтрации (ослабления дуг) уточняется
решение на транспортной сети.
3. Множество дополнительных узлов сети вместе с оптимальной стартовой
точкой рассматриваетсяё как стартовые точки для оптимального алгоритма
движения по пересеченной местности, причем для стартовых точек задается уровень
затрат, полученный при расчете движения по транспортной сети.
4. С помощью волнового алгоритма рассчитывается оптимальный маршрут
движения по пересеченной местности от множества стартовых точек.
5. Выделяется оптимальная стартовая точка.
6. При необходимости построения точного маршрута выполняются этапы фильт-
рации в алгоритме движения по пересеченной местности.
Заключение
Представленные алгоритмы покрывают практически значимые варианты проклад-
ки оптимальных маршрутов. Быстродействие алгоритмов зависит от требуемой точности
построения маршрута. Для построения квазиоптимальных решений достаточно огра-
ничиться волновым алгоритмом. В этом случае вычислительные затраты минимальны и
пропорциональны числу узлов транспортного графа. Дополнительные этапы фильтрации
(ослабления дуг) обеспечивают улучшение решений в пределе до оптимального, при этом
вычислительная эффективность интегрального алгоритма будет не хуже базового алго-
ритма Форда-Беллмана. Число дополнительных этапов фильтрации зависит от сложности
транспортного графа. Поэтому для конкретной задачи использование предложенных
алгоритмов может оказаться значительно более эффективным, чем использование базо-
вого алгоритма.
Литература
1. Кофман А. Введение в прикладную комбинаторику. – М.: Наука, 1975. – 479 с.
2. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. –
Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. – 288 с.
3. Кормен Томас X., Лейзерсон Чарльз И., Ривест Рональд Л., Штайн Клиффорд. Алгоритмы: построение
и анализ: Пер. с англ. – М.: Издательский дом «Вильямс», 2005. – 1296 с.
О.Ю. Дорогов, В.Ю. Лєсних, І.В. Раков, Г.С. Тітов
Алгоритми оптимального руху мобільних об’єктів по пересіченій місцевості і транспортній мережі
Досліджено алгоритми побудови оптимальних і квазіоптимальних маршрутів руху мобільних об’єктів по
пересіченій місцевості і транспортній мережі. Розглянуто алгоритми для комбінованих варіантів руху.
Ефективність запропонованих алгоритмів не гірше базового алгоритму Форда-Беллмана і залежить від
складності транспортного графа. Для побудови квазіоптимальних рішень запропоновано хвильовий
алгоритм з обчислювальною ефективністю, пропорційною числу вузлів транспортного графа.
Статья поступила в редакцию 30.07.2008.
|