Кравченко Михаил Константинович

Факультет компьютерных наук и технологий

Кафедра компьютерной инженерии

Специальность Программное обеспечение средств вычислительной техники

Разработка системы мониторинга и анализа изменений метеоусловий

Научный руководитель: к.т.н., доц. Николаенко Денис Владимирович

Резюме Биография Реферат Библиотека Ссылки Отчет о поиске Индивидуальный раздел

Реферат по теме выпускной работы

Содержание

• Введение
• 1. Актуальность темы
• 2. Цель и задачи исследования, планируемые результаты
• 3. Обзор существующих алгоритмов
• 3.1 Обзор методов краткосрочного прогнозоривания погоды
• 3.2 Обзор алгоритмов построения пути
• 4. Разработка алгоритма функционирования системы
• Выводы
• Список источников

Введение

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

1. Актуальность темы

Количество транспортных средств непрерывно растет. Актуальными становятся проблемы, связанные с составлением маршрутов, анализом трафика, повышением безопасности. Широкое применение умных сред в транспортной отрасли рассматривается, в основном, в рамках концепции интеллектуальных транспортных систем (intelligent transportation systems, ITS) [2]. Устранить все угрозы безопасности на дороге интеллектуальные транспортные системы не могут. Однако они могут предупреждать водителя о тех или иных угрозах. Зная, что есть опасный участок пути, его можно объехать по другому маршруту.

Современные навигационные системы не просто строят маршрут, но и учитывают пробки, ограничения скорости, ремонт дорожных участков и прочие параметры, влияющие на выбор маршрута. Грамотно спланированный маршрут и автоматизация управления позволят сэкономить затраты топлива, соответственно, и уменьшить вред экологии, свести к минимуму аварии и катастрофы [3]. Многие транспортные системы уже имеют встроенные навигаторы, задачей которых является построение маршрута движения из точки А в точку Б. Для этого используются различные алгоритмы, активно используемые в прокладке сетей, разводке печатных плат, движении объектов в компьютерных играх. Но данные алгоритмы не учитывают погодных условий, которые могут оказывать большое влияние на безопасность движения. Актуальной остаётся проблема интеллектуализации транспортных систем с использованием общедоступного оборудования, что позволит прокладывать маршрут, учитывая погодные условия в реальном и будущем времени, с приемлемым быстродействием выбора рационального маршрута.

2. Цель и задачи исследования, планируемые результаты

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

Основные задачи исследования:

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

Объект исследования: построение маршрутов с учетом погоды.

Предмет исследования: объединение методов краткосрочного прогноза погоды с алгоритмом построения маршрута на карте.

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

1. Разработка алгоритма краткосрочного прогноза погоды с последующим определением опасных участков дорожных примитивов в конкретный момент времени, на основании известных методов прогнозирования метеоусловий;
2. Определение наилучшего алгоритма построения пути на взвешенных графах дорог;
3. Объединение алгоритмов прогнозирования погоды и построения пути для нахождения безопасного маршрута на карте.

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

1. Сбор и хранение метеоданных (температуре, влажности и атмосферном давлении) на дорожном примитиве;
2. Определение категории опасности передвижения автотранспорта в зоне действия системы прогнозирования метеоусловий;
3. Прорисовка графа дорог в виде карты исследуемого дорожного участка;
4. Возможность выбора начальной и конечной точки пути для автотранспорта;
5. Построение от одного до 3-х оптимальных маршрутов, в зависимости от прогноза погоды.

3. Обзор существующих алгоритмов

С давних времен люди пытались предсказывать погоду, наблюдая закономерности в каких-либо событиях. Прогноз погоды занимал важное место в жизни общества разных народов с появлением первых цивилизаций. Но на тот момент прогноз связывали с видимыми природными явлениями, поведением животных, что выражалось в народных приметах (закат красный — будет ветер, птицы летают низко над водой — к дождю и т. д.). И только изобретением первых метеоприборов в 17 веке положило начало инструментальных наблюдений, формализацией которых занимались преимущественно зарубежные исследователи. Алгоритмами построения пути занимались различные ученые, начиная с середины 20-го века. В настоящее время проблемами навигации и безопасностью транспортных систем занимаются как зарубежные, так и отечественные исследователи

3.1 Обзор методов краткосрочного прогнозоривания погоды

Предсказание погоды по барометру началось ещё в 17 веке, однако описали алгоритм в компании Negretti and Zambra только в 1920 году [4]. Фирма представила погодный калькулятор Zambretti, представляющий собой компактное устройство, состоящее из кругов (дисков), на обратной стороне которых был расписан прогноз (рис. 1).

Круги учитывали направление ветра, атмосферное давление (АД), его динамику изменения и сезон. Алгоритм работы данного калькулятора можно описать следующим образом:

