Identificando padrões comportamentais do tipo avoidance em trajetórias de objetos móveis

Identificando padrões comportamentais do tipo

avoidance em trajetórias de objetos móveis.

Alisson Moscato Loy (UFRGS)Orientador: Luis Otávio Alvares (UFRGS)Co-Orientadora: Vania Bogorny (UFSC)

2

Estrutura da apresentação

Motivação; Objetivo do trabalho; Heurística para identificação do

padrão comportamental avoidance; Algoritmo desenvolvido; Experimentos; Considerações finais;

3

Trajetórias de objetos móveis

(x1,y1,t1)

(x2,y2,t2)(x10,y10,t10)

Trajetória 1tid Coord tempo

1 x1,y1 t1

1 x2,y2 t2

... ... ...

1 x10,y10 t10

... ... ...

4

Objetivo do trabalho Definir o padrão comportamental que ocorre quando uma

trajetória evita determinadas regiões espaciais.

Avoidance

5

O termo avoidance na literatura

Principalmente utilizado para caracterizar o comportamento de evitar o choque entre objetos móveis (Ex: robôs, aviões, navios, veículos); Collision-avoidance;

Freqüentemente relacionado a uma ação em tempo real;

6

Exemplos de ocorrência do padrão comportamental avoidance proposto neste trabalho

Veículos que evitam câmeras de segurança;

Pessoas que desviam de seguranças em aeroportos e shoppings;

Na busca por rotas de escape em regiões de tráfego lento;

7

Heurística para detecção do avoidance

t1

t2

A trajetória deve estar na direção do objeto-alvo e, num dado

instante, mudar de direção de forma a evitá-lo.

t3

Objeto alvo

8


Objeto alvo

Região de interesse

Para ser considerado um avoidance a trajetória deve

interceptar a região de interesse do objeto-alvo;

9


Objeto alvo


A trajetória deve apresentar uma

subtrajetória direcionada ao alvo dentro da região de

interesse.

t1

t2

t3

10


Objeto alvo


Região de incremento de confiança

t1

t2

Região que permite aumentar o grau de confiança do

avoidance, pela análise do comportamento da trajetória.

11

Confiança local – Um objeto alvo

strong (1.0)

weak (0.5)

none (0.0)

12

Confiança local – Vários objetos-alvo

strong (1.0)

weak (0.5)

none (0.0)

O1

O2

O3

t1

13

Percentual de avoidance por objeto-alvo (Prk)

O3O1

O2

t2t1

t3

Pr2 = 66,66 %Pr2 = 100 %

14

Fator de ponderação (Wk)

O1

O2

t1

t2

t3

W1 = 1.0

W2 = 0.5

15

Evitando falsas ocorrências de avoidance em eventos conhecidos

GID evento início fim geom

0 Manut. Rede Esgoto

2011-01-17 10:00:00

2011-01-19 15:00:00

LINESTRING (...)

1 Feira de rua

2011-01-23 06:30:00

2011-01-23 15:00:00

LINESTRING (...)

... ... ... ... ...

TID GID Geom time

0 1 POINT(...) 2011-01-18 19:52:19

0 2 POINT(...) 2011-01-18 19:52:20

... ... ... ...

16

Cálculo da confiança global

Onde: n corresponde ao número de objetos-alvo cuja região de interesse foi interceptada pela trajetória ti, Avik é a medida de avoidance da trajetória ti em relação ao objeto-alvo ok e wk é o fator de ponderação do objeto-alvo ok.

n

kk

k

n

kik

t

w

wAvAv

i

1

1

Quanto maior o índice Avt, mais forte é a característica da trajetória de evitar determinadas regiões espaciais.

17

Algoritmo desenvolvido

Pseudocódigo principal; Identificação da subtrajetória

direcionada ao alvo; Geração da região de incremento de

confiança;

18

Pseudocódigo principal

Conjunto de trajetóriasConjunto de objetos-alvoTamanho do buffer da região de interesse Tamanho mínimo da subtrajetória direcionada ao alvoConjunto de eventos

Identifica os avoidancese calcula os índices de Confiança locais

Calcula o percentual deavoidance por objeto-alvo Eliminando os casos de 100%

Calcula o índice global de confiança de avoidance por trajetória

Percentual de avoidance por região de interesseConfiança global de avoidance por trajetória

