Premium
Navigating free‐floating minefields via time‐varying Voronoi graphs
Author(s) -
Richards Christopher,
Mehta Dinesh
Publication year - 2019
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21860
Subject(s) - voronoi diagram , computer science , port (circuit theory) , container (type theory) , parametric statistics , variable (mathematics) , operations research , mathematics , engineering , statistics , mechanical engineering , mathematical analysis , geometry , electrical engineering
Despite their illegality, untethered free‐floating naval mines are increasingly employed as part of maritime area‐denial operations. By ignoring international treaties, these mines require less effort to acquire and deploy, and result in a far more dynamic‐threat environment. In order to assist commanders during breach operation planning, we develop several algorithms that generate a minimum‐risk journey through a field of drifting mines. Using Voronoi graphs to capture a series of static snapshots of the operational area, we present a practical methodology for building a fully connected time‐varying graph G V ℰ . Vertices V are defined as specific times and locations, and edges ℰ define the continuous movement of a ship with simple parametric equations. The length, acceleration and risk of each edge is calculated and employed by a threat‐additive A * search to quickly find a plausible, minimum‐risk journey through a given minefield within a specific time frame. Using real‐world data for a modern‐day port and minefields of variable density, we find navigable paths that incur acceptable risk in less than 2 minutes on average. We also introduce several methods for reducing the size of G V ℰand the time required for its generation.