Detekce a lokalizace v yjimecn ych stav u v mestske doprave
1
Uvod
Reakce rdcho systemu na nastale vyjimecne stavy v doprave je velice dulezitou soucast vsech globalnch rdcch systemu. Nez pristoupme ke zkouman vyjimecnych stavu v doprave, vymezme nejdrve to, co v teto praci budeme povazovat za vyjimecny stav. rozumme mimoradnou dopravn situaci, jejz dopad se podstatnym zpusobem odraz v merenych dopravnch datech.
V yjime cn ym stavem v doprav e
m k a: Metody, ktere pouzvame, jsou zalozeny na informaci o strukture zkoumane dopravn Pozna oblasti, apriorn znalosti o chovan automobil u v dane oblasti a zejmena na on-line merenych dopravnch datech. Struktura oblasti je dana, apriorn informace vypovda o "pr umernych" vlastnostech oblasti a pouze realna data nesou informaci o okamzitem den v oblasti. Vsechny dopravn udalosti, ktere se v merenych datech neodraz, jsou pro nas nedosazitelne, a nelze je detekovat ani rdit. Tm samozrejme nemame na mysli, ze bychom potrebovali prmo nastalou poruchu merit! Pozadujeme pouze, aby se porucha v nekterych datech projevila, abychom ji mohli na zaklade techto velicin predpovedet.
V prpade vyjimecneho stavu je situace odlisna od "beznych situac". Rozdlu je nekolik vyjimecna situace nastava vetsinou ve velmi kratkem casovem intervalu a ma prechodnou dobu trvan, dopad nastale vyjimecne situace na stav dopravnho systemu je vetsinou dosti podstatny, jednotlivych skupin podobnych vyjimecnych stavu (alespon co do dopadu na stav dopravnho systemu) byva konecny pocet. Vyjimecne stavy lze samozrejme klasi kovat podle rady hledisek a zahrnovat pod ne vets nebo mens mnozstv udalost, majcch (vetsinou negativn) vliv na dopravn system a vymykajcch se beznym dopravnm podmnkam. My se pridrzme vyctu provedeneho v praci [1]. Zde je uvedena pomerne siroka skala ruznych vyjimecnych dopravnch stavu vcetne jejich vyhodnocen a navodu pro jejich detekci. V teto zprave se vsak nebudeme ani tak zabyvat klasi kac jednotlivych stavu jako obecnou urovn rozpoznavan vyjimecnych stavu vubec a jejich prpadnou klasi kac, tj. urcenm kde a jaky vyjimecny stav nastal. Budeme se pritom drzet jedineho, nejpodstatnejsho druhu z vyjimecnych stavu, a to prekazky ve vozovce. Jako jednotlive vyjimecne stavy budeme uvazovat ruzna msta, kde k teto blokade doslo. Otazkou bude: (I) pozname vubec, ze nekde v oblasti doslo k zablokovan jzdnho pruhu? (II) pozname, na kterem mste k tomuto zablokovan doslo? Zajmave okolnosti pri techto experimentech jsou (i) za jak dlouho jsme schopni vyjimecny stav zaregistrovat, (ii) s 1
jakou jistotou jsme schopni vyjimecny stav detekovat, (iii) jak dlouho mus vyjimecny stav trvat, abychom si jej vubec vsimli, (iv) jak silny dopad mus mt vyjimecny stav, abychom jej zachytili. R esen vyjimecnych stavu zde nechavame stranou a predpokladame, ze po detekci vyjimecneho stavu by nastoupilo urcite expertn rzen, bud' jiz existujc nebo navrzene dopravnmi operatory. 2
Formulace u lohy
Pro testovan byla vybrana liniova mikrooblast se ctyrmi krizovatkami, konkretne ulice Zborovska a Svornosti. Detailn planek teto oblasti, konkretne jejch ctyrech rzenych krizovatek, je na Obrazku 1.
Obr azek 1
: Realna oblast jejz model byl pouzit pro testovan 2
Oblast
se
nal ez a
v
m st e
mal eho
sm chovsk eho
okruhu.
Tato
oblast
obsahuje
ve
skute cnosti 10 k ri zovatek, z nich z zbyl ych sest je ne r zen ych a intenzita provozu v nich nen velk a. Proto jsme brali v u vahu jen uveden e cty ri sv eteln e r zen e k ri zovatky.
Model teto mikroblasti byl vytvoren pomoc dopravnho simulatoru simulovan AIMSUN. Schema modelu je na Obrazku 2. 2
10 4 3 4
1 1 2
j j
6 7 5 6 7
j j
3 Obr azek 2
14 9 11 8 9 10 11
j j j
5
13 12
j j j j
8
j
12
: Mikrooblast se zkoumanymi vyjimecnymi stavy
Mikrooblast je tvo rena cty rmi k ri zovatkami se razen ymi v jedn e linii - podrobnosti viz Obr. 1. Je zde vyzna ceno 12 c sel v krou zku, kter a ozna cuj m sta, kde byla postupn e um st'ov ana blok ada. Siln ej s svisl e u se cky ozna cuj m e ric detektory, ozna cen e rovn e z c sly.
Na vyznacenych mstech 1-12 byla simulovana porucha ve forme stojcho automobilu. Na detektorech v oblasti (viz obr. 2) byla merena data (obsazenosti dopravnho proudu) pro stav bez poruchy (zadne stojc auto) a 12 poruchovych stavu (porucha i odpovda autu stojcmu v pozici i; i = 1; 2 : : : ; 12). Pro stav bez poruchy a kazdy poruchovy stav (urcita doba stan automobilu na zvolene pozici) je tedy k dispozici 13 datovych souboru, charakterizujcch stav oblasti. Otazka je: (i) lze vubec tmto zpusobem poruchu detekovat? (ii) s jakou jistotou lze tvrdit, ze tato porucha skutecne existuje jako pravdiva? (iii) jak dlouhe je treba meren jak pro o -line, tak i pro on-line identi kaci, aby zskana informace o poruse byla dostatecna?
3
3
Model sm esi distribuc a jeho odhad
V teto kapitole naznacme zaklady teorie odhadu smesoveho modelu metodou Quasi-Bayes. Protoze zmnena teorie je znacne obtzna a jej programova realizace vyuzva dosti neprehledne ale zato velmi ucinne odmocninove algoritmy, zustaneme jen u odvozen zakladnch vztahu aniz bychom je prevadeli do podoby algoritmu. Ten je zpracovan v systemu MIXTOOLS vytvorenem v AS U TIA AV C R - viz [2]. U plna teorie odhadu smesovych modelu je popsana v [3]. Komponenty modelu
Predpokladame n modelu, indexovanych prirozenymi csly c 2 f1; 2; :::; ng = c a modelovana data dt ; t 2 t . Modely jsou popsany svymi podmnenymi hustotami pravdepodobnosti hp f (dt jd(t 1); c; c ): Dale predpokladame, ze v kazdem casovem okamziku je aktivn pouze jeden model - komponenta smesoveho modelu, tj. ze prave jen tato komponenta odraz skutecny stav sledovaneho systemu. Ukazatel
Aktivity jednotlivych komponent oznacuje ukazatel - nahodna velicina ct s hodnotami 1; 2; : : : ; n. ct = c znamena, ze v okamziku t je aktivn komponenta c. Pravdepodobnosti aktivity jednotlivych komponent c, bez znalosti aktualnch dat dt, predpokladame konstantn a rovny c, tedy f (ct = cjd(t 1); ) = f (ct = cj ) = c m k a: Vyrazem f (ct = c) myslme fct (c) = P (ct = c) kde P (:) oznacuje pravdepodobnost. Pozna
V okamziku, kdy namerme data dt, mame dals informaci o skutecnem aktualnm stavu. Hp vyjadrujc tento stav je f (ct jd(t)): Nahodna posloupnost ct je neznama a jej hodnoty nelze merit a je treba je odhadovat. 4 4.1
Odhad model u sm esi distribuc Vnit rn popis sm esi
Sdru zen a hp dat a ukazatele
Tato hp popisuje jak data, tak i ukazatele f (dt ; ct jd(t 1); ; ): (1) Je to sdruzena hp, parametrizovana vektorem parametru [; ]. Tato hp urcuje pravdepodobnost, ze data dt pochaz z komponenty ct. 4
Tato sdruzena hp muze byt rozlozena takto (1) = f (dtjd(t 1); ct; ; ) f (ctjd(t 1); ; ) = = f (dtj't ; ct; c ) f (ctj ) = c f (dtj't ; ct; c ) kde f (dt jd(t 1); ct ; ; ) = f (dt j't ; ct ; c ) je popis jedne komponenty (konkretne s indexem ct), a f (ct jd(t 1); ; ) = f (ct j ) = c je pravdepodobnostn popis ukazatele ct. 1
1
t
t
1
t
t
t
(2) (3)
m k a: Z predchozho plynou pozadavky na model Pozna
1. kazda komponenta c = 1; 2; : : : ; n ma sve vlastn parametry
c ,
2. data dt jsou zavisla jen na datech, obsazenych v regresnm vektoru 't hloubky radu modelu), 3. ukazatel je nezavisly na parametrech component
1
(tj. minulych datech az do
c ,
4. ukazatel je podmnene nezavisly na starych datech, je-li znam parametr ukazatele - vektor , 5. pravdepodobnosti komponent v case t bez znalosti dt jsou stacionarn. 4.2
Vn ej s popis sm esi
Hp dat bez ohledu na aktivitu component
Tuto hp lze dostat dvema zpusoby (presne a s aproximac): Prvn zpusob je presny a je dan marginalizac hp (1) vzhledem k ukazateli ct f (dt jd(t 1); ; ) = X X = f (dt ; ct jd(t 1); ; ) = c f (dt ; ct jd(t 1); ; ): 2
2
ct c
ct c
t
(4)
kde jsme pouzili vztah (3). Druha moznost je aproximace. Ta spocva v nahrazen ukazatele ct nejakym jeho bodovym odhadem. Ze sdruzene pravdepodobnosti se pak po dosazen bodoveho odhadu stane hp jedine promenne, a to dt. Tak dostaneme marginaln hp. Tento postup nen, vzhledem k aproximaci, optimaln, zato ale vede na spocitatelne algoritmy pro odhadovan. Touto cestou dostavame f (dt jd(t 1); ; ) / f (dt ; c^t jd(t 1); ; ); (5) kde ct je bodovy odhad poctany na zaklade starych dat d(t 1). Bodovy odhad je poctan jako podmnena stredn hodnota (viz dale).
5
4.3
Odhad
[; ] - (Bayesuv vzorec)
Bayesuv vzorec pro odhad parametru [; ] ma tvar f (; jd(t)) = f (; jdt ; d(t 1)) / f (dtjd(t 1); ; )f (; jd(t 1)) (6) coz je rekurze, ktera prepoctava hp pro jmenovany parametr. Pro jej pouzit se vyzaduje znalost vnejsho popisu smesi f (dtjd(t 1); ; ). Protoze Bayesuv vztah (6) ma soucinovy tvar a vnejs popis smesi je dan ve tvaru souctu (4), dostavame vysledek v tvar soucinu souctu, coz je vypocetne nevhodne. R esen, ktere je spocitatelne, dostaneme s vyuzitm aproximovaneho vztahu (5). To je cesta, kterou se budeme dale zabyvat. 4.4
Odhad
[; ] - (pro statistiky)
Modely komponent v exponenci aln m tvaru
Komponenty vyjadrme pomoc hp z exponencialn trdy f (dt j't ; c; c ) = expfqc ()s('t )g; c 2 c (7) kde qc() je parametricka funkce c-te komponenty a s('t ) je statistika (spolecna vsem komponentam). 1
1
1
Sou cinov y tvar modelu a apriorn hp
Pro dals odvozen je vyhodne formalne vyjadrit jak model, tak i apriorn hp v nasledujcm soucinovem tvaru c f (dt j't ; ct ; c ) = c expfqc ()s('t )g Y = [ c expfqc()s('t )g] c;c t
1
t
t
= a f (; jd(t
1)) =
1
t
2 Y
1
c c
2
c c
Y 2
c c
c(c;ct )
c(t
Y 2
c c
1)
(8)
expfqc()S (t 1)g;
(9)
c c
1
kde (t 1) a S (t 1) jsou statistiky hp parametru v case t 1. m k a: (c; ct ) je Diracova -funkce, de novana takto Pozna
(c; ct ) =
1 0
6
t)
expfqc()s('t )(c; ct)g
Y 2
(
for c = ct for c = 6 ct
Bayes uv vzorec pro sou cinov y tvar hp
Dosadme soucinove tvary hp (8) and (9) do Bayesova vzorce (6) a dostaneme Y t Y c;c Y c expfqc ()S (t)g = c expfqc()s('t )(c; ct)g ( )
(
2
2 Y
c c
t)
c c
2
c c
Y
=
2
c c
2Y
c c
c(t
1)
2
c c
1
expfqc()S (t 1)g
c[(c;ct )+(t
1)]
Y 2
c c
expfqc()[s('t )(c; ct) + S (t 1)]g 1
Z teto rekurze pro hp zskame rekurzi pro statistiky (t) = (t 1) + (c; ct ) (10) S (t) = S (t 1) + (c; ct ) s('t ) (11) ktera rka: prepoctej pouze tu statistiku, jejz komponenta byla v case t aktivn. Tato rekurze ale nen prakticky pouzitelna, nebot' obsahuje neznamou promennou ct. Protoze se ale tato promenna vyskytuje pouze ve funkci , budeme aproximovat celou tuto funkci. 1
4.5
Aproximace
Msto funkce (c; ct) dosadme jej stredn hodnotu (c; ct ) E [(c; ct )jd(t)] wc (t):
(12)
V ypo cet st redn hodnoty
E [(c; ct )jd(t)] =
Z
(c; ct )f (ct jd(t))dct = f (cjd(t)) wc (t); c 2 c ;
coz vyzaduje znalost hp f (cjd(t)); c 2 c. Konstrukce hp
f (cjd(t))
Potrebnou hp lze zskat takto f (cjd(t)) = f (cjdt ; d(t 1)) / f (dt ; cjd(t 1)) = f (dt jc; d(t 1))f (cjd(t 1)): Posledn dve hp mohou byt parametrizovany f (dt jc; d(t
1)) = = =
Z Z
Z
f (dt ; c jc; d(t f (dt jc; d(t
1))dc =
1); c)f (cjd(t 1))dc =
f (dt j't 1 ; c; c )f (c jd(t
7
1))dc
a f (cjd(t
1)) = = =
Tak dostavame wc (t) = f (cjd(t)) =
Z
Z Z Z
f (c; c jd(t f (cjd(t
1))d c =
1); c)f ( cjd(t 1))d c =
c f ( c jd(t
1))d c
f (dt j't 1 ; c; c )f (c jd(t
Z
1))dc cf ( cjd(t 1))d c
(13)
v zavislosti na znamych hp, konkretne jsou to modely komponent a ukazatele a apriorn hp prevzata z minuleho kroku identi kace. m k a: Aproximace rozdeluje p Pozna uvodn deterministicky ukazatel ct s "dirakovskou" hp (c; ct ) na pravdepodobnostn ukazatel s hp w(t). Situace je zachycena na nasledujcm obrazku:
6c (c; c ) t
b b b b b
Obr azek 3.
wc (t)
---
Efekt aproximace ukazovatele
Zat mco p uvodn ukazovatel ukazuje "s jistotou" na jedinou komponentu, aproximovan y ukazatel p ripou st jako aktivn i sousedn komponenty s p r slu sn ymi pravd epodobnostmi aktivit.
8
5
Experimenty
Pro rekonstrukci stavu, ktery urcuje msto simulovane poruchy, pouzijeme odhad modelu mikrooblasti ve forme smesi distribuc. O -line odhadneme model pro bezporuchovy stav a vsechny poruchove poruchove stavy, a s pouzitm vsech dat, ktera mame k dispozici. Tyto modely uschovame. On-line merme data s danou poruchou a odhadujeme prslusny model. Porovnanm online modelu s jednotlivymi modely zskanymi o -line zjistme minimaln vzdalenost odhadnuteho modelu s ostatnmi a pro ktery model je vzdalenost minimaln, tu poruchu prohlasme za aktualn. Experiment ma tedy dve casti: 1. C ast ucen, kdy je pouzita setrvala porucha po dobu 15 dn, 2. C ast testovan, kde jsou pouzita aktualn data v dobe trvan 4.5, 7.5, 15 a 22,5 min. Tyto casy, pri periode vzorkovan 1.5 min, odpovdaj trem, peti, deseti a patnacti aktualnm vzorkum. Pro prezentaci jsme vybrali poruchu c. 5 a pro test byla pouzita data (obsazenost) na detektoru c. 5. Vzajemnou pozici detektoru 5 a stojcho vozidla zpusobujcho poruchu 5 je mozno nalezt na obrazku 2. Na nasledujcch obrazcch jsou vysledky testu aktualnch dat pri poruse 5. Kazdy z obrazku ma dve casti. Na leve strane je vynesen prubeh odhadu poruchy - na ose x je porad zpracovavaneho aktualnho vzorku, na ose y je odhad csla poruchy. Jako vysledny odhad poruchy bereme nejcastejs odhad z jednotlivych kroku. V prave casti kazdeho obrazku jsou vyneseny nenornovane logaritmicke likelihoody pro vsechny smesi naucene na jednotlive poruchy. Vyhrava ta porucha, ktera je nejcasteji maximaln. V idealnm prpade by mel byt jeden prubeh s urcitym odstupem trvale maximaln a ostatn mens. Tento idealn stav vsak nenastava, coz svedc o tom, ze informace o poruse nen v datech mnoho.
Obr azek 3
: Porucha 5, tri vzorky dat = 4.5 minuty 9
Obr azek 4
Obr azek 5
: Porucha 5, pet vzorku dat = 7.5 minuty
: Porucha 5, deset vzorku dat = 15 minut 10
Obr azek 6
: Porucha 5, patnact vzorku dat = 22.5 minuty
Z uvedenych obrazku je patrne, ze porucha c. 5 byla spravne detekovana ve vsech prpadech. Odhad ze tr dat je dosti nejisty, ale ukazuje se, ze pet aktualnch vzorku je pro detekci poruchy dostacujc. Pro uplnost uvadme vysledky pro 3, 5, 10 a 15 vzorku dat pro vsechny typy poruch, tj. poruchu 1 az 13. Csla poruch je mozno sledovat na obrazku 2, pricemz pripomname: 1 je bezporuchovy stav a poruchy 2,3,.. jsou oznaceny jako 1,2,.. Vysledky jsou uvedeny v tabulkach, kde v prvnm radku je skutecne cslo poruchy v druhem radku je cslo odhadu poruchy. skutecna porucha 1 2 3 4 5 6 7 8 9 10 11 12 13 odhadnuta porucha 1 5 4 4 5 6 6 8 9 10 10 12 13 Rozhodovan po trech vzorcch = 4.5 minuty skutecna porucha 1 2 3 4 5 6 7 8 9 10 11 12 13 odhadnuta porucha 1 2 4 4 5 6 6 8 9 10 10 12 13 Rozhodovan po peti vzorcch = 7.5 minuty skutecna porucha 1 2 3 4 5 6 7 8 9 10 11 12 13 odhadnuta porucha 1 2 3 4 5 6 6 8 9 10 10 12 13 Rozhodovan po deseti vzorcch = 15 minut 11
skutecna porucha 1 2 3 4 5 6 7 8 9 10 11 12 13 odhadnuta porucha 1 2 3 4 5 6 2 8 9 10 10 12 13 Rozhodovan po patnacti vzorcch = 22.5 minuty Z uvedeneho je patrne, ze jiz rozhodovan s peti vzorky, tj. daty merenymi po dobu 7.5 minuty je velmi dobre. 6
Z av er
Provedene pokusy, testujc schopnost pravdepodobnostn smesi popsat a rozlisit dopravn data z ruznych dopravnch situac, prokazaly, ze uvedena cesta je perspektivn. Vyhodou tohoto prstupu je, ze je postaven na globalnm pohledu na dopravn oblast, a tedy je v podstate nezavisly na jejm konkretnm vyberu. Zahrnut vsech merenych dat do odhadu rovnez zajist'uje maximaln vyuzit dostupne informace, i kdyz se porucha na nekterych detektorech neprojev. Cestou, ktera zde byla naznacena, se bude dale pokracovat a budou se testovat dals zlepsen. Jednm z nich, napr. je pro testy brat ne jenom merene obsazenosti, ale dvojice [obsazenost, intenzita], ktere predstavuj elementarn stavy dopravy. Reference
[1] Drbohlav J. Pliska Z. Pribyl P., Tichy T., \Navrh expertnho systemu pro resen mimoradnych udalost- oblast smchova", Tech. Rep., ELTODO, Praha 4, Novodvorska 14, Praha, 17. prosince 2005. [2] P. Nedoma, M. Karny, T. V. Guy, I. Nagy, and J. Bohm, , U TIA AV C R, Praha, 2003. [3] M. Karny, J. Bohm, T. V. Guy, L. Jirsa, I. Nagy, P. Nedoma, and L. Tesar, , Springer, London, 2005. Mixtools. (Program)
Optimized Bayesian
Dynamic Advising: Theory and Algorithms
12
