基于混合SA算法的智能汽车全局路径规划
|
摘要
针对目前智能汽车路径规划存在A~*算法规划的路径精度高却搜索耗时长、搜索耗时短但精度差的矛盾问题,提出了一种既保证搜索效率又可提高路径精度的混合连接SA算法.在原有连接方式的基础上,提出了一种新型的连接方式和S算法,设计了混合SA算法的切换机制,确保了SA算法可获取保证搜索效率的次优路径.进行了路径规划单一地图仿真试验,验证了SA算法在不同的单一环境地图中,重复规划的路径具有一致性、耗时具有一定局限性;同时进行了路径规划普适性仿真试验,对比分析了混合连接SA算法与四连接A~*算法的各项性能指标.结果表明:在全局工况下,SA算法相比于四连接A~*算法,在保证搜索耗时优势的同时,提高了规划路径精度,尤其是在低百分比障碍物地图下,效果更为明显.
To solve the contradictory problem of search time-consuming and path accuracy by A~* algorithm for the path planning of current intelligent vehicles, the hybrid SA algorithm was proposed to ensure efficiency of search time-consuming and improve path accuracy in path planning. Based on the traditional connective mode of node, a new connective mode of node and S algorithm were proposed, and the switch mechanism of hybrid SA algorithm was designed to obtain suboptimal paths in shorter time. The single map simulation experiments of path planning were conducted. The SA algorithm was verified that the paths of repeated programming were consistent, and the search time-consuming deviations had certain limitations in different single maps. The universal simulation experiments were also conducted, and the performance indexes of SA algorithm and four-connection A~* algorithm were compared and analyzed. The results show that compared with A~* algorithm by four-connection nodes, SA algorithm can improve the path accuracy and ensure the advantages of search time-consuming under the global working condition, especially for the low percentage obstacle map, the effect is more obvious.
To solve the contradictory problem of search time-consuming and path accuracy by A~* algorithm for the path planning of current intelligent vehicles, the hybrid SA algorithm was proposed to ensure efficiency of search time-consuming and improve path accuracy in path planning. Based on the traditional connective mode of node, a new connective mode of node and S algorithm were proposed, and the switch mechanism of hybrid SA algorithm was designed to obtain suboptimal paths in shorter time. The single map simulation experiments of path planning were conducted. The SA algorithm was verified that the paths of repeated programming were consistent, and the search time-consuming deviations had certain limitations in different single maps. The universal simulation experiments were also conducted, and the performance indexes of SA algorithm and four-connection A~* algorithm were compared and analyzed. The results show that compared with A~* algorithm by four-connection nodes, SA algorithm can improve the path accuracy and ensure the advantages of search time-consuming under the global working condition, especially for the low percentage obstacle map, the effect is more obvious.
引文
[1] ZAMIRIAN M,KAMYAD A V,FARAHI M H.A novel algorithm for solving optimal path planning problems based on parametrization method and fuzzy aggregation[J].Physics Letters A,2009,373:3439-3449.
[2] LATOMBE J C.Robot Motion Planning[M].Germany:Springer,1991.
[3] YE W,MA D W,FAN H D.Algorithm for low altitude penetration aircraft path planning with improved ant co-lony algorithm[J].Chinese Journal of Aeronautics,2005,18(4):304-309.
[4] ROBERGE V,TARBOUCHI M,LABONTE G.Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning[J].IEEE Transactions on Industrial Informatics,2013,9(1):132-141.
[5] TSAI C C,HUANG H C,CHAN C K.Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation[J].IEEE Tran-sactions on Industrial Electronics,2011,58(10):4813-4821.
[6] XIE S R,WU P,LIU H L,et al.A novel method of unmanned surface vehicle autonomous cruise[J].Industrial Robot,2016,43(1):121-130.
[7] HART P E,NILSSON N J,RAPHAEL B.A formal basis for the heuristic determination of minimum cost paths[J].IEEE Transactions on Systems Science & Cybernetics,2007,4(2):100-107.
[8] 顾青,豆风铅,马飞.基于改进A*算法的电动车能耗最优路径规划[J].农业机械学报,2015,46(12):316-322.GU Q,DOU F Q,MA F.Energy optimal path planning of electric vehicle based on improved A* algorithm[J].Transactions of the Chinese Society for Agricultural Machinery,2015,46 (12):316-322.(in Chinese)
[9] TROVATO K I,DORST L.Differential A*[J].IEEE Transactions on Knowledge & Data Engineering,2002,14(6):1218-1229.
[10] RUSSELL S J,NORVIG P.Articial Intelligence:A Modern Approach [M].3rd ed.USA:Pearson Education Inc ,2010.
[11] LOZANO-PéREZ T,WESLEY M A,FRITSCH F N.An algorithm for planning collision-free paths among polyhedral obstacles[J].Communications of the ACM,1979,22(10):560-570.
[12] 王红卫,马勇,谢勇,等.基于平滑A*算法的移动机器人路径规划[J].同济大学学报(自然科学版),2010,38(11):1647-1650.WANG H W,MA Y,XIE Y,et al.Mobile robot optimal path planning based on smoothing A* algorithm[J].Journal of Tongji University (Natural Science),2010,38 (11):1647-1650.(in Chinese)
[2] LATOMBE J C.Robot Motion Planning[M].Germany:Springer,1991.
[3] YE W,MA D W,FAN H D.Algorithm for low altitude penetration aircraft path planning with improved ant co-lony algorithm[J].Chinese Journal of Aeronautics,2005,18(4):304-309.
[4] ROBERGE V,TARBOUCHI M,LABONTE G.Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning[J].IEEE Transactions on Industrial Informatics,2013,9(1):132-141.
[5] TSAI C C,HUANG H C,CHAN C K.Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation[J].IEEE Tran-sactions on Industrial Electronics,2011,58(10):4813-4821.
[6] XIE S R,WU P,LIU H L,et al.A novel method of unmanned surface vehicle autonomous cruise[J].Industrial Robot,2016,43(1):121-130.
[7] HART P E,NILSSON N J,RAPHAEL B.A formal basis for the heuristic determination of minimum cost paths[J].IEEE Transactions on Systems Science & Cybernetics,2007,4(2):100-107.
[8] 顾青,豆风铅,马飞.基于改进A*算法的电动车能耗最优路径规划[J].农业机械学报,2015,46(12):316-322.GU Q,DOU F Q,MA F.Energy optimal path planning of electric vehicle based on improved A* algorithm[J].Transactions of the Chinese Society for Agricultural Machinery,2015,46 (12):316-322.(in Chinese)
[9] TROVATO K I,DORST L.Differential A*[J].IEEE Transactions on Knowledge & Data Engineering,2002,14(6):1218-1229.
[10] RUSSELL S J,NORVIG P.Articial Intelligence:A Modern Approach [M].3rd ed.USA:Pearson Education Inc ,2010.
[11] LOZANO-PéREZ T,WESLEY M A,FRITSCH F N.An algorithm for planning collision-free paths among polyhedral obstacles[J].Communications of the ACM,1979,22(10):560-570.
[12] 王红卫,马勇,谢勇,等.基于平滑A*算法的移动机器人路径规划[J].同济大学学报(自然科学版),2010,38(11):1647-1650.WANG H W,MA Y,XIE Y,et al.Mobile robot optimal path planning based on smoothing A* algorithm[J].Journal of Tongji University (Natural Science),2010,38 (11):1647-1650.(in Chinese)