留言板

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

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

双向跳点搜索算法的移动机器人全局路径规划研究

马小陆 梅宏

马小陆,梅宏. 双向跳点搜索算法的移动机器人全局路径规划研究[J]. 机械科学与技术,2020,39(10):1624-1631 doi: 10.13433/j.cnki.1003-8728.20190342
引用本文: 马小陆,梅宏. 双向跳点搜索算法的移动机器人全局路径规划研究[J]. 机械科学与技术,2020,39(10):1624-1631 doi: 10.13433/j.cnki.1003-8728.20190342
Ma Xiaolu, Mei Hong. Research on Bidirectional Jump Point Search Algorithm of Global Path Planning for Mobile Robots[J]. Mechanical Science and Technology for Aerospace Engineering, 2020, 39(10): 1624-1631. doi: 10.13433/j.cnki.1003-8728.20190342
Citation: Ma Xiaolu, Mei Hong. Research on Bidirectional Jump Point Search Algorithm of Global Path Planning for Mobile Robots[J]. Mechanical Science and Technology for Aerospace Engineering, 2020, 39(10): 1624-1631. doi: 10.13433/j.cnki.1003-8728.20190342

双向跳点搜索算法的移动机器人全局路径规划研究

doi: 10.13433/j.cnki.1003-8728.20190342
基金项目: 国家自然科学基金项目(51574004)、安徽高校自然科学研究重点项目(KJ2019A0065)、安徽省科技重大专项计划项目(16030901032)、特种重载机器人安徽省重点实验室开放课题(ZJQR004-2020)及芜湖市2017年度科技计划项目(2017yf26)资助
详细信息
    作者简介:

    马小陆(1979−),副教授,博士,研究方向为机器人和车联网的研究,maxiaolublade@163.com

  • 中图分类号: P242.6

