Как создавали модели дорожного движения до появления искусственного интеллекта

Задумывались ли вы, почему тот самый лихач, который стремительно маневрирует между рядами в соседней полосе, поступает некорректно? Инженеры и математики пытались разгадать эту загадку еще с 1950-х годов и даже преуспели в расчетах. Правда, зарождалась эта дисциплина задолго до появления нейронных сетей и гигабайтов GPS-треков.

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

Дисклеймер

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

Почему пробки стали рассчитывать раньше, чем устанавливать светофоры 

В послевоенные годы темпы автомобилизации резко возросли. Города расширялись, сеть автомагистралей стремительно увеличивалась, но пропорционально рос и уровень аварийности на дорогах. Скорости повышались, влекуя за собой печальную статистику ДТП.

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

Первые жизнеспособные модели появились в 1950-х. В последующие десятилетия сформировалось несколько кардинально различающихся подходов к симуляции транспортного потока. Они развивались нелинейно: различные научные школы опирались на собственные гипотезы о том, что именно подлежит моделированию, и двигались параллельными курсами. Для удобства можно выделить три основных ракурса на эту задачу: 

• транспортный поток как сплошная среда, напоминающая жидкость, с физическими характеристиками и аналогами;

• дискретные системы, где каждый автомобиль подстраивается под скорость и дистанцию соседей, формируя общий результат из суммы локальных реакций;

• модели с интеграцией психологии водителя и уже подмеченных к тому времени поведенческих закономерностей.

Разумеется, со временем сюда органично интегрировался и искусственный интеллект, однако сперва стоит разобрать фундамент ранних разработок.

Макроскопическая модель

Первая концепция лежала на поверхности: интерпретировать поток машин как поток жидкости по трубе (в рамках одной полосы). Правда, приходилось пренебрегать одной особенностью — плотность автомобильной массы в отличие от жидкости способна колебаться в гораздо более широких пределах.

В 1955 году Майкл Лайтхилл и Джеральд Уитэм опубликовали труд «On Kinematic Waves II. A Theory of Traffic Flow on Long Crowded Roads». Спустя несколько месяцев аналогичную мысль независимо сформулировал Пол Ричардс в статье «Shock Waves on the Highway», благодаря чему модель получила тройное название LWR (Lighthill–Whitham–Richards).

Ученые применили к трафику теорию кинематических волн. С их точки зрения, движение характеризуется тремя ключевыми параметрами:

• плотность (ρ) — концентрация машин на километр пути;

  скорость (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. Базовая идея осталась прежней, однако за десятилетия промышленная реализация прошла глубокую калибровку под актуальные массивы данных и современные автомобили.

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

 

Источник