Dubins Curves for 3D Multi-Vehicle Path Planning using Spline Interpolation

Abstract

This paper proposes a spline interpolation method to map 2D Dubins paths into 3D for multiple Autonomous Underwater Vehicles (AUVs) to visit multiple targets. The multitarget assignment and path planning problem is first modeled as a multiple Traveling Salesmen Problem (mTSP) and a three-step algorithm is used to solve the NP-hard integer programming problem with affordable computational complexity. Step 1 uses the Genetic Algorithm (GA) with the 3D Euclidean distances as the fitness function to assign multiple tasks to multiple AUVs; Step 2 designs the 2D Dubins paths for each AUV target sequence; and Step 3 maps the 2D Dubins paths to 3D paths via cubic spline interpolaten. Finally, potential collision is detected among the resulting paths of the multiple AUVs and paths are discarded if any AUV is within the close vincinity of another AUV at any time. The simulation results show that the proposed algorithm yields shortest Dubnis paths most of the time and gaurantees the G1 continuity. The probability of collision is very small if the multiple AUVs start the mission at the geometric center of the multiple targets.

Meeting Name

OCEANS '17 MTS/IEEE Anchorage (2017, Sep. 18-21, Anchorage, AK)

Department(s)

Electrical and Computer Engineering

Keywords and Phrases

Anchorages (foundations); Genetic algorithms; Integer programming; Interpolation; Motion planning; AUVs; Euclidean distance; Integer programming problems; Multiple autonomous underwater vehicles; Path planning problems; Probability of collisions; Spline interpolation; Traveling salesman; Autonomous underwater vehicles; Genetic algorithm

International Standard Book Number (ISBN)

978-1-5090-6429-8

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2017 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 Sep 2017

Link to Full Text

Share

 
COinS