韩学行，顿向明，林子洋

(上海交通大学机械与动力工程学院，上海 200240)

1 引言

机器人是一种可接受人类指挥，并按照指挥命令，根据预先设置好的编排程序，自动化执行任务的机器装置，以人工智能技术为基础，可协助或取代人类工作。考虑机器人的外部结构完全模拟人体的关节结构，机器人本体的有关部位分别为基座、腕部、手部和行走部等，并安装了对应的驱动装置、检测装置以及控制系统等软件执行设备，保证机器人可以正常的执行命令程序。随着互联网技术以及计算机技术的发展，为了保证机器人可以适应时代的发展，更加精确的完成指挥命令，目前通常使用计算机技术对机器人进行路径规划研究与设计[1]。移动机器人是多学科交融的高智能产品，必须考虑机器人的移动方式，可以通过各个程序执行单元，驱动全向移动机器人。机器人的路径规划是移动机器人自主导航的关键技术之一，所谓机器人路径规划指的是移动机器人按照某一性能指标，例如机器人执行任务时所需的时间、距离等指标，寻找出一条最优路径。

在进行机器人移动路径规划时，需要解决自我定位、自我规划以及自主控制等多个问题，在进行机器人路径规划过程中需要引入和利用多种规划算法。传统的机器人移动路径规划方法经常利用的算法包括：A*算法、粒子群算法以及模糊控制算法，其中利用A*算法的机器人移动路径规划方法，主要是通过静态路网求解最有效的直接搜索方法，通过对初始点以及状态空间的估价函数来得出目标节点的最佳路径[2]。粒子群算法是一种进化计算技术，利用群体智能建立的简化模型，粒子群算法在进行机器人路径规划时，在对集群活动行为观察的基础上，利用群体中的个体对信息的共享，从而得出最终的路径最优解[3]。模糊控制算法是通过对机器人各项机械系数的控制，从而控制机器人系统，模糊控制的关键在于隶属度和模糊级别的划分[4]。经过长时间的研究发现，上述三种路径规划方法中，基于A*算法的移动机器人规划方法准确率最高，但传统方法的通病是撞击率高、鲁棒性低。为了延续机器人移动路径规划方法的准确性，并提升移动路径方法的鲁棒性，将A*算法的改进算法应用到路径规划方法中，得出机器人移动路径优化方法。

2 机器人移动路径优化方法

2.1 机器人移动环境模型描述

在机器人移动路线规划优化的过程中，进行移动机器人工作环境的地图建立，这是路径优化的第一步，地图环境的建立指的是通过多个环境传感器获得机器人移动的环境信息，将多传感器检测到的信息融合在一起，形成最终的抽象地图模型[5]。将环境信息用栅格单位的形式来描述，以此来建立机器人移动的工作环境模型，如图1所示。

图1 机器人移动环境示意图

按照图1中的形式，使用栅格法将机器人的工作环境分割成为形状大小相同的多个栅格，在环境模型的构建过程中，将栅格的形式划分为可通过栅格与不可通过栅格两种。通过对每一个栅格单元进行编码，最后用不同的CV值赋予给每一个栅格单元，以此来表示出目标单元为障碍物区域或自由通行区域[6]。图2当中空白栅格表示的是可通过栅格，也就是移动机器人可以自由通过的位置，而被黑色填充的栅格表示的是不可通过的栅格，也就是环境中的障碍物。将环境模型以坐标系的形式存储在机器人存储器当中，横向向右的增加方向为X的正方向，而纵向向上的增加方向表示的是Y的正方向，并将栅格环境模型用序号法进行编码并存储。

假设在机器人移动环境模型中，机器人的移动不受机器人高度的影响，且在机器人的整个移动范围内，周围环境信息保持理想状态，固定不变。定义栅格尺寸的计算公式为

(1)

式中，l是环境模型中的标准栅格边长，lmin为环境中障碍物的最小边长，nc为栅格数量，ltemp表示环境中障碍物的理想边长。其中ltemp表达式如下

(2)

式中，Sobs为环境当中障碍物的面积之和，S表示的是机器人移动环境的总面积，lmax为环境中障碍物的最大边长。

将栅格化完成的描述环境模型进行直角坐标法进行信息编码，用直角坐标的形式表示栅格的位置，设定环境中的任意一个栅格的位置坐标为(nx，ny)，通过式(3)可以求出坐标nx值。