1. Рассчитываются константы по формулам:

   A = Pmax – Pmin, (1)

   k = A / 22, (2)

   где Pmax и Pmin — это, соответственно, максимальное и минимальное АД для исследуемой местности. Для АД от 950 до 1050 гПа принимаются следующие значения:

   А = 100

   k = 4.4546

2. В течение нескольких часов наблюдается тенденция изменения АД;
3. В момент прогноза определяется абсолютное значение АД (Р);
4. Производится корректировка значения Р с учётом ветра (рис. 2);


Рисунок 2 — Корректировка по ветру

5. Полученное значение корректируется по тенденции изменения АД (только для летнего сезона (Апрель-Сентябрь), и если АД изменяется):
   • давление растет: +7;
   • давление падает: -7.
6. Подставляем полученные значения в формулу 3:

   Z = (P – Pmin) / k, (3)

7. Значение Z берется целая часть и выбирается символьный код в зависимости от тенденции:

8. Полученный код расшифровывается по таблице 1 и определяется прогноз:

Таблица 1 — Расшифровка кода по алгоритму Zambretti

A	Отличная, ясно
B	Хорошая, ясно
C	Становление хорошей, ясной погоды
D	Хорошая, но ухудшается
E	Хорошая, возможен ливень
F	Достаточно хорошая, улучшается
G	Достаточно хорошая, возможен ливень
H	Достаточно хорошая, но ожидается ливень
I	Ливень, но улучшается
J	Переменчивая, но улучшается
K	Достаточно хорошая, вероятны ливни
L	Пасмурно, но проясняется
M	Пасмурно, возможно, улучшение
N	Ливни, возможны временные прояснения
O	Ливни, становится менее устойчивой
P	Переменчивая, небольшие дожди
Q	Пасмурная, короткие прояснения
R	Пасмурная, ожидаются дожди
S	Пасмурная, временами дожди
T	Преимущественно, очень пасмурная
U	Временами дожди, ухудшение
V	Временами дожди, очень плохая, пасмурно
W	Дожди, очень часто
X	Дожди, очень плохая, пасмурно
Y	Штормовая, но улучшается
Z	Штормовая, дожди

Позднее Раймонд М. Сайджер более подробно описал алгоритм прогнозирования [5], который дополнительно учитывал облачность при составлении прогноза (рис. 3).

Калькулятор имеет 4 диска:

1. Учитывает направление и изменение ветра (backing — изменяется против часовой стрелки; steady — неизменный; veering — по часовой стрелке);
2. Указывает на АД (в дюймах рт. ст.);
3. Показывает скорость изменения АД (неизменно, быстро/медленно падает/растёт);
4. Учитывает облачность (ясно, слабая облачность, в основном облачно, облачно, дождь).

Выставив по черному треугольнику данные всех 4-х дисков получается цифровой код. Расшифровка описана в специальном справочнике [5].

Рассмотренные алгоритмы не учитывают температуру воздуха. Наблюдая за закономерностями изменения температуры воздуха в течение дня была выведена вероятность появления ночных заморозков. Графически эту зависимость вывел профессор Броунов (рис. 4) [6]:

По вертикальной оси обозначена температура воздуха в 21:00, а по горизонтальной оси разница температур в 13:00 и 21:00. Необходимо лишь определить в какой точке лежит пересечение этих двух параметров. Это можно сделать, описав наклонные прямы математической формулой:

y = ax + b, (4)

где a и b – это параметры, определяющие направление и наклон прямой. Для их определения известны все параметры:

a = (y2 – y1) / (x2 – x1), (5)

b = (y1x2 – x1y2) / (x2 – x1), (6)

Таким образом подставив в формулы 5,6 значения, показанные на графике, получим константы, приведенные в таблице 2.

Таблица 2 — Константные параметры прямых графика

a	b	%
0.375	11	10
0.391	8.7	20
0.382	6.7	40
0.382	4.7	60
0.391	2.7	80
0.4	1.6	100

Теперь, подставляя исходные данные в формулу 4, получаем значение прямой в точке х. Сравнивая это значение со значением температуры в 21:00, можно сделать вывод, в какой области вероятности находится значение.

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

3.2 Обзор алгоритмов построения пути

Дорожная сеть, по которой необходимо строить маршрут представляется в виде взвешенного графа (рис. 5), который хранится в матричном виде. Вершины графа представляют собой сегменты дорожной сети, а соединения показывают связи между этими сегментами и стоимость перехода из одного в другой. Стоимость перехода определяется геометрической длиной сегмента и средней скоростью движения объекта вдоль сегмента [7]. Таким образом взвешенный граф дорожной сети задаётся в виде квадратной матрицы, размер которой определяется количеством вершин графа.

Наиболее популярные алгоритмы для поиска пути во взвешенном графе [8]:

1. Дейкстры;
2. Беллмана-Форда;
3. А*;
4. Ли (волновой алгоритм).

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

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

Алгоритм А* по сути является расширением алгоритма Дейкстры, но достигает более высокой производительности за счет введения в работу алгоритма эвристической функции. Типичная формула эвристики выражается в виде [9]:

