基于贪心蚁群算法的无人水面艇全局路径规划

为解决无人水面艇(unmanned surface vessel,USV)在地型较复杂小型水域内的全局路径规划问题,提出一种以贪心算法、蚁群算法、栅格法建模为基础,通过加入双向搜索算法来解决传统贪心算法搜索时易陷入局部最优解等问题的贪心蚁群算法。该算法利用贪心算法规划基础路线,利用蚁群算法的信息素机制摆脱局部收敛状态,并通过双向搜索算法降低局部收敛概率。仿真结果表明:该算法搜索时间较传统蚁群算法减少70%以上,迭代次数较传统蚁群算法减少约85%;该算法在处理USV的全局路径规划问题中具有一定的有效性、合理性。

Global path planning for unmanned surface vessels based on greedy ant colony algorithm

In order to solve the global path planning problem for unmanned surface vessels (USVs) in small waters with complex terrain, a greedy ant colony algorithm is proposed, where the greedy algorithm, the ant colony algorithm and the grid method modeling are based on, and the two way search algorithm is added to solve the problem that the traditional greedy algorithm is easy to fall into the local optimal solution when searching. In the algorithm, the greedy algorithm is used to plan the basic route, the pheromone mechanism of the ant colony algorithm is used to get out of the local convergence state, and the two way search algorithm is used to reduce the local convergence probability. The simulation results show that, the search time of the algorithm is reduced by more than 70% compared with the traditional ant colony algorithm, the number of iterations is reduced by about 85% compared with the traditional ant colony algorithm, and the algorithm is effective and reasonable in dealing with the USV global path planning problem.