TY - GEN
T1 - Global Path Planning for USV Waypoint Guidance System Using Dynamic Programming
AU - Gamayanti, Nurlita
AU - Kadir, Rusdhianto Effendi Abdul
AU - Alkaff, Abdullah
N1 - Publisher Copyright:
© 2020 IEEE.
PY - 2020/7
Y1 - 2020/7
N2 - An analytical method for finding the optimal route to be followed by an Unmanned Surface Vehicle (USV) is proposed. The proposed algorithm aims to generate a collision-free route with minimum travel time in reaching some given waypoints. The method comprises of two algorithms. First, a grid map-based algorithm for static obstacle avoidance by forming sub-waypoints at the tangent angle of the obstacle using the weight of each obstacle to generate feasible paths. The obstacle weights are determined based on whether the neighboring cells are also obstacles or not. Second, the dynamic programming-based path planning optimization to find several shortest paths among those feasible paths. The USV is modeled in a Six-Degree-of-Freedom (6-DOF) equations of motion whose parameters are determined based on a physical model USV. Simulation results are presented to show the method successfully guides the USV without crashing into obstacles. As shown, due to the USV's limited maneuverability, the shortest path obtained using dynamic programming is not always the path with the shortest travel distance, and the shortest travel distance does not guarantee the shortest travel time either. As a comparison, a genetic algorithm has been conducted to produce the optimal route. Simulation results show that the proposed algorithm produces an 11.6% reduction in travel time and a 99.55% reduction in computing time than the genetic algorithm.
AB - An analytical method for finding the optimal route to be followed by an Unmanned Surface Vehicle (USV) is proposed. The proposed algorithm aims to generate a collision-free route with minimum travel time in reaching some given waypoints. The method comprises of two algorithms. First, a grid map-based algorithm for static obstacle avoidance by forming sub-waypoints at the tangent angle of the obstacle using the weight of each obstacle to generate feasible paths. The obstacle weights are determined based on whether the neighboring cells are also obstacles or not. Second, the dynamic programming-based path planning optimization to find several shortest paths among those feasible paths. The USV is modeled in a Six-Degree-of-Freedom (6-DOF) equations of motion whose parameters are determined based on a physical model USV. Simulation results are presented to show the method successfully guides the USV without crashing into obstacles. As shown, due to the USV's limited maneuverability, the shortest path obtained using dynamic programming is not always the path with the shortest travel distance, and the shortest travel distance does not guarantee the shortest travel time either. As a comparison, a genetic algorithm has been conducted to produce the optimal route. Simulation results show that the proposed algorithm produces an 11.6% reduction in travel time and a 99.55% reduction in computing time than the genetic algorithm.
KW - dynamic programming
KW - path planning
KW - static obstacle
KW - travel time
KW - unmanned surface vehicle
UR - http://www.scopus.com/inward/record.url?scp=85091693333&partnerID=8YFLogxK
U2 - 10.1109/ISITIA49792.2020.9163712
DO - 10.1109/ISITIA49792.2020.9163712
M3 - Conference contribution
AN - SCOPUS:85091693333
T3 - Proceedings - 2020 International Seminar on Intelligent Technology and Its Application: Humanification of Reliable Intelligent Systems, ISITIA 2020
SP - 248
EP - 253
BT - Proceedings - 2020 International Seminar on Intelligent Technology and Its Application
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2020 International Seminar on Intelligent Technology and Its Application, ISITIA 2020
Y2 - 22 July 2020 through 23 July 2020
ER -