机器人路径规划的时间高效A*算法

作者：Akshay Kumar Guruji, Himansh Agarwal, D. K. Parsediya*

Madhav Institute of Science & Technology, Race course road, Gwalior, Madhya Pradesh, India

摘要

当今时代的焦点主要集中于现代化、工业化和自动化的发展。其中，人的任务逐渐被机器人取代，以达到高精度，高效率，快速和多样性。例如在工业生产的过程中，这些机器人被用来在工作场所携带重物。但由于环境或者工作区域可能是动态变化的，必须要确保设计的寻路算法或规则能够提供最优的无碰撞路径。A*算法是一种基于启发式函数的路径规划算法。为了找到零碰撞概率的最佳解决方案，它需要对工作区域内的每个节点进行启发式函数值的计算，并且涉及到太多相邻节点的检查。因此，它需要大量的处理时间而降低了工作速度。本篇论文提出了用于减少处理时间的A*算法的改进。被提议的A*算法确定启发式函数的值就在碰撞阶段之前而不是最初阶段，它明显减少了处理时间，带来了更快的速度。本文应用了从初始点到目标点的MATLAB仿真机器人运动。提出的改进版A*算法在应用于一些案例时能够在处理时间上表现出最大95%的减少量。

关键词：路径规划，最优路径，启发式函数，处理时间和路径长度

目录

摘要

第1章 简介

第2章 提出的算法与其执行条件

2.1 输入阶段

2.2 接近检测阶段

2.3 确定斜率和投影像素阶段

2.4 碰撞阶段

2.5 A*或转换阶段

第3章 仿真和结果

第4章 结论

引用

第1章 简介

路径规划是找到空间中从一点到另一点的最优路径的方法。它通过确定源点和目标点之间的最短路程，来优化他们之间的路径【1-2】。它有时也被称为运动规划，因为它有助于决定在工作环境中的任何物体的运动。一个物体可以看作是一个在本质上是自主的机器人，因为它可以使用路径搜索算法来决定自己在空间中移动所要经过的点，这种机器人被称为移动机器人【3】。路径规划也被定义为将期望的运动分解为若干迭代的步骤来分离运动以优化一些实体对象的过程。

环境因素在路径规划问题中扮演着十分重要的角色。基于工作场所的性质，路径规划可以分为离线规划和在线规划两种类型。在离线路径规划中，工作空间对应的数据里所包含的障碍物是固定不变的，在使用寻路算法计算出最优路径之前，已知的障碍物的几何形状是给定的【4】。但是对于在线路径规划，很多作者和发表的文章都表明：机器人需要使用传感器或者实时数据采集设备来获取整个工作空间中不断发生移动的障碍物的位置【5-8】。但是，在线路径规划这种想法的实现需要非常复杂的建模过程。在本篇论文中应用的条件是用来处理静态环境因素的，所以所设计的算法在本质上属于离线路径规划。各种各样的路径规划算法比如遗传算法、神经网络算法和A*算法等都被应用于移动机器人导航中【9】。它将整个的工作空间看作是一个导航网格，移动机器人通过找到覆盖最少导航网格数量的路径来达到目的地。A*算法使用启发式函数，通过计算整个工作空间内所有节点的函数值来得到最佳的解决方案【10】。当然，A*算法也有一定的局限性，因此在本研究之前已经有很多人提出了A*算法的改进版【11-13】。