Please wait a minute...
Journal of ZheJiang University (Engineering Science)  2021, Vol. 55 Issue (10): 1806-1814    DOI: 10.3785/j.issn.1008-973X.2021.10.002
    
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
Download: HTML     PDF(982KB) HTML
Export: BibTeX | EndNote (RIS)      

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 wordshigh temperature scene      virtual obstacle      mixed obstacle space      path planning      NSGA-Ⅱ algorithm     
Received: 14 December 2020      Published: 27 October 2021
CLC:  TP 242  
  TP 301  
Fund:  国家重点研发计划资助项目(2019YFC1511502);国家自然科学基金资助项目(51875515);浙江省科技计划资助项目(2021C01149);北京市科技计划资助项目(Z191100001419014)
Corresponding Authors: Guo-dong YI     E-mail: 21925083@zju.edu.cn;ygd@zju.edu.cn
Cite this article:

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.

URL:

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


高温混合障碍空间中的移动机器人路径规划

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


关键词: 高温场景,  虚拟障碍,  混合障碍空间,  路径规划,  NSGA-Ⅱ算法 
Fig.1 Schematic diagram of mixed obstacle space model in ideal state
Fig.2 Specific steps of cross mutation operation
Fig.3 Results of path planning by NSGA-Ⅱalgorithm
算法 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
Tab.1 Parameter setting of three algorithms
Fig.4 Results of path planning by improved algorithm in literature [22]
Fig.5 Results of path planning by improved algorithm
算法 LC CT
NSGA-Ⅱ算法 71.8 660.6
文献[22]算法 72.6 510.2
本文改进算法 75.0 406.2
Tab.2 Comparison of cost value of optimal path
Fig.6 Cost value of solutions obtained by three algorithms in iterative process
算法 Gf Gt
原NSGA-Ⅱ算法 18 50
文献[22]的改进算法 17 48
本文改进算法 18 80
Tab.3 Comparison of population iteration process
[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] Jun LIU,Shuo FENG,Jian-hua REN. Directed D* algorithm for dynamic path planning of mobile robots[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(2): 291-300.
[2] GAO De-dong, LI Qiang, LEI Yong, XU Fei, BAI Hui-quan. Geometric approximation approach based research on kinematics of bevel-tip flexible needles[J]. Journal of ZheJiang University (Engineering Science), 2017, 51(4): 706-713.
[3] MA Li-sha, ZHOU Wen-hui, GONG Xiao-jin, LIU Ji-lin. Motion constrained generalized Field D* path planning[J]. Journal of ZheJiang University (Engineering Science), 2012, 46(8): 1546-1552.
[4] CHEN Jia-qian, LIUYu-tian, HE Yan, JIANG Jing-ping. Novel dynamic mapping method based on occupancy grid
model and sample sets
[J]. Journal of ZheJiang University (Engineering Science), 2011, 45(5): 794-798.