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

doi:10.16180/j.cnki.issn1007-7820.2019.06.012

Abstract

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

CLC Number:

TP242.2

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.

Figures/Tables 9

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

Figure 7.

Table 1

Table 2

References 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

3D Space Path Planning Research Based on Improved Local Search Algorithm

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 16

Related Articles 11

Metrics

Comments

Recommended 10

[1]	LIU Yongjian,ZENG Guohui,HUANG Bo,LI Xiaobin. Research on Robot Path Planning Based on Improved Ant Colony Algorithm [J]. Electronic Science and Technology, 2020, 33(1): 13-18.
[2]	LIU Xuefang,ZENG Guohui,HUANG Bo,LU Dunke. Research on Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm [J]. Electronic Science and Technology, 2019, 32(9): 5-9.
[3]	ZHANG Chen, YOU Xiaoming. Improved Quantum ant Colony Algorithm of Path Planning for Mobile Robot Based on Grid Model [J]. , 2016, 29(7): 1-.
[4]	LIAN Xiaoping,WU Zi'an,KANG Huiqiong. Call Admission Control for OFDMA Systems Based on Ant Colony Algorithm [J]. , 2015, 28(6): 48-.
[5]	FENG Weiwei,QIU Jiong. Application of Ant Colony Algorithm in Fire Evacuation Platform [J]. , 2015, 28(4): 13-.
[6]	HUI Xiaolong,GAO Zhenxin. Research on Multi-objective and Deadlock-free Ant Colony Optimization Scheduling Algorithm with Petri Nets [J]. , 2014, 27(5): 179-.
[7]	CAI Zhen. Parallel test for Digital Microfluidic Biochips Based on the Ant Colony Algorithm [J]. , 2014, 27(10): 156-.
[8]	XIA Wei-Lei, WANG Li-Song. Research on and Implementation of Parallel Ant Colony Algorithm Based on MapReduce [J]. , 2013, 26(2): 146-.
[9]	ZHENG Enxing,LIU Ranran. Research on and Implementation of Ant Colony Algorithm Convergence [J]. , 2013, 26(1): 138-.
[10]	BAI Jian-Pu, WU Qiang. Research on and Application of Ant Colony Algorithms Hybrid Genetic Algorithms [J]. , 2011, 24(4): 20-.
[11]	CHEN Peng-Bo, NA Yan. Solution for Multi-sensor Optimize Assignment Based on Ant Colony Algorithm [J]. , 2011, 24(3): 94-.