А задумывались ли вы, почему вооон тот водитель, который объехал вас шашечками по соседней полосе, не прав? Начиная с 1950-х годов инженеры и математики пытались понять, почему так происходит, и даже кое-что посчитали. Только начиналось все не с нейросетей и не с анализа миллионов записей с GPS.
Предлагаю посмотреть на этот вопрос со стороны истории науки: с чего начали в описании автомобильного потока, как догадались, что пробки возникают и без единой аварии на горизонте, и когда в математическую модель наконец добавили «личность» водителя. Пройдемся по результатам вычислений, к которым удалось прийти задолго до появления машинного обучения.
Дисклеймер
Этот материал не претендует на исчерпывающее описание математических моделей управления движением, а дает теоретический экскурс в историю вопроса.
Почему считать пробки начали раньше, чем ставить светофоры
После Второй мировой войны автомобилизация резко ускоряется. Города растут, автомагистрали появляются одна за другой, но вместе с ними растет и количество машин на дорогах. Увеличиваются скорости, а с ними и травматизм.
Довольно быстро становится понятно, что строительство не успевает за распространением личного транспорта. Чтобы не проиграть в этой гонке, инженерам нужно было учиться заранее — еще на этапе проекта — оценивать пропускную способность и безопасность дорог. Так возникла задача все это посчитать.
Первые реалистичные модели родились в 1950-х. За следующие десятилетия появилось несколько принципиально разных подходов к моделированию транспортного потока. Развивались они не последовательно: разные научные группы отталкивались от собственных представлений о том, что именно нужно моделировать, и вели параллельные линии исследований. Но для нас удобно выделить три взгляда на задачу:
дорожный поток как непрерывная среда — что-то вроде жидкости, с характеристиками, у которых есть аналоги в физике;
дискретные модели, где каждая машина реагирует на расстояние и скорость соседей, а результат складывается из суммы этих реакций;
модели, куда встроена психология водителя — с закономерностями, которые к тому моменту уже успели заметить.
Дальше, разумеется, в эту сферу пришел ИИ. Но пока предлагаю сосредоточиться на ранних подходах.
Макроскопическая модель
Первая идея лежала на поверхности: представить поток машин как жидкость в трубе (на одной полосе дороги). Правда, придется закрыть глаза на одну деталь: плотность автомобильного потока, в отличие от жидкости, может меняться в куда более широком диапазоне.
В 1955 году Майкл Лайтхилл и Джеральд Уитэм опубликовали работу «On Kinematic Waves II. A Theory of Traffic Flow on Long Crowded Roads». Независимо от них несколько месяцев спустя ту же идею в статье «Shock Waves on the Highway» высказал Пол Ричардс, поэтому модель теперь носит тройную фамилию: Lighthill–Whitham–Richards, или LWR.
Ученые применили к потоку теорию кинематических волн. В их интерпретации у транспортного потока три характеристики:
плотность (ρ) — количество машин на километр;
скорость (v) — средняя скорость движения;
интенсивность (q) — количество машин, проезжающих через «сечение» дороги за час, то есть плотность, умноженная на скорость.
Эти характеристики связаны двумя базовыми правилами:
количество машин не меняется — на дороге без ответвлений они не исчезают и не появляются внезапно (сюда встраивается уравнение неразрывности из физики);
скорость зависит от плотности — чем плотнее движение, тем ниже средняя скорость. Однозначной зависимости между этими величинами модель не задает, поэтому чаще всего берут простую линейную функцию.
В итоге получается уравнение, описывающее изменение потока во времени, и фундаментальный график зависимости интенсивности от плотности.
Модель далека от идеала, но даже она привела к выводам, живое воплощение которых вы наверняка видели на дороге.
Ударные волны. Поток, который ехал довольно быстро, натыкается на хвост пробки и начинает тормозить. Между свободным движением и затором возникает резкая граница, которая распространяется назад по дороге. Уже простая макроскопическая модель позволяла рассчитать скорость такой «волны».
Волны разрежения — обратная ситуация. На светофоре загорается зеленый, машины впереди разгоняются, следом трогаются остальные, но плотность потока падает не сразу, а постепенно. Такая волна тоже идет назад по потоку, и ее скорость точно так же можно вычислить.
Макроскопическая модель хорошо описывает коллективную динамику потока, но предполагает идеальную реакцию автомобилей на ситуацию и ничего не знает о человеческом факторе. В реальности пробки нередко возникают из-за поведения одной машины — резкого маневра или заторможенного стиля вождения, — и здесь к LWR накапливается ряд вопросов. Но не стоит забывать, что модель появилась в 1950-х, когда на столе у дорожного инженера еще не было компьютера: все считали в общем виде, решая дифференциальные уравнения вручную. К 1960-м появилась дискретная версия модели, которую уже можно было обсчитывать на ЭВМ размером с физкультурный зал.
Одно из главных достоинств модели — скорость расчета: несколько уравнений на всю дорогу, тогда как в следующих моделях сложность растет с каждой добавленной машиной. В чистом виде LWR сегодня уже нигде не применяется, как минимум потому, что разрабатывалась она для бесконечно длинной одномерной дороги без перекрестков, по которой должны кататься те самые сферические кони в вакууме. Но она легла в основу более современных подходов и до сих пор встречается — например, в дискретной модификации в коммерческих симуляторах дорожного движения вроде VISUM от PTV Group.
Микроскопическая модель
Следующий уровень развития моделирования — введение связи между машинами, когда каждый автомобиль видит соседей и принимает какие-то решения на основе этой информации.
Модель Гиппса
В 1981 году в статье «A Behavioural Car-Following Model for Computer Simulation» Питер Гиппс предложил описывать реакцию автомобиля через явно заданные ограничения.
В модель заложено новое правило: водитель выбирает такую скорость, чтобы успеть безопасно затормозить, если человек впереди резко нажмет на тормоз до полной остановки. Условие добавило несколько переменных: желаемую скорость в голове водителя, расстояние до предыдущей машины и ее скорость, максимальное ускорение и комфортное торможение конкретного автомобиля, а также время реакции водителя.
Если в макроскопической модели пробка была свойством потока в целом, то на микроскопическом уровне становится виден вклад конкретного автомобиля — кто начудил и чем это обернулось для остальных.
По сути, модель Гиппса выявила внутреннюю нестабильность потока. Один водитель слегка притормаживает, следующий за ним замечает это и тормозит чуть сильнее, а через несколько машин небольшое колебание скорости превращается в затор — так называемую фантомную пробку. Гиппс ее, конечно, не изобрел, он просто предложил математический аппарат, благодаря которому это явление больше не нужно задавать в уравнении как внешнее условие: оно возникает само.
Модель также показала, насколько важно учитывать время реакции водителя (его можно задать параметром). Чем оно больше из-за усталости, отвлечения на телефон или чего-то еще, тем шире волна торможения и тем быстрее дорога в симуляции встает намертво.
Изначально Гиппс описывал движение только по одной полосе. Но когда число полос увеличили и добавили препятствия, модель дала вполне внятное объяснение «эффекту бабочки» при перестроении: желание одного водителя перейти в более быстрый ряд заставляет притормозить машину сзади в новой полосе. Торможение передается назад по цепочке и способно полностью заблокировать полосу в километре позади автора маневра. Любопытно, что этот вывод получается еще до того, как в модель вводится какой-либо «стиль вождения».
Модель Гиппса позволила виртуально тестировать длину полос разгона и торможения на автомагистралях — рассчитать, какой выезд на трассу нужен, чтобы вливающийся поток успевал набрать скорость и не заставлял основной поток тормозить экстренно.
Симуляторы, использующие под капотом Гиппса и дополненные сетью дорог, показали причину замыканий перекрестков: хвост пробки в одном направлении блокирует предыдущие перекрестки. Возникает замкнутая петля (gridlock), когда никто не может двинуться, потому что все ждут друг друга.
Модель Гиппса скоро отметит полвека, но до сих пор используется в софте для моделирования транспортных потоков. Например, в симуляторе Aimsun Next от Siemens, который применяют в крупнейших мегаполисах при проектировании развязок. Она же задает «безопасное человеческое поведение» при моделировании потока для автопилотов: параметры модели легко считаются по данным с GPS-трекеров реальных автомобилей.
Intelligent Driver Model (IDM)
Более сложную микроскопическую модель в 2000 году разработали Мартин Трайбер, Ансгар Хеннеке и Дирк Хельбинг. Идеи Гиппса докрутили, добавив плавности и перейдя от дискретного моделирования к непрерывному. В основе Гиппса лежали дискретные разностные уравнения, IDM же построена на дифференциальных.
Предположим, все водители стараются ехать максимально стабильно — держат безопасную дистанцию, не разгоняются рывками. Казалось бы, поток должен двигаться стабильно? А вот и нет! IDM показала, что при достаточно высокой плотности потока малейшее возмущение — один автомобиль чуть изменил скорость — усиливается и расходится волнами. Получаем пробку, которая объясняется не одним плохим водителем, а динамикой всей системы.
Еще одно наблюдение — падение скорости потока на сужении дороги. Из-за суматохи, резких торможений и небольшой задержки в реакции водителей пропускная способность оставшихся полос снижается дополнительно. Разные оценки, в зависимости от конфигурации препятствия, дают снижение на 5–20%.
Небольшая коллекция видео-симуляций и графиков IDM доступна на сайте университета Франкфурта.
Модель с оттенком психологии
Водитель не измеряет расстояние до автомобиля впереди с бесконечной точностью и не вычисляет каждую секунду относительную скорость до сантиметра в секунду. И он вовсе не обязан реагировать на каждое микроскопическое изменение ситуации. Все модели выше описывали движение автомобилей без этой поправки. Но попытки добавить психологию тоже были — они развивались параллельно со строго математическим подходом.
В 1974 году Райнер Видеманн защитил в Университете Карлсруэ диссертацию, посвященную моделированию транспортного потока. Позже предложенная им модель получила название Wiedemann — в противовес более поздней версии для магистралей, Wiedemann 99, появившейся в 1999 году.
В модель заложили идею, что водитель меняет стратегию не при любом изменении расстояния и скорости впереди идущей машины, а только когда пересекает определенную границу восприятия. Учли и то, что есть ситуации, в которых человек вообще не реагирует на стимул: если изменение внешней ситуации слишком незначительно, водитель продолжает двигаться так же, как раньше.
Забавно, что модель Видеманна пришла к той же нестабильности потока, что и IDM, только с другой стороны — и чуть раньше, еще на этапе перфокарт и языка Алгол.
Модель до сих пор используется в некоторых симуляторах, например в PTV Vissim. Исходная идея сохранилась, но за десятилетия промышленная реализация была откалибрована и подстроена под реальные данные и современные автомобили.
Дальше в эту историю пришло машинное обучение: исследователи получили возможность искать закономерности прямо в данных о реальном движении, а не выводить их заранее из уравнений. Но это уже совсем другая история.
