Voronoi-Visibility Roadmap-based Path Planning Algorithm for Unmanned Surface Vehicles

In this paper, a novel Voronoi-Visibility (VV) path planning algorithm, which integrates the merits of a Voronoi diagram and a Visibility graph, is proposed for solving the Unmanned Surface Vehicle (USV) path planning problem. The VM (Voronoi shortest path refined by Minimising the number of waypoin...

Full description

Saved in:
Bibliographic Details
Published in:Journal of navigation 2019-07, Vol.72 (4), p.850-874
Main Authors: Niu, Hanlin, Savvaris, Al, Tsourdos, Antonios, Ji, Ze
Format: Article
Language:English
Subjects:
Algorithms
Computational efficiency
Computing time
Control algorithms
Datasets
Decomposition
Efficiency
Literature reviews
Missions
Path planning
Planning
Shortest path planning
Surface vehicles
Unmanned vehicles
Visibility
Voronoi graphs
Waypoints
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, a novel Voronoi-Visibility (VV) path planning algorithm, which integrates the merits of a Voronoi diagram and a Visibility graph, is proposed for solving the Unmanned Surface Vehicle (USV) path planning problem. The VM (Voronoi shortest path refined by Minimising the number of waypoints) algorithm was applied for performance comparison. The VV and VM algorithms were compared in ten Singapore Strait missions and five Croatian missions. To test the computational time, a high-resolution, large spatial dataset was used. It was demonstrated that the proposed algorithm not only improved the quality of the Voronoi shortest path but also maintained the computational efficiency of the Voronoi diagram in dealing with different geographical scenarios, while also keeping the USV at a configurable clearance distance c from coastlines. Quantitative results were generated by comparing the Voronoi, VM and VV algorithms in 2,000 randomly generated missions using the Singapore dataset.
ISSN:0373-4633
1469-7785
DOI:10.1017/S0373463318001005