Obstacle-avoiding shortest path derivation in a multicore computing environment

摘要

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. (C) 2015 Elsevier Ltd. All rights reserved.