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

作者：宋晓茹; 任怡悦

来源：科学技术与工程, 2020, 20(29): 11992-11999.

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

针对传统全局路径规划算法计算量大、寻路时间过长等问题,为了进一步提高移动机器人综合作业能力,提出一种基于跳点搜索算法的快速全局路径规划算法,旨在减少时间成本,以满足移动机器人在实际复杂环境中对智能性、高效性、安全性和可靠性的要求。首先通过"块"操作方法,在一次搜索中快速扫描底层网格中的一个区域,将跳点搜索算法的修剪规则一次应用于多个节点,减少搜寻跳点时所涉及的大部分迭代计算,并在采取"对角优先"方式的前提下,剔除仅具有改变方向的中间转折点,大量减少Openlist和Closedlist的不必要节点,减少计算量,提高路径规划的实时性。为了验证改进算法的有效性与可行性,分别在规则的网格地图、测试库基准地图及移动机器人Turtlebot2进行仿真实验验证。结果表明:在生成相同路径的基础上,改进跳点搜索算法与A*算法相比扩展节点数目缩减了68.9%,搜索耗费时间降低了71.9%;与传统跳点搜索算法相比,扩展节点数目缩减了41.3%,搜索耗费时间降低了33.4%,能够满足移动机器人快速全局路径规划的要求。

• 出版日期2020
• 单位西安工业大学; 电子信息工程学院