无人快递机器人路径规划算法研究综述

陈键CHEN Jian

（重庆交通大学，重庆400074）

0 引言

近年来，随着互联网的发展，智能手机的普及，短视频平台的发展与直播带货的推广，电子商务规模日益庞大，网购已然成为人们生活中不可缺少的一环。根据中国报告大厅对2020 年1-12 月全国快递量进行监测统计显示：2020 年全国快递量8335789.42 亿件，我国快递体量稳居世界第一。快递员增长率较包裹增长率较低，快递业乱象层出不穷——不送货上门、暴力分拣、快递掉件、用户隐私泄露等。为解决快递行业“最后一公里”乱象，提高用户体验，减轻快递员劳动压力，众多国内外公司投入到无人快递机器人的研发生产[1]。

对无人快递机器人的安全性、高效性、可行性而言，路径规划技术显得尤为重要。无人快递机器人应具备在复杂的社区环境中从起始位置抵达目标位置的能力，此路径应具备耗时少、行驶安全、高效率等特点。并对沿途的动态与静态障碍物做出决策，具有躲避动态障碍物与绕行静态障碍物的能力，同时应实时监测当前已规划路线是否堵塞，是否发生事故，当前客户是否取消取件需求，若发生变故，应具备重新规划路径的能力，合理的路径规划不但能提高无人快递机器人的效率、续航、安全性、使用寿命等，还能减少成本[2]。本文对无人快递机器人的路径规划进行分类总结，剖析各个算法的优缺点，为研究无人快递机器人的学者提供参考。

1 路径规划算法的分类

1.1 基于几何模型算法

在复杂环境下，针对外形不一的障碍物，建立外凸多边形包裹模型，无人快递机器人采取合适的路径绕过障碍物的包裹模型，此方法得到的路径较为平滑，能减少无人快递机器人与障碍物的碰撞。

A*算法是一种启发式算法，启发信息强，变化灵活，可以降低搜索工作量，能用于各式各样的环境，在路径规划中广受欢迎。基本原理：A*算法搜索路径由其估值函数引导方向，A*算法主要由已访问列表与待访问列表组成，列表内每个节点都要存储其父节点，后面生成链路时会用到这个父节点，找到开始节点附近节点，加入到待访问节点，并且选择代价最小节点进行优先访问计算，并且记录已访问节点位置信息和父节点信息到已访问列表中，然后将找到这个节点附近的节点，计算代价值。碰到障碍节点，将其排除在外，不参与计算，如果碰到相同代价值节点，随机选择一个节点走下去，若选择的那一条路径中的节点总代价值大于另一路径，则先放置此路径到待访问列表，换另一总代价值小的路径，所以算法总会从等待队列找最小代价的节点访问，这样的路径是最优的，以此类推，将走到最终目标节点，然后我们根据最后找到的目标节点的父节点，一级一级往回找，直到找到最开始节点，各节点连起来的路径就是最终路径。

f*（n）表示从起始点到目标点途中n 点的估值函数，g*（n）表示从起始点到 n 点的已用成本，h*（n）表示从当前n 点到目标点的启发式估计成本。

A*算法较为完备，得出的解较好，但此算法较为复杂，难以用于障碍物移动的情况。为解决此问题，赵晓[3]等人将跳点搜索算法结合A*算法，优化在搜索过程中的搜索策略，A*算法是挑出周围所有节点进行估值扩展，而跳点搜索算法选择出具有代表性的跳点进行估值扩展。刘子豪[4]等人将反向搜索算法与跳跃点搜索算法相结合，优化传统A*算法用于路径规划时出现的冗余点过多问题和拐点过多问题，林俊等人提出针对L 型路径环境的改进A*算法，优化路径规划中存在的转折问题，减小了转弯次数与转弯角度，提升了无人快递机器人的安全性[5]。

1.2 基于局部避障算法

局部避障算法相对于全局避障算法更为灵活，全局避障算法多为静态环境下的避障，而局部避障算法多考虑动态障碍物的出现，无人快递机器人结合局部避障算法能减少碰撞，使行走更为安全。

1.2.1 人工势场法

