Please wait a minute...
浙江大学学报(工学版)  2021, Vol. 55 Issue (10): 1806-1814    DOI: 10.3785/j.issn.1008-973X.2021.10.002
计算机技术     
高温混合障碍空间中的移动机器人路径规划
吴敬理(),伊国栋*(),裘乐淼,张树有
浙江大学 流体动力与机电系统国家重点实验室,浙江 杭州 310027
Path planning of mobile robots in mixed obstacle space with high temperature
Jing-li WU(),Guo-dong YI*(),Le-miao QIU,Shu-you ZHANG
State Key Laboratory of Fluid Power and Electromechanical Systems, Zhejiang University, Hangzhou 310027, China
 全文: PDF(982 KB)   HTML
摘要:

为了解决高温场景中移动机器人全局路径规划所面临的安全与效率问题,提出高温热源虚拟障碍的定义,建立混合障碍空间模型,将高温场景中的路径规划问题转化为高温混合障碍空间中考虑路径温度代价和长度代价的多目标优化问题. 改进NSGA-Ⅱ算法,通过选取优秀非可行解扩展种群,提高了种群多样性和进化效率,提出新的交叉和变异概率计算方法. 根据种群进化进程和个体代价函数值调整概率,实现了种群前期搜索能力和后期收敛性的平衡. 仿真所得的最优路径结果表明,该改进算法的路径长度代价虽然比原算法和其他改进算法略有增加,但温度代价大幅降低,更有效地避免了陷入局部最优.

关键词: 高温场景虚拟障碍混合障碍空间路径规划NSGA-Ⅱ算法    
Abstract:

The definition of virtual obstacles for high temperature heat sources was proposed in order to solve the safety and efficiency problems faced by the global path planning of mobile robots in high temperature scenarios. A hybrid obstacle space model was established. The path planning problem in high temperature scene was transformed into a multi-objective optimization problem in high temperature mixed obstacle space, which considered the cost of path temperature and length. The NSGA-Ⅱ algorithm was improved to expand the population by selecting excellent non-feasible solutions, which improved the population diversity and population evolution efficiency. A new adaptive crossover and mutation probability calculation method was proposed. The process adjustment value realized the balance between the search ability in the early stage of the population and the convergence in the later stage according to the individual cost function value and the overall evolution process of the population. The simulation results of the optimal path show that although the path length cost of the proposed improved algorithm is slightly higher than that of the original algorithm and other improved algorithms, the temperature cost is greatly reduced. The proposed improved algorithm is more effective to avoid falling into the local optimal solution.

Key words: high temperature scene    virtual obstacle    mixed obstacle space    path planning    NSGA-Ⅱ algorithm
收稿日期: 2020-12-14 出版日期: 2021-10-27
CLC:  TP 242  
基金资助: 国家重点研发计划资助项目(2019YFC1511502);国家自然科学基金资助项目(51875515);浙江省科技计划资助项目(2021C01149);北京市科技计划资助项目(Z191100001419014)
通讯作者: 伊国栋     E-mail: 21925083@zju.edu.cn;ygd@zju.edu.cn
作者简介: 吴敬理(1997—),男,硕士生,从事路径规划的研究. orcid.org/0000-0002-6786-3834. E-mail: 21925083@zju.edu.cn
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章  
吴敬理
伊国栋
裘乐淼
张树有

引用本文:

吴敬理,伊国栋,裘乐淼,张树有. 高温混合障碍空间中的移动机器人路径规划[J]. 浙江大学学报(工学版), 2021, 55(10): 1806-1814.

Jing-li WU,Guo-dong YI,Le-miao QIU,Shu-you ZHANG. Path planning of mobile robots in mixed obstacle space with high temperature. Journal of ZheJiang University (Engineering Science), 2021, 55(10): 1806-1814.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2021.10.002        https://www.zjujournals.com/eng/CN/Y2021/V55/I10/1806

