全局路径规划是智能机器人领域中的核心问题之一,也是机器人学中研究人工智能的一个重要方面。全局路径规划一般包括环境建模和路径搜索策略两个子问题。其中,环境建模的方法主要有可视图法、自由空间法和栅格法等[1-5]。当环境地图比较复杂(例如障碍物比较庞大,自由空间相对狭窄),环境建模将是路径规划能否成功的关键问题。可视图法和自由空间法所建立的模型均为几何数据模型,由于矢量数据有严密的数据结构、数据量小,能很好地描述空间关系,较好地建立实体间的拓扑关系,表示数据的几何精度也较高,但这种数据模型也存在着诸多缺点,如数据结构复杂、较难进行各种模拟模型的建模、数据更新较困难、分析操作困难等。栅格法以栅格为单位记录环境信息,环境被量化成具有一定分辨率的栅格,栅格的大小直接影响着环境信息存储量的大小和规划时间的长短。因此,栅格法不适用于障碍物比较密集、环境空间相对狭窄而实时规划要求高的路径规划问题。路径搜索策略通常使用的搜索技术包括梯度法、A算法、随机搜索法以及遗传算法等[6-10]。传统的路径搜索方法主要利用优化算法从一个初始状态开始不断迭代,最后得到一个全局或者局部最优解,难以生成多条可供替换的路径。然而在实际操作时,预先规划好的路径往往因为环境等的变化而不再适用。为克服复杂性缺点,文中首先在环境建模上,利用一系列不同的多边形表示环境中的障碍物,简化障碍物模型,并采用不同的数组矩阵分别存储机器人和各个障碍物的顶点坐标,以便于计算机进行处理、分析、计算;然后,在路径搜索过程中,建立两个子函数障碍物筛选子函数和凸包计算子函数,通过对两个子函数的循环调用,搜索出多条较优路径后根据一定准则对路径进行择优。该算法能够预先规划出多条较优路径,当环境空间相对狭窄、机器人形状较为复杂,在路径转弯处作旋转运动时,可以根据安全需要选择合适的运动路径,进而增加了算法的适用性。图1环境地图Fig.1Environmentmap1环境建模环境中的实体包括机器人和障碍物,为了方便研究,文中对三维环境空间以二维表示,规定移动机器人的运动环境为矩形(如果不是矩形,可以将其边界补以障碍物)。记AR为机器人在二维平面上的运动区域,以AR的左下角为坐标原点O,横向为x轴,纵向为y轴建立系统直角坐标系(见图1)。将障碍物表示成不同的多边形,用OBSk表示,采用数组矩阵存储每个障碍物的顶点坐标,其坐标按顺时针方向存储,即OBSk=[x1,y1;x2,y2;…;xn,yn;x1,y1],它表示第k个障碍物有n个顶点。障碍物集合用元胞数组来表示,即OBS={OBSk|k=1,2,…,m},它表示环境中有m个障碍物。障碍物坐标一旦确定,则整个机器人所处的环境地图确定。2路径搜索算法2.1算法原理环境地图建立后,当已知运动起始点S(xs,ys)、目标点G(xg,yg)的位置坐标,机器人从起始位置到目标位置所规划的路径是否安全,主要取决于机器人与所经过的障碍物之间的距离是否不小于其运动所规定的安全距离。文中首先将障碍物进行适度膨胀,得到一幅新的环境地图,膨胀的尺寸至少是机器人宽度的一半,从而将机器人简化为一个质点。基于两点之间直线最短的思想,首先作起点与终点连线SG,如果连线与所有障碍物均不相交,则连线SG即为所规划的最优路径;如果连线穿越障碍物,则SG将其障碍物顶点分为上下两部分,规划无碰优化路径,即转换为分别计算连线所穿越的障碍物上、下两个顶点集中的凸包,两个凸包所组成的节点序列即为位于连线SG两侧的两条优化路径。对于两条路径的每个节点对之间的连线需要重复上述步骤进行路径再规划,直到每条连线均与障碍物无碰,