Способ прокладывания маршрута передвижения на пересеченной местности



Способ прокладывания маршрута передвижения на пересеченной местности
Способ прокладывания маршрута передвижения на пересеченной местности
Способ прокладывания маршрута передвижения на пересеченной местности
Способ прокладывания маршрута передвижения на пересеченной местности
Способ прокладывания маршрута передвижения на пересеченной местности
Способ прокладывания маршрута передвижения на пересеченной местности

 


Владельцы патента RU 2439496:

Федеральное государственное унитарное предприятие "Курский научно-исследовательский институт" Министерства обороны Российской Федерации (RU)

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

 

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

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

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

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

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

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

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

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

,

определение затрат на маршруте:

,

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

нахождение оптимальных маршрутов.

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

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

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

Цель достигается тем, что в известном способе, включающем загрузку электронной карты местности, определение точек старта A(xA, yA) и финиша B(xB, yB), согласно изобретению анализируют проходимость местности с помощью введенных коэффициентов, определяют тип и тактико-технические характеристики транспортного средства, предназначенного для перемещения по местности, определяют непроходимые, для выбранного транспортного средства, зоны административного Zi и физического характера, отображают на электронной карте непроходимые зоны, исключают из расчетов непроходимые зоны сравнивают область проходимости Q с непроходимыми зонами Zi и если область проходимости то определяют новые непроходимые зоны Zi и если область проходимости то формируют возможные маршруты движения на карте для выбранного транспортного средства, при этом определяют наличие матрицы высот для карты местности , если матрица высот отсутствует, то определяют минимальное расстояние между изолиниями, если матрица высот присутствует, то определяют шаг матрицы высот, выбирают размер сетки d, формируют на двухмерную сетку с размером d, формируют на трехмерную сетку с учетом матрицы высот , формируют на элементарные ячейки, рассчитывают приведенный вес для каждого участка маршрута Wr, при этом производят оценку участка пути с помощью вычисления частных коэффициентов ki, сравнивают ki, с единицей, если ki≥1, то определяют непроходимые зоны Zi и , если ki≤1, то производят расчет обобщенного коэффициента проходимости для участка пути , производят расчет длины участка пути производят расчет приведенного веса дуги Wr графа, определяют затраты на границах участков местности , производят расчет рационального маршрута для выбранного транспортного средства при минимизации длины пути и энергетических ресурсов с использованием алгоритма Дейкстры.

Сопоставительный анализ технического решения со способом, выбранным в качестве прототипа, показывает, что заявляемый способ отличается новыми операциями, такими как, анализ проходимости местности с помощью введенных коэффициентов, определение типа и тактико-технических характеристик транспортного средства, предназначенного для перемещения по пересеченной местности, определение непроходимых для выбранного транспортного средства зон административного Zi и физического характера, исключение из расчетов непроходимых зон , сравнение области проходимости Q с непроходимыми зонами Zi и , если область проходимости то определяют новые непроходимые зоны Zi и если область проходимости то формируют возможные маршруты движения на электронной карте для выбранного транспортного средства, при этом определяют наличие матрицы высот для , если матрица высот отсутствует, то определяют минимальное расстояние между изолиниями, если матрица высот присутствует, то определяют шаг матрицы высот, производят выбор размера сетки d, формируют на двухмерную сетку с размером d, формируют на трехмерную сетку с учетом матрицы высот , формируют на элементарные ячейки, производят расчет приведенного веса для каждого участка маршрута Wr, при этом производят оценку участка пути с помощью вычисления частных коэффициентов ki, сравнивают ki с единицей, если ki≥1, то определяют непроходимые зоны Zi и , если ki≤1, то производят расчет обобщенного коэффициента проходимости для участка пути , расчет длины участка пути , расчет приведенного веса дуги Wr графа, расчет рационального маршрута для выбранного транспортного средства при минимизации длины пути и энергетических ресурсов с использованием алгоритма Дейкстры.

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

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

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

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

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

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

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

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

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

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

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

- загрузка электронной векторной карты;

- определение точки старта А(xA, yA) и финиша B(xB, yB);

- анализ проходимости местности с помощью введенных коэффициентов;

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

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

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

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

- сравнение области проходимости Q с непроходимыми зонами Zi и ,

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

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

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

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

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

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

- формирование на трехмерной сетки с учетом матрицы высот ;

- формирование на элементарных ячеек;

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

- оценка участка пути с помощью вычисления частных коэффициентов ki;

- сравнение ki с единицей;

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

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

- расчет приведенного веса дуги Wr графа;

- определение затрат на границах участков местности

;

- расчет рационального маршрута с использованием алгоритма Дейкстры.

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

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

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

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

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

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

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

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

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

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

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

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

{Vk} - множество координат (xk, yk) объекта Qm;

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

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

,

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

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

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

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

