Как моделировали дорожное движение до ИИ

А задумывались ли вы, почему вооон тот водитель, который объехал вас шашечками по соседней полосе, не прав? Начиная с 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. Исходная идея сохранилась, но за десятилетия промышленная реализация была откалибрована и подстроена под реальные данные и современные автомобили. 

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