改进RRT在汽车避障局部路径规划中的应用
|
摘要
根据传统快速搜索随机树算法(rapidly random-exploring trees,简称RRT)搜索速度快、所需时间短,但随机性大以及约束不足等特点,建立了直道和弯道的期望路径模型,采用高斯分布描述随机采样点,并引入启发式搜索机制,改进RRT算法.与原算法仿真对比,结果表明:改进算法所规划的路径质量显著提高,规划时间缩短一倍.同时,在Prescan软件中搭建直道和弯道仿真场景,跟随规划路径,结果表明:改进后RRT算法所得路径具有很好的跟随效果,且侧向加速度在车辆稳定性要求范围内,说明采用改进后的RRT算法进行汽车局部路径规划可行实用.
The original Rapidly-exploring Random Trees(RRT)algorithm has a rapid exploring-speed and short required time in path planning though it has large randomness and lacks of constraints.Thus,an improved RRT was proposed where the expected paths were built in both straight and curved roads.The random points were accorded with normal distribution around the expected paths.Heuristic search method that led the random points to the goal with a certain probability was also used for improvement.Compared with the original RRT algorithm,it performs quite well in both time-efficient and path quality in the simulation.Meanwhile,the effectiveness of the improved RRT algorithm was verified in Prescan.The path can be followed well and the secure lateral acceleration was satisfied.In conclusion,the improved RRT is effective in the path planning for vehicle collision avoidance.
The original Rapidly-exploring Random Trees(RRT)algorithm has a rapid exploring-speed and short required time in path planning though it has large randomness and lacks of constraints.Thus,an improved RRT was proposed where the expected paths were built in both straight and curved roads.The random points were accorded with normal distribution around the expected paths.Heuristic search method that led the random points to the goal with a certain probability was also used for improvement.Compared with the original RRT algorithm,it performs quite well in both time-efficient and path quality in the simulation.Meanwhile,the effectiveness of the improved RRT algorithm was verified in Prescan.The path can be followed well and the secure lateral acceleration was satisfied.In conclusion,the improved RRT is effective in the path planning for vehicle collision avoidance.
引文
[1]YAO J,LIN C,XIE X,et al.Path planning for virtual human motion using improved A*algorithm[C]//Proceedings of the Conference on Information Technology:New Generations(ITNG).Washington,DC:IEEE Computer Society,2010:1154
[2]DIJKSTRA E W.A note on two problems in connexion with graphs[J].Numerische Mathematik,1959,1(1):269-271.
[3]KHATIB O.Real-time obstacle avoidance for manipulators and mobile robots[J].The International Journal of Robotics Research,1986,5(1):90-98.
[4]SONG X,CAO H,HUANG J.Vehicle path planning in various driving situations based on the elastic band theory for highway collision avoidance[J].Proceedings of the Institution of Mechanical Engineers,Part D:Journal of Automobile Engineering,2013,227(12):1706-1722.
[5]SONG X,CAO H,HUANG J.Influencing factors research on vehicle path planning based on elastic bands for collision avoidance[J].SAE International Journal of Passenger CarsElectronic and Electrical Systems,2012,5(2):625-637.
[6]肖浩,宋晓琳,曹昊天.基于危险斥力场的自动驾驶汽车主动避撞局部路径规划[J].工程设计学报,2012,19(5):379-384.XIAO Hao,SONG Xiaolin,CAO Haotian.Local path planning for autonomous vehicle collison avoidance based on dangerous repellant fields[J].Chinese Journal of Engineering Design,2012,19(5):379-384.(In Chinese)
[7]康冰,王曦辉,刘富.基于改进蚁群算法的搜索机器人路径规划[J].吉林大学学报:工学版,2014,44(4):1062-1068.KANG Bing,WANG Xihui,LIU Fu.Path planning of searching robot based on improved ant colony algorithm[J].Journal of Jilin University:Engineering and Technology Edition,2014,44(4):1062-1068.(In Chinese)
[8]HU Y,YANG S X.A knowledge based genetic algorithm for path planning of a mobile robot[C]//Proceedings of the Conference on Robotics and Automation.Washington,DC:IEEE Computer Society,2004:4350-4355.
[9]吴乙万,黄智.基于动态虚拟障碍物的智能车辆局部路径规划方法[J].湖南大学学报:自然科学,2013,40(1):33-37.WU Yiwan,HUANG Zhi.Dynamic virtual obstacle based local path planning for intelligent vehicle[J].Journal of Hunan University:Natural Sciences,2013,40(1):33-37.(In Chinese)
[10]SHAH-HOSSEINI H.Problem solving by intelligent water drops[C]//Proceedings of the Conference on Evolutionary Computation.Washington,DC:IEEE Computer Society,2007:3226-3231.
[11]LAVALLE S M.Rapidly-exploring random trees:A new tool for path planning[J].Algorithmic&Computational Robotics New Directions,1998:293-308.
[12]LAVALLE S M,KUFFNER J J.Rapidly-exploring random trees:progress and prospects[J].Algorithmic&Computational Robotics New Directions,2000:293-308.
[13]KUFFNER J J,LAVALLE S M.RRT-connect:An efficient approach to single-query path planning[C]//Proceedings of International Conference on Robotics and Automation.Washington,DC:IEEE Computer Society,2003:995-1001.
[14]FERGUSON D,KALRA N,STENTZ A.Replanning with rrts[C]//Proceedings of International Conference on Robotics and Automation.Washington,DC:IEEE Computer Society,2006:1243-1248.
[15]ZUCKER M,KUFFNER J,BRANICKY M.Multipartite RRTs for rapid replanning in dynamic environments[C]//Proceedings of International Conference on Robotics and Automation.Washington,DC:IEEE Computer Society,2007:1603-1609.
[16]李红,郭孔辉,宋晓琳.基于样条理论的自动垂直泊车轨迹规划[J].湖南大学学报:自然科学版,2012,39(7):25-30.LI Hong,GUO Konghui,SONG Xiaolin.Trajectory planning of automatic vertical parking based on spline theory[J].Journal of Hunan University:Natural Sciences,2012,39(7):25-30.(In Chinese)
[2]DIJKSTRA E W.A note on two problems in connexion with graphs[J].Numerische Mathematik,1959,1(1):269-271.
[3]KHATIB O.Real-time obstacle avoidance for manipulators and mobile robots[J].The International Journal of Robotics Research,1986,5(1):90-98.
[4]SONG X,CAO H,HUANG J.Vehicle path planning in various driving situations based on the elastic band theory for highway collision avoidance[J].Proceedings of the Institution of Mechanical Engineers,Part D:Journal of Automobile Engineering,2013,227(12):1706-1722.
[5]SONG X,CAO H,HUANG J.Influencing factors research on vehicle path planning based on elastic bands for collision avoidance[J].SAE International Journal of Passenger CarsElectronic and Electrical Systems,2012,5(2):625-637.
[6]肖浩,宋晓琳,曹昊天.基于危险斥力场的自动驾驶汽车主动避撞局部路径规划[J].工程设计学报,2012,19(5):379-384.XIAO Hao,SONG Xiaolin,CAO Haotian.Local path planning for autonomous vehicle collison avoidance based on dangerous repellant fields[J].Chinese Journal of Engineering Design,2012,19(5):379-384.(In Chinese)
[7]康冰,王曦辉,刘富.基于改进蚁群算法的搜索机器人路径规划[J].吉林大学学报:工学版,2014,44(4):1062-1068.KANG Bing,WANG Xihui,LIU Fu.Path planning of searching robot based on improved ant colony algorithm[J].Journal of Jilin University:Engineering and Technology Edition,2014,44(4):1062-1068.(In Chinese)
[8]HU Y,YANG S X.A knowledge based genetic algorithm for path planning of a mobile robot[C]//Proceedings of the Conference on Robotics and Automation.Washington,DC:IEEE Computer Society,2004:4350-4355.
[9]吴乙万,黄智.基于动态虚拟障碍物的智能车辆局部路径规划方法[J].湖南大学学报:自然科学,2013,40(1):33-37.WU Yiwan,HUANG Zhi.Dynamic virtual obstacle based local path planning for intelligent vehicle[J].Journal of Hunan University:Natural Sciences,2013,40(1):33-37.(In Chinese)
[10]SHAH-HOSSEINI H.Problem solving by intelligent water drops[C]//Proceedings of the Conference on Evolutionary Computation.Washington,DC:IEEE Computer Society,2007:3226-3231.
[11]LAVALLE S M.Rapidly-exploring random trees:A new tool for path planning[J].Algorithmic&Computational Robotics New Directions,1998:293-308.
[12]LAVALLE S M,KUFFNER J J.Rapidly-exploring random trees:progress and prospects[J].Algorithmic&Computational Robotics New Directions,2000:293-308.
[13]KUFFNER J J,LAVALLE S M.RRT-connect:An efficient approach to single-query path planning[C]//Proceedings of International Conference on Robotics and Automation.Washington,DC:IEEE Computer Society,2003:995-1001.
[14]FERGUSON D,KALRA N,STENTZ A.Replanning with rrts[C]//Proceedings of International Conference on Robotics and Automation.Washington,DC:IEEE Computer Society,2006:1243-1248.
[15]ZUCKER M,KUFFNER J,BRANICKY M.Multipartite RRTs for rapid replanning in dynamic environments[C]//Proceedings of International Conference on Robotics and Automation.Washington,DC:IEEE Computer Society,2007:1603-1609.
[16]李红,郭孔辉,宋晓琳.基于样条理论的自动垂直泊车轨迹规划[J].湖南大学学报:自然科学版,2012,39(7):25-30.LI Hong,GUO Konghui,SONG Xiaolin.Trajectory planning of automatic vertical parking based on spline theory[J].Journal of Hunan University:Natural Sciences,2012,39(7):25-30.(In Chinese)