Research on Bidirectional Jump Point Search Algorithm of Global Path Planning for Mobile Robots

  • 摘要: 针对跳点搜索算法在移动机器人全局路径规划中预处理规则存在不安全、路径搜索时间长和内存消耗大等问题,提出了一种双向跳点搜索算法的全局路径规划方法。该方法改进了跳点筛选规则,且从两个方向交替进行路径搜索,使得路径搜索时间和扩展节点大大减少,同时也提高了机器人的安全。为验证该算法的有效性,使用不同规格的栅格地图进行了仿真实验,仿真结果表明,双向跳点搜索算法的路径搜索时间比跳点搜索算法短,且栅格地图越大,效果越明显。最后在实际的移动服务机器人中进行了导航实验,实验结果证明双向跳点搜索算法比跳点搜索算法的路径搜索时间减少约30%,且安全性高。
  • 图  1  自然邻居的筛选条件

    图  2  强制邻居的筛选条件

    图  3  JPS算法路径寻优

    图  4  机器人行进示意图

    图  5  跳点筛选规则的改进

    图  6  双向JPS算法路径寻优的特殊情况

    图  7  双向JPS算法的路径寻优

    图  8  双向JPS算法移动机器人路径寻优流程图

    图  9  JPS和双向JPS算法的仿真结果

    图  10  实验所用移动机器人

    图  11  机器人硬件架构图

    图  12  目标点1下两种算法的路径规划结果

    图  13  目标点2下两种算法的路径规划结果

    图  14  目标点3下两种算法的路径规划结果

    表  1  JPS和双向JPS算法的搜索时间与扩展节点数量对比

    地图大小搜索时间/ms路径长度/格搜索节点/个搜索时间之比搜索节点之比
    JPS算法双向JPS算法JPS算法双向JPS算法JPS算法双向JPS算法
    15×152226.1428.48192110.90
    30×305479.2171.9970451.251.55
    50×50128214.08212.08109681.51.60
    100×1002612283.97255.56194982.171.98
    下载: 导出CSV

    表  2  目标点1下2种算法寻路时间对比

    参数JPS算法双向JPS算法
    行走路径长度/m 5.4 5.5
    寻路时间/ms 66.61 41.89
    行走时间/s 25.72 22.88
    搜索节点/个 53 39
    下载: 导出CSV

    表  3  目标点2下2种算法寻路时间对比

    参数JPS算法双向JPS算法
    行走路径长度/m 8.5 8.2
    寻路时间/ms 95.74 67.56
    行走时间/s 39.41 38.24
    搜索节点/个 77 45
    下载: 导出CSV
  • [1] 陈彦杰, 王耀南, 谭建豪, 等. 局部环境增量采样的服务机器人路径规划[J]. 仪器仪表学报, 2017, 38(5): 1093-1100 doi: 10.3969/j.issn.0254-3087.2017.05.007

    Chen Y J, Wang Y N, Tan J H, et al. Incremental sampling path planning for service robot based on local environments[J]. Chinese Journal of Scientific Instrument, 2017, 38(5): 1093-1100 (in Chinese doi: 10.3969/j.issn.0254-3087.2017.05.007
    [2] Khatib O. Real-time obstacle avoidance for manipulators and mobile robots[J]. The International Journal of Robotics Research, 1986, 5(1): 90-98 doi: 10.1177/027836498600500106
    [3] Cao L, Qiao D, Xu J W. Suboptimal artificial potential function sliding mode control for spacecraft rendezvous with obstacle avoidance[J]. Acta Astronautica, 2018, 143: 133-146 doi: 10.1016/j.actaastro.2017.11.022
    [4] 李擎, 张超, 韩彩卫, 等. 动态环境下基于模糊逻辑算法的移动机器人路径规划[J]. 中南大学学报, 2013, 44(S2): 104-108

    Li Q, Zhang C, Han C W, et al. Path planning based on fuzzy logic algorithm for mobile robots in dynamic environments[J]. Journal of Central South University , 2013, 44(S2): 104-108 (in Chinese
    [5] Dijkstra E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1(1): 269-271 doi: 10.1007/BF01386390
    [6] Dechter R, Pearl J. Generalized best-first search strategies and the optimality of A*[J]. Journal of the ACM, 1985, 32(3): 505-536 doi: 10.1145/3828.3830
    [7] 黄辰, 费继友, 刘洋, 等. 基于动态反馈A*蚁群算法的平滑路径规划方法[J]. 农业机械学报, 2017, 48(4): 34-40, 120 doi: 10.6041/j.issn.1000-1298.2017.04.004

    Huang C, Fei J Y, Liu Y, et al. Smooth path planning method based on dynamic feedback A* ant colony algorithm[J]. Transactions of the Chinese Society for Agricultural Machinery, 2017, 48(4): 34-40, 120 (in Chinese doi: 10.6041/j.issn.1000-1298.2017.04.004
    [8] 裴以建, 杨亮亮, 杨超杰. 基于一种混合遗传算法的移动机器人路径规划[J]. 现代电子技术, 2019, 42(2): 183-186

    Pei Y J, Yang L L, Yang C J. Mobile robot path planning based on a hybrid genetic algorithm[J]. Modern Electronics Technique, 2019, 42(2): 183-186 (in Chinese
    [9] 王功亮, 王好臣, 李振雨, 等. 基于优化遗传算法的移动机器人路径规划[J]. 机床与液压, 2019, 47(3): 37-40, 100

    Wang G L, Wang H C, Li Z Y, et al. Path planning for mobile robots based on optimized genetic algorithm[J]. Machine Tool & Hydraulics, 2019, 47(3): 37-40, 100 (in Chinese
    [10] Tang B W, Zhu Z X, Luo J J. A convergence-guaranteed particle swarm optimization method for mobile robot global path planning[J]. Assembly Automation, 2017, 37(1): 114-129 doi: 10.1108/AA-03-2016-024
    [11] 游晓明, 刘升, 吕金秋. 一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用[J]. 控制与决策, 2017, 32(3): 552-556

    You X M, Liu S, Lyu J Q. Ant colony algorithm based on dynamic search strategy and its application on path planning of robot[J]. Control and Decision, 2017, 32(3): 552-556 (in Chinese
    [12] 刘建华, 杨建国, 刘华平, 等. 基于势场蚁群算法的移动机器人全局路径规划方法[J]. 农业机械学报, 2015, 46(9): 18-27 doi: 10.6041/j.issn.1000-1298.2015.09.003

    Liu J H, Yang J G, Liu H P, et al. Robot global path planning based on ant colony optimization with artificial potential field[J]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(9): 18-27 (in Chinese doi: 10.6041/j.issn.1000-1298.2015.09.003
    [13] 张原艺, 章政, 王泉. 基于改进多步长蚁群算法的机器人路径规划[J]. 计算机工程与设计, 2018, 39(12): 3829-3834, 3866

    Zhang Y Y, Zhang Z, Wang Q. Robot path planning based on improved multi-step ant colony algorithm[J]. Computer Engineering and Design, 2018, 39(12): 3829-3834, 3866 (in Chinese
    [14] 邱磊. 利用跳点搜索算法加速A*寻路[J]. 兰州理工大学学报, 2015, 41(3): 102-107 doi: 10.3969/j.issn.1673-5196.2015.03.022

    Qiu L. Speed-up of A* pathfinding with jump point search algorithm[J]. Journal of Lanzhou University of Technology, 2015, 41(3): 102-107 (in Chinese doi: 10.3969/j.issn.1673-5196.2015.03.022
    [15] 赵晓, 王铮, 黄程侃, 等. 基于改进A*算法的移动机器人路径规划[J]. 机器人, 2018, 40(6): 903-910

    Zhao X, Wang Z, Huang C K, et al. Mobile robot path planning based on an improved A* algorithm[J]. Robot, 2018, 40(6): 903-910 (in Chinese
  • 加载中
图(14) / 表(3)
计量
  • 文章访问数:  425
  • HTML全文浏览量:  93
  • PDF下载量:  34
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-09-10
  • 网络出版日期:  2020-11-07
  • 刊出日期:  2020-10-05

目录

    /

    返回文章
    返回