Keywords and Phrases
3D Dubins curve; Autonomous underwater vehicles; Geometric continuity; Multiple traveling salesman problem; Path planning; Target assignment
"This thesis proposes a unified algorithm for target assignment and path planning in 3D space for multiple Autonomous Underwater Vehicles (AUVs) to visit multiple targets. The multi-target assignment and path planning problem is modeled as a multiple Traveling Salesmen Problem (mTSP) and is usually solved by two separate algorithms: the multiple task assignment problem is first solved by the Genetic Algorithm (GA) using Euclidean distances between the targets; then the 3D path planning problem is solved for each assignment by selecting Dubins curves or other continuity curves. In contrast, this paper embeds the 3D Dubins curve selection into the target assignment step and uses the true path lengths rather than Euclidean distances as the fitness value of the GA. The unified algorithm is implemented by three functions: Function 1 designs a 3D Dubins path for a given target assignment sequence and given incoming-outgoing angles by an innovative rotation method extended from the well-known 2D Dubins curves; Function 2 uses the back-propagation algorithm to choose the shortest path among all possible incoming-outgoing angle combinations for a given target assignment sequence; Function 3 uses the true lengths of the 3D Dubins curves in the Genetic Algorithm (GA) to assign target sequence to multiple AUVs. Computer simulations demonstrate that the proposed algorithm provides better G2 continuity in 3D space than the existing linear or spline interpolation methods. The unified algorithm solves the NP-hard integer programming problem with an affordable computational complexity"--Abstract, page iii.
Zheng, Y. Rosa
Electrical and Computer Engineering
M.S. in Electrical Engineering
National Science Foundation (U.S.)
Wilkens Missouri Endowment
Missouri University of Science and Technology
ix, 33 pages
© 2018 Yiheng Wang, All rights reserved.
Thesis - Open Access
Electronic OCLC #
Wang, Yiheng, "3D Dubins curves for multi-vehicle path planning" (2018). Masters Theses. 7839.