Global Path Planning for USV Waypoint Guidance System Using Dynamic Programming

Nurlita Gamayanti, Rusdhianto Effendi Abdul Kadir, Abdullah Alkaff

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationProceedings - 2020 International Seminar on Intelligent Technology and Its Application
Subtitle of host publicationHumanification of Reliable Intelligent Systems, ISITIA 2020
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages248-253
Number of pages6
ISBN (Electronic)9781728174136
DOIs
Publication statusPublished - Jul 2020
Event2020 International Seminar on Intelligent Technology and Its Application, ISITIA 2020 - Virtual, Online, Indonesia
Duration: 22 Jul 202023 Jul 2020

Publication series

NameProceedings - 2020 International Seminar on Intelligent Technology and Its Application: Humanification of Reliable Intelligent Systems, ISITIA 2020

Conference

Conference2020 International Seminar on Intelligent Technology and Its Application, ISITIA 2020
Country/TerritoryIndonesia
CityVirtual, Online
Period22/07/2023/07/20

Keywords

  • dynamic programming
  • path planning
  • static obstacle
  • travel time
  • unmanned surface vehicle

Fingerprint

Dive into the research topics of 'Global Path Planning for USV Waypoint Guidance System Using Dynamic Programming'. Together they form a unique fingerprint.

Cite this