Dubins Curves for 3D Multi-Vehicle Path Planning using Spline Interpolation
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.
J. Wang et al., "Dubins Curves for 3D Multi-Vehicle Path Planning using Spline Interpolation," OCEANS 2017 - Anchorage, Institute of Electrical and Electronics Engineers (IEEE), Sep 2017.
OCEANS '17 MTS/IEEE Anchorage(2017, Sep. 18-21, Anchorage, AK)
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)
Article - Conference proceedings
© 2017 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.