Autonomous Surface Vehicle energy-efficient and reward-based path planning using Particle Swarm Optimization and Visibility Graphs
Autonomous Surface Vehicle energy-efficient and reward-based path planning using Particle Swarm Optimization and Visibility Graphs
复制标题
DOI：
10.1016/j.apor.2022.103125
复制
发表时间：
2022-03-23
影响因子：
4.3
通讯作者：
Carrillo, Luis Rodolfo Garcia
中科院分区：
文献类型：
--
作者：
Krell, Evan;King, Scott A.;Carrillo, Luis Rodolfo Garcia
自主水面车辆需要路径规划来在复杂的海岸线和时空环境力(如水流)之间导航。基于水流预报，执行路径规划以生成到目标目的地的节能路线。确定性算法，如Dijkstra的最短路径优先算法，能够生成最优解，但随着搜索空间的大小呈指数级增长。在沿海航行中，复杂的海岸线和力量需要高分辨率的搜索空间，因此传统的规划算法将需要大量的时间。像粒子群优化(PSO)这样的元启发式算法牺牲了保证的最优性来大大减少计算量。然而，存在过早收敛到局部最优解的风险。在展示了PSO很难可靠地产生近最优解之后，我们使用可见图(VGS)来初始化PSO解群体。我们证明，这大大提高了PSO的能力，以可靠地实现与Dijkstra竞争的解决方案。我们还引入了基于机会报酬的规划的概念，并将粒子群算法应用于该规划问题。如果一艘船正在航行到目标目的地，我们建议利用附近的采样机会来增加任务的科学回报。粒子群算法用于优化路径，平衡路径效率和回报。在整个搜索空间中使用复杂的奖励值分配，PSO有很多机会陷入局部最优。同样，我们使用VGS来初始化PSO种群，我们证明这提高了解的一致性，同时提高了回报和效率。我们建议使用VGS来生成初始PSO种群，并证明了该组合对两个复杂的海洋路径规划问题的路径规划是有效的。
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.