基于改进遗传算法的移动机器人路径规划

魏彤; 龙琛

doi:10.13700/j.bh.1001-5965.2019.0298

基于改进遗传算法的移动机器人路径规划

doi: 10.13700/j.bh.1001-5965.2019.0298

魏彤^,,
龙琛

北京航空航天大学仪器科学与光电工程学院, 北京 100083

基金项目:

北京市科技计划项目 Z151100002115022

详细信息

作者简介:
魏彤男，博士，副教授。主要研究方向：计算机视觉、自动控制等。

龙琛男，硕士研究生。主要研究方向：路径规划与控制

通讯作者:
魏彤. E-mail:weitong@buaa.edu.cn

中图分类号: TP242.6
计量
- 文章访问数: 1821
- HTML全文浏览量: 1298
- PDF下载量: 443
- 被引次数: 0
出版历程
- 收稿日期: 2019-06-17
- 录用日期: 2019-08-12
- 网络出版日期: 2020-04-20

Path planning for mobile robot based on improved genetic algorithm

WEI Tong^,,
LONG Chen

School of Instrumentation and Optoelectronic Engineering, Beihang University, Beijing 100083, China

Funds:

Beijing Science and Technology Plan Project Z151100002115022

More Information

Corresponding author: WEI Tong, E-mail:weitong@buaa.edu.cn

摘要

摘要:
路径规划是实现移动机器人自主导航的关键技术。针对常规路径规划算法求解的路径长度非最短以及在前后两次规划过程中规划路径不连贯的问题，提出一种基于改进遗传算法的帧间关联平稳路径规划方法。首先，结合随机和定向两种搜索方式生成候选路径；然后，在常规遗传操作算子中引入插入算子和删除算子，并将规划路径的连贯性考虑进适应度函数中来计算每条候选路径的适应度值；最后，输出适应度值最高的路径作为当前最优路径。仿真结果表明了所提方法的正确性和可行性。实验结果表明，所提方法与A^*算法和常规遗传算法相比，移动机器人行驶路径长度分别减少了3.05%和1.85%；行驶过程中的最大偏航角变化量分别减少了38.02%和32.43%，转角绝对值之和分别减少了23.97%和19.94%，所提方法能规划出更优的路径，并显著提高移动机器人的行驶效率和平稳性。
- 路径规划 /
- 遗传算法 /
- 移动机器人 /
- 帧间关联 /
- 避障
Abstract:
Path planning is the key technology to realize autonomous navigation of mobile robots. For the problem that the path length is not the shortest and the path is not coherent in the two plan cycles with conventional path planning method, a new method for inter-frame correlation smooth path planning based on improved genetic algorithm is proposed. Firstly, the candidate paths were generated by combining random and directional search methods. Then, the insertion operator and deletion operator were added to conventional genetic operators, and the path coherence of two plan cycles was considered in the fitness function to calculate the fitness value of each candidate path. Finally, the path with the highest fitness value was output as the current optimal path. Simulation results show that the proposed method is correct and feasible. Experimental results show that, compared with A^* algorithm and conventional genetic algorithm, the path length of mobile robot is reduced by 3.05% and 1.85%, the variation of maximum yaw angle is reduced by 38.02% and 32.43%, and the sum of absolute value of turning angle is reduced by 23.97% and 19.94% respectively during the movement of mobile robot. It shows that the resulting path of this method is more optimal, which observably improves the moving efficiency and stationarity of the mobile robot.
- path planning /
- genetic algorithm /
- mobile robot /
- inter-frame correlation /
- obstacle avoidance

HTML全文

图 1 实际环境到栅格图的映射

Figure 1. Mapping of actual environment to grid map

下载: 全尺寸图片幻灯片

图 2 预瞄跟踪机制

Figure 2. Preview tracking mechanism

下载: 全尺寸图片幻灯片

图 3 当前帧和上一帧的路径差异

Figure 3. Path difference between current frame and previous frame

下载: 全尺寸图片幻灯片

图 4 改进遗传算法流程图

Figure 4. Flowchart of improved genetic algorithm

下载: 全尺寸图片幻灯片

图 5 路径编码

Figure 5. Path coding