19


Para cada trajetória que intercepta uma região de interesse

Para cada região de interesse interceptada


Intercepta o objeto-alvo?

SIM

NÃO

Identifica Subtrajetória dir. ao alvo

Possui subtrajetória direcionada ao alvo?

SIM

NÃO

Não é avoidance

Calcula região de incrementode confiança

Intercepta região de incremento de confiança??

SIM

NÃO

Strongavoidance

Weakavoidance

Confiança local dos avoidances detectados

Possui evento relacionado?

SIM

NÃO

20

Identificação da subtrajetória direcionada ao alvo

21


Para cada trajetória que intercepta uma região de interesse

Para cada região de interesse interceptada


Intercepta o objeto-alvo?

SIM

NÃO

Identifica Subtrajetória dir. ao alvo

Possui subtrajetória direcionada ao alvo?

SIM

NÃO

Não é avoidance

Calcula região de incrementode confiança

Intercepta região de incremento de confiança??

SIM

NÃO

Strongavoidance

Weakavoidance

Confiança local dos avoidances detectados

Possui evento relacionado?

SIM

NÃO

22

Calculando a região de incremento de confiança

23

Experimentos

Experimentos iniciais para apoio ao desenvolvimento da heurística: Dados obtidos em praça pública em Porto Alegre; Trajetórias coletadas em ruas e avenidas em

diferentes locais;

Experimentos para fins de verificação de eficácia e eficiência do algoritmo desenvolvido: Experimento 1 - trajetórias de veículos em Porto

Alegre; Experimento 2 – trajetórias de veículos em Xangri-lá; Experimento 3 – trajetórias de pedestres no Parque

Germânia;

24

Experimento 1 – trajetórias de veículos em Porto Alegre

21 trajetórias;

4 objetos-alvo;

Região interesse:100m;

Raio do objeto alvo:20m;

Subtrajetóriadirecionada aoalvo: 8m

25


Dados de avoidance por região de interesse:GID Percentual0 50%1 57.14%2 50%3 50%

Cálculo da confiança global do avoidance:TID Confiança Global7 113 118 0.9321 0.515 0.411 0.25

26


27


28

Experimento 2 – trajetórias de veículos em Xangri-lá41 trajetórias;

10 objetos-alvo;

Região interesse: 120m;

Raio do objeto alvo: 20m;

Subtrajetória direcionada ao alvo: 10m;

29

Experimento 2 – trajetórias de veículos em Xangri-láDados de avoidance por região de interesse:

GID Percentual* 0 100%

1 33.34% 2 50% 3 0% 4 40% 5 0%

* 6 100% 7 0% 8 33.34% 9 9.09%

Objetos-alvo marcados com * serão removidos do cálculo do índice de confiança global.Cálculo da confiança global do avoidance:

TID Confiança Global 12 1 33 0.75 9 0.667 17 0.5 19 0.5 20 0.5 29 0.5 7 0.25 21 0.25 2 0.167

30

Experimento 2 – trajetórias de veículos em Xangri-lá

31

Experimento 3 – trajetórias de pedestres no Parque Germânia17 trajetórias;

5 objetos-alvo;

Região interesse: 50m;

Raio do objeto alvo: 10m;

Subtrajetória direcionada ao alvo: 4m;

32

Experimento 3 – trajetórias de pedestres no Parque Germânia

Dados de avoidance por Região de Interesse:GID Percentual 0 11.11% 1 14.28% 2 33.33% 3 37.5% 4 0%

Cálculo da confiança global do avoidance:TID Confiança Global 7 0.667 6 0.5 8 0.5 4 0.167

33


34


35

Trabalhos Publicados

Parte deste trabalho foi publicado no GeoInfo 2010 [Loy et al. 2010] tendo sido selecionado como um dos três melhores artigos do congresso.

An Algorithm to Identify Avoidance Behavior in Moving Object Trajectories (Luis Otavio Alvares, Alisson M. Loy, Chiara Renso and Vania Bogorny), Journal of the Brazilian Computer Society, Volume 17, Number 3, p. 193-203, 2011.

36

Considerações finais – trabalhos futuros

Aprimorar a heurística que determina o índice de confiança local;

Avaliar outras técnicas para criação da região de incremento de confiança;

Aprimorar a determinação do fator de ponderação Wk;

