Математика
Википедия
Математика
Математикой называется наука о структурах, отношениях и порядке, которая исторически сложилась на основе совершаемых операций подсчета, описания и измерен... читать далее »
Статьи по Математике
06.12.2013 18:29
Что и требовалось разрулить. Математика.
Как математика борется с дорожными заторами
В преддверии зимы в крупных городах особенно остро встает вопрос о том, как бороться с пробками на дорогах. Помимо привычных всем административных мер (штрафов и платы за въезд в центр города и парковку) ситуацию могут облегчить автоматизированные способы организации движения транспорта. «Лента.ру» выяснила, как борются с заторами «умные» светофоры, и изучила математические принципы, при помощи которых интеллектуальные транспортные системы пытаются «угадать» поведение водителей.
Практически одновременно с появлением на автомобильных дорогах первых светофоров в конце XIX века возникла задача выстроить управление сигналами таким образом, чтобы всем участникам движения (и водителям, и пешеходам) не приходилось ждать своей очереди на перекрестке слишком долго. Изначально светофоры находились под ручным контролем — полицейский переключал сигналы вручную или при помощи специального пульта управления.
Развитие электроники позволило заменить живых людей таймерами и реле: теперь они переключали фазы светофоров — сочетания запрещающих сигналов для одних направлений и разрешающих — для других. Для каждого светофора существовало свое расписание переключений (то есть своя продолжительность каждой фазы), которое со временем научились корректировать для особых случаев — в часы пик или ночью.
Волоколамское шоссе, Москва
С появлением информационных сетей светофоры начали подключать к единым центрам управления движением, чтобы в экстренной ситуации для изменения сигнала на конкретном перекрестке не приходилось отправлять туда сотрудника полиции. А для того чтобы понять, где именно возник затор, на улицах стали устанавливать датчики присутствия автомобилей — как правило, для этого в дорожное полотно укладывали индукционную петлю, которая фиксировала изменение электромагнитного поля при проезде машины.
Таким образом, примерно ко второй половине ХХ века ответственные службы научились оперативно получать сведения о дорожной обстановке и реагировать на них изменением сигналов светофоров. Поскольку к этому моменту уже началось развитие компьютерной техники, перед программистами и математиками поставили новую задачу: заставить сложную систему самостоятельно адаптироваться к изменяющимся условиям, а не ждать, пока человек примет нужное решение и подаст ей соответствующий сигнал. В настоящее время существуют четыре основных метода построения таких систем (три из них даже реализованы на практике) — о них и пойдет речь.
Непрерывный цикл
Одной из первых систем, реагирующих на транспортную обстановку, стала запущенная в 1973 году в Великобритании SCOOT (Split, Cycle and Offset Optimization Technique — техника оптимизации фаз, цикла и смещения). Она же относится и к числу самых распространенных: ее используют более 200 городов по всему миру (.pdf). В названии системы зашифрованы три основных параметра ее алгоритма:
Каждый светофор в системе SCOOT имеет «свои» датчики присутствия автомобилей (один или несколько — для разных полос движения и на разном удалении), установленные «выше по течению». Как правило, сеть улиц делится на звенья — от перекрестка до перекрестка. Начинается каждое звено датчиком, а заканчивается — реагирующим на его показания светофором.
Для принятия решения об изменении главного параметра — длины цикла — компьютер с программой SCOOT вычисляет так называемую степень насыщения всех фаз светофора. Этот показатель представлен как процент используемого «зеленого» сигнала: алгоритм оценивает, сколько еще машин успели бы проехать перекресток, «втиснувшись» в промежутки между автомобилями, которые фиксирует датчик. Задача SCOOT в том, чтобы для самой «загруженной» фазы насыщенность составляла не более 90 процентов.
Помимо этого, один раз в течение цикла программа рассчитывает коэффициент эффективности по сумме вынужденных остановок и времени ожидания автомобилей. В зависимости от значения коэффициента SCOOT принимает решение о том, чтобы удлинить или укоротить на 4 секунды какую-то фазу. Перед началом новой фазы дополнительно согласуется смещение относительно других светофоров — также в пределах четырех секунд.
Похожий алгоритм применили создатели австралийской SCATS (Sydney Co-ordinated Traffic Control System — система координированного управления движением Сиднея), которая с конца 1970-х годов появилась в 141 городе по всему миру. Опираясь на аналогичные методики расчета «насыщения» светофорных фаз, они разработали алгоритм со сложной иерархической структурой.
Центр управления SCOOT
Перекрестки в SCATS объединены в системы и подсистемы по географическому признаку (например, по районам или расположению на магистралях). Эти системы и подсистемы подчиняются региональному компьютеру, а уже он, в свою очередь, передает информацию в центр управления движением города. Светофоры «на местах» могут самостоятельно менять только длину цикла, а расписания фаз и смещений после каждого цикла выбираются (из стандартного набора) на региональном уровне.
Бюро прогнозов
В начале 1990-х годов американские исследователи из Аризоны начали разрабатывать (.pdf) новую систему адаптивного управления светофорами. Она принципиально отличалась от предшественниц тем, что оценка эффективности переключения фаз не ограничивалась одним разом за цикл. В результате появилась RHODES (Real-time Hierarchical Optimizing Distributed Effective System — распределенная эффективная система для оптимизации в реальном времени), которую используют сейчас в отдельных городах США.
Как следует из названия, RHODES оценивает (.pdf) дорожную обстановку на нескольких уровнях (перекресток, дорожная сеть, распространенные маршруты) и сама конструирует нужные циклы для светофоров. Решения система принимает, анализируя не только информацию от датчиков присутствия автомобилей, но и накопленную историю дорожного движения на контролируемых улицах (звеньях).
На основе этих данных система составляет прогноз развития дорожной ситуации. Ключевую роль в прогнозе играет алгоритм оценки вероятности поворота автомобиля на каждом конкретном перекрестке — так вычисляется возможная загрузка соседних перекрестков. В качестве отправной точки RHODES берет историческое распределение вероятностей поворота, после чего уточняет это распределение данными, полученными за последние пять минут.
Для уточнения прогноза в RHODES используют формулу Байеса — она позволяет вычислить вероятность одного события (исторически наиболее популярного поворота), которое статистически взаимосвязано с другими событиями (только что выполненными поворотами). Такой прогноз ежесекундно обновляется для всей системы, а затем дополняется информацией о предполагаемых пробках на каждом перекрестке.
Стоит отметить, что в системе предусмотрен специальный механизм обработки так называемых очередей автомобилей — колонн, которые движутся с примерно одинаковой скоростью. При появлении таких очередей циклы светофоров корректируются, чтобы по возможности пропустить эти автомобили через все перекрестки без остановок, на «зеленой волне».
Частный случай глобальных прогнозов дорожного движения использует система OPAC (Optimized Policies for Adaptive Control — оптимизированная политика адаптивного управления). Этот алгоритм полагается на дополнительную информацию от датчиков, которые находятся на значительном удалении от перекрестка — они передают данные о приближающихся машинах уже после принятия решения об изменении цикла светофора. Прогноз системы в результате имеет два горизонта: долгосрочный, ограниченный только вычислительными мощностями, и краткосрочный — для отрезка времени, когда точно известен приток новых машин. Степень соответствия краткосрочного прогноза и реальной обстановки используется для корректировки дальнейших расчетов.
«Жадные» перекрестки
Все описанные выше системы имеют два характерных признака, сформированные многолетним опытом организации движения: они пытаются улучшить обстановку для всех контролируемых перекрестков и регулируют работу светофоров не напрямую, а через изменение циклов. В 2008 году в США впервые запустили систему InSync, лишенную обоих этих ограничений. В 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 эксперты установили только то, что она по меньшей мере не хуже существующих систем с фиксированным расписанием циклов.
Российские водители могут испытать на себе все прелести адаптивных систем управления дорожным движением лишь в очень ограниченном формате. В Москве и Казани используется итальянская система UTOPIA (Urban Traffic Control System Architecture — архитектура системы управления городским дорожным движением) — она сочетает в себе механизмы прогнозирования и создания преимуществ для общественного и специального транспорта. Однако даже в Москве эта система пока внедрена всего лишь на 72 перекрестках со светофорами из более чем двух тысяч.