Long-Distance Path Planning for Unmanned Surface Vehicles in Complex Marine Environment

Many missions require unmanned surface vehicles to operate in complex environments over large distances. Marine environments are dynamic in nature and change over time as a result of tides, weather, and environmental restrictions. As a result, the available free traversal space for a marine vehicle in the given map can change over time. This requires the marine vehicle to dynamically generate and update the traversal map to represent the free space. This paper presents techniques for speeding up A* search on the nodes of visibility graphs. We use a quadtree representation of the marine environment to enable the algorithm to efficiently compute the nodes of the visibility graphs. We have developed an admissible heuristic that considers the large islands while estimating cost-to-go, and provide better estimates than a Euclidean distance-based heuristic. Due to the large size of the marine environment, the branching factor of the search tree can become large and reduce the efficiency of the path planner. We have developed an approach that focuses the search by only considering the child nodes lying in the local region around each node. Our experiments demonstrate that by focusing the search, we can reduce the computational time without significantly sacrificing the optimality of the computed path. We also present an extension to the algorithm for handling dynamic environments with time-varying free spaces. We incorporated the depth charts developed by the National Oceanic and Atmospheric Administration (NOAA), Silver Spring, MD, USA, along with the tide predictions to estimate the time-varying free space that can be used by the planner.