将无人快递机器人在环境中的路径规划问题，虚拟为在人工势场中的运动问题。目标位置对无人快递机器人有着“吸引力”，环境中的障碍物对无人快递机器人有着“排斥力”，无人快递机器人在两种力的合力下改变运动轨迹，使无人快递机器人行走于无障碍路径，人工势场法结构简单，能实时躲避障碍物，路径较为平滑且安全。但在复杂环境时，会陷入局部最优，在狭窄环境中易产生剧烈震荡。基本原理如图1。

图1 人工势场法原理图

陈晓娥等人[6]提出一种基于地图栅格化的路径规划算法，提前将已知环境栅格化，用分区算法构建地图模型。在分区中采取VORONOI 图算法与深度优先算法和Dijkstra算法结合，最终得到无人机器人在分区内的最终路线，通过仿真实验，验证了该方法的可行性，该方法能使机器人行进路径缩短，适用于任意形状障碍物。李二超等人[7]针对人工势场法在全局路径规划在多障碍物环境下易陷入狭窄区域与局部最小点问题，提出一种简化障碍物预测碰撞人工势场法，该方法提出简化障碍物模型，引入预测碰撞思想，通过仿真并对比传统方法，得出该方法解决人工势场法在复杂环境，易陷入狭窄环境与局部最小点问题。

1.2.2 动态窗口法

一种基于速度空间的局部规划算法，对当前周围环境进行采样，计算出无碰撞状态下到达目标点的最佳速度，过于依赖全局数据，在未知环境中难以运用。

西安电子科技大学李文刚等人[8]针对动态窗口法与A*算法各自缺点，提出将两种方法结合用于无人机器人路径规划的方法，通过仿真实验，提出的方法比动态窗口法路径短59%，比A*算法搜索路径短21%，验证了所提方法的优越性。哈尔滨工程大学原新等人[9]针对无人机器人在路径规划中动态避障与寻求最优路线问题，提出将动态窗口法与蝙蝠算法结合的方法，用于路径规划的混合规划，该方法在蝙蝠算法部分引入柯西扰动与对数递减策略，并将多个路径指标作为适应度函数；在动态窗口法部分把全局路径规划的路径节点作为局部目标点，将局部避障与全局避障结合。通过仿真实验表明该方法将路径变短，且实现了动态避障。

1.3 智能仿生算法

智能仿生算法是模拟自然界动物昆虫觅食筑巢等行为与生物进化的智能算法。路径规划中常用的方法有神经网诺算法、蚁群算法、遗传算法、粒子群算发、人工鱼群算法、烟花算法以及灰狼化算法等。本文介绍其中几种算法在无人机器人路径规划中的研究现状与进展。

1.3.1 粒子群算法

粒子群算法是模仿鸟群在自然界的觅食行为，鸟群中的个体会互相分享自我的位置信息，个体与群体间的相互交流，最终使群体能锁定食物所处位置，这种模仿鸟群觅食行为中个体与群体的信息交流而得到全局最优解的方法称为粒子群算法。基本原理如图2。

图2 粒子群算法原理图

江西理工大学巫光福等人[10]针对无人机器人在路径规划中使用粒子群算法出现的收敛缓慢，路径不平滑等不足，通过改善粒子群算法，当粒子困于局部最优数值，对全局表现最优粒子速度的大小方向进行扰动，从而加快粒子的收敛速度。提出一个关于路径平滑性和最短路径的函数，且着重考虑非线性惯性的权重。通过仿真实验测试，在动态变化环境中，改良的粒子群算法能及时躲避障碍物，且收敛速度快，所求路径较优。重庆邮电大学胡章芳等人[11]探讨在路径规划中使用单一算法时，大多算法易陷入局部最优解或陷入狭窄空间等问题，提出一种改进的粒子群算法，将粒子群算法，细菌觅食算法与遗传算法相结合，针对粒子在不同环境中的关联性将粒子群分两类，并对各算法进行局部优化，对改进后的方法进行路径规划测试，验证所提方法用于移动机器人路径规划，不仅耗时少，路径短，鲁棒性强，且全局和局部搜索能力提高。

1.3.2 蚁群算法

蚁群算法模仿自然界中蚂蚁觅食行为，蚂蚁觅食会派出多个蚂蚁前往不同方向觅食，并在途中分泌信息素，不同蚂蚁间的信息素可相互识别，蚂蚁会调整到前往信息素高的方向觅食，大量蚂蚁在食物所处路径留下信息素，蚂蚁会调整到信息素高的方向觅食，从而形成一个正反馈系统，经过反复迭代，最终形成觅食路径。基本原理如图3。

