基于激光雷达的移动配送机器人自主导航研究

施建壮，张国伟,，卢秋红，黄 威，吴松林

（1.上海电力大学自动化工程学院，上海 200082；2.上海合时智能科技有限公司，上海 201100）

0 引言

随着人工智能和物联网技术的不断发展，服务机器人产品作为智能设备也在进行智能化转型升级，不断实现更强大的功能和更丰富的应用。作为服务机器人的一个分支，室内移动配送机器人，实现了一键配送餐饮功能，代替很多原有的重复性劳动工作。在国内外疫情爆发情况下，室内移动配送机器人可以避免人员接触引起的感染，实现既安全又高效的配送餐饮。并且该室内移动机器人所应用的智能导航技术能够解决在商场、酒店、餐厅、会议室等不同场所时，遇到地毯或坡面等不平坦道路的运行稳定性和行走能力问题，环境或者人为因素发生改变后的适应性问题等。

室内移动配送机器人利用激光雷达进行自主定位和构建地图，再通过导航算法实现机器人自主路径规划功能。全局路径规划是移动配送机器人实现自主导航的关键技术之一，路径规划目的是在机器人获得所处环境的全局信息之后，按照一定评价标准（如转弯次数、时间及代价等），寻找出一条从起始节点到目标节点的最合适路径。目前，路径规划算法已经非常成熟，使用较多的有A算法、人工势场法、Dijkstra算法、遗传算法和蚁群算法等。

由于A算法的可塑性和移植性较强，被应用于制造业、仓储物流等领域。但传统A算法存在拐点数量和遍历节点较多、寻路时间较长等问题。目前，国内外相关学者都对移动机器人全局路径规划方法展开了研究，且获得一定的成果。本文以上海合时智能科技公司的室内移动配送机器人作为研究硬件平台，对移动机器人进行室内导航的研究。

1 路径规划算法

1.1 环境地图的表示

机器人在路径规划前，要对所处环境进行地图构建。按照维数，可将地图划分为二维和三维地图。三维地图能够真实地展示外部环境，但也更容易被环境影响，且计算量大。二维地图可以分成栅格、几何地图等。栅格地图由Elfes和Moraves最先提出，将外部环境分成多个单元格，称为栅格，用概率值表示栅格被占据的可能性。栅格地图是对静态环境的近似表征，易于创建和维护，因此本文采用栅格法来构建地图。栅格地图中路径规划如图1所示，白色表示可以通行的区域；黑色栅格表示障碍物。

图1 栅格地图

1.2 传统A＊算法

A算法是在指定地图上根据移动代价来找到最优路径的启发式算法。其评价函数为：

式中，（）代表从起始节点经过当前节点到目标节点的估算成本；（）代表起始节点到的实际成本；（）是A算法的启发函数，代表当前节点到目标节点的估算成本；在传统A算法中都会使用欧氏距离计算（）和（）。

式中，（x，y）是当前节点坐标，（，）和（x，y）分别是起始点和目标点坐标。（）大小可以决定A算法的搜索效率和搜索路径的长短，（）的估值越小，A需要计算的节点越多，算法搜索的效率也就越低，当（）趋于0时，A就变成了Dijkstra算法；但是当（）估值远超（）或者（）等于0时，A就变成了最佳优先搜索（BFS），此时算法只追求速度，不能得到最合适的路径。

首先，在规划路径前需要定义两个列表：一个是Openlist列表，用来存放即将要遍历的节点；另一个是Closelist列表，用来存放已遍历过的节点。在寻路过程中，先要挑出Openlist列表中代价最低的节点添加进Closelist列表中，再把代价最低节点周围的邻节点添加进Openlist列表中。与此同时更新起始节点到各节点的代价（）和各节点到目标点的代价（），依次进行迭代，直到目标点加入了Openlist列表，寻路完成。传统A算法寻路如图2所示，黑色和白色分别表示不可通行和可通行区域，黑色线段表示路径；表示起点、表示目标点，浅灰色区域为规划中遍历的节点。

