Masters Theses

Yiheng Wang

Keywords and Phrases

3D Dubins curve; Autonomous underwater vehicles; Geometric continuity; Multiple traveling salesman problem; Path planning; Target assignment

Abstract

"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.

Advisor(s)

Zheng, Y. Rosa

Committee Member(s)

Pommerenke, David
Acar, Levent

Department(s)

Electrical and Computer Engineering

Degree Name

M.S. in Electrical Engineering

Sponsor(s)

National Science Foundation (U.S.)
Wilkens Missouri Endowment

Comments

The work is supported in part by National Science Foundation under grant #CPS-1646548 and in part by the Wilkens Missouri Telecommunication Chair endowment.

Publisher

Missouri University of Science and Technology

Publication Date

Fall 2018

Pagination

ix, 33 pages

Note about bibliography

Includes bibliographical references (pages 31-32).

Rights

© 2018 Yiheng Wang, All rights reserved.

Document Type

Thesis - Open Access

File Type

text

Language

English

Thesis Number

T 11447

Electronic OCLC #

1084480860

Download

Share

 
COinS