Autonomous Surface Vehicle energy-efficient and reward-based path planning using Particle Swarm Optimization and Visibility Graphs

Autonomous Surface Vehicles require path planning to navigate among complex shorelines and spatio-temporal environmental forces such as water currents. Path planning is performed to generate an energy-efficient route to a goal destination based on water current forecasts. Deterministic algorithms such as Dijkstra's Shortest Path First are able to generate an optimal solution, but scale exponentially with the size of the search space. In coastal navigation, the complex shorelines and forces require high resolution search spaces such that classical planning algorithms will require substantial time. Metaheuristic algorithms such as Particle Swarm Optimization (PSO) sacrifice guaranteed optimality to substantially reduce computation. However, there is a risk of premature convergence to local optima. After showing PSO struggling to reliably produce near-optimal solutions, we use Visibility Graphs (VGs) to initialize the PSO solution population. We demonstrate that this substantially improves PSO's ability to reliably achieve solutions that are competitive with Dijkstra. We also introduce the concept of opportunistic reward-based planning, and apply PSO to this planning problem. If a vessel is navigating to a goal destination, we propose taking advantage of nearby sampling opportunities to increase the scientific return of the mission. PSO is used to optimize routes that balance path efficiency and reward. Using a complex assignment of reward values across the search space, there are numerous opportunities for PSO to get stuck in local optima. Again, we use VGs to initialize the PSO population which we demonstrate increases solution consistency while improving both the reward and efficiency. We propose using VGs to generate an initial PSO population and demonstrate that the combination efficiently plans routes for two complex marine path planning problems.

Automated summary

Path planning for Autonomous Surface Vehicles in complex shorelines and spatio-temporal environmental forces is a challenging task. Deterministic algorithms provide optimal solutions but are computationally expensive. Metaheuristic algorithms sacrifice optimality for reduced computation but can converge to local optima. This paper proposes using Visibility Graphs (VGs) to initialize the population of a Particle Swarm Optimization (PSO) algorithm, significantly improving its reliability and competitiveness with deterministic algorithms. The concept of opportunistic reward-based planning is also introduced, with VGs used to enhance both reward and efficiency in PSO. The combination of VGs and PSO efficiently plans routes for complex marine path planning problems.