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

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

 

Изобретение относится к области приборостроения и может быть использовано в автоматизированной системе управления войсками, поисково-спасательными командами при управлении движением разнотипных транспортных средств по пересеченной местности. Технический результат - повышение оперативно-технических характеристик и достоверности построения маршрута, а также снижение времени на построение маршрута по пересеченной местности для транспортного средства, сокращение времени на прибытие в конечную точку маршрута, а также расхода горюче-смазочных материалов. Заявляемые преимущества обеспечиваются расширением оцениваемого объектового состава векторной карты, включением новых математических моделей и тематических баз данных об объектах и транспортных средствах, использованием менее ресурсоемкого алгоритма - алгоритма А-звезда. Для достижения данного результата введены новые операции: оценка пересечения участка маршрута с линейным препятствием, анализ преодоления линейных препятствий на основе введенных коэффициентов, исключение дуг из графа возможных маршрутов при невозможности преодоления препятствия выбранным транспортным средством, расчет приведенного веса с учетом преодоления линейных препятствий, учет разнородности среды при оценке приведенного веса дуги. При этом обеспечивается оптимизация маршрута передвижения на пересеченной местности по заданным параметрам и критериям. Положительный эффект заключается в снижении времени на построение маршрута по пересеченной местности, а также его корректности с учетом использования полного объектового состава векторной карты, влияющего на скорость и возможность передвижения выбранного транспортного средства по рассматриваемому участку, сокращение времени прибытия в точку назначения для группы реагирования или наземной поисково-спасательной команды (НПСК), минимизации расхода горюче-смазочных материалов (Фиг. 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г, при этом производят оценку участка пути с помощью вычисления частных коэффициентов kj, сравнивают kj с единицей, если kj≥1, определяют непроходимые зоны и , если kj<1, производят расчет обобщенного коэффициента проходимости для участка пути , производят расчет длины участка пути dO ij, производят расчет приведенного веса дуги Wг графа, определяют затраты на границах участка местности g12=(g1+g2)/2, производят расчет рационального маршрута для выбранного транспортного средства при минимизации длины пути и энергетических ресурсов с использованием алгоритма Дейкстры.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- максимальная ширина траншеи, оросительного канала Sp 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.] Этот алгоритм находит в заданном графе единственный путь, обладающий минимальным весом. В отличие от алгоритма поиска в ширину рассматриваемый алгоритм работает не только с дугами графа, вес которых равен единице. Алгоритм Форда-Беллмана работает с дугами, имеющими отрицательный вес. В нашем случае вес дуг не может быть отрицательным, так как учитываемые длина пути и затрачиваемые энергетические ресурсы не могут быть отрицательными. Алгоритм Флойда требует больших вычислительных операций. Алгоритм А-звезда является более быстрым по сравнению с алгоритмом Дейкстры за счет использования эвристических функций. Поэтому для дальнейших расчетов используется алгоритм А-звезда.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Способ построения маршрута передвижения по пересеченной местности, включающий загрузку цифровой векторной карты местности, задание точек старта А(хАА) и финиша В(хВВ), отличающийся тем, что введено использование дополнительных анализируемых параметров и коэффициентов, описывающих физические свойства среды, рельеф, линейные антропогенные объекты при учете сезонно-климатических условий, использующий алгоритм А-звезда; при этом в предлагаемом способе: определяют тип и тактико-технические характеристики транспортного средства, предназначенного для перемещения по местности; определяют непроходимые для выбранного транспортного средства зоны административного и физического характера ; задают линейные препятствия административного характера; определяют линейные антропогенные препятствия физического характера ; отображают на электронной карте непроходимые зоны; исключают из расчетов непроходимые зоны и формируют область проходимости ; формируют граф возможных маршрутов движения на карте для выбранного транспортного средства, разбивая отображаемую на электронной карте местность на элементарные участки (ЭУ) и формируя на каждом ЭУ направления возможных перемещений; размер ЭУ d определяется имеющейся моделью рельефа Н=Ф(х,у) (при регулярной модели это шаг по сетке рельефа, а при задании модели изолиниями - минимальное расстояние между изолиниями); для узловых точек сетки определяются высоты, на которых строится условная геометрическая поверхность заданной местности; каждый ЭУ удовлетворяет ограничениям на проходимость без учета рельефа, его вершины соответствуют вершинам формируемого графа, а стороны и диагонали -дугам; исключают из формируемого графа дуги (стороны или диагонали ЭУ), если пересекаемая в их направлении линейная преграда или является непреодолимой для выбранного транспортного средства; если оцениваемое направление удовлетворяет ограничению на перемещение, то для соответствующей дуги графа вычисляется частный коэффициент ; вычисляют для каждой дуги графа (допустимого направления перемещения на местности) приведенный вес WГ, характеризующий энергетические затраты на перемещение по дуге графа rj, определяемые длинной дуги dr и сложностью проходимого участка местности, которая выражается через обобщенный коэффициент , который определяется аддитивной функцией учитываемых частных коэффициентов; частные коэффициенты kn рассчитываются для учитываемых факторов среды (объекта (Qm}∈K), характеризующих природные свойства с учетом рельефа и сложившихся климатических условий; если хотя бы один из частных коэффициентов kn>1, то рассматриваемый участок маршрута исключается из графа; если оцениваемая дуга принадлежит двум смежным объектам (Qn,Qk)∈K, то ее вес Wr определяется пропорциональным перераспределением весов WrN и WrK, вычисленных для этих объектов; на сформированном графе с множеством дуг разного веса Wri, производят расчет рационального маршрута для выбранного транспортного средства при минимизации энергетических ресурсов с использованием алгоритма А-звезда.



 

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

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

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

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

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

