移动机器人路径规划融合算法研究

杨伟煌,王容霞

(广州南洋理工职业学院,广东 广州 510900)

0 引言

路径规划是机器人研究领域不可或缺的技术。所谓路径规划,就是让机器人在遵循一定的评价指标函数的前提下,在充满障碍物的环境中顺利避开障碍物,从而规划出从起始位置到目标位置的最优路径。

由于标准A*算法需要从起点开始,不断扩展相邻节点,并使用定义的代价估计函数寻找使函数得到最小的节点F(m)值,所以算法的时间消耗主要在于计算相邻节点的代价估计函数和选择最小的节点F(m)。这样一来,标准的A*算法就会有一些不可避免的缺陷:随着机器人二维空间的增加,算法扩展出来的无用节点的数量越来越多,导致计算数据量和搜索时间增加算法的增加,路径规划效率不高。

本文将基于跳跃点搜索的jump-A*算法与全局最优的动态窗口方法相结合,提出了一种混合路径规划算法。一个新的参数JPHeader(v,ω),它测量模拟轨迹的末端和距离当前轨迹最近的跳跃点之间的方位角偏差,被设计来构造一个新的评估函数。该融合算法基于动态窗口方法,采用跳跃点搜索方法,规划速度更快,避障路径更平滑。

1 jump-A*算法

A*算法是一种启发式搜索算法,用于在静态二维配置空间中计算最优路径,与A*算法不同的是,jump-A*算法引入了跳转点的概念(见图1)。

图1 跳转点搜索算法

在A*算法中,由于评估了大量无意义的节点,如灰色网格,无形中增加了计算量,降低了搜索效率。因此,假设目标位置n是当前节点x的8个邻域中的任意一个节点n,则通过满足约束方程,确定从起点p到目标点n直线延伸的最优路径。当扩展的相邻网格节点遇到障碍物时,除强制邻居节点外,其余的灰色网格都应该被剪掉。节点X是算法中要找到的跳转点。切掉无意义的节点后,就可以得到一系列的跳跃点。然后,可以通过在这些跳跃点上应用标准的A*算法来获得全局最优路径。该算法称之为jump-A*算法[1]。

对于jump-A*算法中的距离测量方法,使用较多的是欧几里得几何距离或曼哈顿距离。为了便于控制机器人,结合以上两种测量方法,设计出更接近实际估计成本h(m)的新距离函数:

假设起点和目标点的坐标为(pi,qi)和(pj,qj),那么dx(m)=|pi-pj|,dy(m)=|qi-qj|。

2 改进的动态窗口方法

2.1 传统的动态窗口方法

动态窗口算法的核心是将路径规划问题转化为约束速度向量空间优化问题。

2.1.1 机器人运动学模型

实现动态窗口法的第一步是获得机器人的运动学模型,这也是模拟机器人运动轨迹的前提。假设机器人的轨迹由一条微小的弧形轨迹组成,每个轨迹对应一个唯一的速度向量(vt,ωt)。由于每条圆弧轨迹产生的时间间隔Δt很短,可以近似看成一条直线轨迹。因此,可以假设机器人在Δt的时间间隔内做匀速直线运动,得到机器人的运动学模型如下:

其中xt,yt,θt为t时刻机器人的坐标位置和方位角；xt+1,yt+1,θt+1为t+1时刻机器人的坐标位置和方位角；vt和ωt是机器人在时间t的平移速度和旋转角速度。

2.1.2 速度采样

速度采样是模拟轨迹所必需的。在动态窗口方法中,定义了3种不同的约束来限制采样速度的范围。

第一个约束是受机器人所处环境和物理结构的限制。机器人可以达到的速度范围是:

其中,vmax和vmin是机器人可以达到的最大和最小线速度,ωmax和ωmin是机器人可以达到的最大和最小角速度。

第二个约束考虑遇到障碍的情况。当机器人采用最大减速度时,v′b,ω′b紧急制动,为了使机器人在碰撞前停止并确保其安全,必须设置允许的速度范围:

其中,dist(v,ω)表示速度向量模拟的轨迹之间的距离(v,ω)和最近的障碍物。

第三个约束是在模拟时间Δt间隔内可以达到的速度范围,由电机允许的最大加速度v′a,ω′a和最大减速度v′b,ω′b限制:

其中vc,ωc表示机器人当前的线速度和角速度。

2.1.3 评价函数

在多组采样速度的集合中,通过仿真可以得到多组可行的轨迹。要从这些可行轨迹中选择最优轨迹,需要从多个维度进行评估,使机器人能够沿着最优轨迹安全到达目标位置。评价函数如下:

其中,head(v,ω)用于测量在当前选择的采样速度下,模拟轨迹终点方向与目标位置方向之间的角度偏差。dist(v,ω)为速度向量(v,ω)模拟的轨迹与最近障碍物的距离,得分越低,机器人与障碍物碰撞的概率越大；σ为平滑函数。α,β,γ为3个评价指标的加权系数[2]。

2.2 改进的动态窗口方法

传统的动态窗口方法具有良好的动态避障性能,但由于陷入局部区域无法到达目标的致命缺陷,难以根据全局环境信息规划全局最优路径。为了解决这个问题,笔者充分考虑了jump-A*算法得到的全局路径信息,改进了原动态窗口方法的评价函数。改进后的动态窗口方法可以动态避开障碍物并确保其全局最优性。改进后的评估函数表达式写为:

方程中的head(v,ω)替换为JPHead(v,ω),它测量模拟轨迹的末端和距离当前轨迹最近的跳跃点之间的方位角偏差。优化的动态窗口方法保证了在动态路径规划中沿着全局最优路径的轮廓平滑的全局最优路径。改进的动态窗口方法的流程如下:

首先初始化,获取机器人的运动学模型,判断是否达到了目标位置,如果达到了目标位置,那么机器人速度采样,模拟运动轨迹,使用全局改进的评估函数,通过jump-A*算法得到的路径信息,选择最优轨迹,机器人按照最佳轨迹移动；以至于得到最优路径[3]。

3 实验与结果

为了验证上面提到的jump-A*算法和改进的动态窗口方法的有效性,MATLAB中建立网格环境,对jump-A*算法结合跳跃点搜索和集成全局路径信息的改进动态窗口方法进行了2次静态仿真实验,如图2所示。

图2 两种不同算法在简单和复杂静态实验环境下的仿真结果

通过仿真结果,无论是简单环境还是复杂境与jump-A*算法相比,具有全局路径信息的改进动态窗口方法可以解决jump-A*算法在相同网格大小和相同障碍物的转折点处曲率不连续的问题分布环境,生成的路径比jump-A*算法更平滑,融合算法也具有全局最优性能。无论障碍物的位置、形状和大小如何变化,融合算法都能在满足全局优化的基础上规划出更平滑的路径。此外,改进的动态窗口方法融合了全局路径信息,克服了原有动态窗口方法陷入局部最优的缺点,达到了该融合算法的设计预期。