基于改进遗传算法的自动导引小车动态路径规划及其实现
|
摘要
针对传统遗传算法求解自动导引小车动态路径规划易早熟的缺点,提出一种改进遗传算法的自动导引小车动态路径规划算法,针对传统变异算子缺少启发式规则导致变异产生优质解的概率较低和算法早熟的缺陷,基于相连的路径片段组成的三角形建立使路径缩短的启发式变异规则,并提出路径微调算法;为了提高路径的光滑程度便于自动导引小车行驶,提出路径光滑处理算法;为了增加改进遗传算法的局部寻优能力,对每一代的最优解进行模拟退火操作;并且基于MATLAB GUI开发工具开发出自动导引小车动态路径规划仿真平台,以证明所改进遗传算法求解自动导引小车动态路径规划问题的有效性。
Aiming at the premature in traditional genetic algorithm for solving Automated Guided Vehicle(AGV)dynamic path planning problem,an Improved Genetic Algorithm(IGA)for AGV dynamic path planning was proposed,in which fine-tuning path algorithm was proposed based on heuristic rule to shorten path by setting up of a triangle consisted of connected path segments to aim at the drawbacks such as low probability of producing high quality solutions and premature resulted from the lack of heuristic rules in traditional mutation operators.To improve the path smoothness for facilitating the running of AGV,the path smoothing algorithm was proposed;to enhance the IGA exploitation performance,the simulated annealing operation was performed for the optimal solution in each generation.An AGV dynamic path planning platform developed based on MATLAB GUI tools so as to verify the proposed IGA for solving AGV dynamic path planning problems.
Aiming at the premature in traditional genetic algorithm for solving Automated Guided Vehicle(AGV)dynamic path planning problem,an Improved Genetic Algorithm(IGA)for AGV dynamic path planning was proposed,in which fine-tuning path algorithm was proposed based on heuristic rule to shorten path by setting up of a triangle consisted of connected path segments to aim at the drawbacks such as low probability of producing high quality solutions and premature resulted from the lack of heuristic rules in traditional mutation operators.To improve the path smoothness for facilitating the running of AGV,the path smoothing algorithm was proposed;to enhance the IGA exploitation performance,the simulated annealing operation was performed for the optimal solution in each generation.An AGV dynamic path planning platform developed based on MATLAB GUI tools so as to verify the proposed IGA for solving AGV dynamic path planning problems.
引文
[1]BECHTSIS D,TSOLAKIS N,VLACHOS D,et al.Sustainable supply chain management in the digitalisation era:the impact of automated guided vehicles[J].Journal of Cleaner Production,2017,142(P4):3970-3984.
[2]UMAR U A,ARIFFIN M K A,ISMAIL N,et al.Hybrid multiobjective genetic algorithms for integrated dynamic scheduling and routing of jobs and automated-guided vehicle(AGV)in flexible manufacturing systems(FMS)environment[J].International Journal of Advanced Manufacturing Technology,2015,81(9/10/11/12):2123-2141.
[3]ZENG N Y,ZHANG H,CHEN Y P,et al.Path planning for intelligent robot based on switching local evolutionary PSO algorithm[J].Assembly Automation,2016,36(2):120-126.
[4]YAZICI A,KIRLIK G,PARLAKTUNA O,et al.A dynamic path planning approach for multirobot sensor-based coverage considering energy constraints[J].IEEE Transactions on Cybernetics,2014,44(3):305-314.
[5]AMMAR A,BENNACEUR H,CHAARI I,et al.Relaxed dijkstra and A*with linear complexity for robot path planning problems in large-scale grid environments[J].Soft Computing,2016,20(10):4149-4171.
[6]WU J,ZHANG D H.Path planning for dynamic target based on kalman filtering algorithm and D*algorithm[J].Electronics Optics&Control,2014,21(8):50-53.
[7]MIN H S,LIN Y H,WANG S J,et al.Path planning of mobile robot by mixing experience with modified artificial potential field method[J].Advances in Mechanical Engineering,2015,7(12):1-17.
[8]NOREEN I,KHAN A,RYU H,et al.Optimal path planning in cluttered environment using RRT*-AB[J].Intelligent Service Robotics,2017,11(1):1-12.
[9]HAN J,SEO Y.Mobile robot path planning with surrounding point set and path improvement[J].Applied Soft Computing,2017,57:35-47.
[10]BAKDI A,HENTOUT A,BOUTAMI H,et al.Optimal path planning and execution for mobile robots using genetic algorithm and adaptive fuzzy-logic control[J].Robotics and Autonomous Systems,2017,89:95-109.
[11]ZHOU Y Q,WANG R.An improved flower pollination algorithm for optimal unmanned undersea vehicle path planning problem[J].International Journal of Pattern Recognition and Artificial Intelligence,2016,30(4):27.
[12]ZHANG S,ZHOU Y Q,LI Z M,et al.Grey wolf optimizer for unmanned combat aerial vehicle path planning[J].Advances in Engineering Software,2016,99:121-136.
[13]DUAN H B,HUANG L Z.Imperialist competitive algorithm optimized artificial neural networks for UCAV global path planning[J].Neurocomputing,2014,125(SI):166-171.
[14]WU Z S,FU W P,XUE R,et al.A novel global path planning method for mobile robots based on teaching-learningbased optimization[J].Information,2016,7(3):39-49.
[15]TANG B W,ZHU Z X,LUO J J.A convergence-guaranteed particle swarm optimization method for mobile robot global path planning[J].Assembly Automation,2017,37(1):114-129.
[16]LIU Erhni H,YAO xifan.AGV path planning based on improved genetic algorithm and implementation platform[J].Computer Integrated Manufacturing Systems,2017,23(3):465-472(in Chinese).[刘二辉,姚锡凡.基于改进遗传算法的自动导引小车路径规划及其实现平台[J].计算机集成制造系统,2017,23(3):465-472.]
[17]LI Y X,YAO X F,ZHOU J F.Multi-objective optimization of cloud manufacturing service composition with cloud-entropy enhanced genetic algorithm[J].Strojniski Vestnik-Journal of Mechanical Engineering,2016,62(10):577-590.
[18]ZHANG Cunji.Research on proactive scheduling approaches for job-shops based on sensory data in wisdom manufacturing[D].GuangZhou:South China University of Technology,2016(in Chinese).[张存吉.智慧制造环境下感知数据驱动的加工作业主动调度方法研究[D].广州:华南理工大学,2016.]
[19]MONTIEL O,OROZCO-ROSAS U,SEP LVEDA R.Path planning for mobile robots using bacterial potential field for avoiding static and dynamic obstacles[J].Expert Systems with Applications,2015,42(12):5177-5191.
[20]TUNCER A,YILDIRIM M.Dynamic path planning of mobile robots with improved genetic algorithm[J].Computers&Electrical Engineering,2012,38(6):1564-1572.
[21]LIU C A,YAN X H,LIU C Y,et al.Dynamic path planning for mobile robot based on improved genetic algorithm[J].Chinese Journal of Electronics,2010,19(2):245-248.
[22]DAS P K,BEHERA H S,JENA P K,et al.Multi-robot path planning in a dynamic environment using improved gravitational search algorithm[J].Journal of Electrical Systems and Information Technology,2016,3(2):295-313.
[23]ZHANG X L,ZHAO Y,DENG N M,et al.Dynamic path planning algorithm for a mobile robot based on visible space and an improved genetic alcorithm[J].International Journal of Advanced Robotic Systems,2016,13(3):91-107.
[24]ZHUANG Y F,SHARMA S,SUBUDHI B,et al.Efficient collision-free path planning for autonomous underwater vehicles in dynamic environments with a hybrid optimization algorithm[J].Ocean Engineering,2016,127:190-199.
[25]LIU Erhui.Research on Internet-of-manufacturing-things-oriented AGV path planning and integrated job shop scheduling[D].Guangzhou:South China University of Technology,2017(in Chinese).[刘二辉.面向制造物联的AGV路径规划及其集成的作业车间调度研究[D].广州:华南理工大学,2017.]
[26]TANG B W,ZHU Z X,LUO J J.Hybridizing particle swarm optimization and differential evolution for the mobile robot global path planning[J].International Journal of Advanced Robotic Systems,2016,13(3):1-17.
[27]AHMED F,DEB K.Multi-objective optimal path planning using elitist non-dominated sorting genetic algorithms[J].Soft Computing,2013,17(7):1283-1299.
[28]MIRJALILI S,MIRJALILI S M,LEWIS A.Grey wolf optimizer[J].Advances in Engineering Software,2014,69:46-61.
[29]QU H,XING K,ALEXANDER T.An improved genetic algorithm with co-evolutionary strategy for global path planning of multiple mobile robots[J].Neurocomputing,2013,120(10):509-517.
[30]HUANG Yingjie.Research on Shop Scheduling Problems based on analytical target cascading and intelligent algorithm[D].Guangzhou:South China University of Technology,2012(in Chinese).[黄英杰.基于目标级联法和智能优化算法的车间调度问题研究[D].广州:华南理工大学,2012.]
[2]UMAR U A,ARIFFIN M K A,ISMAIL N,et al.Hybrid multiobjective genetic algorithms for integrated dynamic scheduling and routing of jobs and automated-guided vehicle(AGV)in flexible manufacturing systems(FMS)environment[J].International Journal of Advanced Manufacturing Technology,2015,81(9/10/11/12):2123-2141.
[3]ZENG N Y,ZHANG H,CHEN Y P,et al.Path planning for intelligent robot based on switching local evolutionary PSO algorithm[J].Assembly Automation,2016,36(2):120-126.
[4]YAZICI A,KIRLIK G,PARLAKTUNA O,et al.A dynamic path planning approach for multirobot sensor-based coverage considering energy constraints[J].IEEE Transactions on Cybernetics,2014,44(3):305-314.
[5]AMMAR A,BENNACEUR H,CHAARI I,et al.Relaxed dijkstra and A*with linear complexity for robot path planning problems in large-scale grid environments[J].Soft Computing,2016,20(10):4149-4171.
[6]WU J,ZHANG D H.Path planning for dynamic target based on kalman filtering algorithm and D*algorithm[J].Electronics Optics&Control,2014,21(8):50-53.
[7]MIN H S,LIN Y H,WANG S J,et al.Path planning of mobile robot by mixing experience with modified artificial potential field method[J].Advances in Mechanical Engineering,2015,7(12):1-17.
[8]NOREEN I,KHAN A,RYU H,et al.Optimal path planning in cluttered environment using RRT*-AB[J].Intelligent Service Robotics,2017,11(1):1-12.
[9]HAN J,SEO Y.Mobile robot path planning with surrounding point set and path improvement[J].Applied Soft Computing,2017,57:35-47.
[10]BAKDI A,HENTOUT A,BOUTAMI H,et al.Optimal path planning and execution for mobile robots using genetic algorithm and adaptive fuzzy-logic control[J].Robotics and Autonomous Systems,2017,89:95-109.
[11]ZHOU Y Q,WANG R.An improved flower pollination algorithm for optimal unmanned undersea vehicle path planning problem[J].International Journal of Pattern Recognition and Artificial Intelligence,2016,30(4):27.
[12]ZHANG S,ZHOU Y Q,LI Z M,et al.Grey wolf optimizer for unmanned combat aerial vehicle path planning[J].Advances in Engineering Software,2016,99:121-136.
[13]DUAN H B,HUANG L Z.Imperialist competitive algorithm optimized artificial neural networks for UCAV global path planning[J].Neurocomputing,2014,125(SI):166-171.
[14]WU Z S,FU W P,XUE R,et al.A novel global path planning method for mobile robots based on teaching-learningbased optimization[J].Information,2016,7(3):39-49.
[15]TANG B W,ZHU Z X,LUO J J.A convergence-guaranteed particle swarm optimization method for mobile robot global path planning[J].Assembly Automation,2017,37(1):114-129.
[16]LIU Erhni H,YAO xifan.AGV path planning based on improved genetic algorithm and implementation platform[J].Computer Integrated Manufacturing Systems,2017,23(3):465-472(in Chinese).[刘二辉,姚锡凡.基于改进遗传算法的自动导引小车路径规划及其实现平台[J].计算机集成制造系统,2017,23(3):465-472.]
[17]LI Y X,YAO X F,ZHOU J F.Multi-objective optimization of cloud manufacturing service composition with cloud-entropy enhanced genetic algorithm[J].Strojniski Vestnik-Journal of Mechanical Engineering,2016,62(10):577-590.
[18]ZHANG Cunji.Research on proactive scheduling approaches for job-shops based on sensory data in wisdom manufacturing[D].GuangZhou:South China University of Technology,2016(in Chinese).[张存吉.智慧制造环境下感知数据驱动的加工作业主动调度方法研究[D].广州:华南理工大学,2016.]
[19]MONTIEL O,OROZCO-ROSAS U,SEP LVEDA R.Path planning for mobile robots using bacterial potential field for avoiding static and dynamic obstacles[J].Expert Systems with Applications,2015,42(12):5177-5191.
[20]TUNCER A,YILDIRIM M.Dynamic path planning of mobile robots with improved genetic algorithm[J].Computers&Electrical Engineering,2012,38(6):1564-1572.
[21]LIU C A,YAN X H,LIU C Y,et al.Dynamic path planning for mobile robot based on improved genetic algorithm[J].Chinese Journal of Electronics,2010,19(2):245-248.
[22]DAS P K,BEHERA H S,JENA P K,et al.Multi-robot path planning in a dynamic environment using improved gravitational search algorithm[J].Journal of Electrical Systems and Information Technology,2016,3(2):295-313.
[23]ZHANG X L,ZHAO Y,DENG N M,et al.Dynamic path planning algorithm for a mobile robot based on visible space and an improved genetic alcorithm[J].International Journal of Advanced Robotic Systems,2016,13(3):91-107.
[24]ZHUANG Y F,SHARMA S,SUBUDHI B,et al.Efficient collision-free path planning for autonomous underwater vehicles in dynamic environments with a hybrid optimization algorithm[J].Ocean Engineering,2016,127:190-199.
[25]LIU Erhui.Research on Internet-of-manufacturing-things-oriented AGV path planning and integrated job shop scheduling[D].Guangzhou:South China University of Technology,2017(in Chinese).[刘二辉.面向制造物联的AGV路径规划及其集成的作业车间调度研究[D].广州:华南理工大学,2017.]
[26]TANG B W,ZHU Z X,LUO J J.Hybridizing particle swarm optimization and differential evolution for the mobile robot global path planning[J].International Journal of Advanced Robotic Systems,2016,13(3):1-17.
[27]AHMED F,DEB K.Multi-objective optimal path planning using elitist non-dominated sorting genetic algorithms[J].Soft Computing,2013,17(7):1283-1299.
[28]MIRJALILI S,MIRJALILI S M,LEWIS A.Grey wolf optimizer[J].Advances in Engineering Software,2014,69:46-61.
[29]QU H,XING K,ALEXANDER T.An improved genetic algorithm with co-evolutionary strategy for global path planning of multiple mobile robots[J].Neurocomputing,2013,120(10):509-517.
[30]HUANG Yingjie.Research on Shop Scheduling Problems based on analytical target cascading and intelligent algorithm[D].Guangzhou:South China University of Technology,2012(in Chinese).[黄英杰.基于目标级联法和智能优化算法的车间调度问题研究[D].广州:华南理工大学,2012.]