Lanci koji oslobađaju

2021-12-04

Primjena Markovljevih lanaca u prometnoj tehnici

U jednoj prethodnoj temi obrađivao sam odlučivanje u prometu i spomenuo Markovljeve lance. Dva su razloga zašto je ovo posebna tema. Prvo, o stohastičkim procesima učio sam na poslijediplomskom studiju pa ovo nije obvezna lektira prometnih inženjera. Drugo, držim da zaslužuje posebnu pozornost. Ova metoda je jednostavna i shvatljiva za svakog inženjera, a izuzetno korisna pa svakako preporučujem odvojiti malo vremena - barem za upoznavanje.

Teorija vjerojatnosti je ograničena na jedan eksperiment (promatranje) u kojem slučajna veličina (ili više njih) poprimi neku vrijednost ili obilježje. Ako eksperiment traje dulje vrijeme i slučajne veličine poprimaju različite vrijednosti tijekom vremena dolazimo do stohastičkog procesa. Ovo se može jako zakomplicirati, ali i dovoljno simplificirati da bude i matematički konzistentno i inženjerski primjenjivo. Olakšavajuća okolnost je da promet (pojava, organizacija, sustav) najčešće ima diskretan skup stanja, ili se može diskretizirati, pa je matematički alat ipak jednostavniji (razumljiviji). Vrijeme je najpoznatiji reprezentant kontinuirane veličine, ali ga uvijek možemo promatrati u diskretnim vremenskim intervalima.

Iako se čini na prvi pogled složenim, a u teorijskoj osnovi i jest, jedan praktičan primjer će pokazati koliko je to efikasno oružje kod prometnih sustava gdje je informacijski (upravljački) element glavni ili presudan u njegovu opisivanju, analiziranju (proučavanju) i promišljanju (optimiziranju).

Grad Rijeka od 2003. godine ima automatizirani semaforski sustav pod nazivom Automatsko upravljanje prometom u Gradu Rijeci ili skraćeno AUP-RI. Ovdje su prikazani podatci za period 2003. - 2006. godina. To je razdoblje prije 2007. godine kada su započeli radovi na rekonstrukciji Riječke zaobilaznice (A7) - izgradnja punog profila. Podatci su realni i opisuju jedno razdoblje riječkog prometa, imaju povijesnu statističku vrijednost, a danas su operativno su bezvrijedni.

Početak 2000-tih su vremena informatičkih rješenja s predefiniranim stanjima gdje su algoritmi izabirali najbolje scenarije (prometne planove) u određenim trenutcima. Što je danas drugačije? Dosta toga. Razvili smo adaptivne sustave, koji su opet danas prevladani primjenama strojnog učenja. Što je danas isto? Dosta toga. Postoje isto sustavi s predefiniranim scenarijima, ali se ti scenariji metodama strojnog učenja (ili još naprednijima metodama umjetne inteligencije, općenito podatkovne znanosti) stalno prilagođavaju aktualnom stanju pa nema potrebe puno "skakanja" između osnovnih scenarija, što tijekom izmjena generira određene (ponekad i znakovite) gubitke. S motrišta prometne potražnje obično se razlikuju dijelovi dana: noć, jutro, prijepodne, poslijepodne, večer, određene aktivnosti (blagdani, sajmovi, sportska i druga događanja, ...). Za takva razdoblja i događanja stvaraju se prometni planovi. Zašto spomenuto "skakanje" ponekad nije dobro? Budući imamo konkretan primjer semaforskog sustava u Rijeci, objasnit će se na semaforskom sustavu. Promjena prometnog plana traži promjenu ciklusa, svaka promjena duljine ciklusa znači da treba naći neku točku u planu izmjene signala od kuda će krenuti novo odbrojavanje, a svaka točka promjene (bez obzira koliko se pažljivo bira) uvijek izaziva dva poremećaja. Prvi je lokalni unutar signalnog plana jer će uvijek neko zeleno prekratko trajati, a drugi je globalno jer će se izgubiti barem jedan ciklus zbog ponovnog usklađivanja offseta između raskrižja za uspostavljanje sinkroniziranog rada. Konkretno, nalazimo se u ciklusu od 80 s i želimo prijeći u ciklus od 100 s. Unutar postojećeg ciklusa izgubit ćemo 10 - 15 s, i još 100 s za potpuno usklađivanje, što znači da ćemo izgubiti dvije minute vremena do stabilnog stanja rada novog programa. Ovakva promjena je unutar sljedećih 15 minuta već "potrošila" 13 % vremena. Zato danas postoje adaptivni algoritmi koji rastežu neke vremenske parametre do sigurnosno prihvatljivih granica i prelaze u drugo stanje kada takve prilagodbe nisu dovoljne.

