Obstacle-avoiding shortest path derivation in a multicore computing environment

• Euclidean shortest path is essential information for spatial analysis, location modeling, and wayfinding.
• Derivation of ESP in continuous space with numerous obstacles is hard task, while existing approaches lack efficiency.
• Parallel Convex Graph algorithm enables efficient ESP derivation by spatial approach and high performance computing approach.
• A notion of convex hull and shortest path spatial filtering technique guarantee derivation of the ESP with minimal effort.
• Parallelization of computationally intensive spatial operations required for ESP derivation enables real time path derivation.

The best obstacle avoiding path in continuous space, referred to as the Euclidean shortest path, is important for spatial analysis, location modeling and wayfinding tasks. This problem has received much attention in the literature given its practical application, and several solution techniques have been proposed. However, existing approaches are limited in their ability to support real time analysis in big data environments. In this research a multicore computing approach is developed that exploits spatial knowledge through the use of geographic information system functionality to efficiently construct an optimal shortest path. The approach utilizes the notion of a convex hull for iteratively evaluating obstacles and constructing pathways. Further, the approach is capable of incrementally improving bounds, made possible through parallel processing. Wayfinding routes that avoid buildings and other obstacles to travel are derived and discussed.