求解多目标点路径规划问题的离散头脑风暴算法

Discrete brainstorm optimization algorithm for solving multi-target route planning problems

为保证移动机器人以最短路径遍历多目标点,该文提出一种基于离散头脑风暴的多目标点路径规划算法。首先,考虑障碍物对路径规划的影响,将目标点间的最短避障距离作为评判依据,提高规划路径合理性。其次,针对传统离散头脑风暴算法在解决组合类优化问题时提前陷入局部最优的问题,提出一种启发式自适应路径优化策略,通过设计与迭代次数相关的适应度选择函数以及改进启发式交叉算子,增加路径多样性和提高算法收敛速度。基于栅格法建立地图模型,在不同环境地图中选取多个目标进行对比仿真,验证所提算法的有效性以及对不同环境的适应性。

In this paper, a multi-target point path planning algorithm is proposed based on discrete brainstorm optimization(DBSO) to guarantee that a mobile robot can traverse multiple target points with the shortest path. First, considering the influence of obstacles on path planning, the shortest obstacle avoidance distance between target points is used as the judgment basis to improve rationality of the planned path. Secondly, the traditional discrete brainstorming algorithm will fall into local optimum in advance when solving combinatorial optimization problems. Therefore, a heuristic adaptive path optimization strategy is proposed. It increases path diversity and improves convergence speed of the algorithm by designing a fitness selection function related to the number of iterations and improving the heuristic crossover operator. A map model is established based on the grid method, and multiple targets are selected in different environmental maps for comparison and simulation to verify effectiveness of the proposed algorithm and its adaptability to different environments.