基于群体智能成果的路径规划程序自动生成系统

doi:10.11959/j.issn.2096-6652.202228

智能科学与技术学报 ›› 2022, Vol. 4 ›› Issue (2): 255-263.doi: 10.11959/j.issn.2096-6652.202228

基于群体智能成果的路径规划程序自动生成系统

王雨倩¹, 丁嵘²

¹ 北京航空航天大学计算机学院，北京 100191
² 北京航空航天大学人工智能研究院，北京 100191

出版日期:2022-06-15 发布日期:2022-06-01
作者简介:王雨倩（1999− ），女，北京航空航天大学计算机学院硕士生，主要研究方向为无人系统智能算法
丁嵘（1975− ），男，博士，北京航空航天大学人工智能研究院博士生导师，主要研究方向为软件工程、自主无人系统、群体智能等
基金资助:
国家重点研发计划资助项目(2017YFB1001802)

Automatic path planning program generation system based on swarm intelligence results

Yuqian WANG¹, Rong DING²

¹ School of Computer Science and Engineering, Beihang University, Beijing 100191, China
² Institute of Artificial Intelligence, Beihang University, Beijing 100191, China

Online:2022-06-15 Published:2022-06-01
Supported by:
The National Key Research and Development Program of China(2017YFB1001802)

摘要/Abstract

摘要：

路径规划算法被广泛地应用于各种运动规划任务，如机器人运动、自动驾驶等。迄今为止，许多优秀的路径规划算法被提出并被应用于不同领域。对于一个特定的任务环境，选择合适的路径规划算法能更高效地规划出满足约束条件的较优路径。基于群体智能成果，以遗传编程算法为框架，研究快速扩展随机树（RRT）路径规划算法及其变种RRT-Star路径规划算法、RRT-Star-Smart路径规划算法在不同任务环境下的适应度及路径规划效率，设计出一个路径规划程序自动生成系统。该系统能自主分析当前环境地图特征，并结合 RRT 路径规划算法及其变种算法的特性，生成新的、更适配当前环境的路径规划算法。生成的路径规划算法能高效地规划出一条从起始点到目标点的可行路径。

关键词: 群体智能, 路径规划算法, 遗传编程, 快速扩展随机树, RRT-Star, RRT-Star-Smart

Abstract:

Path planning algorithms are widely used in various motion planning tasks, such as robot motion and autonomous driving.So far, many excellent path planning algorithms have been proposed for applications in different fields.For a specific task environment, choosing the appropriate path planning algorithm can plan a better path that satisfies the constraints more efficiently.Based on the results of swarm intelligence, the adaptability and path planning efficiency of rapidly-exploring random tree (RRT) path planning algorithm and its variants RRT-Star path planning algorithm and RRT-Star-Smart path planning algorithm under different task environments were studied.Using genetic programming algorithm as a framework to design a system, which could automatically analyze the map features of the current environment and combine the characteristics of RRT path planning algorithm and its variants to generate new path planning algorithms that were more suitable for the current environment.The generated path planning algorithm can efficiently plan a feasible path from the starting point to the target point.

Key words: swarm intelligence, path planning algorithm, genetic programming, rapidly-exploring random tree, RRT-Star, RRT-Star-Smart

中图分类号:

TP181

王雨倩,丁嵘. 基于群体智能成果的路径规划程序自动生成系统[J]. 智能科学与技术学报, 2022, 4(2): 255-263.

Yuqian WANG,Rong DING. Automatic path planning program generation system based on swarm intelligence results[J]. Chinese Journal of Intelligent Science and Technology, 2022, 4(2): 255-263.

图/表 10

图1

图2

图3

表1

图5

图4

图6

图7

图8

表2

4个算法规划出的路径长度及规划用时"

算法	路径长度/px	规划用时/s
RRT路径规划算法	63.641828	0.012558
RRT-Star路径规划算法	60.637968	10.381315
RRT-Star-Smart路径规划算法	56.644553	1.467539
本文算法	$51 . 918036$	$0 . 001001$

表2

参考文献 23

