基于改进局部搜索算法的三维空间路径规划研究

doi:10.16180/j.cnki.issn1007-7820.2019.06.012

摘要/Abstract

摘要：

在机器人路径规划中,搜索区域维数增大会导致路径搜索算法收敛时间过长甚至不收敛的现象发生。针对此类问题,文中以改进的局部搜索算法为基础,融合蚁群算法中信息素因子和人工势场算法中势场因子,建立了启发函数模型以提高寻优的目的性,并对搜索到的路径用迭代法进行优化。文中具体讨论了三维空间中路径点的选取方式和启发函数模型的建立方法,同时给出了算法的详细流程。最后通过MATLAB仿真实验证明基于改进后的算法进行路径规划时,迭代次数降低,搜索速度变快,路径点轨迹趋势更加平稳。

关键词: 局部搜索算法, 蚁群算法, 人工势场算法, 启发函数模型, 迭代法, 三维空间路径规划

Abstract:

In robot path planning, the increase of the search area dimension will cause the path search algorithm to not converge or converge for too long time. Aiming at this problem, heuristic function model was established to improve the purpose of optimization based on the improved local search algorithm, integrating the pheromone in ant colony algorithm and potential field factor in the artificial potential field algorithm. The iteration method was used for search path optimization. The selection of path points in three-dimensional space and the establishment of heuristic function model were discussed in detail, and the detailed flow of the algorithm was presented. Finally, through the MATLAB simulation experiment, the results showed when the path planning was carried out based on the improved algorithm, the number of iterations was decreased, the search speed was faster, and the path point trajectory trend was more stable.

Key words: local search algorithm, ant colony algorithm, artificial potential field algorithm, heuristic function model, iterative method, three-dimensional space path planning

中图分类号:

TP242.2

赵威,曾国辉,黄勃,朱爽鑫,刘瑾. 基于改进局部搜索算法的三维空间路径规划研究[J]. 电子科技, 2019, 32(6): 58-63.

ZHAO Wei,ZENG Guohui,HUANG Bo,ZHU Shuangxin,LIU Jin. 3D Space Path Planning Research Based on Improved Local Search Algorithm[J]. Electronic Science and Technology, 2019, 32(6): 58-63.

图/表 9

图1

图2

图3

图4

图5

图6

图7

表1

表2

参考文献 16

[1]	Rubio F, Abu-Dakka F J, Valero F ,et al.Comparing the efficiency of five algorithms applied to path planning for industrial robots[J]. Industrial Robot:An International Journal, 2012,39(6):580-591. doi: 10.1108/01439911211268787
[2]	Dasgupta B, Gupta A, Singla E . A variational approach to path planning for hyper-redundant manipulators[J]. Robotics and Autonomous Systems, 2009,57(2):194-201. doi: 10.1016/j.robot.2008.05.001
[3]	Ananthanarayanan, Hariharan S . Complete path planni ng of higher DOF manipulators in human like envir onments[D].Dayton:University of Dayton. Electrical Engineering, 2015.
[4]	武雅杰, 杨晶东 . 基于A~*算法的机器人路径规划[J]. 电子科技, 2017,30(6):124-127.
	Wu Yajie, Yang Jingdong . Robot path planning based on A~* algorithm[J]. Electronic Science and Technology, 2017,30(6):124-127.
[5]	胡荟, 蔡秀珊 . 基于改进蚁群算法的三维空间机器人路径规划[J]. 计算机系统应用, 2011,20(11):95-98.
	Hu Hui, Cai Xiushan . 3D robot path planning based on improved ant colony algorithm[J]. Application of Computer System, 2011,20(11):95-98.
[6]	刘利强, 于飞, 戴运桃 . 基于蚁群算法的水下潜器三维空间路径规划[J].系统仿真学报, 2008(14):3712-3716.
	Liu Liqiang, Yu Fei, Dai Yuntao . Three-dimensional space path planning of water submersible based on ant colony algorithm[J].Journal of System Simulation, 2008(14):3712-3716.
