首页|期刊简介|投稿指南|分类索引|刊文选读|订阅指南|证明资料|样刊邮寄查询|常见问题解答|联系我们
宋晓茹,任怡悦. 面向移动机器人快速全局路径规划的改进跳点搜索算法[J]. 科学技术与工程, 2020, 20(29): 11992-11999.
Song Xiao-ru,任怡悦.Research on Improved Jump Point Search Algorithm for Fast Global Path Planning of Mobile Robots[J].Science Technology and Engineering,2020,20(29):11992-11999.
面向移动机器人快速全局路径规划的改进跳点搜索算法
Research on Improved Jump Point Search Algorithm for Fast Global Path Planning of Mobile Robots
投稿时间:2019-09-09  修订日期:2020-06-24
DOI:
中文关键词:  移动机器人 全局路径规划 跳点搜索算法 “块”操作
英文关键词:mobile robot global path planning jump point search "block" operation
基金项目:国家重点研发计划(2016YFE0111900)、国家自然科学基金(61773016)和陕西省重点研发计划(2018KW‐022)资助
     
作者单位
宋晓茹 西安工业大学 电子信息工程学院 陕西 西安
任怡悦 西安工业大学 电子信息工程学院
摘要点击次数: 76
全文下载次数: 40
中文摘要:
      针对传统全局路径规划算法计算量大,寻路时间过长等问题,为了进一步提高移动机器人综合作业能力,本文提出了一种基于跳点搜索算法的快速全局路径规划算法,旨在减少时间成本,以满足移动机器人在实际复杂环境中对智能性、高效性、安全性和可靠性的要求。首先通过“块”操作方法,在一次搜索中快速扫描底层网格中的一个区域,将跳点搜索算法的修剪规则一次应用于多个节点,减少搜寻跳点时所涉及的大部分迭代计算,并在采取“对角优先”方式的前提下,剔除仅具有改变方向的中间转折点,大量减少Openlist和Closedlist的不必要节点,减少计算量,提高路径规划的实时性。为了验证改进算法的有效性与可行性,分别在规则的网格地图、测试库基准地图及移动机器人Turtlebot2进行仿真实验验证,结果表明在生成相同路径的基础上,改进跳点搜索算法与A*算法相比扩展节点数目缩减了68.9%,搜索耗费时间降低了71.9%;与传统跳点搜索算法相比,扩展节点数目缩减了41.3%,搜索耗费时间降低了33.4%,能够满足移动机器人快速全局路径规划的要求。
英文摘要:
      Aiming at the problems of large computational complexity and long path-finding time for traditional global path planning algorithms, the fast global path planning algorithm based on the jump point search algorithm is studied in this paper , to further improve the comprehensive operation capability of mobile robots. The time cost is reduced, the comprehensive operation capability of the mobile robot is further improved and the requirements for intelligence, efficiency, safety and reliability of robots in practical complex environments are met. First, through the "block" operation method, the area in the underlying grid is quickly scanned in one search, and the pruning rules of the jump point search algorithm are applied to multiple nodes at once,so the most of the iterations involved in searching for jump points are reduced. On the premise of adopting the "diagonal priority" method, eliminate the intermediate turning points with only changing directions, thus the unnecessary nodes of OpenList and ClosedList are greatly reduced, the calculation amount is reduced, and the real-time performance of the path planning is improved. In order to verify the effectiveness and feasibility of the improved algorithm, the simulation experiments were carried out on the regular grid map, the benchmark sets and the mobile robot Turtlebot2. The results show that on the basis of generating the same path, compared with the A* algorithm, the improved jump point search algorithm reduces the number of extended nodes by 68.9%, and the search time is reduced by 71.9%. Compared with the traditional jump point search algorithm, the improved jump point search algorithm reduces the number of extended nodes by 41.3% and the search time by 33.4%. Therefore the improved jump point search can meet the requirements of fast global path planning for mobile robots.
查看全文  查看/发表评论  下载PDF阅读器
关闭
你是第33881836位访问者
版权所有:科学技术与工程编辑部
主管:中国科学技术协会    主办:中国技术经济学会
Tel:(010)62118920 E-mail:stae@vip.163.com
京ICP备05035734号-4
技术支持:本系统由北京勤云科技发展有限公司设计

京公网安备 11010802029091号