Як математика бореться з дорожніми заторами

Напередодні зими в великих містах особливо гостро постає питання про те, як боротися з заторами на дорогах. Крім звичних всім адміністративних заходів (штрафів та плати за в'їзд в центр міста і парковку) ситуацію можуть полегшити автоматизовані способи організації руху транспорту. Портал Лента.ру з'ясувала, як борються з заторами «розумні» світлофори, і вивчила математичні принципи, за допомогою яких інтелектуальні транспортні системи намагаються «вгадати» поведінку водіїв.
 
 
 
Практично одночасно з появою на автомобільних дорогах перших світлофорів в кінці XIX століття постало завдання вибудувати управління сигналами таким чином, щоб усім учасникам руху (і водіям, і пішоходам) не доводилося чекати своєї черги на перехресті занадто довго. Спочатку світлофори знаходилися під ручним контролем - поліцейський перемикав сигнали вручну або за допомогою спеціального пульту управління.
 
Розвиток електроніки дозволив замінити живих людей таймерами і реле: тепер вони перемикали фази світлофорів - поєднання забороняючих сигналів для одних напрямків і дозволяючих - для інших. Для кожного світлофора існував свій розклад перемикань (тобто своя тривалість кожної фази), який з часом навчилися коригувати для особливих випадків - в години пік або вночі.
З появою інформаційних мереж світлофори почали підключати до єдиних центрів управління рухом, щоб в екстреній ситуації для зміни сигналу на конкретному перехресті не доводилося відправляти туди співробітника поліції. А для того щоб зрозуміти, де саме виник затор, на вулицях стали встановлювати датчики присутності автомобілів - як правило, для цього в дорожнє полотно укладали індукційну петлю, яка фіксувала зміну електромагнітного поля при проїзді машини.
 
Таким чином, приблизно до другої половини ХХ століття відповідальні служби навчилися оперативно отримувати відомості про дорожню ситуацію і реагувати на них зміною сигналів світлофорів. Оскільки до цього моменту вже почався розвиток комп'ютерної техніки, перед програмістами і математиками поставили нове завдання: змусити складну систему самостійно адаптуватися до умов, що змінюються, а не чекати, поки людина прийме потрібне рішення і подасть їй відповідний сигнал. В даний час існують чотири основні методи побудови таких систем (три з них навіть реалізовані на практиці) - про них і піде мова.
 
Безперервний цикл
 
Однією з перших систем, що реагують на транспортну ситуацію, стала запущена в 1973 році у Великобританії SCOOT (Split, Cycle and Offset Optimization Technique - техніка оптимізації фаз, циклу і зміщення). Вона ж відноситься і до числа найбільш поширених: її використовують понад 200 міст по всьому світу.  У назві системи зашифровані три основних параметри її алгоритму:
 
 
Кожен світлофор в системі SCOOT має «свої» датчики присутності автомобілів (один або кілька - для різних смуг руху і на різній відстані), встановлені «вище за течією». Як правило, мережа вулиць ділиться на ланки - від перехрестя до перехрестя. Починається кожна ланка датчиком, а закінчується - реагуючим на його показання світлофором.
 
Для прийняття рішення про зміну головного параметру - довжини циклу - комп'ютер з програмою SCOOT обчислює так звану ступінь насичення всіх фаз світлофора. Цей показник представлений як відсоток використовуваного «зеленого» сигналу: алгоритм оцінює, скільки ще машин встигли б проїхати перехрестя, «втиснувшись» в проміжки між автомобілями, які фіксує датчик. Завдання SCOOT в тому, щоб для самої «завантаженої» фази насиченість становила не більше 90 відсотків.
 
Крім цього, один раз протягом циклу програма розраховує коефіцієнт ефективності за сумою вимушених зупинок і часу очікування автомобілів. Залежно від значення коефіцієнта SCOOT приймає рішення про те, щоб подовжити або вкоротити на 4 секунди якусь фазу. Перед початком нової фази додатково узгоджується зсув щодо інших світлофорів - також в межах чотирьох секунд.
 
Схожий алгоритм застосували творці австралійської SCATS (Sydney Co-ordinated Traffic Control System - система координованого управління рухом Сіднея), яка з кінця 1970-х років з'явилася в 141 місті по всьому світу. Спираючись на аналогічні методики розрахунку «насичення» світлофорних фаз, вони розробили алгоритм зі складною ієрархічною структурою.
 
 
Перехрестя в SCATS об'єднані в системи і підсистеми за географічною ознакою (наприклад, по районам або розташуванню на магістралях). Ці системи і підсистеми підпорядковуються регіональному комп'ютеру, а вже він, в свою чергу, передає інформацію в центр управління рухом міста. Світлофори «на місцях» можуть самостійно змінювати тільки довжину циклу, а розклад фаз і зсувів після кожного циклу вибираються (зі стандартного набору) на регіональному рівні.
 
Бюро прогнозів
 
На початку 1990-х років американські дослідники з Арізони почали розробляти  нову систему адаптивного управління світлофорами. Вона принципово відрізнялася від попередниць тим, що оцінка ефективності перемикання фаз обмежувалася одним разом за цикл. В результаті з'явилася RHODES (Real-time Hierarchical Optimizing Distributed Effective System - розподілена ефективна система для оптимізації в реальному часі), яку використовують зараз в окремих містах США.
 
Як випливає з назви, RHODES оцінює дорожню ситуацію на декількох рівнях (перехрестя, дорожня мережа, поширені маршрути) і сама конструює потрібні цикли для світлофорів. Рішення система приймає, аналізуючи не тільки інформацію від датчиків присутності автомобілів, але і накопичену історію дорожнього руху на контрольованих вулицях (ланках).
 
На основі цих даних система робить прогноз розвитку дорожньої ситуації. Ключову роль в прогнозі грає алгоритм оцінки ймовірності повороту автомобіля на кожному конкретному перехресті - так обчислюється можливе завантаження сусідніх перехресть. У якості відправної точки RHODES бере історичний розподіл ймовірностей повороту, після чого уточнює цей розподіл даними, отриманими за останні п'ять хвилин.
 
 
Для уточнення прогнозу в RHODES використовують формулу Байеса - вона дозволяє обчислити вірогідність однієї події (історично найбільш популярного повороту), яке статистично взаємопов'язане з іншими подіями (тільки що виконаними поворотами). Такий прогноз щомиті оновлюється для всієї системи, а потім доповнюється інформацією про передбачувані пробки на кожному перехресті.
 
Варто зазначити, що в системі передбачений спеціальний механізм обробки так званих черг автомобілів - колон, які рухаються з приблизно однаковою швидкістю. При появі таких черг цикли світлофорів коригуються, щоб по можливості пропустити ці автомобілі через все перехрестя без зупинок, на «зеленій хвилі».
 
Окремий випадок глобальних прогнозів дорожнього руху використовує система OPAC (Optimized Policies for Adaptive Control - оптимізована політика адаптивного управління). Цей алгоритм покладається на додаткову інформацію від датчиків, які знаходяться на значній відстані від перехрестя - вони передають дані про наближення машин вже після прийняття рішення про зміну циклу світлофора. Прогноз системи в результаті має два горизонти: довгостроковий, обмежений тільки обчислювальними потужностями, і короткостроковий - для відрізка часу, коли точно відомий приплив нових машин. Ступінь відповідності короткострокового прогнозу і реальної ситуації використовується для коригування подальших розрахунків.
 
«Жадібні» перехрестя
 
Всі описані вище системи мають дві характерні ознаки, сформовані багаторічним досвідом організації руху: вони намагаються поліпшити ситуацію для всіх контрольованих перехресть і регулюють роботу світлофорів не безпосередньо, а через зміну циклів. У 2008 році в США вперше запустили систему InSync, позбавлену обох цих обмежень. У InSync акцент робиться на так званий «жадібний алгоритм» - коли передбачається, що знайдені оптимальні локальні рішення (на окремих перехрестях) дозволять прийти до оптимального глобального вирішення - зменшення заторів у всьому місті.
 
 
На кожному перехресті InSync точно обчислює, скільки часу стоять машини чекають «зеленого» сигналу - це робиться за допомогою камер і технології розпізнавання образів. Самі світлофори в системі керовані не циклами і розкладами, а моделями автоматів - програмами, в яких прописані умови зміни сигналів. Наприклад, алгоритм може взагалі не включити «зелений» для направлення, на якому немає жодної машини.
 
«Мережевий» режим система передбачає лише для тих випадків, коли необхідно пропустити вже згадувану чергу автомобілів. В такому випадку тривалість фаз окремих світлофорів коригується, щоб сформувати «зелену хвилю». Кількість запущаних «хвиль» регулюється параметрами системи в залежності від часу доби і побажань оператора.
 
Гра в «машинки»
 
Найоригінальніший підхід до регулювання руху в містах запропонували в 2011 році в канадському Торонто - MARLIN-ATSC (Multiagent Reinforcement Learning for Integrated Network of Adaptive Traffic Signal Controllers - навчання з підкріпленням агентів інтегрованої мережі адаптивного управління світлофорами). Автори розробки вирішили піти від централізованої системи, замінивши її світлофорами-агентами - пристроями, які наділені штучним інтелектом і спілкуються між собою для вибору схеми руху.
 
У програмі, яку завантажують в кожен світлофор, описаний Марковський процес прийняття рішень, а точніше, його окремий випадок - Q-навчання. Цей принцип машинного навчання передбачає спілкування агента (світлофора) з системою (дорожнього руху). Кожна дія світлофора якимось чином впливає на дорожню ситуацію, про зміну якої можна судити за інформацією, одержуваної з датчиків. Отримавши цю інформацію (так звану винагороду), світлофор-агент обчислює функцію своєї корисності Q і надалі спирається на набутий досвід.
 
 
Для координації агентів між собою використана теорія ігор, а саме - стохастична гра. Під час гри агенти перебирають варіанти своїх рішень (залишити або змінити фазу світлофора) і отримують винагороди (дані про простій автомобілів), засновані на загальних рішеннях. Кожне рішення світлофора-агента прив'язане до набору показників поточного стану: яка включена фаза, як давно включена ця фаза, яка пробка зібралася по кожному з напрямків перехрестя.
 
«Гравці» повинні виробити такі моделі поведінки, які приведуть до найкращого загального результату - так званої рівноваги Неша. Отримані таблиці «корисності» для пар «стан-рішення» і стають тією політикою, якою в подальшому буде керуватися кожен світлофор. «Навчаються» світлофори, природно, на комп'ютерній моделі, а не в реальних дорожніх умовах.
 
* * *
 
Безпосередньо порівняти ефективність всіх перерахованих систем управління світлофорами неможливо - для цього довелося б по черзі випробувати кожну з них в одному і тому ж місті (на одних і тих же перехрестях). Тому різні алгоритми порівнюють з того, наскільки вони поліпшили транспортну ситуацію.
 
За даними проведеного в 2010 році дослідження (.pdf), «жадібний» алгоритм InSync в кілька разів краще класичних механізмів коригування світлофорних циклів (SCATS) - в години пік він знижує простої автомобілів на 60 відсотків (проти 15 відсотків у SCATS). Штучний інтелект MARLIN-ATSC поки проходив випробування лише на моделі з 60 перехресть Торонто, де показав зниження простою на 41 відсоток. За підсумками обмежених польових випробувань (.pdf) алгоритму прогнозу RHODES експерти встановили тільки те, що вона щонайменше не гірше існуючих систем з фіксованим розкладом циклів.
 
 

 

Додати новий коментар

Ви сповіщаєте про орфографічну помилку в наступному тексті:
Щоб надіслати повідомлення, натисніть кнопку нижче.