图2 传统A＊寻路

2 改进A＊算法

传统A算法存在遍历节点和转折点多，内存消耗严重等问题。本文首先提出改进启发函数的计算方式，再结合选取关键点替换传统A中Openlist和Closelist的两个列表，剔除多余的冗余节点，寻找出一条更优路径。

2.1 改进启发函数

传统的A通常是采用欧氏距离计算（），定义移动机器人是八个方向，因此欧氏距离计算出（）的代价值都小于当前节点n到目标节点的实际代价，从而导致寻路过程中遍历的节点较多。

本文采用改进曼哈顿距离计算函数，传统曼哈顿距离是指两个点在标准坐标系上绝对轴距之和，其基本距离公式为：

两种启发函数仿真结果对比如图3所示，欧氏距离函数遍历节点数为75个，曼哈顿距离函数遍历节点数是48个，大大提高了搜索效率。

图3 两种启发函数仿真结果

2.2 结合JPS改进A＊

在A算法规划出路径前采用JPS算法跳点搜索原理进行预处理，JPS算法寻路可以分成两个部分：第一是从Openlist列表中取一个最佳节点，从几个特定方向进行搜索，将各个方向得到的跳跃点加入Openlist中；第二部分就是找到一个跳跃点。对于起始点是向所有方向进行搜索；对于其它节点，需要看父节点指向该节点的方向，再面向所有自然邻节点和被迫邻节点方向进行搜索。

如图4所示，节点周围是无障碍物的，由于从父节点()出发到所有灰色扩展节点的移动代价都小于或等于()经过再到灰色节点，因此不用计算灰色节点，只用裁剪规则剪去灰色节点即可。

图4 无障碍邻节点

直线移动：

斜线移动：

如图5所示，当节点的相邻节点有障碍物时，就不能修剪灰色节点。如果每一条从()出发经过节点后到达节点的路径都比不经过节点的路径短，那么节点就是强制邻节点，强制邻节点的公式为：

图5 障碍邻节点

一个节点是否为跳点可以从三个方面来判断：①节点是起点或终点；②节点在当前搜索方向的前提下有强迫邻居；③当前搜索方向是斜向，且在节点处经过该斜向的水平分量或垂直分量方向移动可以找到跳点，那么当前节点是跳点。

3 仿真分析

在栅格地图上模拟公司环境搭建仿真地图，将前台设置为室内移动机器人的起点，收到送咖啡指令后将咖啡送到会议桌和展厅等不同的目标点。在栅格地图上通过采用改进前后的A算法进行对比，在CPU为i7-8565U@1.80Ghz的电脑上对其搜索路径的效果进行验证。从图6所示的仿真结果可以看出，改进后的A算法拐点数量和寻路过程中遍历的节点数都大大减少，并且在寻路时间上也有所改善。

图6 改进A＊前后仿真结果

表1列出了三组仿真结果中各项指标的对比，改进前后两种算法路径长度基本一样，三条路径的拐点数量相较于传统A依次减少了50%、64%和60%，可以解决咖啡机器人运送过程中拐弯次数多的问题；遍历的节点数依次减少了75%、89%和89%，可以很大程度提高算法的搜索效率和内存的占用率。

表1 仿真结果指标对比

4 结语

针对传统A算法在室内移动配送机器人中存在转折点和遍历节点过多等问题，通过使用改进曼哈顿作为启发函数，即在传统曼哈顿距离函数中允许对角移动，这样既可以解决欧氏距离的路径最短但运行时间长和传统曼哈顿距离搜索时间短但路径不是最短的问题，再结合跳点搜索改进A算法转折点过多的问题，避免运送过程中咖啡洒落和机器多次转弯发生电机堵转的问题，提高了室内移动咖啡机器人导航中的路径搜索效率，符合室内移动机器人的实际运用。