基于复杂环境非均匀建模的蚁群路径规划

doi:10.13973/j.cnki.robot.2016.0276

摘要
图/表
参考文献
相关文章 (15)

全文: PDF (890 KB) HTML ( ) 输出: BibTeX \| EndNote (RIS)
引用本文:
卜新苹, 苏虎, 邹伟, 王鹏, 周海. 基于复杂环境非均匀建模的蚁群路径规划[J]. 机器人, 2016, 38(3): 276-284.DOI: 10.13973/j.cnki.robot.2016.0276. BU Xinping, SU Hu, ZOU Wei, WANG Peng, ZHOU Hai. Ant Colony Path Planning Based on Non-uniform Modeling of Complex Environment. ROBOT, 2016, 38(3): 276-284. DOI: 10.13973/j.cnki.robot.2016.0276.

摘要针对复杂环境中的大型辅助工装，本文在非均匀环境建模的基础上，提出了一种搜索工装可行路径的改进型蚁群算法．首先，在环境建模过程中，利用凸投影计算环境中的障碍物在投影平面的障碍区域，然后利用 Minkowski 和对其进行拓展，并利用线性四叉树法实现环境的非均匀栅格建模．其次，在进行路径规划时，提出一种改进型蚁群算法对工装的可行路径进行搜索．该算法采取了以下策略以提高性能：融合了最大最小蚁群（MMAS）算法与蚁群系统（ACS）算法的信息素更新方式，在栅格选择策略中引入了目标距离和障碍物距离等启发式信息，设计了与已建立的环境模型相符合的适应度函数．最后，以大型激光驱动器的靶场环境为对象，对本文算法的有效性进行了验证，证明本文算法能够在存在多障碍物的复杂环境中高效完成工装运动路径的规划．设计了对比实验，将本文算法与基本蚁群算法进行了对比，实验结果表明，与基本蚁群算法相比，本文算法具有更快的收敛速度，规划结果具有更高的适应性．

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	卜新苹
	苏虎
	邹伟
	王鹏
	周海

关键词 ：路径规划, 蚁群算法, 四叉树, Minkowski和

Abstract：For a large auxiliary robot working in complex environment, an improved ant colony algorithm based on non-uniform environment modeling is proposed to search feasible paths. In the process of environment modeling, convex projection is firstly conducted to calculate the obstacle area of each environment obstacle on the projection plane. Then, the obstacles are extended by using the concept of the Minkowski sum, and a grid model of the environment is non-uniformly constructed based on the linear quadtree method. During path planning, an improved ant colony algorithm is adopted to search feasible paths of the vehicle. In order to improve performance, the pheromone update mechanisms of the max-min ant system (MMAS) and ant colony system (ACS) algorithms are fused, some target distance based and obstacle distance based heuristic search methods are used in grid selection, and a fitness function suitable for the constructed environment model is designed. Finally, the method is experimentally verified in the target area of a large laser facility, and the result shows that it can efficiently plan the vehicle path in complex environment in the presence of obstacles. Further, comparison experiments are also well conducted to demonstrate the superior performance of the proposed method in convergence and adaptability comparing with the basic ant colony algorithm.

Key words： path planning ant colony algorithm quadtree Minkowski sum

收稿日期: 2016-01-01 录用日期: 2016-03-10

TP242.2

基金资助:国家自然科学基金（61403382，61379097）；国家863计划（2015AA042307）

通讯作者: 苏虎，hu.su@ia.ac.cn E-mail: hu.su@ia.ac.cn

作者简介: 卜新苹（1990-），女，硕士生．研究领域：运动优化与建模.
苏虎（1986-），男，博士，助理研究员．研究领域：机器人控制，路径规划.
邹伟（1974-），男，博士，研究员．研究领域：机器人视觉，智能控制.

链接本文:

https://robot.sia.cn/CN/10.13973/j.cnki.robot.2016.0276 或 https://robot.sia.cn/CN/Y2016/V38/I3/276

[1] 李磊,叶涛,谭民,等.移动机器人技术研究现状与未来 [J].机器人,2005,24(5):475-480.Li L, Ye T, Tan M, et al. Present state and future development of mobile robot technology research[J]. Robot, 2002, 24(5): 475-480.
[2] Lozano-Perez T, Wesley M A. An algorithm for planning collision-free paths among polyhedral obstacles[J]. Communications of the ACM, 1979, 22(10): 560-570.

[3] Brooks R A. Solving the find-path problem by good representation of free space[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1983, 13(2): 190-197.
[4] Alajlan M, Koubaa A, Chaari I, et al. Global path planning for mobile robots in large-scale grid environments using genetic algorithms[C]//International Conference on Individual and Collective Behaviors in Robotics. Piscataway, USA: IEEE, 2013: 1-8.
[5] 谭民,徐德,候增广,等.先进机器人控制[M].北京:高等教育出版社,2007.Tan M, Xu D, Hou Z G, et al. Advanced robot control[M]. Beijing: Higher Education Press, 2007.
[6] Alexopoulos C, Griffin P M. Path planning for a mobile robot[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1992, 22(2): 318-322.

[7] Fan D K, Shi P. Improvement of Dijkstra's algorithm and its application in route planning[C]//7th International Conference on Fuzzy Systems and Knowledge Discovery. Piscataway, USA: IEEE, 2010: 1901-1904.
[8] Dorigo M, Maniezzo V, Colorni A. Ant system: Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1996, 26(1): 29-41.

[9] Zhou Y R. Runtime analysis of an ant colony optimization algorithm for TSP instances[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(5): 1083-1092.

[10] Tsutsui S, Liu L C. Solving quadratic assignment problems with the cunning ant system[C]//IEEE Congress on Evolutionary Computation. Piscataway, USA: IEEE, 2007: 173-179.
[11] Garai G, Debbarman S, Biswas T. An efficient ant colony optimization algorithm for function optimization. A guided search technique for high and low dimensional functions[C]//IEEE Congress on Evolutionary Computation. Piscataway, USA: IEEE, 2013: 2345-2351.
[12] Juang C F, Hsu C H. Reinforcement ant optimized fuzzy controller for mobile-robot wall-following control[J]. IEEE Transactions on Industrial Electronics, 2009, 56(10): 3931-3940.

[13] Dorigo M, Gambardella 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.

[14] Stutzle T, Hoos H H. MAX-MIN ant system[J]. Future Generation Computer Systems, The International Journal of Escience, 2000, 16(8): 889-914.

[15] Zeng D W, He Q, Leng B, et al. An improved ant colony optimization algorithm based on dynamically adjusting ant number[C]//IEEE International Conference on Robotics and Biominetics. Piscataway, USA: IEEE, 2012: 2039-2043.
[16] Maekawa T, Noda T, Tamura S, et al. Curvature continuous path generation for autonomous vehicle using B-spline curves[J]. Computer-Aided Design, 2010, 42(4): 350-359.

[17] O'Rourke J. Computational geometry in C[M]. Cambridge, UK: Cambridge University Press, 1997.
[18] Sahni S. Data structures, algorithms, and application in C++[M]. Summit, USA: Silicon Press, 2004.