Ipak, i nekad je postojala adaptivnost na način da se mijenjao vremenski korak od 0,9 - 1,2 s; meni nisu poznate veće granice. Na taj način se npr. duljina ciklusa od 80 s mogla mijenjati od 72 - 96 s. Glede "stezanja" je trebalo biti jako oprezan zbog minimalnih i zaštitnih međuvremena, a kod "rastezanja" zbog povećanja izgubljenih vremena i ukupnog izgubljenog vremena u ciklusu.

Matematički se to jednostavno opiše, a puno važnije i jednostavno izračuna. Ako kažemo da stanje prometnog upravljačkog sustava (TCS) karakterizira njegovo aktualno stanje prometnog plana (TPi) u vremenu (to), onda taj aktualni prometni plan (TPi) funkcionira po nekim mjerilima kvalitete, Ako nakon nekog vremena (dt) neki drugi plan (TPj) upućuje na bolje pokazatelje, uzimajući u obzir i troškove prelaska (Lij), onda treba napraviti prelazak.

Ideja je uvijek bila, a danas se to može i puno bolje realizirati, rad sustava sa što manje stresa - globalnih promjena. Ovdje možemo parafrazirati ekološku maksimu: optimiziraj lokalno, a promatraj (promišljaj) globalno.

Vratimo se opet na konkretan primjer, Grad Rijeku prije 2007. godine. Aplicirano je bilo šest prometnih planova.

Rad svakog prometnog plana može se prikazati vektorom. To je vektor vjerojatnosti jer su njegove komponentne nenegativne i njihov zbroj je jednak 1. Nadalje se prikazuju svi podatci za radni dan u periodu od 2003. do 2006. godine. Prometni plan TP1 ima sljedeće komponente.

Prvi član pokazuje da je 16,7 % vremena bio u funkciji TP1, da je najveća vjerojatnost (a i vrijeme akcije) od 45,5 % bio prelazak u TP2. Plan TP1 kratko je radio, a puno više akcije (vremena) je bilo utrošeno za prelaske u TP2 i TP3. Svih šest vektora rada prometnih planova može se prikazati matricom. To je regularna stohastička matrica. Ima svojstvo regularnosti jer su svi članovi neke njezine potencije pozitivni.

Pet najvećih brojeva u matrici pokazuje pet najčešćih akcija:

0,4550; prelazak iz TP1 u TP2,
0,4090; prelazak iz TP6 u TP5,
0,3830; prelazak iz TP2 u TP3,
0,3500; prelazak iz TP2 u TP1,
0,3300; prelazak iz TP3 u TP4.

Ova rang lista govori jednu lošu i jednu dobru stvar. Loša stvar je što su najveća učešća kod prijelaznih stanja. Sustav je bio aktivan (živahan), stalno je istraživao bolja rješenja. Dobra stvar je što su ti prelasci postepeni; prelazak iz višeg u niži plan za jedan broj i obrnuto, nigdje nema preskakanja. Iz matrice se može zaključiti:

sustav je možda previše "radio"; ne mora nužno značiti i lošu karakteristiku,
sustav je bio dobro podešen (dobar set-up) jer nije bilo čestih preskakanja prometnih planova; najviše preskoka je bilo iz TP6 u TP4 - 0,2500,
česte izmjene govore o fluktuaciji prometne potražnje,
fluktuacija prometne potražnje govori o atraktivnosti središnjeg područja Rijeke (gdje je AUP-RI bio tada apliciran) prije 2007. godine,
sustav je najviše radio u planu TP3 - srednja prometna potražnja, nakon toga u TP4 - velika prometa potražnja te jednako vremena u programima TP1, TP2 i TP5,
itd., ..., npr. prosječno jedan sat dnevno radi i program za izvanredne situacije.

