基于改进蚁群算法的泊车系统路径规划
|
摘要
针对智能立体车库中自动导引运输车(Automated Guided Vehicle,AGV)存取车路径规划问题,提出一种基于改进蚁群算法(IACO)的泊车系统路径规划方法。首先利用栅格法建立环境模型;其次,通过引入新的距离启发函数因子、调整状态转移概率和更改信息素更新规则对传统蚁群算法(TACO)进行优化改进;最后,在不同规格栅格环境下,以路径长度最短、算法收敛代数最小为评价指标,以传统蚁群算法和改进蚁群算法为搜索策略,运用Matlab对AGV存取车路径规划过程进行仿真测试,结果显示:AGV运用传统蚁群算法和改进蚁群算法均能有效避开障碍物,然后搜索到一条从起点到终点的无碰优化路径;与传统蚁群算法相比,改进蚁群算法规划的路径长度最短,开始收敛代数最小,表明改进算法正确、可行及有效,且具有较强的全局搜索能力和较好的收敛性能,能够满足AGV存取车路径规划要求。
Aiming at the path planning problem of AGV accessing cars in intelligent solid garages, the method of path planning of the parking system based on the improved ant colony algorithm is proposed. In the method, firstly, the grid method is utilized to create the working environment model of AGV. Secondly, the traditional ant colony algorithm is optimized through introducing a new distance heuristic function factor and update strategy of pheromone that includes the local updating and global updating of pheromone. Finally, under the different grid environments, the shortest path length and the minimum convergence algebra are used as evaluation indexes, the traditional ant colony algorithm and the improved ant colony algorithm are used as search strategy, the path planning process of AGV accessing cars is simulated with MATLAB software. The results show that the optimized path from the starting point to the end point could be obtained with the traditional ant colony algorithm and the improved ant colony algorithm on the premise of effectively avoiding obstacles. Moreover, the path length and the convergence algebra of the improved ant colony algorithm are optimal through being compared with the traditional ant colony algorithm. The results indicate that the improved ant colony algorithm is correct, feasible and effective, simultaneously exhibits stronger global search ability and better convergence performance, and can meet the requirement of AGV accessing cars in path planning.
Aiming at the path planning problem of AGV accessing cars in intelligent solid garages, the method of path planning of the parking system based on the improved ant colony algorithm is proposed. In the method, firstly, the grid method is utilized to create the working environment model of AGV. Secondly, the traditional ant colony algorithm is optimized through introducing a new distance heuristic function factor and update strategy of pheromone that includes the local updating and global updating of pheromone. Finally, under the different grid environments, the shortest path length and the minimum convergence algebra are used as evaluation indexes, the traditional ant colony algorithm and the improved ant colony algorithm are used as search strategy, the path planning process of AGV accessing cars is simulated with MATLAB software. The results show that the optimized path from the starting point to the end point could be obtained with the traditional ant colony algorithm and the improved ant colony algorithm on the premise of effectively avoiding obstacles. Moreover, the path length and the convergence algebra of the improved ant colony algorithm are optimal through being compared with the traditional ant colony algorithm. The results indicate that the improved ant colony algorithm is correct, feasible and effective, simultaneously exhibits stronger global search ability and better convergence performance, and can meet the requirement of AGV accessing cars in path planning.
引文
[1]Charles E B,Brian G P,Christian A Y,et al.Automated automotive vehicle parking/storage system[P].US Patent:US12855017,2014-05-27.
[2]王辉,朱龙彪,王景良,等.基于Dijkstra-蚁群算法的泊车系统路径规划研究[J].工程设计学报,2016,23(5):489-496.Wang H,Zhu L B,Wang J L,et al.Research on path planing of parking system based on Dijkstra-Ant colony hybrid algorithm[J].Chinese Journal of Engineering Design,2016,23(5):489-496.
[3]Li D L,Niu K.Dijkstra's algorithm in AGV[C]//Proceedings of the2014 9th IEEE Conference on Industrial Electronics and Applications,Hangzhou,China,2014:1867-1871.
[4]Chaari I,Koubaa A,Sahar T,et al.Smart path:an efficient hybrid ACO-GA algorithm for solving the global path planning problem of mobile robots[J].International Journal of Advanced Robotic Systems,2014,11(1):1-15.
[5]何少佳,史剑清,王海坤.基于改进蚁群粒子群算法的移动机器人路径规划[J].桂林理工大学学报,2014,34(4):765-770.He S J,Shi J Q,Wang H K.Path planning for mobile robot based on improved ant colony and particle swarm optimization[J].Journal of Guilin University of Technology,2014,34(4):765-770.
[6]周明秀,程科,汪正霞.动态路径规划中的改进蚁群算法[J].计算机科学,2013,40(1):314-316.Zhou M X,Cheng K,Wang Z X.Improved ant colony algorithm with planning of dynamic path[J].Computer Science,2013,40(1):314-316.
[7]李士勇,陈勇强,李研.蚁群算法及其应用[M].哈尔滨:哈尔滨出版社,2004:1-33.Li S Y,Chen Y Q,Li Y.Ant colony algorithms with applications[M].Harbin:Harbin Press,2004:1-33.
[8]Taylor B,Choi A.Fuzzy ant colony algorithm for terrain following optimization[C]//Conference Proceedings-IEEE International Conference on Systems,Man and Cybernetics,New York,USA,2014:3834-3839.
[9]Wang Z,Li J Q,Fang M L,et al.A multimetric ant colony optimization algorithm for dynamic path planning in vehicular networks[J].International Journal of Distributed Sensor Networks,2015,2015(1):1-10.
[10]张勇.基于改进蚁群算法物流配送路径优化的研究[J].控制工程,2015,22(2):252-256.Zhang Y.Study of optimizing logistic distribution routing based on improved ant colony algorithm[J].Control Engineering of China,2015,22(2):252-256.
[11]Mohammad S M,Saeed D A,Farshid E,et al.An ant colony algorithm(ACA)for solving the new integrated model of job shop scheduling and conflict-free routing of AGVs[J].Computers and Industrial Engineering,2015,86(C):2-13.
[12]姜康,胡龙.复杂环境下的装配路径求解与优化[J].中国机械工程,2015,26(5):632-636.Jiang K,Hu L.Assembly path planning and optimization under complex environments[J].China Mechanical Engineering,2015,26(5):632-636.
[13]Liu D,Zheng L J,Wang J M.Application of improved ant colony algorithm in solving TSP[J].International Journal of Multimedia and Ubiquitous Engineering,2014,9(7):395-402.
[14]屈鸿,黄利伟,柯星.动态环境下基于改进蚁群算法的机器人路径规划研究[J].电子科技大学学报,2015,44(2):260-265.Qu H,Huang L W,Ke X.Research of improved ant colony based robot path planning under dynamic environment[J].Journal of University of Electronic Science and Technology of China,2015,44(2):260-265.
[15]康冰,王曦辉,刘富.基于改进蚁群算法的搜索机器人路径规划[J].吉林大学学报(工学版),2014,44(4):1062-1068.Kang B,Wang X H,Liu F.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.
[16]Shu J,Wu L,Han B,et al.Enhanced multi-dimensional power network planning based on ant colony optimization[J].International Transactions on Electrical Energy Systems,2015,25(7):1204-1222.
[17]万晓凤,胡伟,方武义,等.基于改进蚁群算法的机器人路径规划研究[J].计算机工程与应用,2014,50(18):63-66.Wan X F,Hu W,Fang W Y,et al.Research on path planning of robot based on improved ant colony algorithm[J].Computer Engineering and Applications,2014,50(18):63-66.
[18]吴天羿,许继恒,刘建永.基于改进蚁群算法的越野路径规划[J].计算机应用,2013,33(4):1157-1160.Wu T Y,Xu J H,Liu J Y.Cross-country path planning based on improved ant colony algorithm[J].Journal of Computer Applications,2013,33(4):1157-1160.
[2]王辉,朱龙彪,王景良,等.基于Dijkstra-蚁群算法的泊车系统路径规划研究[J].工程设计学报,2016,23(5):489-496.Wang H,Zhu L B,Wang J L,et al.Research on path planing of parking system based on Dijkstra-Ant colony hybrid algorithm[J].Chinese Journal of Engineering Design,2016,23(5):489-496.
[3]Li D L,Niu K.Dijkstra's algorithm in AGV[C]//Proceedings of the2014 9th IEEE Conference on Industrial Electronics and Applications,Hangzhou,China,2014:1867-1871.
[4]Chaari I,Koubaa A,Sahar T,et al.Smart path:an efficient hybrid ACO-GA algorithm for solving the global path planning problem of mobile robots[J].International Journal of Advanced Robotic Systems,2014,11(1):1-15.
[5]何少佳,史剑清,王海坤.基于改进蚁群粒子群算法的移动机器人路径规划[J].桂林理工大学学报,2014,34(4):765-770.He S J,Shi J Q,Wang H K.Path planning for mobile robot based on improved ant colony and particle swarm optimization[J].Journal of Guilin University of Technology,2014,34(4):765-770.
[6]周明秀,程科,汪正霞.动态路径规划中的改进蚁群算法[J].计算机科学,2013,40(1):314-316.Zhou M X,Cheng K,Wang Z X.Improved ant colony algorithm with planning of dynamic path[J].Computer Science,2013,40(1):314-316.
[7]李士勇,陈勇强,李研.蚁群算法及其应用[M].哈尔滨:哈尔滨出版社,2004:1-33.Li S Y,Chen Y Q,Li Y.Ant colony algorithms with applications[M].Harbin:Harbin Press,2004:1-33.
[8]Taylor B,Choi A.Fuzzy ant colony algorithm for terrain following optimization[C]//Conference Proceedings-IEEE International Conference on Systems,Man and Cybernetics,New York,USA,2014:3834-3839.
[9]Wang Z,Li J Q,Fang M L,et al.A multimetric ant colony optimization algorithm for dynamic path planning in vehicular networks[J].International Journal of Distributed Sensor Networks,2015,2015(1):1-10.
[10]张勇.基于改进蚁群算法物流配送路径优化的研究[J].控制工程,2015,22(2):252-256.Zhang Y.Study of optimizing logistic distribution routing based on improved ant colony algorithm[J].Control Engineering of China,2015,22(2):252-256.
[11]Mohammad S M,Saeed D A,Farshid E,et al.An ant colony algorithm(ACA)for solving the new integrated model of job shop scheduling and conflict-free routing of AGVs[J].Computers and Industrial Engineering,2015,86(C):2-13.
[12]姜康,胡龙.复杂环境下的装配路径求解与优化[J].中国机械工程,2015,26(5):632-636.Jiang K,Hu L.Assembly path planning and optimization under complex environments[J].China Mechanical Engineering,2015,26(5):632-636.
[13]Liu D,Zheng L J,Wang J M.Application of improved ant colony algorithm in solving TSP[J].International Journal of Multimedia and Ubiquitous Engineering,2014,9(7):395-402.
[14]屈鸿,黄利伟,柯星.动态环境下基于改进蚁群算法的机器人路径规划研究[J].电子科技大学学报,2015,44(2):260-265.Qu H,Huang L W,Ke X.Research of improved ant colony based robot path planning under dynamic environment[J].Journal of University of Electronic Science and Technology of China,2015,44(2):260-265.
[15]康冰,王曦辉,刘富.基于改进蚁群算法的搜索机器人路径规划[J].吉林大学学报(工学版),2014,44(4):1062-1068.Kang B,Wang X H,Liu F.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.
[16]Shu J,Wu L,Han B,et al.Enhanced multi-dimensional power network planning based on ant colony optimization[J].International Transactions on Electrical Energy Systems,2015,25(7):1204-1222.
[17]万晓凤,胡伟,方武义,等.基于改进蚁群算法的机器人路径规划研究[J].计算机工程与应用,2014,50(18):63-66.Wan X F,Hu W,Fang W Y,et al.Research on path planning of robot based on improved ant colony algorithm[J].Computer Engineering and Applications,2014,50(18):63-66.
[18]吴天羿,许继恒,刘建永.基于改进蚁群算法的越野路径规划[J].计算机应用,2013,33(4):1157-1160.Wu T Y,Xu J H,Liu J Y.Cross-country path planning based on improved ant colony algorithm[J].Journal of Computer Applications,2013,33(4):1157-1160.