留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

魏彤 龙琛

魏彤, 龙琛. 基于改进遗传算法的移动机器人路径规划[J]. 北京航空航天大学学报, 2020, 46(4): 703-711. doi: 10.13700/j.bh.1001-5965.2019.0298
引用本文: 魏彤, 龙琛. 基于改进遗传算法的移动机器人路径规划[J]. 北京航空航天大学学报, 2020, 46(4): 703-711. doi: 10.13700/j.bh.1001-5965.2019.0298
WEI Tong, LONG Chen. Path planning for mobile robot based on improved genetic algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(4): 703-711. doi: 10.13700/j.bh.1001-5965.2019.0298(in Chinese)
Citation: WEI Tong, LONG Chen. Path planning for mobile robot based on improved genetic algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(4): 703-711. doi: 10.13700/j.bh.1001-5965.2019.0298(in Chinese)

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

doi: 10.13700/j.bh.1001-5965.2019.0298
基金项目: 

北京市科技计划项目 Z151100002115022

详细信息
    作者简介:

    魏彤  男,博士,副教授。主要研究方向:计算机视觉、自动控制等。

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

    通讯作者:

    魏彤. E-mail:weitong@buaa.edu.cn

  • 中图分类号: TP242.6

Path planning for mobile robot based on improved genetic algorithm

Funds: 

Beijing Science and Technology Plan Project Z151100002115022

More Information
  • 摘要:

    路径规划是实现移动机器人自主导航的关键技术。针对常规路径规划算法求解的路径长度非最短以及在前后两次规划过程中规划路径不连贯的问题,提出一种基于改进遗传算法的帧间关联平稳路径规划方法。首先,结合随机和定向两种搜索方式生成候选路径;然后,在常规遗传操作算子中引入插入算子和删除算子,并将规划路径的连贯性考虑进适应度函数中来计算每条候选路径的适应度值;最后,输出适应度值最高的路径作为当前最优路径。仿真结果表明了所提方法的正确性和可行性。实验结果表明,所提方法与A*算法和常规遗传算法相比,移动机器人行驶路径长度分别减少了3.05%和1.85%;行驶过程中的最大偏航角变化量分别减少了38.02%和32.43%,转角绝对值之和分别减少了23.97%和19.94%,所提方法能规划出更优的路径,并显著提高移动机器人的行驶效率和平稳性。

     

  • 图 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
  • [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.
  • 加载中
图(15) / 表(2)
计量
  • 文章访问数:  520
  • HTML全文浏览量:  3
  • PDF下载量:  198
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-06-17
  • 录用日期:  2019-08-12
  • 刊出日期:  2020-04-20

目录

    /

    返回文章
    返回
    常见问答