基于改进渐进最优的双向快速扩展随机树的移动机器人路径规划算法
|
摘要
针对带启发式的快速扩展随机树(RRT-Connect)算法路径生成的随机性以及渐进最优的双向快速扩展随机树(B-RRT~*)算法收敛速度的缓慢性,提出了一种基于B-RRT~*改进的高效路径规划算法(EB-RRT~*)。首先引入一种智能采样函数,使随机树的扩展更具方向性,从而减少寻路时间,并提高路径的平滑性;其次在B-RRT~*算法的基础上,在EB-RRT~*算法中加入了一种快速扩展策略,使改进后的算法在自由空间中使用RRT-Connect算法的扩展方式进行快速扩展,而在障碍物空间则使用改进的渐进最优的快速扩展随机树(RRT~*)算法进行扩展,在提高扩展效率的同时避免算法陷入局部最优。将EB-RRT~*算法分别与快速扩展随机树(RRT)、RRT-Connect、RRT~*和B-RRT~*算法进行仿真对比,仿真结果表明,改进后的算法在路径规划效率及路径平滑性方面均明显优于其他算法;且相对于B-RRT~*算法,其在路径规划时间上降低了68.3%,在迭代次数上减少了48.6%。
To overcome the randomness of RRT-Connect and slow convergence of B-RRT~*(asymptotically-optimal Bidirectional Rapidly-exploring Random Tree) in path generation, an efficient path planning algorithm based on B-RRT~*, abbreviated as EB-RRT~*, was proposed. Firstly, an intelligent sampling function was intriduced to achieve more directional expansion of random tree, which could improve the smoothness of path and reduce the seek time. A rapidly-exploring strategy was also added in EB-RRT~* by which RRT-Connect exploration mode was adopted to ensure rapidly expanding in the free space and improved asymptotically-optimal Rapidly-exploring Random Tree(RRT~*) algorithm was adopted to prevent trapped in local optimum in the obstacle space. Finally, EB-RRT~* algorithm was compared with Rapidly-exploring Random Tree(RRT), RRT-Connect, RRT~* and B-RRT~* algorithms. The simulation results show that the improved algorithm is superior to other algorithms in the efficiency and smoothness of path planning. It reduced the path planning time by 68.3% and the number of iterations by 48.6% compared with B-RRT~* algorithm.
To overcome the randomness of RRT-Connect and slow convergence of B-RRT~*(asymptotically-optimal Bidirectional Rapidly-exploring Random Tree) in path generation, an efficient path planning algorithm based on B-RRT~*, abbreviated as EB-RRT~*, was proposed. Firstly, an intelligent sampling function was intriduced to achieve more directional expansion of random tree, which could improve the smoothness of path and reduce the seek time. A rapidly-exploring strategy was also added in EB-RRT~* by which RRT-Connect exploration mode was adopted to ensure rapidly expanding in the free space and improved asymptotically-optimal Rapidly-exploring Random Tree(RRT~*) algorithm was adopted to prevent trapped in local optimum in the obstacle space. Finally, EB-RRT~* algorithm was compared with Rapidly-exploring Random Tree(RRT), RRT-Connect, RRT~* and B-RRT~* algorithms. The simulation results show that the improved algorithm is superior to other algorithms in the efficiency and smoothness of path planning. It reduced the path planning time by 68.3% and the number of iterations by 48.6% compared with B-RRT~* algorithm.
引文
[1] DORIGO M,GAMBARELLA L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.
[2] 韩明,刘教民,吴朔媚,等.粒子群优化的移动机器人路径规划算法[J].计算机应用,2017,37(8):2258-2263.(HAN M,LIU J M,WU S M,et al.Path planning algorithm of mobile robot based on particle swarm optimization[J].Journal of Computer Applications,2017,37(8):2258-2263.)
[3] OZDIKIA O.Genetic algorithm with random coordinates for route planning on a 3D terrain[C]// Proceedings of the 2011 5th International Conference on Genetic and Evolutionary Computing.Washington,DC:IEEE Computer Society,2011:146-149.
[4] CHEN T B,ZHANG Q.Robot motion planning based on improved artificial potential field[C]// Proceedings of the 2013 3rd International Conference on Computer Science and Network Technology.Piscataway,NJ:IEEE,2013:1208-1211.
[5] LIN M,YUAN K,SHI C,et al.Path planning of mobile robot based on improved A* algorithm[C]// Proceedings of the 2017 29th Chinese Control and Decision Conference.Piscataway,NJ:IEEE,2017:3570-3576.
[6] KAVRAKI L E,SVESTKA P,LATOMBE J C,et al.Probabilistic roadmaps for path planning in high-dimensional configuration spaces [J].IEEE Transactions on Robotics and Automation,1996,12(4):566-580.
[7] LAVALLE S M,KUFFNER J J.Randomized Kinodynamic planning [C]// Proceedings of the 1999 IEEE International Conference on Robotics and Automation.Piscataway,NJ:IEEE,1999:473-479.
[8] 宋金泽,戴斌,单恩忠,等.一种改进的RRT路径规划算法[J].电子学报,2010,38(Z1):225-228.(SONG J Z,DAI B,SHAN E Z,et al.An improved RRT path planning algorithm[J].Acta Electronica Sinica,2010,38(Z1):225-228.)
[9] GAMMELL J D,SRINIVASA S S,BARFOOT T D.Informed RRT*:optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic[C]// Proceedings of the 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems.Piscataway,NJ:IEEE,2014:2997-3004.
[10] DOSHI A A,POSTULA A J,FLETCHER A,et al.Development of micro-UAV with integrated motion planning for open-cut mining surveillance [J].Microprocessors and Microsystems,2015,39(8):829-835.
[11] KUFFNER J J,LAVALLE S M.RRT-connect:an efficient approach to single-query path planning[C]// Proceedings of the 2000 IEEE International Conference on Robotics and Automation.Piscataway,NJ:IEEE,2000:995-1001.
[12] KARAMAN S,FRAZZOLI E.Sampling-based algorithms for optimal motion planning[J].The International Journal of Robotics Research,2011,30(7):846-894.
[13] JORDAN M,PEREZ A.Optimal bidirectional rapidly-exploring random trees [EB/OL].[2018- 03- 20].https://dspace.mit.edu/bitstream/handle/1721.1/79884/MIT-CSAIL-TR- 2013-021.pdf.
[14] QURESHI A H,AYAZ Y.Intelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments*[J].Robotics and Autonomous Systems,2015,68:1-11.
[15] OLZHAS A,HUSEYIN A V.A novel RRT*-based algorithm for motion planning in dynamic environments[C]// Proceedings of the 2017 IEEE International Conference on Mechatronics and Automation.Piscataway,NJ:IEEE,2017:1416-1421.
[16] 康亮,赵春霞,郭剑辉.基于模糊滚动RRT算法的移动机器人路径规划[J].南京理工大学学报(自然科学版),2010,34(5):642-648.(KANG L,ZHAO C X,GUO J H.Path planning based on fuzzy rolling rapidly-exploring random tree for mobile robot[J].Journal of Nanjing University of Science and Technology (Natural Science),2010,34(5):642-648.
[17] 冯楠.自主移动机器人路径规划的RRT算法研究[D].大连:大连理工大学,2014.(FENG N.Research on RRT algorithm of path planning for autonomous mobile robot[D].Dalian:Dalian University of Technology,2014.
[18] 潘思宇,徐向荣.基于改进RRT*的移动机器人运动规划算法[J].山西大学学报(自然科学版),2017,40(2):244-254.(PAN S Y,XU X R.Improved RRT*-based motion planning algorithm for mobile robot [J].Journal of Shanxi University (Natural Science Edition),2017,40(2):224-254.)
[19] ZAID T,AHMED H Q,YASAR A,et al.Potentially guided bidirectionalized RRT* for fast optimal path planning in cluttered environments[J].Robotics and Autonomous Systems,2018,108:13-27.
[20] NOREEN I,KHAN A,HABIB Z.Optimal path planning using RRT* based approaches:a survey and future directions[J].International Journal of Advanced Computer Science & Application,2016,7(11):97-107.
[21] IRAM N,AMNA K,HYEJEONG R,et al.Optimal path planning in cluttered environment using RRT*-AB[J].Intelligent Service Robotics,2017,11(1):41-52.
[2] 韩明,刘教民,吴朔媚,等.粒子群优化的移动机器人路径规划算法[J].计算机应用,2017,37(8):2258-2263.(HAN M,LIU J M,WU S M,et al.Path planning algorithm of mobile robot based on particle swarm optimization[J].Journal of Computer Applications,2017,37(8):2258-2263.)
[3] OZDIKIA O.Genetic algorithm with random coordinates for route planning on a 3D terrain[C]// Proceedings of the 2011 5th International Conference on Genetic and Evolutionary Computing.Washington,DC:IEEE Computer Society,2011:146-149.
[4] CHEN T B,ZHANG Q.Robot motion planning based on improved artificial potential field[C]// Proceedings of the 2013 3rd International Conference on Computer Science and Network Technology.Piscataway,NJ:IEEE,2013:1208-1211.
[5] LIN M,YUAN K,SHI C,et al.Path planning of mobile robot based on improved A* algorithm[C]// Proceedings of the 2017 29th Chinese Control and Decision Conference.Piscataway,NJ:IEEE,2017:3570-3576.
[6] KAVRAKI L E,SVESTKA P,LATOMBE J C,et al.Probabilistic roadmaps for path planning in high-dimensional configuration spaces [J].IEEE Transactions on Robotics and Automation,1996,12(4):566-580.
[7] LAVALLE S M,KUFFNER J J.Randomized Kinodynamic planning [C]// Proceedings of the 1999 IEEE International Conference on Robotics and Automation.Piscataway,NJ:IEEE,1999:473-479.
[8] 宋金泽,戴斌,单恩忠,等.一种改进的RRT路径规划算法[J].电子学报,2010,38(Z1):225-228.(SONG J Z,DAI B,SHAN E Z,et al.An improved RRT path planning algorithm[J].Acta Electronica Sinica,2010,38(Z1):225-228.)
[9] GAMMELL J D,SRINIVASA S S,BARFOOT T D.Informed RRT*:optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic[C]// Proceedings of the 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems.Piscataway,NJ:IEEE,2014:2997-3004.
[10] DOSHI A A,POSTULA A J,FLETCHER A,et al.Development of micro-UAV with integrated motion planning for open-cut mining surveillance [J].Microprocessors and Microsystems,2015,39(8):829-835.
[11] KUFFNER J J,LAVALLE S M.RRT-connect:an efficient approach to single-query path planning[C]// Proceedings of the 2000 IEEE International Conference on Robotics and Automation.Piscataway,NJ:IEEE,2000:995-1001.
[12] KARAMAN S,FRAZZOLI E.Sampling-based algorithms for optimal motion planning[J].The International Journal of Robotics Research,2011,30(7):846-894.
[13] JORDAN M,PEREZ A.Optimal bidirectional rapidly-exploring random trees [EB/OL].[2018- 03- 20].https://dspace.mit.edu/bitstream/handle/1721.1/79884/MIT-CSAIL-TR- 2013-021.pdf.
[14] QURESHI A H,AYAZ Y.Intelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments*[J].Robotics and Autonomous Systems,2015,68:1-11.
[15] OLZHAS A,HUSEYIN A V.A novel RRT*-based algorithm for motion planning in dynamic environments[C]// Proceedings of the 2017 IEEE International Conference on Mechatronics and Automation.Piscataway,NJ:IEEE,2017:1416-1421.
[16] 康亮,赵春霞,郭剑辉.基于模糊滚动RRT算法的移动机器人路径规划[J].南京理工大学学报(自然科学版),2010,34(5):642-648.(KANG L,ZHAO C X,GUO J H.Path planning based on fuzzy rolling rapidly-exploring random tree for mobile robot[J].Journal of Nanjing University of Science and Technology (Natural Science),2010,34(5):642-648.
[17] 冯楠.自主移动机器人路径规划的RRT算法研究[D].大连:大连理工大学,2014.(FENG N.Research on RRT algorithm of path planning for autonomous mobile robot[D].Dalian:Dalian University of Technology,2014.
[18] 潘思宇,徐向荣.基于改进RRT*的移动机器人运动规划算法[J].山西大学学报(自然科学版),2017,40(2):244-254.(PAN S Y,XU X R.Improved RRT*-based motion planning algorithm for mobile robot [J].Journal of Shanxi University (Natural Science Edition),2017,40(2):224-254.)
[19] ZAID T,AHMED H Q,YASAR A,et al.Potentially guided bidirectionalized RRT* for fast optimal path planning in cluttered environments[J].Robotics and Autonomous Systems,2018,108:13-27.
[20] NOREEN I,KHAN A,HABIB Z.Optimal path planning using RRT* based approaches:a survey and future directions[J].International Journal of Advanced Computer Science & Application,2016,7(11):97-107.
[21] IRAM N,AMNA K,HYEJEONG R,et al.Optimal path planning in cluttered environment using RRT*-AB[J].Intelligent Service Robotics,2017,11(1):41-52.