СПОСОБ ПОСТРОЕНИЯ МАРШРУТА ПЕРЕДВИЖЕНИЯ НА ПЕРЕСЕЧЕННОЙ МЕСТНОСТИ Российский патент 2016 года по МПК G01C21/34 

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

Известен способ прокладывания маршрутов движения на местности с использованием бумажных карт [Военная топография / Псарев А.А., Коваленко А.Н., Куприн A.M., Пирнак Б.И. // М.: Военное изд-во, 1986 г.], заключающийся в прокладывании пользователем маршрутов и измерении их длины при помощи циркуля, курвиметра и линейки.

Недостатком известного способа является существенные затраты времени на прокладывание маршрутов.

Известны способы определения кратчайшего маршрута движения (патенты US №4408192 от 20.11.1984 г., НКИ 340/995; №5486822 от 23.01.1986 г., НКИ 340/995, G08G 1/123), в которых предложено использовать находящуюся в памяти бортовой ЭВМ карту дорог города (цифровую векторную карту), информация о точке отправления и точке назначения вводится в ЭВМ водителем, а затем рассчитывается кратчайший путь.

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

Известен способ, реализованный на устройстве выбора оптимального маршрута маневра (патент RU №2045773, МПК G06F 17/16 от 19.10.1995 г.), в котором предложено управление движением разнотипных транспортных средств по автодорожной сети с различной проходимостью участков дорог.

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

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

Известен способ прокладывания оптимального движения мобильных объектов по пересеченной местности [Дорогов А.Ю., Лесных В.Ю., Раков В.И., Титов Г.С. Алгоритмы оптимального движения мобильных объектов по пересеченной местности и транспортной сети. // Санкт-Петербургский государственный электротехнический университет, 2006 г.], в котором предложено строить маршрут в виде последовательно улучшаемых решений, причем на первом этапе для прокладки маршрута используется волновой алгоритм. На последующих этапах маршрут уточняется за счет последовательного ослабления дуг. Алгоритм завершается при стабилизации накопленных затрат для узлов графа.

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

Наиболее близким по своей сущности к заявляемому изобретению является способ прокладывания маршрута передвижения на пересеченной местности (патент RU №2439496 С1, МКП G01C 21/34 от 15.07.2010 г.), включающий загрузку электронной карты местности, определение точек старта A(х_А,у_А) и финиша В(х_В,у_В), определяют непроходимые для выбранного транспортного средства зоны административного и физического характера , исключают из расчетов непроходимые зоны , сравнивают область проходимости с непроходимыми зонами и , если область проходимости , то определяют новые непроходимые зоны и , если область проходимости , то формируют возможные маршруты движения на карте для выбранного транспортного средства, при этом определяют наличие матрицы высот для , если матрица высот отсутствует, то определяют минимальное расстояние между изолиниями, если матрица высот присутствует, то определяют шаг матрицы высот, выбирают размер сетки d, формируют на двумерную сетку с размером d, формируют на трехмерную сетку с учетом матрицы высот Н=Ф(х,у), формируют на элементарные ячейки, рассчитывают приведенный вес для каждого участка маршрута W_г, при этом производят оценку участка пути с помощью вычисления частных коэффициентов k_j, сравнивают k_j с единицей, если k_j≥1, определяют непроходимые зоны и , если k_j<1, производят расчет обобщенного коэффициента проходимости для участка пути , производят расчет длины участка пути d_{O ij}, производят расчет приведенного веса дуги W_г графа, определяют затраты на границах участка местности g₁₂=(g₁+g₂)/2, производят расчет рационального маршрута для выбранного транспортного средства при минимизации длины пути и энергетических ресурсов с использованием алгоритма Дейкстры.

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

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

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

Таким образом, заявляемое техническое решение соответствует критерию изобретения «новизна».

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

Таким образом, техническое решение соответствует критерию «изобретательский уровень», так как оно для специалиста явным образом не следует из уровня развития техники.

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

Таким образом, изобретение соответствует критерию «промышленная применимость».

На фиг. 1 представлена структурная схема построения маршрута,

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

на фиг. 3 - блок-схема алгоритма формирования элементарных ячеек на цифровых векторных картах,

на фиг. 4 - блок-схема алгоритма оценки преодоления преграды,

на фиг. 5 - блок-схема алгоритма определения критерия затрат пути,

на фиг. 6 - схема элементарного участка.

Способ включает следующие операции:

- загрузка цифровой векторной карты и модели рельефа местности;

- задание точки старта А(х_А,у_А) и финиша В(х_В,у_В);

- задание типа и выбор из базы данных тактико-технических характеристик транспортного средства, предназначенного для перемещения по местности;

- определение непроходимых для выбранного транспортного средства зон административного и физического характера;

- исключение из расчетов непроходимых зон ;

- формирование множества объектов местности , проходимых заданным транспортным средством;

- отображение на электронной карте непроходимых зон;

- формирование графа G возможных маршрутов движения на карте , m∈[1, М] для выбранного транспортного средства;

- определение наличия матрицы высот для ;

- определение шага матрицы высот;

- определение минимального расстояния между изолиниями;

- выбор размера сетки d;

- формирование на двухмерной сетки с размером d;

- формирование на физической поверхности из элементарных участков (ЭУ);

- вычисление геометрических параметров ЭУ α_ij, d_ij, i, j∈[1,4];

- оценка пересечения ЭУ линейной преградой или ;

- определение преодолимости линейных преград и ;

- исключение дуги из графа W_Г в случае, если препятствие для выбранного технического средства непреодолимо;

- вычисление частных коэффициентов и оценка преодоления преград и выбранным транспортным средством;

- расчет обобщенного коэффициента проходимости для участка пути , прокладываемого по объекту Q_m∈K;

- расчет длины участка пути ;

- расчет приведенного веса дуги W_Г графа для однородной среды;

- расчет приведенного веса дуги W_Г графа для разнородной среды W_r=W_rN·δN+W_rK·δK, где W_rN, W_rK, δN, δK - приведенные веса для смежных участков местности и нормированные пропорции принадлежности дуги смежным участкам соответственно;

- расчет рационального маршрута с использованием алгоритма А - звезда.

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

В данном способе учитывается:

- тактико-технические характеристики средства перемещения, предназначенного для движения по построенному маршруту;

- тактические свойства местности в сочетании с сезонными климатическими условиями;

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

- длина пути и энергетические ресурсы, затрачиваемые средством перемещения на преодоление выбранного маршрута.

Задача построения маршрута может быть сформулирована следующим образом.

Пусть имеется:

1) Электронная векторная карта участка местности, которая представляет собой множество K, состоящее из М графических объектов

с каждым, из которых связана определенная картографическая и тематическая информация. Каждый объект множества представлен в виде:

где:

N_m - параметр, определяющий принадлежность (классификацию) объекта (лес, гидрография и т.п.);

{V_k} - множество координат (x_k,y_k) вершин объекта Q_m;

A_m - тематическая информация, присоединенная к соответствующему объекту Q_m, элементы а_р которой характеризуют текущее состояние объекта (например, толщина льда).

2) Цифровая модель рельефа местности

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

