基于深度学习改进的机器人轨迹规划算法

刘玉 邓琛 李文帅 韩宝磊

摘要：在公路环境巡逻机器人轨迹规划问题中，实时准确的交通流量预测对机器人轨迹规划尤为重要。然而由于车流量的随机非线性，使得机器人轨迹规划任务仍然充满挑战。提出一种深度神经网络与轨迹规划算法相结合的融合算法。通过深度学习预测短期交通流量，优化交通网络图并运用轨迹规划算法完成路径规划。实验表明，改进的机器人能够更快、更安全地完成道路巡逻任务。

关键词：机器人;深度学习;融合算法;优化网络图;轨迹规划

DOI：10.11907/rjdk.192115开放科学（资源服务）标识码（OSID）：

中图分类号：TP312文献标识码：A 文章编号：1672-7800（2020）006-0015-04

0 引言

巡逻机器人是一种自动、半自动或由人类控制完成安防工作的机器人，其主要技术之一就是轨迹规划。蒋伟等通过拉格朗日插入值优化A*运动轨迹点找寻最短轨迹;魏玉等提出偏向目标的改进RRT算法优化机器人行驶时间;孙钦鹏等通过动态设置机器人最小转弯半径和最小安全距离以确保机器人安全导航。对于传统轨迹规划算法的优化，虽然能得到一条较优的规划轨迹，但当道路发生拥堵、事故、人流量暴增等情况时，实用性会很差。

智能交通是智慧城市的重要组成部分。Tian等采用基于长短期记忆（LSTM）算法分析不规则采样和丢失的交通流量数据;程健等通过基于状态的过滤模块优化交通物理对象（TPO）与交通信息空间（TIS）的人工智能算法;Chen等提出模糊深度学习方法FDCN预测交通流量。

这些交通流量预测研究为机器人轨迹规划提供了较好的基础。本文提出一种基于深度学习的改进机器人轨迹规划算法。首先，使用深度学习算法对交通流量进行预测;其次，通过交通流量的预测结果优化交通网络图;最后，采用轨迹规划算法获得行驶路径。

1 系统模型

交通流量预测在城市交通管理中非常重要，目前产生了很多交通流量预測方法，一般将其分为参数模型和非参数模型两类。

1.1 模型介绍

参数模型：此类算法通常由简单模型实现并能够明确理解，因此建模实现相对容易。常见的有岭回归算法（Ridge Regression）、弹性网络（Elastic Net）、支持向量回归（Support Vector Regression）等。但由于交通流的随机性，参数模型无法很好地描述这种随机特性。

非參数模型：指没有固定结构且没有固定参数的模型。流行的非参数模型有k近邻算法（k nearest neigh.bor，KNN）、随机森林（Random Forest）、人工神经网络（Artificial Neural Network，ANN）等。基于神经网络的非参数模型具有优越的映射能力，几乎可以使所有函数适应任意精度。

对于公路环境路径规划问题，本文通过分析随机性搜索算法（Rapidly exploring random Trees，RRT）、概率性搜索算法（Probabilistic Roadmap，PRM）和启发性搜索算法A*（A-Star），寻找最优规划算法。

1.2 参数模型

Ridge回归，即在线性回归损失函数上直接加入一个正则项，使模型不但可以拟合数据，并且能够使参数权重尽量小。这个正则项只需在训练进程中加入损失函数。

Lasso回归是另一种正则化的线性回归。与岭回归相似，在损失函数上增加了一个正则化项，但是使用权重向量的L1范数而不是权重向量L2范数平方的一半。

Elastic Net弹性网络介于Ridge回归与Lasso回归之间，它的正则项是Ridge回归和Lasso回归正则项的混合。该模型能够调控它们的混合率，当r=0时，弹性网络就是Ridge回归，当r=1时，其就是Lasso回归。

式（1）-式（3）分别是Ridge回归、Lasso回归和ElasticNet回归的代价损失函数，其中Ridge回归应用L2范数，Lasso回归应用Ll范数，Elastic Net回归应用L1+L2的混合范数，实现正则化。

SVM模型中边界上的点以及两条边界内部违反margin的点被当作支持向量，在后续预测中起作用。在SVR模型中边界上的点以及两条边界以外的点被当作支持向量在预测中起作用。从图1可以看到，在margin内部的这些点误差都为0，只有超出margin的点才会计算error。

1.3 非参数模型

1.3.1 LSTM神经网络

RNN神经网络最初用于语言模型，因为它具有长期记忆能力。但随着时间增长，RNN的梯度可能会随着网络层数增加变为非常深的前馈神经网络。为了解决梯度消失问题，提出了具有遗忘门的RNN结构（LSTM）。

LSTM神经网络的典型结构由输入门、存储单元、遗忘门和输出门4个门组成。输入门从外部获取新数据，存储单元接收输入数据最后一次迭代结果，遗忘门决定何时遗忘输出结果，输出门计算所有的输出单元为LSTM的输出结果。

输入的时间序列特征表示为X=（x1，x2，…，xn），隐藏层记忆细胞的状态H=（h1，h2，…，hn），输出时间序列结果为Y=（Y1，Y2，…，Yn），LSTM网络计算如下：