Regularna stohastička matrica ima jedno lijepo svojstvo da njezina potencija teži matrici čiji su svi redci predstavljaju fiksni vektor vjerojatnosti. U ovo slučaju peta potencija.

Ovo nam govori u kojem je stanju sustav bio; imao vjerojatnosti pojavljivanja određenog prometnog plana. Najčešća stanja su bila srednje, male i velike prometne potražnje, a rjeđe zahtjevi vršne prometne potražnje. Konkretno sustav je prosječno radio 19:50 sati dnevno za raspone od minimalne do velike prometne potražnje. Preostalo vrijeme od 4:10 sati predstavljaju vršna i izvanredna stanja. Iz ovog se jednostavno zaključuje da je Rijeka u periodu 2003. - 2006. u središnjem gradskom dijelu imala uobičajena četiri vršna sata: možda dva ujutro i dva poslijepodne, a možda nešto kraće s dodatnim satom oko podnevna kada je smjena školaraca i studenata.

Puno priče, i brojeva, do sada a još nisam spomenuo Markovljeve lance. Evo ih! Markovljev lanac je proces s diskretnim vremenom i konačnim skupom stanja, a vjerojatnost ponašanja sustava u budućnosti ovisi isključivo u stanju sadašnjosti, bez utjecaja stanja sustava u prošlosti. Sve navedeno ima prikazani primjer: konačni kup stanja (šest prometnih planova), diskretne vremenske korake (jedan sat) i evidentno stanje dolazećeg prometnog plana ovisi o aktualnom planu, što je bilo prije nema utjecaja. Postoje Markovljevi lanci višeg reda; npr. oni drugog reda uzimaju u obzir stanje sustava u dva prethodna koraka. Ipak, klasični (oni prvog reda) se najčešće koriste. Ja osobno u svojem dijelu posla nisam vidio aplikaciju Markovljevih lanaca višeg reda, iako nisam baš neki uzor po tom pitanju. Čemu Markovljevi lanci služe? Opet, lakše pokazati nego teoretizirati.

Može se postaviti pitanje. Ako je sustav u planu TP3, koje su vjerojatnosti zadržavanja i prelaska u druga stanja. Jednostavno pomnožimo vektor sustava TP3 i matricu P. Dakle, imamo vektor stanja sustava u programu TP3 na početku, označimo ga pTP3(0) i želimo vidjeti kakvo će stanje sustava biti nakon jednog koraka (jednog sata), označimo to stanje pTP3(1).

Za ovo nije trebala matematika, jasno je da je to treći redak matrice P jer se radi o TP3. Međutim, sada dolazimo do pravog učinka Markovljevog lanca. Kakva je vjerojatnost stanja sustava u drugom koraku, ako smo krenuli iz TP3. Odgovor je.

Kakva je vjerojatnost stanja nakon tri i četiri sata (koraka):

Dakle, Markovljevi lanci mogu nam pokazati različite vjerojatnosti stanja sustava u pojedinim vremenskim koracima. Ovdje je prikazano da stanje prometnog plana TP3 (srednja prometna potražnja) teži prema prometnom planu TP4 (prvi korak), nakon toga najveća vjerojatnost je vratiti se u TP3 (drugi korak), a tri sata nakon toga sustava ima i dalje najveću vjerojatnost ostati u TP3. Prikazuju se vjerojatnosti tranzicije stanja za P1 i P4 riječkog AUP-RI sustava tijekom radnih dana u periodu 2003. - 2006. godine.

Općenito vrijedi:

odnosno svejedno da li se penjemo do željenog koraka preko vektora stanja ili preko potencija stohastičke regularne matrice.

