Будуть роботи стояти в пробках?

Ця історія почалася з того що я застряг у пробці на хайвеї, не особливо великий, але півгодини простояв практично на місці. І, як це часто буває, пробка розсмокталася сама по собі — не було попереду ні аварії, ні ремонту, машини просто в якийсь момент почали рухатися швидше, ще швидше, і все — вільна дорога попереду.
Чим зазвичай займаються в пробках? Ну хто-чим і коли-як, а я в той день був у мирному філософському настрої — просто сидів і розмірковував. Згадав зокрема посада на Гиктаймс про робомобилях де в коментарях бурхливо порівнювали манеру водіння людей і роботів і в кінці здається прийшли до висновку, що майбутнє на дорогах за AI, при ньому і рух стане безпечніше і середня швидкість зросте. Цікаво, а пробки тоді будуть? Іншими словами, наскільки пробки зумовлені зовнішніми (об'єктивними) обставинами, і наскільки ефектом натовпу, агресивною або, навпаки, гальмівної манерою водіння? Заодно згадалася прочитана колись книга де стверджувалося що моделювання дорожнього трафіку — одна з найбільш складних математичних завдань, яка досі не вирішена. Ну це напевно давно вже неправда, читав я це давно і книга вже тоді була не новою, зараз вже напевно і теорії правильні написали, і на комп'ютерах своїх все порахували. Хоча… пробки ж залишилися? Загалом, політ фантазії було вже не зупинити.
Отже, під катом ми спробуємо побудувати більш-менш осмислену модель руху транспорту на дорозі і, якщо пощастить, спробуємо змоделювати різницю у водінні водія-людини і AI. Я звичайно віддаю собі звіт, що цією проблемою професійно займаються цілі організації і взагалі дуже розумні люди, але тим цікавіше. І взагалі, ставте собі нереальні цілі.
І ще одне — я переконаний прихильник думання головою, тому в цьому пості комп'ютерного моделювання не буде, взагалі зовсім не буде, тільки хардкорний олівець і папір.

Для початку треба сказати, що існує два походу — мікроскопічна модель і статистична. Перша розглядає окремо рух кожної машини в потоці як окремий набір незалежних змінних в одній величезній системі рівнянь і, зі зрозумілих причин, користується найбільшою популярністю у теоретиків. Друга розглядає всю сукупність як безперервну середу де кожна окрема машина описується лише попередньо. З почуття протиріччя з цього другого випадку і почнемо.
Найпростіша статистична модель
Нехай є одна смуга з рівномірно розподіленими машинами з лінійною щільністю ρ. Однак швидкості у всіх машин різні, будемо вважати що вірогідність мати швидкість v описується щільністю ймовірності P(v,t) залежить звичайно від часу і дорівнює в момент t=0 деякої відомої функції P(v,0). Можна без обмеження спільності вважати що вірогідність P(v,t) визначена на інтервалі від нуля до (хай вибачать мене дорожні поліції всіх країн) безкінечності. Визначено також поняття нормування і середньої (групової) швидкості:

     (1.1)
За час dt кожна має швидкість v проходить відстань vdt і може як "зникнути" наздогнавши більш повільну і втративши швидкість, так і "збільшити масу", будучи догнанной більш швидкою. Легко зміркувати, що за інтервал часу dt ймовірність машині зі швидкістю v наздогнати більш повільну машину зі швидкістю u (і загальмуватися) буде P(u,t)(v-u)dtdu і симетричне вираз для ймовірності бути догнанной більш швидкою машиною (і загальмувати її). Таким чином зміна щільності ймовірності з часом:
     (1.2)
Трохи подумавши досить легко зрозуміти, що рішення повинно мати вигляд A(v)B(t)exp(-ρvt) і звідси повне рішення:
     (1.3)
Рівняння вийшло витончене, але незамкнутого, оскільки середня швидкість сама залежить від часу. Однак нас не цікавлять деталі зміни щільності ймовірності P(v,t) з часом, тим більше що вони залежать від довільної елементарної функції P(v,0), тому ми можемо скористатися (1.1) щоб замкнути рівняння відносно v
звідси
     (1.4)
ось з цим рівнянням вже можна працювати, давайте розглянемо кілька окремих випадків для ілюстрації.
Нехай спочатку всі машини рухаються строго з однією швидкістю:
      звідси
      як і повинно бути.
Нехай спочатку швидкість розподілена рівномірно в деякому інтервалі:

      при цьому середня швидкість падає як 1/t a середнє пройдену відстань зростає логарифмічно
      — і це хороша новина для тих хто читає цей пост стоячи в пробці — до місця ви все таки дійдете, правда за експоненційний час.
Однак Тут є одне гадане протиріччя — якщо в потоці присутні машини з як завгодно малою швидкістю, як може середнє пройдену відстань збільшуватися з часом? Відповідь в тому, що число машин зі строго нульовою швидкістю теж дорівнює нулю. Якщо ми візьмемо початковий розподіл у вигляді:
      тобто майже всі машини рухаються з однаковою швидкістю, а деяка дуже мала частина просто стоїть, то групова швидкість буде падати експоненціально
      середнє пройдену відстань прагне до фіксованого межі.
Таким чином ми витратили пару аркушів паперу і показали що на односмуговою дорогою все рано чи пізно встромити в хвіст самій повільній машині і будуть тягнутися з її швидкістю — блискучий результат. Спробуємо тепер трохи більш реальний варіант.
Крок назустріч реальності
Якщо ви читали уважно, до цього місця у вас повинно було виникнути почуття законного здивування — а де ж пробки? З якого дива ми вважаємо лінійну щільність ρ константою не залежить ні від часу, ні від координати? Зрештою пробка і є по суті скупчення машин. Все правильно, в рамках нашої поточної моделі ми розглядаємо профіль руху усереднений за дуже великим інтервалом, настільки великим що усереднена по ньому щільність постійна. Всередині нього машини збиваються в колони між якими зовсім порожні проміжки, але в характерному масштабі нашої моделі все це несуттєво. Характерний розмір неоднорідності, колони або проміжку, зростає з часом і ось, коли він нарешті зрівняється з характерним масштабом, пробка… могла б виникнути, але не виникає, тому що модель більше не застосовується. Треба шукати більш деталізовану модель. Зверніть також увагу, що для окремої машини, що рухається в потоці немає ніякого розподілу за швидкостями P(v,t) з яким ми працювали раніше, існує тільки швидкість v(x,t) і локальна густина ρ(x,t). От з нею і попрацюємо.
Перш за все, для щільності повинно виконуватися рівняння безперервності:
      (2.1)
абсолютно фундаментальний закон по суті означає що скільки в трубу втекло, стільки повинно витекти. Зауважте, що ρv — це просто число машин перетинають перетин дороги за одиницю часу.
Зрозуміло, у цього рівняння існує нескінченна безліч рішень, наприклад це може бути довільна функція f(x-vt) описує рух довільного профілю щільності з довільною швидкістю v. Якщо перейти в рухому систему координат разом з машиною, то це вираз приймає ще більш простий вигляд: ρv=const. Якщо скажімо щільність змінюється за законом ρf(x -vt) і попереду ділянка дороги з пониженою швидкістю u, u < v, то там профіль щільності буде виглядати як Pf(x-ut), ρv=Pu. Така модель подібна ідеального газу і описує ідеальне поведінка трафіку на дорозі — при зменшенні швидкості відбувається пропорційне збільшення щільності а кількість машин перетинають перетин дороги в одиницю часу постійно (з точністю до флуктуацій f(x)), ви завжди можете розрахувати час, за який ви проїдете певну відстань і воно не буде залежати від інших машин на дорозі.
Так все-таки, де ж пробки?
Модель ідеального газу описує стан невзаємодіючих частинок, неідеальність починається при врахуванні взаємодії. Аналогічно виходить і у нас — доведеться враховувати пригальмовування коли машини виявляються занадто близько. Гальмівний шлях можна описати виразом v2/2a+vτ+d, — прискорення комфортного гальмування оцінене (грубо) константою; τ — величина розмірності часу і порядку часу реакції водія; d — величина порядку довжини автомобіля. Просторова щільність ρ повинна бути зворотною величиною. Виходить? Немає, очевидно, що у межі великих швидкостей щільність повинна падати як 1/v а не 1/v2, а у нас вийшло що навіть потік машин через перетин дороги ρv падає з ростом швидкості. Помилка в тому що водії зовсім не тримають інтервал назад пропорційний гальмівного шляху, це було б так, якби попереду йде машина могла б зупинитися миттєво — занадто сильне припущення, насправді вона гальмує з тим же самим прискоренням a. Тоді у нас зникає квадратичний член і виходить розумне вираз:
ρmax=1/(vτ+d)       (2.2)
при збільшенні щільності до 1/d (тобто бампер в бампер) машини можуть тільки стояти, а при зростанні швидкості потік прагне до межі: ρv=1/τ. Це вираз граничної щільності при даної швидкості, якщо автомобілі зійдуться ще тісніше, вони почнуть пригальмовувати. Може бути, я занадто детально на цьому зупинився, але хотілося показати як правильно закладена модель починає коригувати сама себе, через розгляд приватних та граничних випадків виявляє помилки.
Нехай по дорозі рухається колона машин з однаковими швидкістю v і щільністю ρ. Якщо ця колона вьезжает на ділянку зі зниженою швидкістю u<v, то щільність машин збільшується, як ми вже бачили раніше, ρ*=ρv/u.

Однак, якщо щільність наближається до критичної, може виявитися що нова ділянка дороги нездатний пропустити такий потік (максимальний потік машин через перетин дороги νmax(u)=uρmax(u)=u/(uτ+d) і монотонно зменшується із зменшенням швидкості)
ρ*=ρv/u > ρmax=1/(uτ+d).
Тепер в гру вступає рівняння (2.1) що описує зміну швидкості і профілю густини, яке однак має нескінченну безліч рішень, включаючи нестаціонарні та коливальні. Давайте для оцінки зверху візьмемо ідеальний випадок, що оптимізує пропускну здатність дороги, для цього кожну машину повинен вести всезнаючий демон Максвелла, але тим не менш. Тоді кожна машина буде пригальмовувати заздалегідь точно вгаданий момент до містично угаданной швидкості u, приблизно ось так:

Більш того, межа гальмування буде рухатися вліво легко обчислюється швидкістю:
[ρv-u/(uτ+d)]/[1/(uτ+d)-ρ]=[ν-νmax(u)]/[ρmax(u)-ρ]      (2.3)
А що відбувається на передньому фронті? Припустимо, що обмеження на швидкість в деякий момент зникло, тоді фронт почне випаровуватися — машини почнуть прискорюватися до початкової швидкості v і фронт теж почне рухатися вліво. Однак швидкість випаровування свідомо менше швидкості гальмування; головним чином тому що водій гальмує відразу ж як тільки помітить стоп-сигнали попереду, а для розгону йому потрібно оцінювати відстань до машини, що йде попереду і її швидкість. Оцінити швидкість випаровування фронту досить важко без залучення емпіричних міркувань, проте ми можемо припустити, що вона може бути як більше, так і менше швидкості лівої межі (2.3), яка в свою чергу залежить від обмеження швидкості u. І, якщо вона виявиться менше, то ми отримуємо щось типу солітону на дорозі — стійке утворення, що виникає при випадковому короткому гальмуванні однієї з машин і існуюче кінцеве час. Важливо додати, що для виникнення такого солітону вже необов'язково реального обмеження швидкості, достатньо якщо одна з машин спонтанно сповільниться на час τ до швидкості менше деякої критичної.
До власне пробок залишився один маленький крок, досить помітити що утворився солітон нестабільний, його щільність дорівнює критичній (2.2) і будь-яке випадкове досить сильне гальмування однієї з машин в колоні викличе новий аналогічний процес і освіта нового ущільнення з ще меншою швидкістю. При досить великому часу життя такої освіти цей сценарій буде повторюватися і лавинно накладатися один на інший аж до досягнення розрідженого ділянки на дорозі або повної зупинки машин в кінці колони, що ми власне і спостерігаємо в реальному житті.
Зараз можна було б залучити теорію ймовірностей і прикинути довжину отриманого солітону (яка визначається флуктуаціями щільності трафіку), а так само час його життя і ймовірність виникнення ще більших ущільнень і шанси повної зупинки руху, так само як і середнє зменшення пропускної здатності дороги. Коротше, грунтуючись на цій простій моделі можливо побудувати повне імовірнісний опис дорожнього трафіку. Однак я підозрюю, що давно вичерпав ліміт на кількість формул в пості, крім того, треба було б залучення якихось емпіричних та/або кількісних даних, чого я намагався уникати всіма силами. Особисто я вже досяг розуміння як трапляються пробки і отримав від цього певне задоволення. Крім того я зрозумів яка зла сила вирвала півгодини з мого життя, і жити мені відразу стало краще і веселіше.
А як же роботи?
А з ними все просто, оскільки я не робив ніяких людино-специфічних припущень, базова модель вірна і для них. Тобто якщо змусити робомобили їхати по дорозі на межі її пропускної спроможності, в потоці руху можуть виникати спонтанні збурення призводять до уповільнення аж до повної зупинки. Однак імовірність таких збурень можна постаратися істотно знизити.
  • По-перше, в потоці складається виключно з роботів набагато рідше виникають спонтанні флуктуації, роботи не чхають за кермом, не опускають запалену сигарету, не відволікаються на балаканину пасажирів і субьективных причин пригальмовувати у них практично немає. Однак об'єктивні причини (слизьку ділянку дороги наприклад) все-таки залишаються.
  • По-друге, теоретично час реакції τ робота набагато менше, в межі прагне до нуля. Однак я боюся, що розробники робомобилей перестраховуючись його штучно завищують в алгоритмах водіння. З часом цей резерв теж буде задіяний.
  • -третє, роботам чужі емоції, зокрема нетерпіння, заздрість і жадібність. Це дозволяє їм тримати дистанцію трохи більше мінімально необхідного, в результаті лінійно трохи знижується пропускна здатність, однак імовірність виникнення заторів падає нелінійно у багато разів. Однак для цього необхідно, щоб на дорозі робомобили як мінімум переважали.
  • -четверте, і це найсуттєвіше, що відрізняє їх від людини — роботи набагато ближче до демонів Максвелла. Зокрема, якщо дозволити їм обмінюватися інформацією на дорозі, можна створити віртуальний розподілений ІІ керуючий рухом на кожній ділянці. Як простий приклад — колона з фур може очевидно виграти, якщо кожна буде знати швидкість першою в колоні фури в кожен момент. Ще один — якщо стає відомо, що десь попереду (може бути досить далеко) починається ущільнення, машини можуть заздалегідь збільшити інтервал і таким чином блокувати поширення пробки. Ну і нарешті, час розгону можна кардинально зменшити якщо машина отримує сигнал про прискорення від йде попереду, це дозволило б різко скоротити час життя солітону і запобігти лавинний ефект.
  • Ну і нарешті для тих хто проектує і будує дороги — не забувайте що у кожної дороги з обмеженням швидкості vmax є максимальна пропускна здатність близько vmax/(τvmax+d) і, якщо очікується збільшення потоку (місто росте) на якійсь ділянці до цієї величини, добре б заздалегідь передбачити розширення дороги або збільшення максимальної швидкості. Ну це вже з області абсолютних фантазій звичайно.
Я не знаю які моделі розробляються зараз виробниками робомобилей, і взагалі, чи готуються вони морально до того часу коли вони будуть переважати на дорогах; але мені здається, що вже пора. Локальні алгоритми водіння пора доповнювати і розширювати до кооперативних і тоді ми будемо витрачати менше часу на стояння в пробках, а значить і світ стане трішки краще.


PS: Спочатку я планував цей пост на Гиктаймс, але з подивом виявив відсутність відповідних хабів. На мій погляд, правильним поєднанням було б Математика+Цікаві завдання+Транспорт майбутнього, однак виявилося, що перші два присутні тільки на Хабре, причому в розділі Розробка. Ну й добре, пишу туди де хаби відповідають.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.