3) Заданы условия и ограничения на перемещение в зависимости от местности, включающие:

а) ограничения административного характера на движение по участку местности, закрытому по каким либо соображениям должностными лицами для перемещения, например, частное владение;

б) ограничения физического характера на движение, обусловленные свойствами местности, например, непреодолимый для автомобиля лесной массив;

в) ограничения административного характера на пересечение некоторой границы, например, заповедник, огороженный забором, через который можно проехать только через специально организованные въезды/выезды;

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

Требуется проложить и отобразить на электронной карте маршрут движения технического средства из точки старта в точку финиша с учетом тактических свойств местности и линейных объектов местности при минимизации длины пути и временно-энергетических ресурсов.

Решаемые способом задачи:

- оценка влияния тактических свойств местности в сочетании с сезонными климатическими условиями на передвижение конкретного средства перемещения;

- оценка влияния линейных объектов местности на передвижение конкретного средства перемещения;

- формирование возможных маршрутов движения;

- определение критерия для оценки затрачиваемых средством перемещения ресурсов при преодолении построенных маршрутов;

- выбор маршрута движения при минимизации длины пути и энергетических ресурсов.

Проходимость местности определяется ее пересеченностью. Местность с оврагами, крутыми скатами и обрывами, реками и заболоченными участками, с большими площадями лесных массивов в сочетании с сезонными явлениями (дождь, снег и т.п.) существенно затрудняют перемещение по ней технических средств [Военная топография в служебно-боевой деятельности оперативных подразделений. Под редакцией Ю.Г. Маслака// М.: Академический проспект, 2005 г.].

Проходимость местности можно оценить с помощью следующих коэффициентов: угла ската α в направлении предполагаемого движения; плотность грунта ρ; густоты леса (кустарников) R; мощности растительного покрова M_R; глубины водной преграды с учетом плотности дна Г_В; интенсивности гололедных явлений Е_Г; глубины снежного покрова h_C; толщины льда Т_Л.

Преодоление линейных препятствий можно оценить с помощью следующих коэффициентов: высоты насыпи H_ν; ширина траншеи или оросительного канала S_p; мощность ограждения M_S.

Учитывая тактико-технические характеристики (ТТХ) средств перемещения [Военная топография. Под редакцией генерал-лейтенанта технических войск А.С. Николаева. // М.: Военное изд-во, 1977 г.], введем для них следующие коэффициенты (ограничения) проходимости (для вновь разрабатываемых транспортных средств предлагаемые значения характеристик могут быть скорректированы, исходя из их ТТХ):

- преодоление скатов при сухом твердом грунте α_d в направлении предполагаемого движения. Для автомобилей повышенной проходимости α_d≤30°, для гусеничных тягачей с прицепами α_d≤25°, для танков и самоходных артиллерийских установок (САУ) α_d≤40°, для пешеходов значение не учитывается, та как практически любые скаты для пешеходов являются преодолимыми;

- проходимость по асфальтовым и грунтовым поверхностям ρ_П, имеющим различную плотность. Автомобильные дороги с твердым покрытием допускают движение транспорта в любую погоду. При ρ_П=0 - техника, способная перемещаться только по асфальту; ρ_П=1 - техника, способная перемещаться по супесчаной почве в сухую погоду; ρ_П=2 - техника, способная перемещаться по песчаной почве в сухую погоду; ρ_П=3 - техника, способная перемещаться по суглинистой почве или чернозему при промокании грунта до 5 см; ρ_П=4 - техника, способная перемещаться по суглинистой почве или чернозему при промокании грунта до 10 см; ρ_П=5 - техника, способная перемещаться по грунту при его промокании более 10 см.

При влажности грунта 50% (в обычном состоянии грунт имеет влажность 20%) преодолеваемые скаты меньше в 2 раза [В.А. Ильиных, В.А. Колесов. Военная топография: учебное пособие/ В.А. Ильиных, В.А. Колесов. - СПб.: ВКА имени А.Ф. Можайского, 2008. - 193 с]:

- проходимость по снежному покрову с учетом его глубины h_max;

- предельная глубина водной преграды Г_mах при средней плотности грунта (глина, суглинок) без герметизации двигателя. Для автомобилей весом до 2 т Г_mах≤0,6 м, для автомобилей весом до 5 т Г_mах≤0,9 м, для гусеничных тягачей Г_mах≤1 м, для средних танков Г_mах≤1,2 м, для тяжелых танков Г_mах≤1,5 м, для подразделений в пешем порядке Г_mах≤1 м;

- требуемая толщина льда T_min. Для автомобилей весом 2-4 т T_min≥16 см, для автомобилей весом 6-8 т T_min≥27 см, Для автомобилей весом до 10 т T_min≥35 см, для средних танков T_min≥50 см, для тяжелых танков T_min≥70 см, для пеших подразделений T_min≥4 см;

- густота леса (кустарников) R_max. Для танков, бронетранспортеров и автомобилей повышенной проходимости лес является проходимым в том случае, если среднее расстояние между деревьями более 6 м и отсутствует подлесок. Лес со средним расстоянием между деревьями 3,5 м, толщиной деревьев менее 20 см и порослью проходим для танков с валкой деревьев. Лес, проходимый для танков на ровной местности, на скатах крутизной более 10° становится труднопроходимым.

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

- максимальная высота насыпи H_{ν max}. Для гусеничных транспортных средств H_{ν max}=70 см; для автомобилей повышенной проходимости H_{ν max}=30 см; для других средств H_{ν max}=20 см. Если скаты насыпи имеют уклон скатов, преодолимый выбранным транспортным средством, то расчет проходимости ведется, как для обычного ската. Считается, что пешая группа способна преодолеть любую насыпь.

- максимальная ширина траншеи, оросительного канала S_{p max}. Для гусеничного транспортного средства траншея или оросительный канал считается преодолимым, если его ширина не превышает 2 м.

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

Анализ существующих алгоритмов поиска пути (алгоритм поиска в ширину, алгоритм Форда-Беллмана, алгоритм Дейкстры, алгоритм Флойда и алгоритм А-звезда) показал, что для решения задачи построения маршрута наиболее пригодным является алгоритм А-звезда [Dechter, R., Pearl, J. Generalized best-first search strategies and the optimality of A* // Journal of the ACM. - 1985. - T. 32. - №3. - C. 505-536.] Этот алгоритм находит в заданном графе единственный путь, обладающий минимальным весом. В отличие от алгоритма поиска в ширину рассматриваемый алгоритм работает не только с дугами графа, вес которых равен единице. Алгоритм Форда-Беллмана работает с дугами, имеющими отрицательный вес. В нашем случае вес дуг не может быть отрицательным, так как учитываемые длина пути и затрачиваемые энергетические ресурсы не могут быть отрицательными. Алгоритм Флойда требует больших вычислительных операций. Алгоритм А-звезда является более быстрым по сравнению с алгоритмом Дейкстры за счет использования эвристических функций. Поэтому для дальнейших расчетов используется алгоритм А-звезда.

В качестве параметров, характеризующих уровень энергетических затрат на прохождение соответствующего участка местности, введем математические модели, которые позволят оценивать воздействие свойств местности и ее линейных объектов на сложность прохождения средства перемещения. Для оценки сложности прохождения участка пути значения частных коэффициентов k_j и приводятся к интервалу [0, 1]. При этом, чем больше значение частного коэффициента, тем сложнее преодолеть оцениваемый участок пути. Если значение частного коэффициента превышает единицу, то участок пути (дуга на графе) непроходим для рассматриваемого средства перемещения. Значение обобщенного коэффициента проходимости для участка пути определяется как сумма частных коэффициентов всех учитываемых факторов и может быть больше единицы.

Отметим, что расчет частных коэффициентов следует проводить в том случае, если текущее значение оцениваемого ограничения удовлетворяет условиям проходимости средства перемещения.

Рассмотрим расчет значений частных коэффициентов в зависимости от условий возможного перемещения на пересеченной местности.

Рельеф местности является основным фактором, влияющим на движение транспортного средства, поскольку одна из его характеристик - крутизна ската в направлении движения, оказывает влияние при учете многих физических свойств местности. Очевидно, что чем ближе текущее значение угла α, характеризующего крутизну ската к максимальному углу подъема средства перемещения α_d, тем интенсивнее расход энергетических ресурсов на передвижение, поэтому для расчета коэффициента k_1, учитывающего крутизну ската, предлагается выражение:

Значение угла ската α для транспортных средств не должно превышать 40°, поскольку согласно [Военная топография. Под редакцией генерал-лейтенанта технических войск А.С. Николаева. // М.: Военное изд-во, 1977 г.] максимально преодолимая крутизна ската не превосходит 40° (для новых образцов техники данный способ позволяет вводить соответствующие другие значения).

Коэффициент k₂, характеризующий проходимость местности в зависимости от интенсивности гололедных явлений в сочетании с рельефом, может быть определен следующим образом:

Интенсивность проявления гололедных явлений Е_г в выражении (5) задается на качественном уровне Е_Г∈{0,1,2,3} и соответствует 0 - отсутствию, 1 - слабому, 2 - среднему, 3 - сильному проявлению гололедных явлений.

Коэффициент k₃, характеризующий проходимость местности в зависимости от состояния грунта, определяется из выражения

Плотность грунта ρ в выражении (6) задается на качественном уровне ρ∈{0,1,2,3,4,5}. При этом: При этом: 0 соответствует дорожному покрытию (асфальту), 1 - супесчаной почве в сухую погоду, 2 - песчаной почве в сухую погоду, 3 - суглинистой почве или чернозему при промокании грунта до 5 см (средний дождь), 4 - суглинистой почве или чернозему при промокании грунта до 10 см (сильный дождь, ливень), 5 - состоянию почвы в осеннюю, весеннюю распутицу (промокание более 10 см).

Коэффициент k₄, характеризующий проходимость от глубины снежного покрова, определяется из выражения

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

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

Коэффициент k₇, характеризующий зависимость проходимости по лесу или кустарнику с учетом густоты, определяется из выражения

Характеристики леса R в выражении (10) задается на качественном уровне R∈{1,2,3} и соответствует: 1 - лес, проходимый для транспортных средств (среднее расстояние между деревьями более 6 м и отсутствует подлесок); 2 - лес, проходимый для танков с валкой деревьев (среднее расстояние между деревьями 3,5 м, толщина деревьев менее 20 см, мелкая поросль); 3 - лес, непроходимый для транспортных средств (среднее расстояние между деревьями менее 3 м, толщина деревьев более 20 см, поросль, бурелом). Для пешеходов любой лес считается проходимым.

Коэффициент k₈, характеризующий проходимость в зависимости от мощности растительного покрова. Этот коэффициент сильно коррелирует с плотностью грунта (природными условиями) и определяется из выражения

Мощность растительного покрова M_R в выражении (11) задается на качественном уровне M_R∈{0,1,2} и соответствует: 0 - густая низкая растительность (терн); 1 - невысокая растительность (ниже 50 см, степь); 2 - высокая растительность (выше 50 см, сельхозугодия).

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

Характеристики насыпей Н в выражении (12) задается на качественном уровне Н∈{1,2,3} и соответствует: 1 - насыпь преодолима для транспортных средств; 2 - насыпь преодолима для автомобилей повышенной проходимости; 3 - насыпь преодолима для гусеничных транспортных средств. Для пешеходов любая насыпь считается проходимым.

Коэффициент , характеризующий преодоление траншей или оросительных каналов от их ширины

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

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

Характеристика заборов и стен M_S в выражении (14) задается на качественном уровне M_S∈{1,2,3} и соответствует его степени прочности. Для пешеходов любой забор считается проходимым. Данная преграда считается административной, но в некоторых случаях может восприниматься как физическая.

Коэффициент , характеризующий зависимость преодоления транспортным средством ручьев и малых рек, рассчитывается как k₅.

Трубопроводы считаются преодолимыми для пеших подразделений.

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

Рассмотрим основные шаги рассматриваемого способа:

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

Области проходимости для средства перемещения формируются из объектов . Эти объекты образуют множество , , . Области, не вошедшие в K^d - это заданные и определенные административного и физического характера.

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

Вершины четырехугольника (они же вершины формируемого графа) характеризуются координатами (x,y,h); значения (х,у) определяются построением сетки, а значения высоты h - с помощью цифровой модели рельефа. Стороны четырехугольника и его диагонали (они же предполагаемые дуги формируемого графа) в общем случае будут иметь различную длину и разную сложность прохождения, которые обусловлены характером рельефа в сочетании с физическими свойствами среды на оцениваемый момент времени. Таким образом, для множества K^d сформирована условная геометрическая поверхность из элементарных участков, каждый из которых удовлетворяет ограничениям на проходимость без учета рельефа. Эта поверхность и все построения на ней используются только для расчетов и не отображаются на карте. На этой поверхности предлагается строить граф возможных путей, удовлетворяющий условиям алгоритма А-звезда и условиям задачи.

3. Для дальнейшего уменьшения размерности задачи осуществляется исключение на элементарном участке (ЭУ) дуг графа, пересекающих непреодолимые линейные преграды (см. фиг. 4). Если через элемент соответствующий рассматриваемому элементарному участку проходит линейная преграда, то для каждой дуги r_j∈ЭУ выполняются следующие действия:

- определяется наличие пересечения ;

- при наличии дуга исключается, а при наличии оцениваются ограничения;

- для дуги r_j∈ЭУ удовлетворяющей условиям проходимости (ограничениям) вычисляются частные коэффициенты . В противном случае дуга исключается.

Таким образом, на множестве K^d для каждого элементарного участка определены дуги графа, удовлетворяющие условиям проходимости, которым в соответствии с условиями задачи надо сопоставить единый критерий - вес дуги, в котором учитываются пройденный путь, энергетические затраты, а также время движения.

4. Расчет приведенного веса W_r для дуг сформированного графа осуществляется в следующей последовательности (см. фиг. 5).

Сначала для оцениваемого ребра r_ij определяется возможность передвижения в зависимости от рельефа. Для этого рассчитывается значение угла ската в оцениваемом направлении (см. фиг. 6) по формуле:

При этом положительный знак угла ската указывает на подъем, а отрицательный - на спуск.

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

Если значение угла лежит в допустимых пределах, то для этого ребра:

- рассчитываются его фактическая длина d_Фij по пространственным

координатам соответствующих вершин ЭУ с помощью формулы [Александров П.С. Лекции по аналитической геометрии. - М.: Наука, 1968 г.]

- рассчитываются частные коэффициенты .

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

и приведенный вес дуги .

В выражениях (15)-(17) нижние индексы i, j - номера вершин ЭУ в оцениваемом направлении движения от i к j.

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

Выражения (15)-(18) обеспечивают вычисление приведенного веса дуги W_r, когда прокладка пути осуществляется в однородной среде, т.е. начало и конец дуги принадлежат одному объекту.

Если оцениваемая дуга принадлежит двум смежным объектам, то ее вес определяется пропорциональным перераспределением весов W_rN и W_rK, вычисленных для этих объектов

где δN, δK - нормированные пропорции принадлежности дуги смежным участкам.

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

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

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

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

Изобретение относится к области приборостроения и может быть использовано в автоматизированной системе управления войсками и поисково-спасательными командами при управлении движением разнотипных транспортных средств по пересеченной местности. Технический результат - повышение достоверности построения маршрута, а также снижение времени на построение маршрута с использованием векторных карт. Для достижения результата введены новые операции: оценка пересечения участка маршрута с линейным препятствием, анализ преодоления линейных препятствий, исключение дуг из графа возможных маршрутов при невозможности преодоления препятствия, расчет приведенного веса с учетом преодоления линейных препятствий, учет разнородности среды при оценке приведенного веса дуги; применен алгоритм А-звезда. 6 ил.

Способ построения маршрута передвижения по пересеченной местности, включающий загрузку цифровой векторной карты местности, задание точек старта А(х_А,у_А) и финиша В(х_В,у_В), отличающийся тем, что введено использование дополнительных анализируемых параметров и коэффициентов, описывающих физические свойства среды, рельеф, линейные антропогенные объекты при учете сезонно-климатических условий, использующий алгоритм А-звезда; при этом в предлагаемом способе: определяют тип и тактико-технические характеристики транспортного средства, предназначенного для перемещения по местности; определяют непроходимые для выбранного транспортного средства зоны административного и физического характера ; задают линейные препятствия административного характера; определяют линейные антропогенные препятствия физического характера ; отображают на электронной карте непроходимые зоны; исключают из расчетов непроходимые зоны и формируют область проходимости ; формируют граф возможных маршрутов движения на карте для выбранного транспортного средства, разбивая отображаемую на электронной карте местность на элементарные участки (ЭУ) и формируя на каждом ЭУ направления возможных перемещений; размер ЭУ d определяется имеющейся моделью рельефа Н=Ф(х,у) (при регулярной модели это шаг по сетке рельефа, а при задании модели изолиниями - минимальное расстояние между изолиниями); для узловых точек сетки определяются высоты, на которых строится условная геометрическая поверхность заданной местности; каждый ЭУ удовлетворяет ограничениям на проходимость без учета рельефа, его вершины соответствуют вершинам формируемого графа, а стороны и диагонали -дугам; исключают из формируемого графа дуги (стороны или диагонали ЭУ), если пересекаемая в их направлении линейная преграда или является непреодолимой для выбранного транспортного средства; если оцениваемое направление удовлетворяет ограничению на перемещение, то для соответствующей дуги графа вычисляется частный коэффициент ; вычисляют для каждой дуги графа (допустимого направления перемещения на местности) приведенный вес W_Г, характеризующий энергетические затраты на перемещение по дуге графа r_j, определяемые длинной дуги d_r и сложностью проходимого участка местности, которая выражается через обобщенный коэффициент , который определяется аддитивной функцией учитываемых частных коэффициентов; частные коэффициенты k_n рассчитываются для учитываемых факторов среды (объекта (Q_m}∈K), характеризующих природные свойства с учетом рельефа и сложившихся климатических условий; если хотя бы один из частных коэффициентов k_n>1, то рассматриваемый участок маршрута исключается из графа; если оцениваемая дуга принадлежит двум смежным объектам (Q_n,Q_k)∈K, то ее вес W_r определяется пропорциональным перераспределением весов W_rN и W_rK, вычисленных для этих объектов; на сформированном графе с множеством дуг разного веса W_ri, производят расчет рационального маршрута для выбранного транспортного средства при минимизации энергетических ресурсов с использованием алгоритма А-звезда.