Nadalje, cestovni prometni upravljački sustavi spadaju u nerazložive lance jer je moguć prelazak bilo kojeg prometnog plana u bilo koje stanje i ta su stanja pozitivno ponavljajuća i aperiodička. Pozitivno ponavljajuća jer je vrijeme ponavljanja nekog stanja konačno. Aperiodička jer se različita stanja ne pojavljuju u nekim određenim vremenskim intervalima; postoji određena uniformnost npr. vršnih sati u radnim danima, ali nipošto se ne radi o periodičkom ponavljanju. Ova klasa naziva se Markovljevi ergodički lanci.

Što nam ovo pokazuje? Puno toga, jako puno toga. Dobivamo jasne odgovore na pitanja:

u kojem prometnom planu (stanju) će se sustav najviše nalaziti u kraćem/dužem vremenskom razdoblju?
kakva je vjerojatnost da sustav iz određenog stanja prijeđe u neko drugo stanje?
kakva je vjerojatnost da sustav iz određenog stanja prijeđe u neko željeno stanje?
da li će sustav biti učinkovitiji ako je unaprijed predefinirano više ili manje osnovnih stanja - prometnih planova?
kakvo će biti ponašanje sustava na prijelazu s prometnog stanovišta različitih vremenskih razdoblja; na primjer prijelaz iz radnog dana u dane vikenda ili blagdana (ovdje to nije pokazano)?

Što možemo s odgovorima? Možemo:

analizirati (optimizirati) sustav sa stanovišta određenih promjena u strategijama upravljanja, bilo sa stanovišta vremena ili stanovišta upravljačkih struktura,
analizirati ponašanje sustava u sklopu kratkoročnih ili dugoročnih (prometnih) prognoza,
pronaći (odrediti) optimalne strategije za različite kombinacije mogućih stanja,
usporediti različita rješenja unutar postojeće prometne mreže (postojeće prometne ponude).

Ako ništa drugo, možemo vidjeti koji se prijelazi najčešće dešavaju pa "mehanički" podesiti taj prijelaz s najmanje gubitaka. U prikazanom slučaju bili bi zanimljivi prijelazi P2 - P3 i P3 - P4 jer se oni najčešće vrte tijekom dnevnog perioda radnim danom. Drugi pristup bi bio promisliti povezivanje P1 i P2 te P3 i P4, a možda čak i P5 i P6. Prigovor je stvaranje rješenja s puno manjim brojem prometnih planova. Ako manjem broju planova dodamo lokalne adaptivne algoritme, onda smo stvorili (u ovom slučaju) tri osnovna plana s "bezbroj" varijanti.

Negdje oko 2003. godine u Zagrebu je bio u posjetu gospodin iz Londona koji mi je objasnio da je London tada imao osam osnovnih prometnih planova od kojih nisu svi bili stalno u funkciji; različiti planovi za radne dane, subote, nedjelje, blagdane, razna događanja i dr.. Svaki plan je imao sedam varijanti - sekundarnih planova (kiša, magla, različita prometna opterećenja i/ili gustoće prometa, sportska događanja, VIP rute i dr.). Ukupno je tada London imao na raspolaganju 64 različite kombinacije koje su prometnim vlastima pružale ogromnu paletu mogućnosti upravljanja i vođenja prometa. Primjena Markovljevih lanaca pokazuje što je potrebno, ima li što suvišno, što se može povezati, a što je bolje riješiti nekim lokalnim promjenama i/ili usklađivanjima.

Procesi Markovljevih lanaca nisu niti malo profana metodologija kako sam ih ovdje predstavio. Intencija ove teme, kao i većine ostalih, nije učenje već promocija i motivacija koleg(ic)a koji možda nisu susreli ovu metodu, ali vrijedi se malo pomučiti (samoučiti) jer njihova korisnost višestruko nadvladava uloženi trud.

Zato držim da Markovljevi lanci oslobađaju prometnog inženjera brojnih dilema i pitanja jer jasno upućuju (opisuju) kako je bilo, što je, što će biti, ali i puno važnije - što bi moglo biti, što i kako promijeniti da bi bilo bolje.