Publication Date:
2014-02-22
Description:
In Euclidean and/or $lambda$ -geometry planes with obstacles, the shortest path problem involves determining the shortest path between a source and a destination. There are three different approaches to solve this problem in the Euclidean plane: roadmaps, cell decomposition, and potential field. In the roadmaps approach, a visibility graph is considered to be one of the most widely used methods. In this paper, we present a novel method based on the concepts of Delaunay triangulation, an improved Dijkstra algorithm and the Fermat points to construct a reduced visibility graph that can obtain the near-shortest path in a very short amount of computational time. The length of path obtained using our algorithm is the shortest in comparison to the other fastest algorithms with $O(nlog n)$ time complexity. The proposed fast algorithm is especially suitable for those applications which require determining the shortest connectivity between points in the Euclidean plane, such as the robot arm path planning and motion planning for a vehicle.
Print ISSN:
1083-4435
Electronic ISSN:
1941-014X
Topics:
Electrical Engineering, Measurement and Control Technology
,
Mechanical Engineering, Materials Science, Production Engineering, Mining and Metallurgy, Traffic Engineering, Precision Mechanics
,
Technology
