多窄路口下改进的bi-RRT路径规划
|
摘要
多窄路口的复杂环境路径规划中,快速扩展随机树(rapidly exploring random Trees,RRT)存在重复搜索和难以通过等缺点。提出改进的双向快速随机扩展树(bi-directional RRT,bi-RRT)的路径规划算法,在多路口来设置人工虚拟目标点,首先根据其连通域采用Dijsktra算法求出一组最短路径的虚拟目标点,再根据虚拟目标点构建采样区域,结合小车的非完整积分约束、环境约束和上述构建的采样区域,利用bi-RRT搜索可行路径。该算法解决了机器人在狭窄路口重复搜索的问题并提高全局搜索效率。通过仿真实验验证该算法的高效性、实时性和正确性。
Path planning of multiple narrow intersections in the complex environment, rapidly exploring random trees(RRT) has the shortcomings of repeated search and hard to pass. An improved bi-directional RRT(bi-RRT) path planning algorithm was proposed to set artificial virtual target points at multiple intersections. Firstly, according to the connected domain, Dijsktra algorithm was used to solve a set of shortest path virtual target points. Then a sampling region was constructed according to the virtual target points. Combined with the nonholonomic integral constraints and environmental constraints of the trolley, the bi-RRT search was feasible with the above sampling region to get path. The algorithm solved the problem of robot repeated search at a narrow intersection and improved the global search efficiency. The effectiveness, real time and correctness of the algorithm are verified by simulation experiments.
Path planning of multiple narrow intersections in the complex environment, rapidly exploring random trees(RRT) has the shortcomings of repeated search and hard to pass. An improved bi-directional RRT(bi-RRT) path planning algorithm was proposed to set artificial virtual target points at multiple intersections. Firstly, according to the connected domain, Dijsktra algorithm was used to solve a set of shortest path virtual target points. Then a sampling region was constructed according to the virtual target points. Combined with the nonholonomic integral constraints and environmental constraints of the trolley, the bi-RRT search was feasible with the above sampling region to get path. The algorithm solved the problem of robot repeated search at a narrow intersection and improved the global search efficiency. The effectiveness, real time and correctness of the algorithm are verified by simulation experiments.
引文
[1] 黄静,陈汉伟.移动机器人全局路径规划算法的研究[J].仪表技术与传感器,2014(12):80-83.
[2] 王晓林.基于栅格法的仿生机器鱼路径规划研究[D].天津:天津大学,2010.
[3] 曲成刚,曹喜滨,张泽旭.人工势场和虚拟领航者结合的多智能体编队[J].哈尔滨工业大学学报,2014,46(5):1-5.
[4] 李龙澍,喻环.改进蚁群算法在复杂环境中机器人路径规划上的应用[J].小型微型计算机系统,2017,38(9):2067-2071.
[5] LAVALLE S M,KUFFNER J J.Randomized kinodynamic planning[J].The International Journal of Robotics Research,2001,20(5):378-400.
[6] WANG W,LII Y.A multi-RRTs framework for robot path planning in high-dimensional configuration space with narrow passages [C].International Conference on Mechatronics and Automation.2009:4952-4957.
[7] 刘多能.基于人机智能融合的移动机器人路径规划方法研究 [D].长沙:国防科学技术大学,2011.
[8] SUCAN I A,KAVRAKI L E.A sampling-based tree planner for systems with complex dynamics [J].IEEE Transactions on Robotics,2012,28(1):116 -131
[9] 尹高扬,周绍磊,吴青坡.基于改进RRT算法的无人机航迹规划[J].电子学报,2017,45(7):1764-1769.
[10] 刘华伟,张帅,赵搏欣,等.改进RRT算法陷阱空间下的无人机航迹规划,[J].计算机工程与应用,2018,54(8):119-122.
[11] 杜明博,梅涛,陈佳佳,等.复杂环境下基于RRT的智能车辆运动规划算法[J].机器人,2015,37(4):443-450.
[12] INGERSOLL B T,INGERSOLL J K,DEFRANCO P,et al.UAV path-planning using Bezier curves and a receding horizon approach[C]// AIAA Modeling and Simulation Technologies Conference.2016:3675.
[13] LAU B,SPRUNK C,BURGARD W.Kinodynamic motion planning for mobile robots using splines[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems.IEEE,2009:2427-2433.
[14] LAU B,SPRUNK C,BURGARD W.Kinodynamic motion planning for mobile robots using splines[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems.IEEE,2009:2427-2433.
[15] RODRIGUEZ s,TANG,Lien J M,et al.An obstacle-based rapidly-exploring random tree[C]//Proceedings 2006 IEEE International Conference on Robotics and Automation,ICRA 2006.IEEE,2006:895-900.
[16] 李加东.基于RRT算法的非完整移动机器人运动规划[D].上海:华东理工大学,2014.
[17] ELBANHAWI M,SIMIC M.Randomised kinodynamic motion planning for an autonomous vehicle in semi-structured agricultural areas[J].Biosystems Engineering,2014,126:30-44.
[18] GUNKEL C,STEPPER A,MüLLER A C,et al.Micro crack detection with Dijkstra's shortest path algorithm[J].Machine Vision & Applications,2012,23(3):589-601.
[2] 王晓林.基于栅格法的仿生机器鱼路径规划研究[D].天津:天津大学,2010.
[3] 曲成刚,曹喜滨,张泽旭.人工势场和虚拟领航者结合的多智能体编队[J].哈尔滨工业大学学报,2014,46(5):1-5.
[4] 李龙澍,喻环.改进蚁群算法在复杂环境中机器人路径规划上的应用[J].小型微型计算机系统,2017,38(9):2067-2071.
[5] LAVALLE S M,KUFFNER J J.Randomized kinodynamic planning[J].The International Journal of Robotics Research,2001,20(5):378-400.
[6] WANG W,LII Y.A multi-RRTs framework for robot path planning in high-dimensional configuration space with narrow passages [C].International Conference on Mechatronics and Automation.2009:4952-4957.
[7] 刘多能.基于人机智能融合的移动机器人路径规划方法研究 [D].长沙:国防科学技术大学,2011.
[8] SUCAN I A,KAVRAKI L E.A sampling-based tree planner for systems with complex dynamics [J].IEEE Transactions on Robotics,2012,28(1):116 -131
[9] 尹高扬,周绍磊,吴青坡.基于改进RRT算法的无人机航迹规划[J].电子学报,2017,45(7):1764-1769.
[10] 刘华伟,张帅,赵搏欣,等.改进RRT算法陷阱空间下的无人机航迹规划,[J].计算机工程与应用,2018,54(8):119-122.
[11] 杜明博,梅涛,陈佳佳,等.复杂环境下基于RRT的智能车辆运动规划算法[J].机器人,2015,37(4):443-450.
[12] INGERSOLL B T,INGERSOLL J K,DEFRANCO P,et al.UAV path-planning using Bezier curves and a receding horizon approach[C]// AIAA Modeling and Simulation Technologies Conference.2016:3675.
[13] LAU B,SPRUNK C,BURGARD W.Kinodynamic motion planning for mobile robots using splines[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems.IEEE,2009:2427-2433.
[14] LAU B,SPRUNK C,BURGARD W.Kinodynamic motion planning for mobile robots using splines[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems.IEEE,2009:2427-2433.
[15] RODRIGUEZ s,TANG,Lien J M,et al.An obstacle-based rapidly-exploring random tree[C]//Proceedings 2006 IEEE International Conference on Robotics and Automation,ICRA 2006.IEEE,2006:895-900.
[16] 李加东.基于RRT算法的非完整移动机器人运动规划[D].上海:华东理工大学,2014.
[17] ELBANHAWI M,SIMIC M.Randomised kinodynamic motion planning for an autonomous vehicle in semi-structured agricultural areas[J].Biosystems Engineering,2014,126:30-44.
[18] GUNKEL C,STEPPER A,MüLLER A C,et al.Micro crack detection with Dijkstra's shortest path algorithm[J].Machine Vision & Applications,2012,23(3):589-601.