基于跳点优化蚁群算法的菠萝田间导航路径规划

Navigation Path Planning of Pineapple Planting Field Based on Jump Point Optimized Ant Colony Algorithm

摘要:

针对传统蚁群算法在农机导航路径规划中存在前期搜索盲目、死锁、收敛速度慢、收敛路径质量低的问题，本文提出基于跳点优化蚁群算法(Jump point optimized ant colony algorithm, JPOACO)的路径规划方法。首先，使用优化跳点搜索算法对地图进行预处理，获得简化跳点；其次，通过简化跳点对栅格地图进行信息素初始化，以加强简化跳点的引导能力和减少前期盲目搜索；接着，设计蚂蚁死亡惩罚机制，以降低陷入死锁蚂蚁走过路径的信息素，减少死锁问题的发生；再者，通过重新设计启发式信息函数并引入分级式信息素因子改进状态转移概率函数，以提高收敛速度，缩短路径长度；最后，采用路径优化策略删减不必要路径节点，以进一步缩短路径长度、提升平滑度，提高路径质量。仿真结果表明,在简单环境中，JPOACO算法求得的路径长度较传统蚁群算法和另一种优化蚁群算法短约22.6%和2.0%，收敛迭代次数、收敛时间分别减少约77.0%、77.5%和49.3%、87.8%，零死亡迭代次数和零死亡时间较后者减少约19.5%和80.5%；在复杂菠萝种植环境中，JPOACO算法较传统蚁群算法和另一种优化蚁群算法求得的路径长度短16.6%和4.7%，收敛迭代次数、收敛时间分别减少约77.1%、17.4%和73.7%、47.4%，零死亡迭代次数和零死亡时间较后者减少约34.3%和58.2%，表明本文算法具有较高的适用性和可行性。

Abstract:

In order to solve the problems of traditional ant colony algorithm in agricultural machinery path planning, such as initial blind searches, deadlock, slow convergence rate, and low-quality converged path, a path planning method based on jump point optimized ant colony algorithm (JPOACO) was proposed. Initially, the jump point search optimization algorithm was employed to preprocess the map, thereby obtaining simplified jump points. These simplified jump points were utilized for pheromone initializing on the grid map, to enhance the guiding capability of simplified jump points and reduce blind search in the early stages. Secondly, a punish mechanism for dead ant was designed to lower the pheromone levels on paths traversed by ants which fell into deadlock, and to decrease the occurrence of deadlocks. Furthermore, the heuristic information function was redesigned and a hierarchical pheromone factor was introduced to enhance convergence speed and shorten the converged path length. Finally, a path optimization strategy was applied to eliminate unnecessary path nodes, further reduce converged path length and improve smoothness, ultimately improve the converged path quality. Simulation results showed that in simple environments, the JPOACO algorithm reduced path length by about 22.6% and 2% in comparison with traditional ant colony algorithm and other optimized ant colony algorithms, respectively. It also decreased convergence number and convergence time by about 77.0%, 77.5% and 49.3%, 87.8%, respectively. The zero-death number and zero-death time were reduced by about 19.5% and 80.5% in comparison with the latter. In complex pineapple planting environments, JPOACO achieved a path length reduction of 16.6% and 4.7%, decreased convergence number and convergence time by about 77.1%, 17.4% and 73.7%, 47.4%, respectively. The zerodeath number and zerodeath time were reduced by about 34.3% and 58.2% in comparison with the latter. These results indicated that the JPOACO algorithm was highly feasible and applicable.