Изобретение относится к области автоматизированного управления движением транспортных средств (ТС). Способ заключается в автоматическом формировании маршрута движения (МД) ТС с минимизацией последствий воздействия неблагоприятных факторов на участников движения.

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

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

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

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

Изобретение относится к области компьютерной техники, а именно к обработке поискового запроса пользователя, относительно интересующих объектов. Технический результат – эффективная обработка поискового запроса пользователя, связанного с географическим положением. Способ обработки поискового запроса пользователя, связанного с электронным устройством, включающий получение поискового запроса, определение указания, связанного с географическим положением, которое, в свою очередь, связано с пользователем, определение указания, связанного со сценарием, который содержит данные, определяющие последовательность событий; создание результирующего набора, связанного с поисковым запросом, посредством определения процессором сервера указания, связанного с первым интересующим объектом, на основе анализа данных, связанных с первым интересующим объектом, указания, связанного с географическим положением, указания, связанного со сценарием, определения процессором сервера указания, связанного со вторым интересующим объектом, на основе анализа данных, связанных со вторым интересующим объектом, указания, связанного с географическим положением, указания, связанного со сценарием, формирования процессором сервера результирующего набора, содержащего указание первого интересующего объекта и указание второго интересующего объекта, сохранения на постоянном машиночитаемом носителе информации, доступном серверу, результирующего набора, инициирование отображения электронным устройством результирующего набора пользователю. 2 н. и 36 з.п. ф-лы, 10 ил.

Изобретение относится к области приборостроения и может быть использовано в тренажерах подготовки операторов локационных станций. Технический результат - расширение функциональных возможностей. Для достижения данного результата положение и геометрическое представление траектории движения объекта в пространстве плавно комплексируется из последовательно сопрягаемых сегментов с наглядными графическими интуитивными изменениями их формы и кривизны, расчетом параметрических уравнений движения в каждом сегменте по трем координатам x(t), y(t), z(t) зоны обзора локационной станции в функции безразмерного параметра t∈[0;1] с преобразованием его при различных законах изменений линейной скорости движения в функцию от аргумента - линейно-нарастающего временного интервала реального времени tp воспроизведения траектории путем определения проходимого по сегментам пути S(tp), вычисления в соответствии с обратной функцией значений t(S) в каждом сегменте и последующим вычислением в блоке расчета координат по параметрическим уравнениям движения значений текущих декартовых координат объекта. Геометрическая форма каждого сегмента общей траектории движения выстраивается на основе итерационного изменения расположения координат n опорных точек ({Pi}={xi, yi, zi}, i=0, …, n-1) опорной ломаной линии кривой Безье сегмента с n узлами с исключением критических перегрузок при максимальных линейных скоростях движения. 5 з.п. ф-лы, 8 ил.

