基于改进Maklink图的多点遍历路径规划算法  

Multi-point Traversal Task Path Planning Based on Improved Maklink Graph

作　　者：郭浩年 彭星光[1] GUO Haonian;PENG Xingguang(School of Marine Science and Technology,Northwestern Polytechnical University,Xi’an710114,China)

机构地区：[1]西北工业大学航海学院,西安710114

出　　处：《无人系统技术》2024年第4期84-94,共11页Unmanned Systems Technology

基　　金：国家自然科学基金(62076203)。

摘　　要：针对无人设备在执行如定点巡逻任务和货物搬运作业时,需要解决多点遍历和避障路径规划的问题,开展了一种基于改进Maklink图的全局路径规划算法研究,优化避障作业路径。首先,建立改进Maklink图作为空间模型,简化作业空间;随后,设计一种改进蚁群算法在上述空间模型内规划路径,算法采用针对多点遍历的启发式函数、禁忌搜索、局部最优处理机制和精英个体保留与额外进化策略;最后,对比实验证明了所提算法在不同任务环境下的有效性,具有更强的寻优能力和更好的稳定性,在10个案例中,相对基于概率路线图的算法和传统蚁群算法,路径长度优化提升最大分别可达21.13%和49.31%,稳定性提升最大分别可达99.56%和99.82%。When unmanned equipment performs tasks such as fixed-point patrol and cargo handling,it is necessary to solve the problem of multi-point traversal with obstacle avoidance path planning.This paper studies a global path planning algorithm based on improved Maklink graph to optimize the obstacle avoidance path with strong stability.Firstly,improved Maklink graph is established as the space model to simplify the work space.Then,an improved ant colony algorithm is designed to plan the path in the above space model.The algorithm adopts the heuristic function for multi-point traversal,tabu search,local optimal processing mechanism and elite individual retention and additional evolution strategy.Finally,comparative experiments show that the proposed algorithm is effective,has better optimization ability and stronger stability in different task environments.Compared with the probabilistic roadmap-based algorithm and the traditional ant colony algorithm in 10 cases,the improvement in path length optimization can reach 21.13%and 49.31%maximally,and the stability improvement can reach 99.56%and 99.82%maximally.

关 键 词：无人设备 多点遍历 避障 路径规划 Maklink图 蚁群算法 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置]