基于校园园区的送货机器人全局路径规划

李亚正，王 丰

(华北理工大学 机械工程学院，河北 唐山 063210)

0 引言

近年来物流行业发展迅速，由于客户需求的多样性，网购商品的种类越来越多，并且购买者的收货地点往往不集中，这对快递配送的效率要求很高。自主送货机器人作为高度智能化产品，可有效解决电子商务“最后一公里”面临的困境。路径规划技术是实现机器人自主行驶的基础，研究自主送货机器人路径规划技术可有效解决当前电子商务面临的配送难的问题，因此，开展对自主送货机器人的研究符合物流行业当下的实际需求，具有重要的意义。

1 全局路径规划流程

在所建立的园区电子地图上进行全局路径规划主要包括两个方面：建立电子地图和全局路径规划[1]。

建立电子地图分为园区地图的抽象、路阻的标定及园区电子地图的存储三个步骤。地图抽象是将道路交叉口抽象为拓扑图中的顶点，道路抽象为边，这样就将园区地图抽象为顶点和边的集合；路阻标定也就是对车道抽象成的边进行赋值；电子地图的存储是将拓扑图的信息进行存储。

全局路径规划分为路径搜索及道路还原两步。路径搜索是在电子地图建立好之后，根据机器人配送的要求在地图中选择起点和目标点，然后利用路径规划算法规划出起点和终点之中总路阻最小的路径;道路还原是将规划出的路径还原成真实路径。

2 全局路径规划

2.1 路网抽象

以某大学校园作为全局路径规划的环境，通过对路网的结构进行分析，采用图论中的拓扑图来表示路网，根据校园地图中的道路拓扑关系进行图的顶点和边的抽象，将标定的点抽象为拓扑图中的点，道路节点间路段抽象成拓扑图中的边，完成地图的抽象。将路网抽象成的拓扑地图如图1所示，在校园区域内标定了81个节点。考虑到送货机器人在快递站点装取货物，对多个目标点进行配送，将点1(三角形地标)设定为机器人配送站，即机器人配送的起点与终点，并在校园区域内选定了16个配送点，对应的节点为点2～点17(方形地标)。

图1 拓扑结构效果图

2.2 路阻标定

对于路阻的评价，实际上就是出行费用的计算过程[2]。路阻有多种含义，如果要求规划出的路径长度最短，则将路阻设置为道路的长度；如果要求机器人行驶的时间最短，则路阻设置为道路的行驶时间。研究对象为校园园区，道路较规范并且不拥堵，因此以道路长度作为路阻最合理。

使用BIGEMAP坐标采集系统中的谷歌地球无偏移地图，采集校园道路交叉口的大地坐标。在实际的采集系统使用过程中，直接采集的坐标通常是以WGS-84坐标系为基准坐标系测得的大地坐标，由于大地坐标无法直接用于电子地图的建立，因此还需要对所测得的大地坐标进行高斯-克吕格投影，将所提取的大地坐标转换为平面坐标。

已知椭球面上的大地坐标纬度B、经度L，求平面坐标X、Y的问题称为高斯投影正算[3]，也就是将基于WGS-84坐标系采集的道路交叉口的大地坐标根据高斯-克吕格投影正算法转换为平面坐标。

如图2所示，高斯-克吕格投影的几何概念是：假定有一个椭圆柱与地球椭球体上某一经线相切，其椭圆柱的中心轴位于赤道平面上，而后按等角投影的条件将中央子午线两侧各一定经差范围内的地区投影到椭圆柱面上，再将此柱面展开即成为投影面[4]。

图2 高斯-克吕格投影

图2中阴影部分的投影面展开如图3所示，中央子午线的投影是纵坐标轴X，赤道的投影是横坐标轴Y。

图3 高斯-克吕格平面直角坐标系

高斯-克吕格平面直角坐标系中每带以中央经线投影后的直线为X轴，以赤道投影后的直线为Y轴，两轴交点为每个投影带的坐标原点。我国地处北半球，X值都为正值，而在每个投影带中央经线左边坐标值为负，规定使纵坐标轴向左平移500 km，避免Y坐标出现负值[5]。

高斯投影的思想是通过经差对地球球面划分投影带来限制长度方向的变形。为减少投影变形，分带的经差通常为6°或3°，即六度带投影和三度带投影[6]，本文采用六度带投影。要想获得互通的两节点间道路长度，就需要知道各节点的平面坐标，使用BIGEMAP坐标采集系统采集图1拓扑结构效果图中的道路节点的大地坐标。以节点1～节点5为例，WGS-84坐标系下这些节点的大地坐标(B，L)和经过投影后的平面坐标(X，Y)如表1所示。

表1 BIGEMAP采集的部分数据及转换值

获取了各节点的平面坐标便可得到两互通节点间的道路长度，以道路长度作为路阻。部分节点间的路阻如表2所示。

表2 部分节点间的路阻

2.3 电子地图存储

电子地图的存储表示方法是多种多样的，例如邻接矩阵、十字链表和邻接表等[7]。本文采用邻接矩阵这种存储结构，该矩阵可以表示图中顶点间的相邻关系。

邻接矩阵的存储“是通过一维数组来存储图中节点的信息，再由二维数组即矩阵来表示各节点之间的邻接关系”。通过校园地图的抽象及路阻的标定，在此基础上运用MATLAB编写邻接矩阵。邻接矩阵的创建过程如下：

(1) 将全局地图抽象为拓扑图之后，确定每条边的路阻。

(2) 初始化邻接矩阵，Inf代表两个顶点之间无通路，表示不互通。

(3) 将两节点间道路的权值放入邻接矩阵中，同一节点间路阻为0。

本文在校园地图内选取了81个节点，通过计算各节点间的距离得到了各邻接点的距离矩阵。本文所建立的电子地图的部分邻接矩阵如表3所示。

表3 部分校园地图邻接矩阵 m

2.4 路径搜索及道路还原

在全局路径规划中，基于图形学的路径规划算法要与建模中的地图构建集成使用，所以校园电子地图建立好之后，需要采用路径规划算法进行搜索来完成机器人对多个目标点的配送任务。

模拟退火算法适用于计算多目标点的最短路径问题，可以计算出图中某一节点到所需要经过的多个节点间的最短路径，相比其他算法具有原理简单、运算速度快的优点。

由建立的电子地图邻接矩阵，通过MATLAB编写适用于邻接矩阵的模拟退火算法程序。对基于校园区域建立的电子地图进行最短路径规划，首先将邻接矩阵导入MATLAB，机器人需要在点1装取货物，设定点1为起始点，途中要经过2、3、12这三个配送点，配送完毕后，回到点1。所规划的全局最短路径由以下道路节点构成：1-19-34-4-36-29-81-80-54-55-11-61-12-64-79-78-18-3-39-1，该最短路径长度为2 455.34 m。最后将规划出的道路节点还原成实际交通地图中的真实路径，如图4所示，箭头所指引的路径为规划的最短路径。

图4 路径规划结果图

3 结论

本文通过对某校园地图进行抽象，并在建立电子地图的基础上完成了全局路径规划，并将抽象的路线还原成实际交通地图中的真实路径。本文通过多次仿真，调整参数，在一定程度上克服了算法本身的缺点。在实际生活中，路径规划算法在机器人配送问题上仍有提高空间。本文将模拟退火算法应用于自主送货机器人路径规划中，旨在为电子商务物流配送问题的创新提供参考。