Research on Path Planning Based on Variable Parameters Firefly Algorithm and Maklink Graph
-
摘要: 针对静态二维环境下的全局路径规划问题,提出了一种基于变参数萤火虫算法和Maklink图的全局路径规划方法。将定参数的连续型萤火虫算法改进为变参数的离散型萤火虫算法;根据全局路径规划问题的特点,定义了变参数萤火虫算法的编码规则及萤火虫之间的距离表征方法;以含有多个任意形状障碍物的环境为例,在Maklink图的基础上采用变参数萤火虫算法对路径进行优化,改进后的萤火虫算法能够较好的解决离散路径规划问题。实验表明:变参数萤火虫算法的性能不仅优于标准萤火虫算法,而且在收敛速度、算法稳定性等方面优于粒子群算法。Abstract: A global path planning method, based on the firefly algorithm with variable parameters and Maklink graph, is proposed to solve the global path planning problem in two-dimensional static environment. At first, the continuous firefly algorithm with fixed parameters is modified to be the discrete firefly algorithm with variable parameters. Then, according to the characteristics of the global path planning problem we define, the encoding rules and the distance between fireflies. Finally, taking the environment with some obstacles of stochastic shape as the example, and based on the Maklink graph, the firefly algorithm with variable parameters is adopted to optimize the path. The results show that the proposed method can not only solve the discrete path planning problem well, but also has better performance than the standard firefly algorithm. Furthermore, it's better than the PSO algorithm in convergence speed and computation stability.
-
Key words:
- algorithms /
- computer simulation /
- convergence of numerical methods
-
[1] 李磊,叶涛,谭民,等.移动机器人技术研究现状与未来[J].机器人,2002,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 (in Chinese) [2] Romero A, Cazorla M. Topological visual mapping in robotics[J]. Cognitive Processing, 2012,13(1):305-308 [3] 柳长安,鄢小虎,刘春阳,等.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报,2011,39(5):1220-1224 Liu C A, Yan X H, Liu C Y, et al. Dynamic path planning for mobile robot based on improved ant colony optimization algorithm[J]. Acta Electronica Sinica, 2011,39(5):1220-1224 (in Chinese) [4] 宋金泽,戴斌,单恩忠,等.一种改进的RRT路径规划算法[J].电子学报,2010,38(2A):225-228 Song J Z, Dai B, Shan E Z, et al. An improved RRT path planning algorithm[J]. Acta Electronica Sinica, 2010,38(2A):225-228 (in Chinese) [5] Tan G Z, He H, Sloman A. Ant colony system algorithm for real-time globally optimal path planning of mobile robots[J]. Acta Automatica Sinica, 2007,33(3):279-285 [6] 陈曦,谭冠政,江斌.基于免疫遗传算法的移动机器人实时最优路径规划[J].中南大学学报,2008,39(3):577-583 Chen X, Tan G Z, Jiang B. Real-time optimal path planning for mobile robots based on immune genetic algorithm[J]. Journal of Central South University, 2008,39(3),577-583 (in Chinese) [7] 吴宪祥,郭宝龙,王娟.基于粒子群三次样条优化的移动机器人路径规划算法[J].机器人,2009,31(6):556-560 Wu X X, Guo B L, Wang J. Mobile robot path planning algorithm based on particle swarm optimization of cubic splines[J]. Robot, 2009,31(6):556-560 (in Chinese) [8] Yang X S. Firefly algorithm, stochastic test functions and design optimization[J]. International Journal of Bio-Inspired Computation, 2010,2(2):78-84 [9] Yang X S. Firefly algorithm, levy flights and global optimization[C]//Research and Development in Intelligent Systems XXVI, London: Springer, 2010:209-218 [10] 周季华,叶春明.应用萤火虫算法求解置换流水线问题[J].计算机应用研究,2013,30(1):152-154 Zhou J H, Ye C M. Using firefly algorithm to solve permutation flow-shop scheduling problem[J]. Application Research of Computers, 2013,30(1):152-154 (in Chinese) [11] Jati G K, Suyanto. Evolutionary discrete firefly algorithm for travelling salesman problem[J]. Adaptive and Intelligent Systems, 2011,6943:393-403 [12] Miguel L F F, Lopez R H, Miguel L F F. MultiModal size, shape, and topology optimisation of truss structures using the firefly algorithm[J]. Advances in Engineering Software, 2013,56:23-37 [13] Sayadi M K, Hafezalkotob A, Naini S G J. Firefly-inspired algorithm for discrete optimization problems: An application to manufacturing cell formation[J]. Journal of Manufacturing Systems, 2013,32(1):78-84 [14] 曾冰,李明富,张翼,等.基于萤火虫算法的装配序列规划研究[J].机械工程学报,2013,49(11):177-184 Zeng B, Li M F, Zhang Y, et al. Research on assembly sequence planning based on firefly algorithm[J]. Journal of Mechanical Engineering, 2013,49(11):177-187 (in Chinese) [15] Wang C G, Guo L H, Duan H, et al. A modified firefly algorithm for UCAV path planning[J]. International Journal of Hybrid Information Technology, 2012,5(3):123-142
点击查看大图
计量
- 文章访问数: 164
- HTML全文浏览量: 24
- PDF下载量: 5
- 被引次数: 0