图 1  理想状态下混合障碍空间模型的示意图
图 2  交叉变异操作的具体步骤
图 3  NSGA-Ⅱ算法路径规划
算法 N Pc Pcmax Pcmin Pm Pmmax Pmmin l
NSGA-Ⅱ算法 100 0.6 ? ? 0.05 ? ? 10
文献[22]算法 100 ? 0.8 0.4 ? 0.1 0.01 10
本文改进算法 100 ? 0.8 0.4 ? 0.1 0.01 10
表 1  3种算法的参数设置
图 4  文献[22]中改进算法的路径规划
图 5  本文改进算法的路径规划
算法 LC CT
NSGA-Ⅱ算法 71.8 660.6
文献[22]算法 72.6 510.2
本文改进算法 75.0 406.2
表 2  最优路径的代价比较
图 6  迭代过程中3种算法所得解的代价值
算法 Gf Gt
原NSGA-Ⅱ算法 18 50
文献[22]的改进算法 17 48
本文改进算法 18 80
表 3  种群迭代过程的比较
1 MAC T T, COPOT C, TRAN D T, et al Heuristic approaches in robot path planning: a survey[J]. Robotics and Autonomous Systems, 2016, 86: 13- 28
doi: 10.1016/j.robot.2016.08.001
2 OROZOCO-ROSAS U, MONTIEL O, SEPULVEDA R Mobile robot path planning using membrane evolutionary artificial potential field[J]. Applied Soft Computing, 2019, 77: 236- 251
doi: 10.1016/j.asoc.2019.01.036
3 NIRMAL S N, CHATTERJEE A, CHATTERJEE A, et al A two-layered subgoal based mobile robot navigation algorithm with vision system and IR sensors[J]. Measurement, 2011, 44 (4): 620- 641
doi: 10.1016/j.measurement.2010.12.002
4 ZHANG Y, GONG D, ZHANG J Robot path planning in uncertain environment using multi-objective particle swarm optimization[J]. Neurocomputing, 2013, 103: 172- 185
doi: 10.1016/j.neucom.2012.09.019
5 NAZARAHARI M, KHANMIRZA E, DOOSTIE S Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm[J]. Expert Systems with Applications, 2019, 115: 106- 120
doi: 10.1016/j.eswa.2018.08.008
6 TAVARES R S, MARTINS T C, TSUZUKI M S G Simulated annealing with adaptive neighborhood: a case study in off-line robot path planning[J]. Expert Systems with Applications, 2011, 38 (4): 2951- 2965
doi: 10.1016/j.eswa.2010.08.084
7 陈智. 基于栅格法多目标路径规划研究[D]. 湖北: 华中科技大学, 2015.
CHEN Zhi. Study on the method of multi-objective path planning based on grid[D]. Hubei: Huazhong University of Science and Technology, 2015.
8 范江波, 王彧, 郑昆, 等 基于改进萤火虫算法的移动机器人多目标路径规划[J]. 济南大学学报: 自然科学版, 2020, 34 (5): 459- 469
FAN Jiang-bo, WANG Yu, ZHENG Kun, et al Multi-objective path planning for mobile robot based on improved firefly algorithm[J]. Journal of University of Jinan: Science and Technology, 2020, 34 (5): 459- 469
9 WANG B, LI S, GUO J, et al Car-like mobile robot path planning in rough terrain using multi-objective particle swarm optimization algorithm[J]. Neurocomputing, 2018, 282: 42- 51
doi: 10.1016/j.neucom.2017.12.015
10 邹春明, 张云雷, 徐言民, 等 基于NSGA-Ⅱ算法的AUV三维全局路径规划[J]. 武汉理工大学学报: 交通科学与工程版, 2021, 45 (1): 49- 53
ZOU Chun-ming, ZHANG Yun-lei, XU Yan-min, et al Three-dimensional global path planning based on NSGA-II algorithm for AUV[J]. Journal of Wuhan University of Technology: Transportation Science and Engineering, 2021, 45 (1): 49- 53
11 PEI Q, HAO L, CHEN C, et al Minimum collective dose based optimal evacuation path-planning method under nuclear accidents[J]. Annals of Nuclear Energy, 2020, 147: 107644
doi: 10.1016/j.anucene.2020.107644
12 于德春. 基于离散数据的火灾温度场构建算法与应用研究[D]. 江苏: 中国矿业大学, 2020.
YU De-chun. The construction algorithm and application research of fire temperature field based on discrete data[D]. Jiangsu: China University of Mining and Technology, 2020.
13 任泽霈. 热工手册[M]. 北京: 机械工业出版社, 2002: 45.
14 陈曦, 葛少成, 张兴华, 等 选煤厂暗道多热源叠加作用对通风排尘特性的影响[J]. 中国安全科学学报, 2017, 27 (11): 150- 156
CHEN Xi, GE Shao-cheng, ZHANG Xing-hua, et al Analysis of multithermo-sources superimposed effect onventilation dedusting in coal preparation plant[J]. China Safety Science Journal, 2017, 27 (11): 150- 156
15 徐力, 刘云华, 王启富 自适应遗传算法在机器人路径规划的应用[J]. 计算机工程与应用, 2020, 56 (18): 36- 41
XU Li, LIU Yun-hua, WANG Qi-fu Application of adaptive genetic algorithm in robot path planning[J]. Computer Engineering and Applications, 2020, 56 (18): 36- 41
doi: 10.3778/j.issn.1002-8331.1912-0062
16 肖闪丽, 王宇嘉, 聂善坤 动态邻居维度学习的多目标粒子群算法[J]. 计算机工程与应用, 2017, 53 (20): 31- 37
XIAO Shan-li, WANG Yu-jia, NIE Shan-kun Multi-objective particle swarm optimization based on dynamic neighborhood for dimensional learning[J]. Computer Engineering and Applications, 2017, 53 (20): 31- 37
doi: 10.3778/j.issn.1002-8331.1606-0137
17 DEB K, JAIN H An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach part I: solving problems with box constraints[J]. IEEE Strategy on Evolutionary Computation, 2014, 18 (4): 577- 601
doi: 10.1109/TEVC.2013.2281535
18 马硕. 基于非支配排序遗传算法的多目标车辆路径规划研究[D]. 辽宁: 大连海事大学, 2019.
MA Shuo. Multi-objective vehicle route planning based on non-dominated sorting genetic algorithm[D]. Liaoning: Dalian Maritime University, 2019.
19 DEB K, PRATAP A, AGARWAL S, et al A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6 (2): 182- 197
doi: 10.1109/4235.996017
20 CAO J, LI Y, ZHAO S C. Genetic-algorithm-based global path planning for AUV[C]// Proceedings of the 9th International Symposium on Computational Intelligence and Design. Hangzhou: IEEE, 2016: 79-82.
21 孙波, 姜平, 周根荣, 等 基于改进遗传算法的AGV路径规划[J]. 计算机工程与设计, 2020, 41 (2): 550- 556
SUN Bo, JIANG Ping, ZHOU Gen-rong, et al AGV optimal path planning based on improved genetical algorithm[J]. Computer Engineering and Design, 2020, 41 (2): 550- 556
22 曹海涛. 基于改进NSGA-Ⅱ的多目标柔性作业车间调度问题研究[D]. 浙江: 浙江工业大学, 2019.
CAO Hai-tao. Research on multi-objective flexible job shop scheduling problem based on improved NSGA-II[D]. Zhejiang: Zhejiang University of Technology, 2019.
23 雷永锋, 彭浩, 孙莉莉 基于正弦式自适应遗传算法的堆垛机路径优化研究[J]. 机械与电子, 2019, 37 (9): 59- 63
LEI Yong-feng, PENG Hao, SUN Li-li Research on path optimization of stacker based on sinusoidal adaptive genetic algorithm[J]. Machinery and Electronics, 2019, 37 (9): 59- 63
doi: 10.3969/j.issn.1001-2257.2019.09.014
[1] 戴天伦,李博涵,臧亚磊,戴华,于自强,陈钢. PORP:面向无人驾驶的路径规划并行优化策略[J]. 浙江大学学报(工学版), 2022, 56(2): 329-337.
[2] 刘洁,董献洲,韩维,王昕炜,刘纯,贾珺. 采用牛顿迭代保辛伪谱算法的舰载机甲板路径规划[J]. 浙江大学学报(工学版), 2020, 54(9): 1827-1838.
[3] 刘军,冯硕,任建华. 移动机器人路径动态规划有向D*算法[J]. 浙江大学学报(工学版), 2020, 54(2): 291-300.
[4] 高德东, 李强, 雷勇, 徐飞, 白辉全. 基于几何逼近法的斜尖柔性穿刺针运动学研究[J]. 浙江大学学报(工学版), 2017, 51(4): 706-713.
[5] 马丽莎, 周文晖, 龚小谨, 刘济林. 基于运动约束的泛化Field D*路径规划[J]. J4, 2012, 46(8): 1546-1552.
[6] 陈家乾,柳玉甜,何衍,蒋静坪. 基于栅格模型和样本集合的动态环境地图创建[J]. J4, 2011, 45(5): 794-798.
[7] 江万里 熊蓉 褚健. 复杂动态环境下基于侧滑力的局部路径规划[J]. J4, 2007, 41(10): 1609-1614.
[8] 吴思源 周晓军 江健 杨辰龙. 超声检测中曲面重构和路径规划方法研究[J]. J4, 2006, 40(5): 763-767.