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

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

Кафедра комп'ютерної інженерії

Спеціальність Програмне забезпечення засобів обчислювальної техніки

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

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

Резюме Біографія Реферат

Реферат за темою випускної роботи

Зміст

• Вступ
• 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 столітті, однак описано алгоритм тільки в 1920 році в компанії Negretti and Zambra [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...