Hardware design of a fast, parallel Random Tree path planner

Xiao, Size, Postula, Adam and Bergmann, Neil (2016). Hardware design of a fast, parallel Random Tree path planner. In: 2015 International Conference on Field Programmable Technology, FPT 2015. International Conference on Field Programmable Technology, FPT 2015, Queenstown, New Zealand, (204-207). 7-9 December 2015. doi:10.1109/FPT.2015.7393151


Author Xiao, Size
Postula, Adam
Bergmann, Neil
Title of paper Hardware design of a fast, parallel Random Tree path planner
Conference name International Conference on Field Programmable Technology, FPT 2015
Conference location Queenstown, New Zealand
Conference dates 7-9 December 2015
Convener IEEE
Proceedings title 2015 International Conference on Field Programmable Technology, FPT 2015
Journal name 2015 International Conference on Field Programmable Technology, FPT 2015
Place of Publication Piscataway, NJ, United States
Publisher Institute of Electrical and Electronics Engineers
Publication Year 2016
Year available 2016
Sub-type Fully published paper
DOI 10.1109/FPT.2015.7393151
Open Access Status Not Open Access
ISBN 9781467390910
Start page 204
End page 207
Total pages 4
Collection year 2017
Language eng
Abstract/Summary The Rapidly-Exploring Random Trees (RRT) method has been proved successful and efficient for solving path planning problems. Most recent work focuses on optimizing RRT itself and presents the results achieved from software. In this paper a dedicated hardware architecture for FPGA implementation of Rapidly-Exploring Random Tree (RRT) path planning is developed. The proposed architecture fully takes advantage of FPGAs' natural parallel computing ability. The near neighbour (NN) search speed is improved by splitting the whole search space into several sub-spaces; correspondingly the tree nodes are stored in separate block RAMs and each Block RAM owns its independent traversal query module to enhance the memory throughput. Furthermore, to speed up the space exploration, each single path planning unit consists of two cooperating RRT modules which grow trees from each end of the path. One complete path planner involves several path planning units which work in a parallel master-slave mode to increase the probability of obtaining available path. Implementation in a 2D environment shows good path planning performance of the hardware design, with a 30x speed improvement compared to a PC implementation.
Keyword Rapidly-Exploring Random Trees (RRT)
Near neighbour (NN) search speed
Path planning problems
UAV (Unmanned Aerial Vehicle)
Algorithm
Trajectory planning algorithm
Q-Index Code E1
Q-Index Status Provisional Code
Institutional Status UQ

 
Versions
Version Filter Type
Citation counts: Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Tue, 03 May 2016, 01:50:14 EST by System User on behalf of Learning and Research Services (UQ Library)