(3)

式中，nx表示的是栅格中心位置的坐标表示方法。同理通过式(4)便可以得出栅格端点位置的坐标ny的值

(4)

式中mod为求余运算函数，而n表示的是栅格序号[7]。按照图2所示，S为机器人移动路径的起点，而D为移动路径的终点，可以将环境中的所有栅格点进行编码存储在机器人存储器中。

2.2 栅格模型优化处理

结合A*改进算法对构建的环境栅格模型做膨胀处理，通过增加环境障碍物周围的栅格运动代价值来表示环境区域的危险系数[8]。设定膨胀处理中map(nx，ny)表示(nx，ny)位置上的栅格CV值，膨胀处理过程如式(5)所示

map(nx，ny)=map(nx-1，ny-1)+nyW

(5)

式中W表示的是代价增加值。用CV值来表示环境障碍的安全等级，在进行机器人移动路径优化过程中，自动选择安全等级更高的位置作为优化的规划路径。

2.3 获得机器人移动原始路径

定义机器人用Ai来表示，Ai的中心为xi(t)，机器人在t时刻的姿态角为θi(t)，xi是一个指数位置的参数化多项式，使用xi参数来表示Ai的规划路径，定义tfi作为Ai的最终运动时间的一个实数值。将Ai规划出的规划路径为xi，其表达式为

xi=map(nx，ny)[x1i(t)+x2i(t)]

(6)

式中，x1i(t)与x2i(t)分别表示动态和静态运动方向，对应指数为M和N。

借助环境传感器以及机器人装置上人工智能摄像机，可以在移动环境中侦测到障碍物的位置，可实时获取障碍物的路径信息。通常情况下，移动环境中的障碍物类型可以分为无障碍、静态障碍和动态障碍三个方面，假设Ok(q)为障碍物的表示方法，其当k取值为0时表示环境内无障碍物，k为1表示环境内存在静态障碍，取2表示存在动态障碍，而q表示的是障碍物的数量[9]。分别通过k的取值来判定机器人移动路径上的环境类型，并分别针对不同的环境条件利用A*改进算法来获得原始机器人移动规划路径，其规划步骤如下所示：

2.3.1 无障碍下路径规划

通过传感器检测到环境中的障碍物体时，Ok(q)中k的值取0，那么在进行路径规划时，取起点与终点的最短距离路线即可[10]。使用A*改进算法选择机器人运动距离最短的作为路径极限，从而得到规划路径。假设路径的横向距离为0.25，纵向距离为0.035，则规划的路径结果可表示为

xi(t)=0.25+0.25t+…+0.25(xi)N+M

(7)

机器人按照规划完成的路径进行移动，从该起始位姿无碰撞的移动待终止位姿。

2.3.2 静态障碍下路径规划

首先经过传感器与摄像机得到障碍的位置信息Obsi(x，y)，那么可以得出规划函数

(8)

通过目标函数给出不同区间上的规划路径，机器人以远离静态障碍物为前提，从起始位置到达终止位置。

2.3.3 动态障碍下路径规划

在动态障碍环境下，对机器人的移动路线进行规划，首先需要对障碍物的移动路线进行初步分析，得出有关于动态障碍物的移动规律。以障碍物的移动情况作为路线规划的参考，遵循远离障碍的原则得出动态障碍下机器人移动路径的规划结果，如图2所示。

图2 动态障碍下路径规划结果

综合上述分析步骤，可基于A*改进算法来获得原始机器人移动规划路径，流程图如图3所示。

图3 原始机器人移动规划路径获取流程图

2.4 机器人移动路径优化方法

2.4.1 计算路径优化约束条件

在得到原始路径的基础上，使用A*改进算法得出机器人移动路径的优化约束条件，其中优化约束条件包括：运动学约束和避障约束[11]。运动学描述就是指机器人在沿着规划路径移动时，需要控制机器人移动的速度和加速度，避免机器人在移动过程中的滑失情况。因此运动学约束可以表示为

(9)

式中，vi(t)和ai(t)表示约束条件函数，vmaxi和amaxi分别表示机器人移动时的速度和加速度，t表示运动约束值，J表示最大约束取值。