图3 蚁群算法原理图

广西大学雷金羡等人[12]探讨传统蚁群算法易陷入局部最优问题，通过改进蚁群算法信息素更新阶段不同路径信息素的更新规则，着重更新最优路径信息素，并在前期迭代搜索中增加一个奖励机制，并在蚁群算法中加入顺序插入策略，顺序交换策略，2-opt 算法。将改进后的方法经过仿真测试，所提改进方法路径的最优解优于改进前，验证算法更优。华中科技大学冯振辉等人[13]探讨传统蚁群算法单一正反馈机制，导致易陷入局部最优与收敛缓慢问题，提出一种混合反馈机制的扩展蚁群算法，定义一种扩展性蚂蚁，此蚂蚁具有全局搜索能力。当遇见局部最优情况，此蚂蚁能跳出局部最优，参照蚁群分工，加入刺激-响应分工负反馈机制，调节算法全局搜索与收敛能力，改进蚂蚁信息素策略，从而改善蚁群算法收敛速度，经过仿真测试与实际实验，此方法用于无人机器人路径规划时，相较于传统蚁群算法具有优越性。

1.3.3 遗传算法

遗传算法参考生物进化总朝向适应环境的方向发展，将问题转化为遗传物质交叉变异问题，利用遗传算子变异模拟进化，逐步进化适用于当前路径规划，此算法收敛快，实现简单，多用于简单地图，在复杂地图中表现较差。基本原理如图4。

图4 遗传算法原理图

山东科技大学王吉岱等人[14]探讨当下无人机器人路径规划效率低下问题，提出一种改进模糊自适应遗传算法，运用领域策略对起初路径进行筛选，筛选出可行路径，再采取模糊控制器调节遗传算法，改良遗传算法在路径规划中的择优速度，在测评遗传因子时，加入余弦函数平滑度。调节不同路径夹角，进而使移动机器人路径更平滑。通过仿真实验验证此方法比改进前更优。上海工程技术大学袁梦飞等人[15]探讨快递物流车行驶不规范，对物流车路径规划采取自适应精英遗传算法。通过定位系统，实时监控车辆运行路线，在路径规划地图上建立快递物流点位置模型，建立适应函数匹配物流点位置经纬度坐标，以距离作为种群评价标准，引入自适应变异算子和自适应交叉算子，把精英个体通过遗传算法保留，平衡算法全局优化与局部搜索能力，通过仿真对比试验，验证改进后的遗传算法收敛快，精度高。

2 总结与展望

2.1 总结

本文主要讲述无人快递机器人路径规划常用算法优缺点，以及一些学者对相应算法的应用与改进，但大多数学者仅仅进行仿真实验，并未实际应用。移动机器人路径规划不仅需要考虑全局路径规划，也要结合局部路径规划。室外环境复杂，不仅对移动机器人的路径规划算法有着高要求，对移动机器人的传感器也是挑战，要求机器人能对突发状况进行处理，实现精确避障，且要求路径短，转弯平滑。

2.2 展望

随着科学技术发展，快递配送的“最后一公里”相对落后，无人快递机器人的路径规划问题面临许多挑战[16,17]，无人快递机器人路径规划在以下几个方面还需提高：

①局部路径规划与全局路径规划相结合。全局路径规划一般是建立在已知环境信息的基础上，适应范围相对有限。局部路径规划能适应未知环境，但有时反应速度不快，对局部路径规划系统品质要求较高，因此，如果把两者结合可达到更好的规划效果。

②提高动态环境的处理能力。城市环境多为动态环境，路面移动物体复杂多变，考虑提高移动机器人自主性，优化移动机器人决策方案，结合5G 通信，提前获取前方位置环境信息，提高移动机器人应急处理能力。

③多传感器数据融合。移动机器人未能将摄像头、激光雷达、温度传感器、姿态传感器等数据完善处理。对于复杂环境，采用多传感器信息融合，由于局部路径规划移动机器人在动态环境中进行路径规划所需的信息都是从传感器获得，因此单一传感器难以保证输入信息的准确性与可靠性，多传感器所获得的信息具有冗余性、互补性、实时性，无人快递机器人若能将算法与多传感器数据结合，可快速并行分析现场环境，提高效率与安全性。