Um Método Heurístico para Cálculo de Rotas com Desvios de Obstáculos em Serviços Web de Mapas Digitais
Resumo
O cálculo de rotas entre dois pontos que desviem de obstáculos é uma atividade típica de sistemas de geoprocessamento, mas que não é provida por serviços web de mapas digitais dado o seu alto custo computacional. Propomos aqui uma abordagem para o problema que consiste em usar conjuntamente o cálculo de rota mais curta provido por esses serviços e métodos heurísticos baseados em algoritmos de visibilidade. Esses métodos são inspirados em planejamento de rotas para robôs, levando a sugerir pontos intermediários alternativos às rotas originalmente traçadas pelos SWMD que forcem o desvio dos obstáculos identificados. Uma avaliação comparativa em diversos cenários indica a viabilidade do método e seu potencial de melhoria.Referências
Cormen, Thomas H. et al. (2001). “Section 24.3: Dijkstra's algorithm”. In: “Introduction to Algorithms”, 2nd ed. MIT Press and McGraw Hill. pp. 595601.
Dobrin, Adam (2005). “A Review of Properties and Variations of Voronoi Diagrams”, Whitman College.
Fu, L., Sun D. and Rilett L. R. (2006) “Heuristic shortest path algorithms for transportation applications: state of the art”, In: Computers and Operations Research, Volume 33, Issue 11, Elsevier Science Ltd., Oxford, UK.
Furtado, Vasco, Ayres, Leonardo, de Oliveira, Marcos, Vasconcelos, Eurico, Caminha, Carlos, D’Orleans, Jonathan, Belchior, Mairon. (2010) “Collective Intelligence: The WikiCrimes System. Information Science”, v(180), 1.
Ishikawa et al (1991): “Map Navigation Software of the Electro Multivision of the ’91 Toyota Soarer”. In: IEEE Int. Conf. Vehicle Navig.Inform. Syst. pp. 463–473.
Joseph O'Rourke (1993) “Computational geometry column 18”, In: ACM SIGACT News, Volume 24, Issue 1, New York NY, USA.
Lima, Natan Costa and Ferreira, Carlos Eduardo (2008). “Algoritmos e estrutura de dados para problemas de deslocamento no plano”, In: IV Simpósio de Iniciação Científica e Pós-Graduação, Instituto de Matemática e Estatística, USP, São Paulo, SP, Brasil.
McLafferty (2000). “Identification, development and implementation of innovative crime mapping techniques and spatial analysis”. Washington, D.C: U.S. Department of Justice, p.27.
Merril Duane. “Mashups: The new breed of Web app” at [link]
Rosen, Kenneth H. “Handbook of Discrete and Computational Geometry and its Applications”. Rouse, J., Bergeron, S.J., Harris, T.M., “Participating in the geospatial web: collaborative mapping, social networks and participatory GIS,” in Scharl, A., Tochtermann, K. (Eds.), The Geospatial Web: How Geobrowsers, Social Software and the Web 2.0 are Shaping the Network Society, Springer, New York, NY, pp. 1538, 2007
Sánchez Miralles, A. and Sanz Bobi (2004), M. A.: “Global Path Planning in Gaussian Probabilistic Maps”, Journal of Intelligent and Robotic Systems, Volume 40, Issue 1, Kluwer Academic Publishers, Hingham, MA, USA.
Senjuti, B. R., Gautam, D. and Sajal D. (2007) “Computing Best Coverage Path in the Presence of Obstacles in a Sensor Field”, In: WADS.
Dobrin, Adam (2005). “A Review of Properties and Variations of Voronoi Diagrams”, Whitman College.
Fu, L., Sun D. and Rilett L. R. (2006) “Heuristic shortest path algorithms for transportation applications: state of the art”, In: Computers and Operations Research, Volume 33, Issue 11, Elsevier Science Ltd., Oxford, UK.
Furtado, Vasco, Ayres, Leonardo, de Oliveira, Marcos, Vasconcelos, Eurico, Caminha, Carlos, D’Orleans, Jonathan, Belchior, Mairon. (2010) “Collective Intelligence: The WikiCrimes System. Information Science”, v(180), 1.
Ishikawa et al (1991): “Map Navigation Software of the Electro Multivision of the ’91 Toyota Soarer”. In: IEEE Int. Conf. Vehicle Navig.Inform. Syst. pp. 463–473.
Joseph O'Rourke (1993) “Computational geometry column 18”, In: ACM SIGACT News, Volume 24, Issue 1, New York NY, USA.
Lima, Natan Costa and Ferreira, Carlos Eduardo (2008). “Algoritmos e estrutura de dados para problemas de deslocamento no plano”, In: IV Simpósio de Iniciação Científica e Pós-Graduação, Instituto de Matemática e Estatística, USP, São Paulo, SP, Brasil.
McLafferty (2000). “Identification, development and implementation of innovative crime mapping techniques and spatial analysis”. Washington, D.C: U.S. Department of Justice, p.27.
Merril Duane. “Mashups: The new breed of Web app” at [link]
Rosen, Kenneth H. “Handbook of Discrete and Computational Geometry and its Applications”. Rouse, J., Bergeron, S.J., Harris, T.M., “Participating in the geospatial web: collaborative mapping, social networks and participatory GIS,” in Scharl, A., Tochtermann, K. (Eds.), The Geospatial Web: How Geobrowsers, Social Software and the Web 2.0 are Shaping the Network Society, Springer, New York, NY, pp. 1538, 2007
Sánchez Miralles, A. and Sanz Bobi (2004), M. A.: “Global Path Planning in Gaussian Probabilistic Maps”, Journal of Intelligent and Robotic Systems, Volume 40, Issue 1, Kluwer Academic Publishers, Hingham, MA, USA.
Senjuti, B. R., Gautam, D. and Sajal D. (2007) “Computing Best Coverage Path in the Presence of Obstacles in a Sensor Field”, In: WADS.
Publicado
19/07/2011
Como Citar
BASSO, Victor E. D.; FURTADO, Vasco.
Um Método Heurístico para Cálculo de Rotas com Desvios de Obstáculos em Serviços Web de Mapas Digitais. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 8. , 2011, Natal/RN.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2011
.
p. 275-286.
ISSN 2763-9061.
