高级搜索

一种针对大型凹型障碍物的组合导航算法

李庆华 尤越 沐雅琪 张钊 冯超

引用本文: 李庆华, 尤越, 沐雅琪, 张钊, 冯超. 一种针对大型凹型障碍物的组合导航算法[J]. 电子与信息学报, doi: 10.11999/JEIT190179 shu
Citation:  Qinghua LI, Yue YOU, Yaqi MU, Zhao ZHANG, Chao FENG. Integrated Navigation Algorithm for Large Concave Obstacles[J]. Journal of Electronics and Information Technology, doi: 10.11999/JEIT190179 shu

一种针对大型凹型障碍物的组合导航算法

    作者简介: 李庆华: 男,1977年生,副教授,研究方向为信号与信息处理;
    尤越: 女,1996年生,硕士生,研究方向为智能路径规划;
    沐雅琪: 女,1996年生,硕士生,研究方向为复杂环境路径规划算法;
    张钊: 男,1995年生,硕士生,研究方向为人工智能运动目标行为识别;
    冯超: 男,1984年生,讲师,研究方向为路径规划运动规划
    通讯作者: 冯超,cfeng@qlu.edu.cn
  • 基金项目: 国家自然科学基金(61701270),齐鲁工业大学(山东省科学院)青年博士合作基金(2017BSHZ008)

摘要: 针对移动机器人导航过程中无法规避大型凹型障碍物问题,该文提出一种多状态的组合导航算法。算法按照不同的运动环境,将移动机器人的运行状态分类为运行态、切换态、避障态,同时定义了基于移动机器人运行速度和运行时间的状态双切换条件。当移动机器人处于运行态时,采用人工势场法进行导航,并实时观测毗邻障碍物的几何构型。在遭遇障碍物时,切换态用于判断是否满足状态切换条件,以进入避障态执行避障算法。避障完成后,状态自动切换回运行态继续执行导航任务。多状态的提出,可有效解决传统人工势场法在大型凹形障碍物的避障过程中存在局部震荡的问题。基于运行速度和运行时间的双切换条件判定算法,可实现多状态间的平滑切换。实验结果表明,该算法在解决局部震荡问题的同时,还可降低避障时间,提升导航算法效率。

