A Heuristic Method for Route Calculation with Obstacle Avoidance in Digital Map Web Services
Abstract
Computing a route between two points that deviate from an obstacle is a typical activity of geoprocessing systems, but that is not supported by services of digital map in the web due to the high computational cost. We propose here an approach to the problem that uses conjointly the shortest route provided by these services and heuristic methods based on visibility algorithms. This method is inspired in route planning for robots what can suggest alternative waypoints to force the contour of the obstacles identified. A comparative assessment of different scenarios indicates the feasibility of the method and its potential for improvement.References
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.
Published
2011-07-19
How to Cite
BASSO, Victor E. D.; FURTADO, Vasco.
A Heuristic Method for Route Calculation with Obstacle Avoidance in Digital Map Web Services. In: NATIONAL MEETING ON ARTIFICIAL AND COMPUTATIONAL INTELLIGENCE (ENIAC), 8. , 2011, Natal/RN.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2011
.
p. 275-286.
ISSN 2763-9061.