其中，y代表实际交通流量，p代表预测交通流量。为了最小化训练误差，同时防止局部最优出现，使用Adam梯度下降法。神经网络容易出现过拟合问题。常用正则化配合dropout的方法解决过拟合问题。由于LSTM神经细胞的传递具有“记忆”特性，使得该网络在交通流量预测方面具有特殊优势。

1.3.2 GRU神经网络

GRU作为LSTM的一种变体，将遗忘门和输入门合并为一个更新门。与LSTM单元类似，隐藏单元输出为h_t，是使用隐藏单元输出h_t-1和当前特征X_t计算的，公式如下：

h_t=f（h_t-1，x_t） （11）

复位门的功能类似于LSTM遗忘门。由于GRU结构与LSTM结构相似，这里不再赘述。

1.4 轨迹规划模型

随机搜索算法：RRT算法通过状态空间的随机采样点，把搜索导向空白区域，从而寻找到一条从起始点到目标点的轨迹。RRT-Master算法引入目标点作为随机产生的引导因子，使随机树的生长更有效率，大大缩短了搜索时间。

启发性搜索算法：A*算法是一种启发性全局择优搜索算法，搜索过程中没有舍弃节点，避免了最优节点的丢失，可以找到最短路径。A*算法估价函数可以表示为：

f（n）=g（n）+h（n） （12）

式（12）中，f（n）是节点n的估价函数，h（n）是状态空间中从起点到终点的距离代价函数，g（n）是当前点到目标点的最优估计代价函数，反映搜索的启发信息。

图2（a）是RRT-Master轨迹路线，算法的枝丫生成步长是随机的，一般取地图尺寸的5%-10%，从图中可以看出轨迹曲折性很大，且可重复性小，是一种不完备搜索算法。图2（b）是A*搜索的機器人轨迹。作为一种完备性搜索算法可以搜索出最优路径，但搜索地图尺寸越大，g（n）节点信息越多，计算量就会变大，运行耗费时间相应增多。

概率性搜索算法：PRM将连续空间转换成离散空间，再利用基于图的规划算法（D，A*等）在网络图上寻找路径，算法分为两个阶段：

（1）网络图构建。在状态空间中随机撤点（自定义个数），构建路径网络图。

（2）路径查询。将起始点和目标点连接到网络图中，利用A*完成路径搜索。静态轨迹规划中只需进行一次搜索就可产生引导路径。

图3（a）是采样点网络图，图3（b）是轨迹路线图。地图采样点数是随机的，当采样点较少时得到的是不完备地图，当采样点增加时得到的轨迹可以趋近于一条完备路径，但对计算机的资源消耗也会相应增多。综合算法效率和稳定性考虑，本文使用PRM算法作为路径规划算法。

2 预测交通流量

2.1 数据描述与实验设计

本文使用PEMS数据集。在加利福尼亚范围内部署了超过15000台传感器，多次分析数据集发现5分钟的交通流量预测更合适。其中缺失数据仅占整个数据集的一小部分，所以使用历史平均值来估算缺失数值，以下实验基于该数据集。

实验选择过去30分钟的交通流量，实际上是用6个数据点的时间序列预测未来5分钟的交通流量。前三周用于训练模型，第四周数据用于测试模型。由于每个路段可能都有自己的交通流模式，没有一个通用模式可以适应所有路段，因此为每个道路口构建唯一一个由单个传感器收集的交通流量模型。实验中使用均方误差（MSE）比较算法性能。

2.2 基于参数模型的交通流量预测

首先使用传统回归模型岭回归（Ridge）、弹性网络（Elastic Net）、支持向量回归（SVR）。

图4（a）中横轴为实验次数，纵轴为代价损失函数。为使实验能更好地展示各算法性能优劣，首先打散数据集，然后对每个模型进行CROSS validation=5的交叉验证，每个模型实验20次。可以看出Elastic Net优于Ridge，也优于SVR且更稳定，从图4（b）中看出总体偏差很大。

2.3 基于非参数模型的交通流量预测

非参数模型中，随机森林回归（RFR）、LSTM模型以及GRU模型预测结果如图5所示。

从图5（a）可以看出，非参数模型代价损失函数明显低于参数模型。其中随机森林回归虽然表现相对稳定但整体偏差较大，LSTM与GRU表现接近，但在算法运行过程中GRU耗费时间比LSTM少了近30%。不过实际应用仍选择精度稍高的LSTM模型作为最终的交通流量预测模型。

3 仿真实验

机器人行驶道路环境的卫星地图经过二值化处理生成黑白二值图像，道路区域由0值表示，非道路区域用l值表示，即图7（a）中白色通道和黑色多边形区域（只考虑主干路线，冗余的支线略去），机器人移动区域就是图中的白色道路区域。

为了对比实验结果，首先采用PRM在原始道路中进行路径规划，见图7（b）。接着，采用深度学习模型进行道路交通流量预测，见图7（c），图中黄色区域为拥堵路段即车流量在未来5分钟大于1000辆，从交通道路段集合O删除黄色路段编号。此时重新运行PRM算法，规划出一条时间较短且较安全的新路径，见图7（d）。

4 结语

为了更好地帮助机器人完成路径规划任务，本文对交通流量进行了预测。经过对比参数模型和非参数模型，发现对于非线性的交通车流量预测，非参数模型LSTM预测效果更好，以此得到优化的交通网络图。最后利用PRM路径规划算法寻找到最优路径。该模型算法还可进一步优化，如加入启发式算法优化机器人回调路径。