f(n)=g(n)+h(n), (1)

где f(n) — значение оценки, назначенной узлу n,

g(n) — наименьшая стоимость прибытия в узел n из точки старта,

h(n) — эвристическое приближение стоимости пути к цели от узла n.

Данный алгоритм пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдет минимальный.

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

Google скрывает алгоритм, который использует в качестве основного для работы в своём сервисе. В отличие от него, Яндекс в открытом доступе не только указывает, что использует алгоритм Дейкстры, но и описывает его работу [10]. Среди рассмотренных алгоритмов одним из самых популярных для навигационных систем является алгоритм Дейкстры (рис. 6).

На первом шаге для начальной вершины определяется вес 0 (все остальные бесконечность). После чего проверяются все возможные пути из начальной вершины. В данном случае только в вершину B. Её вес устанавливается равным сумме значения предыдущей вершины и веса перехода. Затем то же самое для вершины B. В данном случае 3 возможных пути (C, I, E). Выбирается наименьший вес перехода, то есть вершина Е. Действия повторяются циклично. Таким образом каждый раз выбирается вершина перехода, куда дешевле всего добраться из исходной точки, даже если эта вершина находится в обратной стороне пути. Поэтому после вершины Е, сразу осуществляется выбор вершины С, а после F. Если на определённом шаге в уже посещённую вершину обнаруживается путь дешевле, то её вес изменяется. В примере в вершину К был найден путь со стоимостью перехода = 14. Но алгоритм не выбрал её, та как были вершины дешевле. В результате чего был найден путь со стоимостью 11.

4. Разработка алгоритма функционирования системы

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

Устройство сбора и передачи метеоусловий состоит из:

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

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

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

Справа на рисунке приведен пример наложения известных погодных параметров. Каждая клетка представляет собой зону отдельного устройства сбора метеоданных. Более яркие круги в клетке показывают неблагоприятные погодные условия. Прозрачные круги обозначают прогнозируемые неблагоприятные условия. Отсутствие кругов символизирует хорошие погодные условия, которые сохраняться в ближайшее время. Таким образом стандартный алгоритм, используемый в картах выберет путь под номером 1, так как он быстрее всего. Но учитывая, что по пути 1 в пути будут плохие погодные условия, лучше выбрать 2 или 3. При этом нужно учитывать, через какое время транспортное средство преодолеет зону возможных неблагоприятных погодных условий. В случае, когда путь займёт более чем несколько часов, рационально сразу выбрать путь под номером 3.

Выводы

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

Список источников

1. Кравченко М.К. Разработка структуры системы мониторинга и анализа изменений метеоусловий / М.К. Кравченко, Д.В. Николаенко // 69–я Международная студенческая научно–техническая конференция, Астрахань, 15–19 апреля 2019 года [Электронный ресурс]: материалы / Астрахан. гос. техн. ун–т. — Астрахань: Изд–во АГТУ, 2019.
2. Николаева Р.В., Газизова З.С., Загидулина А.Д. Формирование и развитие интеллектуальных транспортных систем // Техника и технология транспорта. Выпуск № 1(1) – Казань, КГАСУ, 2016. С. 8-14.
3. Кривошеев С.В. Исследование эффективности параллельных архитектур вычислительных систем для расчета параметров движения транспортного средства // Научные труды Донецкого национального технического университета. Выпуск № 1(10)-2(11). Серия «Проблемы моделирования и автоматизации проектирования». – Донецк, ДонНТУ, 2012. С. 207-214.
4. Монатко Д. Погодный калькулятор Zambretti [Электронный ресурс] // Monatkodenis: [сайт] 2016. URL: http://monatkodenis...
5. Raymond M. Sager. A scientific instrument for accurate prediction of the weather The Sager weathercaster // Published 1969 by Distributed by October House in New York. URL: https://openlibrary...
6. Гринченко Н.Н., Потапова В.Ю., Тарасов А.С. Алгоритмы прогнозирования погодных условий в системах сбора и обработки метеорологических данных // Известия Тульского государственного университета. Технические науки, 2018, Вып. 2. — С. 113–119 // URL: https://cyberleninka.ru/article...
7. Дорогов А.Ю., Лесных В.Ю., Раков И.В., Титов Г.С. Алгоритмы оптимального движения мобильных объектов по пересеченной местности и транспортной сети // Санкт-Петербургский государственный электротехнический университет, 2008, № 3. — С. 419–427 // URL: http://dspace.nbuv.gov...
8. Изотова Т.Ю., Обзор алгоритмов поиска кратчайшего пути в графе // Новые информационные технологии в автоматизированных системах. 2016. С. 341–344.
9. Bryan Stout. The Basics of A* for Path Planning. In Game Programming Gems. // Charles River Media, 2000. PP. 254–263.
10. Маршрутизация [электронный источник] // ООО «Яндекс»: [сайт]. 1997-2019. URL: https://yandex.ru...