下载: 全尺寸图片幻灯片

图 6 变异点的八邻域范围

Figure 6. Eight neighborhoods of mutated points

下载: 全尺寸图片幻灯片

图 7 删除前后路径对比

Figure 7. Comparison of path before and after deletion

下载: 全尺寸图片幻灯片

图 8 三种场景下的路径规划结果对比

Figure 8. Comparison of path planning results in three scenarios

下载: 全尺寸图片幻灯片

图 9 移动机器人转角变化曲线

Figure 9. Curves of mobile robot turning angle change

下载: 全尺寸图片幻灯片

图 10 改进遗传算法和A^*算法路径规划结果对比

Figure 10. Path planning results comparison between improved genetic algorithm and A^* algorithm

下载: 全尺寸图片幻灯片

图 11 改进遗传算法和常规遗传算法路径规划结果对比

Figure 11. Path planning results comparison between improved genetic algorithm and conventional genetic algorithm

下载: 全尺寸图片幻灯片

图 12 Jaugar4×4轮式移动机器人

Figure 12. Jaugar4×4 wheeled mobile robot

下载: 全尺寸图片幻灯片

图 13 移动机器人实际行驶过程中转角变化曲线

Figure 13. Curves of turning angle change in actual driving process of mobile robot

下载: 全尺寸图片幻灯片

图 14 改进遗传算法和A^*算法移动机器人行驶轨迹对比

Figure 14. Comparison of mobile robot trajectory between improved genetic algorithm and A^* algorithm

下载: 全尺寸图片幻灯片

图 15 改进遗传算法和常规遗传算法移动机器人行驶轨迹对比

Figure 15. Comparison of mobile robot trajectory between improved genetic algorithm and conventional genetic algorithm

下载: 全尺寸图片幻灯片

表 1 路径规划仿真结果比较

Table 1. Comparison of path planning simulation results

算法	路径长度/m	最大偏航角变化量/(°)	转角绝对值之和/(°)
A^*	15.4	28.8	385.0
GA	15.2	25.0	250.8
IGA	15.2	10.9	135.8

下载: 导出CSV

表 2 路径规划实验结果比较

Table 2. Comparison of path planning experiment results

算法	路径长度/m	最大偏航角变化量/(°)	转角绝对值之和/(°)
A^*	16.4	12.1	206.5
GA	16.2	11.1	196.1
IGA	15.9	7.5	157.0

下载: 导出CSV

参考文献(18)

