AGV复合自主路径规划方法研究
2022-04-27肖献强王鼎用王家恩耿奕旻
肖献强，王鼎用，王家恩，耿奕旻
（合肥工业大学机械工程学院，安徽 合肥 230009）
1 引言
如今，工厂逐渐转向智能化的发展趋势愈加明显，AGV（Au‐tomated Guided Vehicle）成为众多学者研究的热点课题。路径规划作为AGV智能化的核心部分，目前主要有两种规划方式：基于环境已知的全局路径规划和基于环境未知的局部路径规划方法。在这两种类型的规划方法中，主要有Dijkstra算法[1]、蚁群算法[2]、人工势场法[3]、遗传算法[4]、A*算法[5-7]、D*算法[8]等。在工厂的实际应用中，AGV的工况具有大范围、动态性、人机混杂的3种特征。基于此，研究解决AGV在动态环境下的自动避让和动态路径规划显得尤为重要。国内外相关领域的学者提出了全局路径规划与局部路径规划相互结合的方式，文献［9］提出了将A*算法与人工势场法相结合的方式，其优化了力源，将AGV后面的斥力去除及最大角度的优化，但是仍然没有解决局部最优的根本问题。文献［10］将文化基因算法与Morphin算法相结合，虽然作者对机器人混合路径规划进行了改进，但是此路径规划算法较为复杂。
针对提高AGV实时路径规划的效率，提出了将A*算法与D*算法相结合的自主路径规划方法，主要思想是：AGV在已经创建的栅格地图上设置全局路径的起始点与目标点，根据路径的起始点与目标点调用A*算法生成全局路径；当AGV在全局路径上行驶检测到障碍物时，将路径上障碍物的下一点设置为局部路径的目标点，根据当前点与局部路径目标点确定局部路径搜索的栅格地图，较小的路径搜索范围，提高了路径规划的实时性。
2 复合路径规划方法
2.1 A＊算法
A*算法作为经典的路径搜索算法，是最有效的直接搜索算法，其搜索的方式是在Dijkstra算法的基础上采用启发式搜索算法，其启发式估价函数如下：
式中：f(n)—节点n的估价函数；g(n)—从起始点到节点n的实际的代价；h(n)—从节点n到目标点的预估代价值。其中h(n)有3种方式预估代价值，分别有曼哈顿距离、欧几里得距离、对角线距离。
2.2 D＊算法
D*算法，即为动态的A*算法，其通过一个维护一个优先队列来对场景中的路径节点进行搜索，用Dijstra算法从目标节点向起始节点搜索，储存路网中目标点到各个节点的最短路径和该位置到目标点的实际值，如式（2）所示：
式中：h(n)—当前点到目标点的实际代价值；c(next，n)—当前点到下一节点的新权值，next—下一节点的原实际值。
2.3 这里的复合路径规划模型
在栅格地图上，AGV自主地根据起始点与目标点以及障碍物的位置关系，基于曼哈顿启发搜索方式的A*算法搜索得到从起始点到目标点且绕开障碍物的一条路径。假设当前点的位置为(x i,y i)，目标点的位置为(x j,y j)，移动单位距离的代价为P，则曼哈顿的距离求解公式如示（3）：
当AGV在行驶过程中检测到障碍物时，在全局路径上搜索和设置局部路径目标点，如图1所示。
图1 复合自主路径规划示意图Fig.1 Schematic Diagram of Composite Autonomous Path Planning Method
根据当前点与局部路径目标点确定的虚线栅格地图区域，将其设置为局部路径搜索范围。调用D*算法生成局部路径，将局部路径与全局路径进行拼接，实现AGV当前位置到目标位置的全局规划路径更新，完成实时自主避障的功能。
2.4 复合路径规划数学方法
在AGV行驶中，根据环境的动态变化初始化的栅格地图,创建一个M×N的数学矩阵A M×N：
矩阵式（4）中，任意元素ai j代表的含义具体如下：0—表示空闲点，1—障碍点；2—起始点；3—目标点；8—路径点。假设此时矩阵A M×N中为没有障碍物，则A M×N中的内部元素全为0，在栅格矩阵中设置起始点为A［f］［k］，设置目标点为A［g］［h］，起始点与目标点的相对距离大于2个元素距离。定义矩阵A M×N中行向量坐标增大的方向为路径搜索的Y轴正方向，列向量坐标增大的方向为路径搜索的X轴正方向，设置起始点路径搜索的方向为Y轴正方向。根据A*算法的启发式函数搜索生成全局路径，在生成的全局路径中，将路径上任意相互正交相邻3点的正交点去除，得到如式（5）所示包含路径的矩阵：
假设修剪的拐点数为x，根据起始点A［f］［k］与目标点A［g］［h］，得到从起始到目标点的总耗费为：
若在栅格地图坐标为
根据具体生成的路径数据，设置局部路径的起始点和目标点。在生成的路径上，将AGV当前点A M×N[m][n]设置为起始点，将障碍点的下一点A M×N[s][t]设置为局部路径的目标点，并根据局部路径起始站点与目标站点在矩阵中位置确定包含起始点与目标站点的局部栅格地图，具体确定方式如下：
截取横向的矩阵，设矩阵E|m-s|×M的表示为：
截取纵向的矩阵，设矩阵E N×|n-t|的表示为：
则截取后的矩阵为：
此时调用D*算法在生成的局部地图中规划局部路径，设局部路径的拐点数为y，则局部路径从起始点到目标点的耗费为：
假设全局路径上路径局部路径的数量为z，每个局部路径避开路径上的障碍点数量为ei，则路径的总耗费值F：
3 应用分析与仿真
3.1 应用分析
本次测试方法为使用含有站点坐标信息的二维码标签，根据空间大小布置二维码。利用二维码标签构建AGV理想行驶路径L，路径中Ln表示为路径中第n个二维码站点坐标，表示方法为
3.2 路径仿真
首先设置路径的起始站点为<0，0>与目标站点<2，4>，并设置AGV的路径搜索方式为曼哈顿搜索。AGV根据起始点与目标点相互位置关系调用A*算法搜索全局的路径，并将拐点去除得到全局路径L=[L0，L1，L3，L3，L4，L5]，当行驶到每个站点时，实时解析路径的下两个站点，此处称之为“预备站点”和“目标站点”，并检测栅格地图中的目标站点是否有障碍物。假设在路径上将障碍点设置为<0，3>。当AGV行驶到<0，1>坐标点时，其通过报站的站点检测到目标站点有障碍物，调用D*算法，以<0，2>为起始点，以<1，4>为目标点确定局部路径搜索范围进行局部路径规划，得到局部路径S=[S0，S1，S2]，其中S0=<0，2>，S1=<1，3>，S2=<1，4>。进行拼接得到路径L'=[L0，L1，S0，S1，S2，L5]，如矩阵（13）所示为进行路径拼接得到的矩阵表示：
根据在矩阵中规划出的路径站点坐标及相互位置关系得到各个站点的信息，将规划出的路径信息写入路径数据文件中，如表1所示。
表1 路径数据文件Tab.1 Path Data File
表中：坐标值为站点在矩阵中的所处的位置，目标速度为根据AGV的电机特性在配置文件中的标定值，目标方向的设定原则为：当目标点的坐标为（x，y），目标点的下一点坐标为（x，y+1）,则目标点的方向为1，对应的方向角度为90°；当目标点的下一点为（x-1，y）,则目标点的方向为2，对应的方向角度为180°；当目标点的下一点为（x，y-1）,则目标点的方向为3，对应的方向角度为270°；当目标点的下一点坐标为（x+1，y）,则目标点方向为4，对应的方向角度为0°。
4 试验
4.1 地图构建
AGV根据试验场地大小在系统界面中创建栅格地图，同时在实际场景地面上按照比例张贴二维码栅格，试验现场的地图构建，如图2所示。
图2 测试现场Fig.2 Test Site
试验的AGV类型为双轮差速驱动，有2个驱动轮和4个万向随动轮，导航方式为二维码和惯性导航复合的形式，车载传感器有前后6个光电开关和6个碰撞开关，AGV中间底部安装有工业摄像机用于识别车体相对二维码地标位置。
4.2 复合路径规划测试
地图中AGV的起始站点和目标站点分别设置为<0，0>和<2，4>，测试生成路径试验AGV轨迹，如图3所示。
图3 AGV测试路径Fig.3 AGV Test Path
根据地图的起始点与目标点坐标，调用A*算法曼哈顿启发方式生成的全局路径，如图3（a）所示，并在拐点<0，4>处修剪为光滑的曲线路径。当在<0，3>存在障碍时，AGV在行驶到<0，1>时检测到目标站点存在障碍，将<0，2>设置为局部路径的起始点，将<1，4>设置为局部路径目标点，进行路径拼接得到路径，如图3（b）所示。
通过AGV行驶轨迹可以看出，当AGV在目标站点检测到障碍物时，确定局部路径起始点为障碍物的前一站点，确定局部路径目标站点为障碍物的下一站点，并在存在拐点处的局部路径修剪为光滑的曲线路径。试验结果表明，所提出的方法实现AGV在动态障碍场景中自主规避障碍的能力。
5 结论
（1）根据障碍物位置和全局规划的路径确定局部地图搜索范围，使得局部路径规划效率更高和避障的实时性。（2）所提的复合路径规划方法，可应用于多种导航方式，例如：SLAM导航、激光导航、二维码导航等。（3）所研究的方法目前只能在栅格地图中实现，若地图没有采用栅格建模，则只能将地图转换为栅格地图才能采用，针对此问题，我们将继续研究解决这种问题。