37

Referências[Alvares et al. 2007] Alvares, L. O.; Bogorny, V.; Kuijpers, B.; Macedo, J. A. F.; Moelans,

B.; Vaisman, A.: A Model for Enriching Trajectories with Semantic Geographical Information.. In: Proc. of the ACM 15th International Symposium on Advances in Geographic Information Systems (ACM-GIS'07), Seattle, Washingthon, 7-9 November (2007).pp. 162-169.

[Andersson et al. 2008] Mattias Andersson, Joachim Gudmundsson, Patrick Laube, and Thomas Wolle: Reporting Leaders and Followers Among Trajectories of Moving Point Objects, Geoinformatica (2008), Volume 12, Number 4, 497-528, DOI:10.1007/s10707-007-0037-9.

[Benkert et al. 2006] Benkert, M., Gudmundsson, J., H¨ubner, F., Wolle, T.: Reporting flock patterns. In: Algorithms - ESA 2006, Proceedings. Volume 4168 of Lecture Notes in Computer Science. Springer-Verlag Berlin, Berlin (2006) 660–671.

[Bernabeu et al. 2001] Bernabeu, E.J., Tornero, J., Tomizuka, M.: Collision prediction and avoidance amidst moving objects for trajectory planning applications in: Robotics and Automation. (2001) 3801 - 3806 vol.4. ISSN:1050-4729.

[Bogorny et al. 2008] Bogorny, V. and Wachowicz, M. A Framework for Context-Aware Trajectory Data Mining. In: Longbing Cao, Philip S. Yu, Chengqi Ahang, Huaifeng Zhang. (Org.). Data Mining for Business Applications. Springer, 2008.

[Bogorny et al. 2009] Bogorny, V.; Kuijpers, B.; Alvares, L.O. ST-DMQL: A Semantic Trajectory Data Mining Query Language. In: International Journal of Geographical Information Science. Taylor and Francis, 2009.

[Cao et al. 2006] Cao H.; Mamoulis, N.; Cheung, D.W.: Discovery of collocation episodes in spatiotemporal data. In ICDM, pages 823–827. IEEE Computer Society, 2006.

38

Referências[Cao et al. 2007] Cao, H., Mamoulis, N., and Cheung, D. W. (2007). Discovery of periodic patterns in spatiotemporal

sequences. IEEE Transactions on Knowledge and Data Engineering, 19(4):453–467.[Elnekave et al. 2007] Sigal Elnekave, Mark Last, Oded Maimon: Predicting future locations

using clusters' centroids. Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems , 2007.

[Giannotti et al. 2006] F. Giannotti, M. Nanni, and D. Pedreschi. Eficient mining of sequences with temporal annotations. In Proc. SIAM Conference on Data Mining, pages 346–357. SIAM, 2006.

[Giannotti et al. 2007] Giannotti, F., Nanni, M., Pinelli, F., and Pedreschi, D. (2007). Trajectory pattern mining. In Berkhin, P., Caruana, R., and Wu, X., editors, KDD, ACM, p. 330–339.

[Gudmundsson et al. 2006] Gudmundsson, J.; Kreveld, M.. Computing longest duration flocks in trajectory data. In GIS’06: Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, pages 35–42, New York, NY, USA, 2006. ACM Press.

[Gudmundsson et al. 2007] Gudmundsson, J., van Kreveld, M. J., and Speckmann, B. (2007). Efficient detection of patterns in 2d trajectories of moving points. GeoInformática, 11(2):195–215.

[Guo 2008] Danhuai Guo; Mining Traffic condition from trajectories. Fifth International Conference on Fuzzy Systems and Knowledge Discovery (pp. 256-260). Shandong, China: IEEE Computer Society (2008).

[Gütting et al. 2000] Gütting, R. H.; Böhlen, M. H.; Erwig, M.; Jensen, C. S.; Lorentzos, N. A.; Schneider, M.; Vazirgiannis, M. A foundation for representing and quering moving objects. ACM Trans. Database Syst., [S.1.], v.25, n.1, p.1-42, 2000.

[Hornsby 2001] Hornsby, K. Temporal zooming. Transactions in GIS, 5, pp. 255–272, 2001.[Kim et al. 2007] Dae-Jin Kim, Kwang-Hyun Park, M., Bien, Z.: Hierarchical longitudinal controller for rear-end collision

avoidance, (2007).[Laube et al. 2002] Laube, P. and Imfeld, S. Analyzing relative motion within groups of trackable moving point objects. In

Egenhofer, M. J. and Mark, D. M., editors, GIScience, volume 2478 of Lecture Notes in Computer Science, pages 132–144. Springer, 2002.

[Laube et al. 2004] Laube, P., van Kreveld, M., Imfeld, S.: Finding REMO - detecting relative motion patterns in geospatial lifelines. In Fisher, P.F., ed.: Developments in Spatial Data Handling. Proceedings of the 11th International Symposium on Spatial Data Handling. Springer, Berlin Heidelberg, DE (2004) 201–214.

[Laube et al. 2005] Laube P., Imfeld S., Weibel R. Discovering relative motion patterns in groups of moving point objects, in: International Journal of Geographic Information Science, vol. 19, Taylor & Francis Group, pp. 639–668, 2005.

39

Referências[Lee et al. 1999] Lee, S.W., Lee, B.H., Lee, K.D.: A configuration space approach to collision avoidance of a

two-robot system. Robotica 17, 131–141 (1999).[Lee et al. 2008] Lee, J.G., Han, J., Li, X.: Trajectory outlier detection: A partition-and-detect framework. In:

ICDE, pp. 140–149. IEEE (2008).[Liu et al. 2005] Liu, Y.H., Shi, C.J.: A fuzzy-neural inference network for ship collision avoidance. In:

Proceedings of 2005 International Conference on Machine Learning and Cybernetics, pp. 4754–4754. IEEE Computer Society (2005)

[Loy et al. 2010] Loy, A. M., Bogorny, V., Renso C., Alvares L. O., Um algoritmo para identificar padrões comportamentais do tipo avoidance em trajetórias de objetos móveis. GeoInfo 2010. Campos do Jordão-SP.

[Nedevschi et al. 2009] Stereo-Based Pedestrian Detection for Collision-Avoidance Applications. Sergiu Nedevschi, Silviu Bota and Corneliu Tomiuc. Ieee Transactions On Intelligent Transportation Systems, Vol. 10, No. 3, September 2009.

[Palma et at. 2008] Palma, A. T; Bogorny, V.; Kuijpers, B.; Alvares, L.O. A Clustering-based Approach for Discovering Interesting Places in Trajectories. In: 23rd Annual Symposium on Applied Computing, (ACM-SAC'08), Fortaleza, Ceara, 16-20 March (2008) Brazil. pp. 863-868.

[Shandy et al. 2001] Shandy, S., Valasek, J.: Intelligent agent for aircraft collision avoidance. In: Proceedings of AIAA Guidance, Navigation, and Control Conference, pp. 1–11. American Institute of Aeronautics and Astronautics (2001).

[Soldera 2007] John Soldera, Detecção de movimentos suspeitos em seqüências de vídeo. Dissertação de mestrado, Universidade do Vale do Rio dos Sinos, 2007.

[Suh et al. 1988] Suk-Hwan Suh, Albert B. Bishop. Collision-avoidance trajectory planning using tube concept: Analysis and simulation. – Journal of Robotic System 5(6), 497-525 (1988).

[Suh et al. 1992] Suk-Hwan Suh, Kim, M.S.: An algebraic approach to collision-avoidance trajectory planning for dual-robot systems: Formulation and optimization. Robotica 10(02), 173–182 (1992).

40

Entrada: T // Conjunto de trajetóriasO // Conjunto de objetos-alvod // Tamanho do buffer da região de interesse em torno do objeto-alvol // Tamanho mínimo da subtrajetória direcionada ao alvoE // Conjunto de eventos

Saída: Avt // Conjunto de graus de confiança de avoidance por trajetória

1. Início2. Para ok Є O faça3. wk 0,5 // valor inicial da ponderação4. Fim Para5. Para ti Є T | intersects (ti, buffer(O, d)) faça // intercepta região de interesse6. Para ok Є O faça7. Se intersects (ti, ok) // Testa interseção com objeto-alvo8. avik none // não é avoidance9. wk 1 // ajusta ponderação10. Senão11. S Subtrajetoria(ti, ok, d) // obtém maior subt. em dir. ao alvo12. Se S.dist >= l // é subtrajetória direcionada ao alvo?13. Se ( ej Є E | intersects (ok, ej) período de ti

está inserido no tempo de validade de ej )14. Ric RegIncrConf(ok, d, S.ini) // Calcula região de

// incremento de confiança15. Se intersects (ti, Ric) período de ti > período de S

// cruza a reg. de incr. de conf. em um tempo

// posterior à subtrajetória direcionada ao alvo.

16. avik strong // avoidance forte17. Senão18. avik weak // avoidance fraco19. Fim Se20 Fim Se21. Senão22. avik none // não é avoidance23. Fim Se24. Fim Se25. Fim Para26. Fim Para27. Para cada ok Є O faça28. Calcula Prk29. Se Prk = 130. Retira ok de O31. Fim se32. Fim para33. Para cada ti Є T34. Calcula Avti35. Fim para36. Retorna Avt37. Fim

41

Identificação da subtrajetória direcionada ao alvo

Entrada: P // Conjunto de pontos da trajetória que interceptam a região de interesseo // objeto-alvo em análised // tamanho do buffer da região de interesse em torno do objeto-alvo

Saída: Subt // Subtrajetória direcionada ao alvo

Método: Subtrajetoria()

1.Início2. i 13. próximo i + 14. distaux 05. dist 0 // Inicializa variável 6. ini Pi // Guarda ponto inicial da subtrajetória7. Repete até o final de P8. ap azimute (Pi , Ppróximo) // Calcula o azimute entre os pontos9. Pauxx sen(ap) · ( 2 · d ) + Pix // Calcula coordenada x do ponto auxiliar10. Pauxy cos(ap) · ( 2 · d )+ Piy // Calcula coordenada y do ponto auxiliar11. Se intersects (makeline(Pi, Paux), o) // Intercepta o objeto alvo?12. distaux Calcula distância euclidiana(Pi , Ppróximo)13. Se distaux > dist14. dist distaux // Guarda maior distância euclidiana 15. ini Pi // Guarda ponto inicial da maior subtrajetória

identificada16. Fim Se17. próximo próximo +118. Senão // Avalia o próximo ponto da trajetória19. i i +120. próximo i + 121. Fim Se22. Fim Repete23. Subt {dist, ini}24. Retorna Subt25.Fim

42

Calculando a região de incremento de confiança

Entrada: o //objeto alvod // tamanho do buffer da região de interesseini // ponto inicial da subtrajetória direcionada ao alvo

Saída: reg // região de incremento de confiança

Método: RegIncrConf()

1.Início2. Oc centroid(o) // centro geométrico de o3. az azimute(ini, Oc) // Obtém inclinação da região de incremento de

confiança4. lim1 makeline1 (az, o, exteriorring(buffer(o, d))) 5. lim2 makeline2 (az, o, exteriorring(buffer(o, d))) 6. reg CalculaRegião(lim1, exteriorring(o), lim2,

exteriorring(buffer(o, d))) // calcula região dentro dos limites informados

7. retorna reg // devolve a região de incremento de confiança8.Fim

43

Gráfico comparativo entre o número total de pontos nas trajetórias e o número de pontos dentro de alguma região de interesse

3099

519

19780

2097

5499

2051

0

2000

4000

6000

8000

10000

12000

14000

16000

18000

20000

Veículos em Porto Alegre Veículos em Xangri-lá Pedestres no parque Germânia

Total de pontos Pontos dentro de região de interesse

44

Gráfico comparativo entre a quantidade de objetos-alvo, avoidance identificados e trajetórias que interceptaram alguma região de interesse

4

11 1110

13

30

5

8

13

0

5

10

15

20

25

30

Veículos em Porto Alegre Veículos em Xangri-lá Pedestres no parque Germânia

Objetos-alvo Avoidances identificados Trajetórias que interceptaram região de interesse

45

Gráfico comparativo dos tempos médios de execução para os diferentes tipos de dados utilizados nos experimentos

4791 5442

39166

11745

0

5000

10000

15000

20000

25000

30000

35000

40000

Tempo

(

ms

)

Veículos em PortoAlegre (sem eventos)

Veículos em PortoAlegre (com eventos)

Veículos em Xangri-lá Pedestres no parqueGermânia

Documents

Identificando padrões comportamentais do tipo avoidance em trajetórias de objetos móveis