[1]	MAC T T, COPOT C, TRAN D T, et al.Heuristic approaches in robot path planning:A survey[J].Robotics and Autonomous Systems, 2016, 86:13-28. https://www.sciencedirect.com/science/article/pii/S0921889015300671
[2]	赵晓, 王铮, 黄程侃, 等.基于改进A^算法的移动机器人路径规划[J].机器人, 2018, 40(6):137-144. http://d.old.wanfangdata.com.cn/Periodical/dianzixb201105043 ZHAO X, WANG Z, HUANG C K, et al.Mobile robot path planning based on improved A^ algorithm[J].Robot, 2018, 40(6):137-144(in Chinese). http://d.old.wanfangdata.com.cn/Periodical/dianzixb201105043
[3]	周慧子, 胡学敏, 陈龙, 等.面向自动驾驶的动态路径规划避障算法[J].计算机应用, 2017, 37(3):883-888. http://d.old.wanfangdata.com.cn/Periodical/jsjyy201703049 ZHOU H Z, HU X M, CEHN L, et al.Dynamic path planning obstacle avoidance algorithm for autonomous driving[J].Computer Application, 2017, 37(3):883-888(in Chinese). http://d.old.wanfangdata.com.cn/Periodical/jsjyy201703049
[4]	PADEN B, CAP M, YONG S Z, et al.A survey of motion planning and control techniques for self-driving urban vehicles[J].IEEE Transactions on Intelligent Vehicles, 2016, 1(1):33-55. http://cn.bing.com/academic/profile?id=c0bf0b899f4f5a9b0e860a01a2fc3ce2&encoded=0&v=paper_preview&mkt=zh-cn
[5]	ALIA C, GILLES T, REINE T, et al.Local trajectory planning and tracking of autonomous vehicles, using clothoid tentacles method[C]//IEEE Symposium on Intelligent Vehicles.Piscataway, NJ: IEEE Press, 2015: 674-679.
[6]	CHU K, LEE M, SUNWOO M.Local path planning for off-road autonomous driving with avoidance of static obstacles[J].IEEE Transactions on Intelligent Transportation Systems, 2012, 13(4):1599-1616. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=e9bf32af8035d38a1cee3d6ad1c2632c
[7]	王景存, 张晓彤, 陈彬, 等.一种基于Dijkstra算法的启发式最优路径搜索算法[J].北京科技大学学报, 2007, 29(3):346-350. http://d.old.wanfangdata.com.cn/Periodical/bjkjdxxb200703022 WANG J C, ZHANG X T, CHEN B, et al.Heuristic optimization path-finding algorithm based on Dijkstra algorithm[J].Journal of University of Science and Technology Beijing, 2007, 29(3):346-350(in Chinese). http://d.old.wanfangdata.com.cn/Periodical/bjkjdxxb200703022
[8]	WANG Q, HUANG W H, LIU B, et al.An improved A^* algorithm for path-planning of two-wheeled self-balancing vehicle[C]//IEEE Conference on Industrial Electronics and Applications(ICIEA).Piscataway, NJ: IEEE Press, 2018: 841-846.
[9]	辛煜, 梁华为, 杜明博, 等.一种可搜索无限个邻域的改A^算法[J].机器人, 2014, 36(5):627-633. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=jqr201405015 XIN Y, LIANG H W, DU M B, et al.An improved A^ algorithm for searching infinite neighborhood[J] Robot, 2014, 36(5):627-633(in Chinese). http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=jqr201405015
[10]	XU W D, WEI J Q, DOLAN J M, et al.A real-time motion planner with trajectory optimization for autonomous vehicles[C]//IEEE International Conference on Robotics and Automation.Piscataway, NJ: IEEE Press, 2012: 2061-2067.
[11]	GU T Y, SNIDER J, DOLAN J M, et al.Focused trajectory planning for autonomous on-road driving[C]//IEEE Symposium on Intelligent Vehicle.Piscataway, NJ: IEEE Press, 2013: 547-552.
[12]	LI X H, SUN Z P, LIU D X, et al.Combining local trajectory planning and tracking control for autonomous ground vehicles navigating along a reference path[C]//IEEE International Conference on Intelligent Transportation Systems.Piscataway, NJ: IEEE Press, 2014: 725-731.
[13]	WU M H, CHEN E K, SHI Q Q, et al.Path planning of mobile robot based on improved genetic algorithm[C]//2017 Chinese Automation Congress(CAC).Piscataway, NJ: IEEE Press, 2017: 6696-6700.
[14]	GONG Z H, SHAN Y X, DENG Y Q, et al.Balance mechanism design for the fusion of pure pursuit and PI tracking controller[C]//2018 Chinese Automation Congress (CAC).Piscataway, NJ: IEEE Press, 2018: 3149-3152.
[15]	LIU R, DUAN J.A path tracking algorithm of intelligent vehicle by preview strategy[C]//Proceedings of the 32nd Chinese Control Conference.Piscataway, NJ: IEEE Press, 2013: 5630-5635.
[16]	LAMINI C, BENHLIMA S, ELBEKRI A.Genetic algorithm based approach for autonomous mobile robot path planning[J].Procedia Computer Science, 2018, 127:180-189. http://cn.bing.com/academic/profile?id=cd3a606abf82a7e767a43c6eb198e7d2&encoded=0&v=paper_preview&mkt=zh-cn
[17]	LI Q, ZHANG W, YIN Y X, et al.An improved genetic algorithm of optimum path planning for mobile robots[C]//International Conference on Intelligent Systems Design & Applications.Piscataway, NJ: IEEE Press, 2006: 637-642.
[18]	SU J, LI J.Path planning for mobile robots based on genetic algorithms[C]//Proceedings of 9th International Conference on Natural Computation.Piscataway, NJ: IEEE Press, 2014: 723-727.