[7]	张文强 . 6 kg工业机器人路径规划及运动仿真研究[D]. 合肥:合肥工业大学, 2017.
	Zhang Wenqiang . Research on path planning and motion simulation of 6 kg industrial robot[D]. Heifei:Hefei University of Technology, 2017.
[8]	刘方洁 . 基于分组与局部搜索的大规模全局优化新算法[D]. 西安:西安电子科技大学, 2017.
	Liu Fangjie . New large-scale global optimization algorithm based on grouping and local search[D]. Xi’an:Xidian University, 2017.
[9]	Secara C, Vladareanu L . Iterative strategies for obstacle avoidance of a redundant manipulator[J].WSEAS Transactions on Mathematics, 2010(7):1129-1137.
[10]	沈黎明 . 基于启发式搜索方法的机器人三维空间路径规划研究[D]. 秦皇岛:燕山大学, 2014.
	Shen Liming . Research on robot 3D spatial path planning based on heuristic search method[D]. Qinhuangdao:Yanshan University, 2014.
[11]	丁家如, 杜昌平, 赵耀 , 等. 基于改进人工势场法的无人机路径规划算法[J]. 计算机应用, 2016,36(1):287-290. doi: 10.11772/j.issn.1001-9081.2016.01.0287
	Ding Jiaru, Du Changping, Zhao Yao , et al. Uav path planning algorithm based on improved artificial potential field method[J]. Computer Application, 2016,36(1):287-290. doi: 10.11772/j.issn.1001-9081.2016.01.0287
[12]	Lin J S, Wang C H . Enhancement of the gobal convergence of using iterative dynamic programming to solve optimal control problems[J]. Industrial and Engineering Chemistry Research, 1998,37(9):2469-2478. doi: 10.1021/ie970629j
[13]	徐达, 蔡满春, 陈悦 . 基于改进Floyd算法的城市交通网络最短路径规划[J]. 电子科技, 2017,30(7):17-20.
	Xu Da, Cai Manchun, Chen Yue . Urban traffic network shortest path planning based on improved Floyd algorithm[J]. Electronic Science and Technology, 2017,30(7):17-20.
[14]	林保蛟, 华云松, 顾岩秀 . 双足行走机器人运动轨迹规划[J]. 电子科技, 2017,30(2):45-48.
	Lin Baojiao, Hua Yunsong, Gu Yanxiu . Motion trajector planning of biped walking robot[J]. Electronic Science and Technology, 2017,30(2):45-48.
[15]	Schneider H C, Wahrburg J . Robot surgery[M]. Berlin:Intech, 2010.
[16]	卜新苹, 苏虎, 邹伟 , 等. 基于复杂环境非均匀建模的蚁群路径规划[J]. 机器人, 2016,38(3):276-284. doi: 10.13973/j.cnki.robot.2016.0276
	Bu Xinping, Su Hu, Zou Wei , et al. Ant colony path planning based on heterogeneous modeling of complex environment[J]. Robot, 2016,38(3):276-284. doi: 10.13973/j.cnki.robot.2016.0276

参数	传统蚁群算法	改进蚁群算法	综合改进搜索算法
起始点坐标和目标点坐标	起始点(0,18,5) 目标点(32,19,5)
P:信息素初值	1	1	1
ξ:局部信息素挥发系数	0.5	0.5	0.5
ρ:全局信息素挥发系数	0.9	0.9	0.9
α₁:引力因子重要程度	-	1	1
α₂:障碍因子重要程度	-	1	1
α₃:距离因子重要程度	-	1	1
α₄:信息素因子重要程度	2	2	2
d_m:障碍物极限距离	-	1	1
d₀:斥力作用距离	-	2	2
l:蚂蚁批次	100	100	100
ζ(i):阀值	-	-	1
y_max(搜索区域)	3	3	3
h_max(搜索区域)	3	3	3