[1]	LA VALLE S M . Motion planning[J]. IEEE Robotics ＆ Automation Magazine, 2011,18(2): 108-118.
[2]	ZHANG H Y , LIN W M , CHEN A X . Path planning for the mobile robot:a review[J]. Symmetry, 2018,10(10): 450.
[3]	LAVALLE S M , KUFFNER J J . Rapidly-exploring random trees:progress and prospects[M].[S.l.:s.n.], 2001.
[4]	PéREZ-HIGUERAS N , CABALLERO F , MERINO L . Learning robot navigation behaviors by demonstration using a RRT* planner[C]// Proceedings of the International Conference on Social Robotics.[S.l.:s.n.], 2016.
[5]	ISLAM F , NASIR J , MALIK U ,et al. RRT-Smart:rapid convergence implementation of RRT towards optimal solution[C]// Proceedings of 2012 IEEE International Conference on Mechatronics and Automation. Piscataway:IEEE Press, 2012: 1651-1656.
[6]	SAKAMOTO E , IBA H . Inferring a system of differential equations for a gene regulatory network by using genetic programming[C]// Proceedings of 2001 Congress on Evolutionary Computation.[S.l.:s.n.], 2001.
[7]	SRINIVAS M , PATNAIK L M . Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Transactions on Systems Man ＆ Cybernetics, 2002,24(4): 656-667.
[8]	LE G C , NGUYEN T , FORREST S ,et al. GenProg:a generic method for automatic software repair[J]. IEEE Transactions on Software Engineering, 2012,38(1): 54-72.
[9]	KHAN J A , LIU L , WEN L ,et al. Crowd intelligence in requirements engineering:current status and future directions[C]// Proceedings of the International Working Conference on requirements Engineering:Foundation for Software Quality. Cham:Springer, 2019: 245-261.
[10]	LIU J R , JI W . Crowd intelligence evolution based on complex network[J]. International Journal of Crowd Science, 2021,5(3): 281-292.
[11]	CUI B J , LI J S , GUO T ,et al. Code comparison system based on abstract syntax tree[C]// Proceedings of 2010 3rd IEEE International Conference on Broadband Network and Multimedia Technology. Piscataway:IEEE Press, 2010: 668-673.
[12]	FERREIRA C . Gene expression programming:a new adaptive algorithm for solving problems[J]. Complex Systems, 2001,13(2): 87-129.
[13]	YAN Z C , BI Y , XUE B ,et al. Automatically extracting features using genetic programming for low-quality fish image classification[C]// Proceedings of 2021 IEEE Congress on Evolutionary Computation. Piscataway:IEEE Press, 2021: 2015-2022.
[14]	AHVANOOEY M T , LI Q M , WU M ,et al. A survey of genetic programming and its applications[J]. KSll Transactions on Internet and Information Systems. 2019,13(14): 1765-1794.
[15]	OLTEAN M . Solving classification problems using traceless genetic programming[J]. arXiv preprint,2021,arXiv:2111.14790.
[16]	KANG J G , JUNG J W . Post triangular rewiring method for shorter RRT robot path planning[J]. International Journal of Fuzzy Logic and Intelligent Systems, 2021,21(3): 213-221.
[17]	KALA R . Rapidly exploring random graphs:motion planning of multiple mobile robots[J]. Advanced Robotics, 2013,27(14): 1113-1122.
[18]	ZHANG L W , LIN Z B , WANG J ,et al. Rapidly-exploring random trees multi-robot map exploration under optimization framework[J]. Robotics and Autonomous Systems, 2020131: 103565.
[19]	GE Q Y , LI A J , LI S H ,et al. Improved bidirectional RRT path planning method for smart vehicle[J]. Mathematical Problems in Engineering, 2021:6669728.
[20]	SUDHAKARA P , GANAPATHY V , SUNDARAN K . Optimal trajectory planning based on bidirectional spline-RRT? for wheeled mobile robot[C]// Proceedings of 2017 3rd International Conference on Sensing,Signal Processing and Security. Piscataway:IEEE Press, 2017: 65-68.
[21]	TAK H T , PARK C G , LEE S C . Improvement of RRT*-Smart algorithm for optimal path planning and application of the algorithm in 2＆ 3-dimension environment[J]. Journal of the Korean Society for Aviation and Aeronautics, 2019,27(2): 1-8.
[22]	HASSANAT A , ALMOHAMMADI K , ALKAFAWEEN E ,et al. Choosing mutation and crossover ratios for genetic algorithms—a review with a new dynamic approach[J]. Information, 2019,10(12): 390.
[23]	DENG W , XU J J , SONG Y J ,et al. Differential evolution algorithm with wavelet basis function and optimal mutation strategy for complex optimization problem[J]. Applied Soft Computing, 2021,100: 106724.

指令	简化符号	概率	操作	参数
funcRand	?	[0, 0.1)	随机采样一个点	无
funcAddNodeNearest	-	[0.1, 0.4)	将距离采样点最近的树中节点作为新扩展节点的父节点	采样点坐标
funcAddNodeRewire	*	[0.4, 0.7)	以采样点为圆心画圆，将圆范围内到起点最近的树中节点作为新扩展节点的父节点，并进行重布线	采样点坐标
funGoalRatePath	=	[0.7, 0.8)	调整采样点趋于目标点概率	无
funcPathOptimization	$	[0.8, 0.9)	从叶子节点开始，寻找能避开障碍物直接到达的父节点并与之相连，化曲为直	无
实数	无	[0.9, 1)	生成节点坐标	无

基于群体智能成果的路径规划程序自动生成系统

Automatic path planning program generation system based on swarm intelligence results

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 23

相关文章 3

Metrics

推荐阅读 0

[1]	杨强, 童咏昕, 王晏晟, 范力欣, 王薇, 陈雷, 王魏, 康焱. 群体智能中的联邦学习算法综述[J]. 智能科学与技术学报, 2022, 4(1): 29-44.
[2]	冯埔, 吴文峻, 罗杰, 于鑫, 田雍恺. 基于群体熵的机器人群体智能汇聚度量[J]. 智能科学与技术学报, 2022, 4(1): 65-74.
[3]	项羽铭, 陈焜, 赵志峰, 李荣鹏, 张宏纲. 脑注意力机制启发的群体智能协同避障方法[J]. 智能科学与技术学报, 2022, 4(1): 84-96.