另外避障约束的目的是为了保证正在移动的机器人需要与障碍物之间保持最小的安全距离。设定dobs和doik分别为机器人Ai与障碍物Ok(q)之间的安全距离与实际距离的值。那么在移动环境中机器人需要满足式(10)中的避障约束条件

dobs-doik≤0，∀k=1，…，J

(10)

2.4.2 平滑优化规划路径输出

从路径路线序列的第二个节点开始，若连续两个节点存在一致的移动方向，则认为这两个节点为冗余节点，可以删除该节点，并更新路径点的序列。按照顺序依次遍历所有的路径点，最终得出起点、转折点以及终点的路径序列。具体的平滑优化输出流程如图4所示。

图4 路径平滑优化流程图

通过计算获得规划优化路径，在移动机器人r路径规划优化过程中，采用评价函数的最小节点作为优化节点并将该节点存入路径列表当中，直到优化至目标节点为止[12]，由此则可以完成对机器人移动路径的优化分析。

3 仿真对比实验

为了验证本文机器人移动路径优化方法的有效性，进行仿真对比实验，实验过程中设立传统方法作为实验的对比方法。由于操作机器人实际移动的成本高，且操作过程复杂，因此此次验证实验借助计算机仿真技术，通过构建仿真环境以及安装硬件设备等步骤，在仿真环境下对优化方法进行验证。最终通过对移动路径与移动时间等参数的对比，得出优化方法的有效性。

3.1 构建仿真环境

在进行实验时，利用计算机仿真技术搭建所需的仿真环境，仿真环境的计算机参数为：CPU Intel Core2 Duo，内存32GB，编译工具MATLAB8.0。选择机器人移动的仿真环境，测量仿真环境的大小尺寸，并将实验中机器人移动的环境数据输入到路径规划显示界面当中。如图5所示。

图5 路径规划显示界面

假设随机分布的环境障碍物，以相同的标识标记在移动环境中。选择MobileRobots出厂的Pioneer3-DX型号的机器人作为实验对象，将机器人的相关数据输入到仿真环境当中。图6为机器人虚拟环境仿真图。

图6 机器人虚拟环境仿真图

通过路径规划显示界面，采用本文方法将Pioneer3-DX型号机器人在有障碍物的空间中进行最短路径规划，浅色部分为障碍物，图7为避开障碍物的路径图。

图7 避开障碍物的最短路径图

根据图7可知，采用本文基于A*改进算法可以有效避开障碍物后，再沿着全局最短路径前进达到目标点，实现最短路径规划。

3.2 实验过程

在实验环境下，将本文基于A*改进算法的机器人移动路径优化规划方法设置为实验方法，将传统的路径规划方法、基于A*算法的机器人移动路径规划方法当做对比方法。利用三种规划方法首先分析仿真环境，设立实验中机器人的起始点与终止点。在仿真机器人上安装传感器，在机器人的移动过程中每当与障碍物发生碰撞，便记录一次撞击系数。与此同时，记录机器人的移动路径长度以及移动时间。

3.3 实验对比结果与分析

通过仿真实验得出对比方法与实验方法输出的路径界面如图8所示。

图8 路径输出结果对比

从图8中的输出结果可以看出，经过优化的机器人移动路径更加平滑，在移动过程中可以与障碍物保持安全距离。

建立一个 200 ×200 的栅格环境模型，每个栅格边长为 1m，起点 S 坐标为(3，4)，终点 G 坐标为(195，190)，如图9 所示。

图9 复杂环境模型

通过复杂环境模型对移动时间、移动路径长度以及撞击次数、转弯次数进行记录，得出表1中的实验对比结果。

从表中的数据可以看出，本文基于A*改进算法的机器人移动路径优化规划方法，其路径长度比其它两种方法的路径长度节省约46米，在时间上也节省了约19分钟。经过计算发现，与其它两种路径规划方法相比，本文优化方法的路径转弯次数和撞击次数均出现了较大的降低，明显优于其它两种方法，表明本文利用A*改进算法进行机器人移动路径优化，能够获取较好的成果。

4 结束语

机器人学研究中，路径规划一直是广受关注的研究热点之一。本文将A*改进算法用于机器人移动路径优化规划中，并通过实验验证了所提方法的有效性，结果表明，所提方法能够较好的完成机器人路径规划，节省时间和成本，且且能够减轻机器人在移动过程中的消耗，具有较强的应用价值。