A novel scalable parallel algorithm for finding optimal paths over heterogeneous terrain
Abstract
The area of path planning has received a great deal of attention recently. Algorithms are required that can deliver optimal paths for robots to take over homogeneous or non-homogeneous terrain. Optimal paths may be those that involve the shortest distance travelled, the least number of turns or the least number of ascents and descents. The often highly complex nature of terrains and the necessity for realtime solutions have lead to a requirement for the development of parallel algorithms. Such problems have been notoriously difficult to parallelise efficiently; indeed it has been said that an efficiency of 25-60% should be considered a success. In this paper we present a parallel algorithm for finding optimal paths over non-homogeneous terrain that demonstrates superlinear speed-up.Citation
Maple, C., Hitchcock, J. (2005) "A novel scalable parallel algorithm for finding optimal paths over heterogeneous terrain", Proceedings of the Ninth International Conference on Information Visualisation (IV’05), 664-669Additional Links
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1509145Type
Conference papers, meetings and proceedingsLanguage
enISSN
1550-6037ISBN
0769523978ae974a485f413a2113503eed53cd6c53
10.1109/IV.2005.12