移动机器人多目标搜寻的D*-蚁群融合算法

Multi-objective Search Based on D*-ant Colony Fusion Algorithm

针对在中小范围内移动机器人以最短遍历找到所有目标,同时也要使得两两目标之间的路径最优的问题,提出一种基于改进D*算法融合蚁群算法的方案.尽管蚁群算法相对于其他优化算法或启发式算法在解决TSP问题上有较好表现,但其在路径规划上耗时长、路径质量较差;而对于原始D*算法路径转角大、转角次数多、较复杂地图下规划量大、生成路径贴近障碍物且多目标搜寻中无法实现最短遍历等缺点,通过改进原始D*算法的启发函数和子节点扩展方式,将蚁群算法的评价函数用改进D*算法来计算.基于格栅法建立地图模型,在不同复杂度的地图选取多个目标进行对比仿真实验,结果证明了该融合算法的高效性和针对不同环境的适应性.

Aiming at the problem that mobile robots can find all targets with the shortest traversal in the small and medium range,and at the same time make the path between the two targets optimal,a scheme based on improved D* algorithm fusion ant colony algorithm is proposed. Although ant colony algorithm has better performance than other optimization algorithms or heuristic algorithms in solving TSP problems,ant colony algorithm takes a long time in path planning and has poor path quality,while traditional D* algorithm has many shortcomings,such as large turning angle,many turning times,large amount of planning under complex maps,generating path close to obstacles and unable to achieve the shortest traversal in multi-objective search. By improving the heuristic function and sub-node expansion of the original D* algorithm,the evaluation function of the ant colony algorithm is calculated using the improved D* algorithm. In this paper,the map model is built based on the grid method,and several targets are selected on maps with different complexity to carry out comparative simulation experiments. The results show that the proposed fusion algorithm is effective and adaptable to different environments.