Требуется проложить и отобразить на электронной карте маршрут движения для выбранного должностными лицами (командирами) типа средства перемещения из точки старта А{xA, yA)|A в точку финиша B(xB, yB)|B, с учетом тактических свойств местности, при минимизации длины пути и энергетических ресурсов.

Решаемые способом задачи следующие:

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

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

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

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

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

Проходимость местности можно оценить с помощью следующих коэффициентов: угла ската α в направлении предполагаемого движения; плотность грунта ρ; густоту леса (кустарников) R; мощность растительного покрова MR; глубину водной преграды с учетом плотности дна ГB; интенсивность гололедных явлений EГ; глубину снежного покрова hС, толщину льда ТЛ.

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

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

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

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

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

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

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

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

Исходя из представленных выше ограничений, предлагается решение задачи прокладывания маршрута. Ее суть представлена на фиг.4, а решение задачи предусматривает:

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

- аппроксимирование элементарными участками (ЭУ) сформированных зон проходимости, с целью упрощения логики построения графа;

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

- построение маршрута следования средства перемещения и отображение его в виде линии на электронной векторной карте местности.

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

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

Вес дуги зависит от:

- длины самой дуги;

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

Анализ существующих алгоритмов поиска пути (алгоритм поиска в ширину, алгоритм Форда-Беллмана, алгоритм Дейкстры и алгоритм Флойда) показал, что для решения задачи маршрутизации наиболее пригодным является алгоритм Дейкстры [Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. // Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001 г.; Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. - М.: Наука, 1990 г.; Шапорев С.Д. Математическая логика. Курс лекций и практических занятий. // М.: Наука, 2000 г.]. Этот алгоритм находит в заданном графе единственный путь, обладающий минимальным весом. В отличие от алгоритма поиска в ширину, алгоритм Дейкстры работает не только дугами графа, вес которых равен единице. Алгоритм Форда-Беллмана работает с дугами, имеющими отрицательный вес. В нашем случае вес дуг не может быть отрицательным, т.к. учитываемые в методике длина пути и затрачиваемые энергетические ресурсы не могут быть отрицательными. Алгоритм Флойда требует больших вычислительных операций. Поэтому для дальнейших расчетов используется алгоритм Дейкстры.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Значение обобщенного коэффициента проходимости для участка пути рассчитывается по формуле:

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

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

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

- вершинами графа являются узловые точки ЭУ - {1, 2, 3, 4};

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

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

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

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

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

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

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

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

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

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

Приведенный вес дуги Wr графа является функцией от фактической длины дуги, свойств местности передвижения, рельефа местности в сочетании с погодными условиями, ограничений на перемещение.

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

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

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

Способ прокладывания маршрута передвижения на пересеченной местности, включающий загрузку электронной карты местности, определение точек старта А(хA, уA) и финиша В(хB, уB), отличающийся тем, что анализируют проходимость местности с помощью введенных коэффициентов, определяют тип и тактико-технические характеристики транспортного средства, предназначенного для перемещения по местности, определяют непроходимые для выбранного транспортного средства зоны административного Zi и физического характера, отображают на электронной карте непроходимые зоны, исключают из расчетов непроходимые зоны , сравнивают область проходимости с непроходимыми зонами Zi и , если область проходимости , то определяют новые непроходимые зоны Zi и , если область проходимости , то формируют возможные маршруты движения на карте K={Qm} для выбранного транспортного средства, при этом определяют наличие матрицы высот для K={Qm}, если матрица высот отсутствует, то определяют минимальное расстояние между изолиниями, если матрица высот присутствует, то определяют шаг матрицы высот, выбирают размер сетки d, формируют на K={Qm} двухмерную сетку с размером d, формируют на K={Qm} трехмерную сетку с учетом матрицы высот , формируют на K={Qm} элементарные ячейки, рассчитывают приведенный вес для каждого участка маршрута Wr, при этом производят оценку участка пути с помощью вычисления частных коэффициентов ki, сравнивают ki с единицей, если ki≥1, определяют непроходимые зоны Z1 и , если ki≤1, производят расчет обобщенного коэффициента проходимости для участка пути производят расчет длины участка пути , производят расчет приведенного веса дуги Wr графа, определяют затраты на границах участка местности g12=(g1+g2)/2, производят расчет рационального маршрута для выбранного транспортного средства при минимизации длины пути и энергетических ресурсов с использованием алгоритма Дейкстры.



 

Похожие патенты:

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

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

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

Изобретение относится к области автоматизированного управления движением транспортных средств (ТС)

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

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

Изобретение относится к системе определения экономного маршрута транспортного средства. Техническим результатом является определение кратчайшего маршрута, вывод маршрута оптимального по расходу топлива. Заявлен способ определения экономного маршрута транспортного средства, в котором осуществляют: сбор данных в бортовой навигационной системе (VNS) для нескольких маршрутов между двумя пунктами; взвешивание в системе VNS двух или более возможных маршрутов на основании по меньшей мере собранных данных; настройку веса в системе VNS для каждого взвешенного маршрута на основании прогнозируемого расхода топлива; определение в системе VNS маршрута, оптимального по расходу топлива, на основании настроенного веса; корреляцию одного или нескольких элементов собранных данных с одной или несколькими энергогенерирующими системами транспортного средства, причем взвешивание основано, по меньшей мере частично, на индикации, основанной на собранных данных, о том, что на отрезке или на всем возможном маршруте возникают благоприятные условия для генерирования энергии путем ее рекуперирования во время движения транспортного средства; и вывод по меньшей мере одного вычисленного оптимального маршрута, эффективного по расходу топлива. 5 з.п. ф-лы, 7 ил.

Изобретение относится к способам и навигационным устройствам для определения маршрута перемещения из первого местоположения во второе местоположение, имеющего относительно низкие затраты. Технический результат - уменьшение общих затрат на перемещение по маршруту в транспортном средстве. Навигационное устройство содержит память с сохраненной картографической базой данных, содержащей множество сегментов дороги и значений затрат транспортного средства (ТС), представляющие собой ожидаемое потребление энергии или топлива ТС, извлеченное из данных об ускорении, полученных от множества транспортных средств, которые перемещались по сегменту дороги; процессор, рассчитывающий маршрут перемещения для ТС из первого местоположения во второе, причем рассчитанный маршрут минимизирует или относительно уменьшает общее ожидаемое потребление энергии или топлива транспортного средства, перемещающегося между первым местоположением и вторым местоположением; и устройство вывода, выводящее определенный маршрут перемещения. 5 н. и 13 з.п. ф-лы, 6 ил.

Изобретение относится к области автоматизированного управления движением транспортных средств (ТС). Способ заключается в автоматическом формировании маршрута движения (МД) ТС с минимизацией последствий воздействия неблагоприятных факторов на участников движения. Предварительно задают значения предельно допустимых уровней (ПДУ) вредных веществ (ВВ), содержащихся в выбросах потенциально-опасных объектов (ПОО) в зонах расположения ПОО. От ПОО передают на центральную станцию (ЦС) сигналы о состоянии ПОО. Рассчитывают прогнозируемые площади зон (ППЗ). На ЦС вводят исходные данные о характере дорог дорожной сети (ДС), формируют модельную цифровую карту (МЦК) ДС и передают ее на ТС. От ТС на ЦС передают данные о запланированном МД и характеристиках ТС. Если от ПОО не получен сигнал «авария», то на ЦС для ТС формируют МД. Затем корректируют МЦК и МД ТС с учетом минимизации суммарных затрат, необходимых для перемещения по сформированному МД. Если от ПОО получен сигнал «авария», то с учетом фактических метеоусловий уточняют ППЗ и корректируют для ТС МД, исключающий проезд участков ДС. Передают повторно откорректированный МД для ТС. Технический результат заключается в формировании оптимального и безопасного маршрута движений ТС по ДС. 3 з.п. ф-лы, 4 ил.

Изобретение относится к области навигации и предназначено для обеспечения портов, судоходных каналов, водных путей рек, озер и морей надежным навигационным средством, позволяющим осуществлять автоматическую проводку судов в сложных навигационных условиях. Техническим результатом предлагаемого изобретения является повышение безопасности проводки морских и речных судов по заданному курсу, в том числе в условиях отказа или радиотехнического подавления спутниковой навигационной системы ГЛОНАСС/NAVSTAR. Для достижения данного результата в едином интегрированном вычислителе одновременно с информацией от существующих систем навигации обрабатывается информация от береговой радиолокационной станции, получаемая от створного маяка, оборудованного средствами связи с береговой радиолокационной станцией, излучающего оптический сигнал, дополнительно содержащий информацию о координатах и параметрах движения как судоводителя, так и других судов, движущихся по фарватеру, полученную от береговой радиолокационной станции. 1 з.п. ф-лы, 1 ил.

Изобретение относится к планированию маршрута для транспортного средства. Система для планирования мультимодального маршрута поездки, включающая в себя компьютер транспортного средства с процессором и запоминающим устройством, выполненным принимать входную информацию о начальном и конечном пунктах маршрута; прокладывать несколько предварительных маршрутов между начальным и конечным пунктом через различные промежуточные пункты. Также извлекают данные, относящиеся к параметрам маршрута, отражающим индивидуальные предпочтения пользователя, и типу транспортного средства, и данные, по крайней мере, одного атрибута одного или нескольких промежуточных пунктов маршрута. Причем этот атрибут относится к доступности парковки для конкретного типа транспортного средства поблизости от рассматриваемого промежуточного пункта. Выбирают из предварительных маршрутов тот маршрут, в котором атрибуты промежуточных пунктов согласуются с параметрами и типом транспортного средства. При учете параметров маршрута из рассмотрения исключается один промежуточный пункт. Достигается оптимизация маршрута. 2 н. и 6 з.п. ф-лы, 3 ил.
Наверх