English

    1. [1]

      王勇臻, 陈燕, 于莹莹. 求解多旅行商问题的改进分组遗传算法[J]. 电子与信息学报, 2017, 39(1): 198–205. doi: 10.11999/JEIT160211
      WANG Yongzhen, CHEN Yan, and YU Yingying. Improved grouping genetic algorithm for solving multiple traveling salesman problem[J]. Journal of Electronics &Information Technology, 2017, 39(1): 198–205. doi: 10.11999/JEIT160211

    2. [2]

      黄长强, 赵克新. 基于改进蚁狮算法的无人机三维航迹规划[J]. 电子与信息学报, 2018, 40(7): 1532–1538. doi: 10.11999/JEIT170961
      HUANG Changqiang and ZHAO Kexin. Three dimensional path planning of UAV with improved ant lion optimizer[J]. Journal of Electronics &Information Technology, 2018, 40(7): 1532–1538. doi: 10.11999/JEIT170961

    3. [3]

      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

    4. [4]

      PARK M G, JEON J H, and LEE M C. Obstacle avoidance for mobile robots using artificial potential field approach with simulated annealing[C]. 2001 IEEE International Symposium on Industrial Electronics, Pusan, South Korea, 2001: 1530–1535. doi: 10.1109/ISIE.2001.931933.

    5. [5]

      况菲, 王耀南. 基于混合人工势场-遗传算法的移动机器人路径规划仿真研究[J]. 系统仿真学报, 2006, 18(3): 774–777. doi: 10.16182/j.cnki.joss.2006.03.061
      KUANG Fei and WANG Yaonan. Robot path planning based on hybrid artificial potential field/genetic algorithm[J]. Journal of System Simulation, 2006, 18(3): 774–777. doi: 10.16182/j.cnki.joss.2006.03.061

    6. [6]

      LEE D, JEONG J, KIM Y H, et al. An improved artificial potential field method with a new point of attractive force for a mobile robot[C]. The 2017 2nd International Conference on Robotics and Automation Engineering, Shanghai, China, 2017: 63–67. doi: 10.1109/ICRAE.2017.8291354.

    7. [7]

      ROSTAMI S M H, SANGAIAH A K, WANG Jin, et al. Obstacle avoidance of mobile robots using modified artificial potential field algorithm[J]. EURASIP Journal on Wireless Communications and Networking, 2019, 2019(1): 70. doi: 10.1186/s13638-019-1396-2

    8. [8]

      HART P E, NILSSON N J, and RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100–107. doi: 10.1109/TSSC.1968.300136

    9. [9]

      DECHTER R and 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

    10. [10]

      田景文, 孔垂超, 高美娟. 一种车辆路径规划的改进混合算法[J]. 计算机工程与应用, 2014, 50(14): 58–63. doi: 10.3778/j.issn.1002-8331.1208-0319
      TIAN Jingwen, KONG Chuichao, and GAO Meijuan. Improved hybrid algorithm of vehicle path planning[J]. Computer Engineering and Applications, 2014, 50(14): 58–63. doi: 10.3778/j.issn.1002-8331.1208-0319

    11. [11]

      胡中华, 潘洲, 王凯凯. 基于混合算法的动态路径规划[J]. 煤矿机械, 2015, 36(12): 243–245. doi: 10.13436/j.mkjx.201512103
      HU Zhonghua, PAN Zhou, and WANG Kaikai. Dynamic path planning based on hybrid algorithm[J]. Coal Mine Machinery, 2015, 36(12): 243–245. doi: 10.13436/j.mkjx.201512103

    12. [12]

      唐志荣, 冀杰, 吴明阳, 等. 基于改进人工势场法的车辆路径规划与跟踪[J]. 西南大学学报: 自然科学版, 2018, 40(6): 174–182. doi: 10.13718/j.cnki.xdzk.2018.06.025
      TANG Zhirong, JI Jie, WU Mingyang, et al. Vehicles path planning and tracking based on an improved artificial potential field method[J]. Journal of Southwest University:Natural Science Edition, 2018, 40(6): 174–182. doi: 10.13718/j.cnki.xdzk.2018.06.025

    13. [13]

      赵奇, 赵阿群. 一种基于A*算法的多径寻由算法[J]. 电子与信息学报, 2013, 35(4): 952–957. doi: 10.3724/SP.J.1146.2012.00983
      ZHAO Qi and ZHAO Aqun. A multi-path routing algorithm base on A* algorithm[J]. Journal of Electronics &Information Technology, 2013, 35(4): 952–957. doi: 10.3724/SP.J.1146.2012.00983

    14. [14]

      DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1(1): 269–271. doi: 10.1007/BF01386390

    15. [15]

      沈文君. 基于改进人工势场法的机器人路径规划算法研究[D]. [硕士论文], 暨南大学, 2009.
      SHEN Wenjun. Algorithm research of path planning for robot based on improved artifical potential field[D]. [Master dissertation], Jinan University, 2009.

    1. [1]

      马彬, 李尚儒, 谢显中. 异构无线网络中基于人工神经网络的自适应垂直切换算法. 电子与信息学报,

    2. [2]

      陈光武, 程鉴皓, 杨菊花, 刘昊, 张琳婧. 基于改进神经网络增强自适应UKF的组合导航系统. 电子与信息学报,

    3. [3]

      任炯炯, 李航, 陈少真. 减轮Simeck算法的积分攻击. 电子与信息学报,

    4. [4]

      李云, 唐英, 刘涵霄. 基于Q-Learning算法的毫微微小区功率控制算法. 电子与信息学报,

    5. [5]

      冯浩, 黄坤, 李晶, 高榕, 刘东华, 宋成芳. 基于深度学习的混合兴趣点推荐算法. 电子与信息学报,

    6. [6]

      高敏娟, 党宏社, 魏立力, 张选德. 基于非局部梯度的图像质量评价算法. 电子与信息学报,

    7. [7]

      谌德荣, 吕海波, 李秋富, 宫久路, 厉智强, 韩肖君. 分块压缩感知的全变差正则化重构算法. 电子与信息学报,

    8. [8]

      王汝言, 梁颖杰, 崔亚平. 车辆网络多平台卸载智能资源分配算法. 电子与信息学报,

    9. [9]

      李林, 王林, 韩红霞, 姬红兵, 江莉. 自适应时频同步压缩算法研究. 电子与信息学报,

    10. [10]

      杨善超, 田康生, 刘仁争, 郑玉军. 基于价值优化的相控阵雷达任务调度算法. 电子与信息学报,

    11. [11]

      李付鹏, 刘敬彪, 王光义, 王康泰. 基于混沌集的图像加密算法. 电子与信息学报,

    12. [12]

      梁春燕, 袁文浩, 李艳玲, 夏斌, 孙文珠. 基于判别邻域嵌入算法的说话人识别. 电子与信息学报,

    13. [13]

      杜永兆, 范宇凌, 柳培忠, 唐加能, 骆炎民. 多种群协方差学习差分进化算法. 电子与信息学报,

    14. [14]

      陈鸿昶, 谢天, 高超, 李邵梅, 黄瑞阳. 候选标记信息感知的偏标记学习算法. 电子与信息学报,

    15. [15]

      杨磊, 李埔丞, 李慧娟, 方澄. 稳健高效通用SAR稀疏特征增强算法. 电子与信息学报,

    16. [16]

      魏嘉琪, 张磊, 刘宏伟, 盛佳恋. 曲线交叠外推的微动多目标宽带分辨算法. 电子与信息学报,

    17. [17]

      曹成虎, 赵永波, 索之玲, 庞晓娇, 徐保庆. 基于频谱校正的中国余数定理多普勒频率估计算法. 电子与信息学报,

    18. [18]

      毕秀丽, 魏杨, 肖斌, 李伟生, 马建峰. 基于级联卷积神经网络的图像篡改检测算法. 电子与信息学报,

    19. [19]

      吕增威, 魏振春, 韩江洪, 孙仁浩, 夏成凯. 基于多目标优化的无线传感器网络移动充电及数据收集算法. 电子与信息学报,

    20. [20]

      路新华, MANCHÓNCarles Navarro, 王忠勇, 张传宗. 大规模MIMO系统上行链路时间-空间结构信道估计算法. 电子与信息学报,

  • 图 1  障碍物建模图

    图 2  组合算法流程图

    图 3  针对大型凹形障碍物仿真结果

    图 4  针对大型凹形障碍物的A*算法的仿真结果

    图 5  针对大型凹形障碍物的改进人工势场法算法的仿真结果

    图 6  组合算法在其他场景下的运行结果

    表 1  人工势场法符号含义

    符号符号含义符号符号含义
    ${\rm{obs}}$障碍物${\bf{X}}{\rm{d}}$目标位置
    ${U_{{\rm{Xd}}}}(x)$引力势能${U_{{\rm{obs}}}}(x)$斥力势能
    ${U_{{\rm{art}}}}(x)$总势能${{F}}$合力
    ${{{F}}_{{\rm{Xd}}}}$吸引力${{F}}_{\rm{obs}}$排斥力
    $j$移动机器人感知到的周边障碍物的个数
    下载: 导出CSV

    表 2  A*算法符号含义

    符号符号含义符号符号含义
    $g(\cdot )$从初始节点到当前移动机器人所在节点node的
    启发式评估代价
    $h(\cdot )$从当前移动机器人所在节点node到目标节点的
    启发式评估代价
    $(x_{\rm{start}},y_{\rm{start}})$初始节点坐标$(x_{\rm{goal}},y_{\rm{goal}})$目标节点坐标
    $(x,y)$移动机器人实时位置坐标
    下载: 导出CSV

    表 3  模型描述符号含义

    符号符号含义符号符号含义
    $O_1$障碍物的左端点$O_2$障碍物的右端点
    $2\alpha $障碍物的长$\beta $障碍物的宽
    $v_t$移动机器人的实时线速度$a$移动机器人在运行态时的最大速度
    $\Delta d$移动机器人在某段时间内的移动距离$S_{\rm{obs}}$所有障碍物总面积
    $S_{\rm{map}}$地图面积$\rho $障碍物密度
    下载: 导出CSV

    表 4  算法性能比较

    算法时间(s)路径长度(m)
    A*算法22.401040.69
    改进人工势场法[15]无穷大无穷大
    本文组合算法10.62707.09
    下载: 导出CSV
  • 加载中
图(6)表(4)
计量
  • PDF下载量:  5
  • 文章访问数:  96
  • HTML全文浏览量:  64
文章相关
  • 通讯作者:  冯超, cfeng@qlu.edu.cn
  • 收稿日期:  2019-03-26
  • 录用日期:  2019-11-10
  • 网络出版日期:  2019-11-13
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章