上海交通大学学报

上海交通大学学报

• •    下一篇

基于改进多目标进化算法的栅格地图路径规划（网络首发）

  

  1. 1. 上海交通大学自动化系；2. 系统控制与信息处理教育部重点实验室；3. 航空工业沈阳飞机设计研究所
  • 基金资助:
    航空科学基金(20220001057001)资助项目；

An ImprovedMulti-Objective Evolutionary Algorithm for Grid Map Path Planning

  1. (1. Department of Automation, Shanghai Jiao Tong University, Shanghai, 200240, China; 2. Key Laboratory of System Control and Information Processing of the Ministry of Education, Shanghai, 200240, China;3. Shenyang Aircraft Design and Research Institute, Shenyang 110035, China)

PDF (PC)

35

摘要： 大范围栅格地图的多目标路径规划具有节点规模大、目标数量多的特征，现有算法难以平衡求解帕累托前沿的速度与质量，研究基于帕累托前沿的高效优化算法具有一定的理论意义。首先，提出基于代价向量的加权图建模方法，并据此研究解决大规模问题的优化算法，相比图搜索算法显著节约时间成本。其次，针对帕累托前沿求解质量低的问题，提出一种改进多目标进化算法，包含新的初始化策略，基于角度和偏移密度的思想设计个体和环境选择策略，改进措施综合考虑了种群多样性和收敛性，提升了求解效率。最后，通过仿真实验对比，验证了改进算法的有效性。

关键词: 栅格地图, 多目标路径规划, 多目标进化算法, 帕累托前沿

Abstract: Multi-objective path planning of large-scale grid maps has large nodes and a large number of targets, and it’s difficult for existing algorithms to balance the speed and quality of getting Pareto front. Therefore, it has certain theoretical significance to study efficient optimization algorithms based on Pareto front. Firstly, the weighted graph modeling method based on cost vectors is proposed, and optimization algorithms for solving large-scale problems are studied accordingly, which significantly saves time and costs compared to graph search algorithms. Secondly, in response to the problem of low quality based on Pareto front solutions, an improved multi-objective evolutionary algorithm is proposed, which includes a new initialization strategy. With the ideas of angle and shift-based density, individual and environment selection strategies are designed. The improvement measures comprehensively consider population diversity and convergence, improving the solving efficiency. Finally, the effectiveness of the improved algorithm was verified through simulation experiments.

Key words: grid map, multi-objective path planning, multi-objective evolutionary algorithm, Pareto front

中图分类号: