面向移动机器人快速全局路径规划的改进跳点搜索算法  

Improved Jump Point Search Algorithm for Fast Global Path Planning of Mobile Robots

作　　者：宋晓茹[1,2] 任怡悦 SONG Xiao-ru;REN Yi-yue(School of Electronic and Information Engineering,Xi'an Technological University,Xi'an 710021,China;Autonomous Intelligent Innovation Team of Xi'an Technological University,Xi'an 710021,China)

机构地区：[1]西安工业大学电子信息工程学院,西安710021 [2]西安工业大学自主智能创新团队,西安710021

出　　处：《科学技术与工程》2020年第29期11992-11999,共8页Science Technology and Engineering

基　　金：国家重点研发计划(2016YFE0111900);国家自然科学基金(61773016);陕西省重点研发计划(2018KW-022)。

摘　　要：针对传统全局路径规划算法计算量大、寻路时间过长等问题,为了进一步提高移动机器人综合作业能力,提出一种基于跳点搜索算法的快速全局路径规划算法,旨在减少时间成本,以满足移动机器人在实际复杂环境中对智能性、高效性、安全性和可靠性的要求。首先通过“块”操作方法,在一次搜索中快速扫描底层网格中的一个区域,将跳点搜索算法的修剪规则一次应用于多个节点,减少搜寻跳点时所涉及的大部分迭代计算,并在采取“对角优先”方式的前提下,剔除仅具有改变方向的中间转折点,大量减少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 in traditional global path planning algorithms,a fast global path planning algorithm based on the jump point search algorithm was proposed to improve the comprehensive operation capability of mobile robots.The time cost was reduced,the comprehensive operation capability of the mobile robot was enhanced and the requirements for intelligence,efficiency,safety,and reliability of robots in practical complex environments were satisfied.First,through the“block”operation method,the area in the underlying grid was quickly scanned in one search,and the pruning rules of the jump point search algorithm were applied to multiple nodes at once,so the most of the iterations involved in searching for jump points were reduced.On the premise of adopting the“diagonal priority”method,the intermediate turning points were eliminated with only changing directions,thus the unnecessary nodes of OpenList and ClosedList were greatly reduced,the calculation amount was reduced,and the real-time performance of the path planning was improved.To verify the effectiveness and feasibility of the algorithm,simulation experiments were carried out on regular grid maps,the benchmark sets,and the mobile robot Turtlebot 2.The results show that on the basis of generating the same path,compared with the A algorithm,the improved jump point search algorithm can reduce 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 proposed 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.

关 键 词：移动机器人 全局路径规划 跳点搜索算法 “块”操作 

分 类 号：TP242.6[自动化与计算机技术—检测技术与自动化装置]