Первичное (6) транспортное средство перевозит вторичное (7) транспортное средство, производящее меньшие или нулевые выбросы СО2, например автомобиль или велосипед. Имеются средство (20) иммобилизации первичного (6) транспортного средства, если вторичное (7) транспортное средство удалено из него, средство (20) хранения данных касательно использования первичного (6) и вторичного (7) транспортных средств, средство (12) пользовательского интерфейса для отображения информации касательно использования первичного (6) и вторичного (7) транспортных средств и средство рекомендаций пользователю для предоставления информации касательно потенциальных возможностей для использования вторичного (7) транспортного средства. Снижаются выбросы СО2 в атмосферу за счет стимулирования использования вторичного транспортного средства. 3 н. и 11 з.п. ф-лы, 8 ил., 1 табл.

Группа изобретений относится к области управления движением транспортных потоков, а более конкретно к способу, устройству и системе для управления движением транспортных средств. В способе соединяют посредством объединенной сети клиентские устройства участников дорожного движения, имеющие блок позиционирования и навигации, с сервером, имеющим модуль нахождения оптимальных рекомендаций построения маршрута для каждого участника дорожного движения, соединенный с модулем осуществления двусторонней связи с клиентскими устройствами. Отправляют на сервер данные, соответствующие параметрам предполагаемого маршрута. Находят оптимальные рекомендации построения маршрута для каждого участника. Отправляют вычисленную рекомендацию на клиентское устройство, а также к устройствам и системам, реализующим способ. Согласно изобретению создают базу данных персональных данных и всех маршрутов всех участников дорожного движения, производят идентификацию участников дорожного движения по ней и находят оптимальные рекомендации построения маршрута для каждого участника дорожного движения путем формирования предложения общего транспортного средства для участников дорожного движения, у которых по меньшей мере частично совпадают маршруты движения. Устройство и система реализуют указанный способ. Достигается уменьшение количества транспортных средств, участвующих в дорожном движении, следовательно, повышается средняя скорость движения транспортных средств. 3 н. и 16 з.п. ф-лы, 2 ил.

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

Изобретение относится к вспомогательным электронным системам транспортных средств, а именно к системам автоматической парковки. Способ постановки транспортного средства на стоянку заключается в том, что выполняют калибровку значения скорости колеса транспортного средства на основании измеренной длины снаружи транспортного средства и паркуют транспортное средство на основании откалиброванного значения скорости колеса. Обеспечивается автоматическая парковка с дополнительной информацией о колесах. 3 н. и 11 з.п. ф-лы, 4 ил.

Изобретение относится к области к автотранспорта, в частности к прогнозированию энергопотребления/расхода топлива при движении транспортного средства. Технический результат заключается в повышении эффективности прогнозирования энергопотребления. Предложено устройство прогнозирования энергопотребления, содержащее: модуль (110) получения, модуль (140, 150) вычисления сопротивления воздуха и модуль (130) прогнозирования энергопотребления. Модуль (110) получения выполнен с возможностью получать информацию дороги, включающую в себя информацию скорости движения, заданную для каждого маршрута. Модуль (140, 150) вычисления сопротивления воздуха выполнен с возможностью вычислять сопротивление воздуха в качестве вычисленного значения сопротивления воздуха посредством формулы вычисления сопротивления воздуха на основе информации скорости движения запланированного маршрута движения и корректировать вычисленное значение сопротивления воздуха так, что сопротивление воздуха увеличивается по мере того, как скорость движения по запланированному маршруту движения понижается. Сопротивление воздуха возникает, когда транспортное средство движется по запланированному маршруту движения. Модуль (130) прогнозирования энергопотребления выполнен с возможностью прогнозировать энергопотребление запланированного маршрута движения на основе скорректированного значения сопротивления воздуха. 2 н. и 9 з.п. ф-лы, 26 ил.

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