智能仓库中基于两层架构的群机器人路径规划*

薛颂东 张 宇 赵 静 潘理虎

（1.太原科技大学 太原 030024）

（2.广东机电职业技术学院 广州 510515）

1 引言

在由群机器人执行拣货任务的智能仓库中，路径规划关系拣货任务执行效率。其控制方法分为集中式和分布式，集中式控制通过中央控制系统处理机器人之间的协调，发现全局最优路径，但随着群机器人系统规模扩大将导致计算复杂度增加，扩展性不好，仅适合小规模仓库情形。分布式控制则基于机器人的实时信息进行路径规划，能较好适应机器人数量增长和环境变化。不过，在有限感知和局部交互机制下，机器人的最优路径非全局。常用的分布式路径规划算法，主要有D*算法、A*算法、蚁群算法等［1］。其中，D*算法属于动态路径规划算法，A*算法和蚁群算法属于启发式算法。Wang C和Wang L［2］针对自动导引车AGV 的路径规划提出了一种改进A*算法，用其去除边缘，解决K 最短路径问题；提出的另一种基于A*算法的冲突路径规划方法，能有效搜索最短路径并避免碰撞。高小杰［3］为Kiva系统设计了机器人动态避障规则，提出了带优先级列表的改进A*算法。针对遗传算法局部搜索能力较差问题，孙波等［4］提出了一种改进的自适应遗传算法。刘昂等［5］融合改进蚁群算法和鸽群算法，以改善蚁群算法收敛速度慢的问题。Digani 等［6］提出分层地图的思想，第一层为拓扑结构地图，机器人用D*算法进行动态路径规划，第二层采用A*算法进行运动控制，一定程度上实现动态路径规划并避免交通堵塞，但系统运行效率不高。泰应鹏等［7］在基础A*算法中引入时间窗，以增加实时避障功能，但算法实现复杂，对系统时序要求严格。裴以建等［8］在遗传算法中增加插入算子、删除算子，使优化后的无障碍路径质量明显提高。

群机器人路径规划，可转化为多维旅行商问题（MTSP），与旅行商问题相比，叠加不能形成MTSP的全局最优解，需要解决群机器人之间的避碰［9］。大多数路径规划算法并不能适应群机器人协同完成大规模的任务，未能做到任务目标与整体路径规划结合。在遗传算法中融入K-means聚类，确保排序后相邻任务之间的距离之和最小，减少成员机器人在完成远距离任务时的路径浪费，从而减少群机器人的总行驶路程，提高群机器人的路径规划效率。故提出基于K-means 聚类算法、遗传算法和A*算法集成的求解群机器人多目标路径规划问题。具体地，采用集中控制与分布控制相结合的多层控制：用融合K-means聚类改进的遗传算法优化任务目标的遍历顺序，通过集中控制获得仓库全局信息，构造预约表，为机器人提供交通信息；在此基础上，用改进A*算法规划相邻目标点之间的最优路径；局部冲突消除和底层安全保护则基于交通规则和预约表实现。

2 问题描述

智能仓库中配置的群机器人R=｛R1，…，Rm｝由m个成员机器人组成，要求其将订单物品从货架上搬运至拣货台，由工人负责打包。中央控制系统首先按机器人个数将所有任务分成m组订单任务T=｛T1，…Tm｝。订单任务Tj（j∈1，…，m）分配给机器人Ri（i∈1，…，m）后，Ri将依次搬运Tj中的t个货物Ti=｛Ti1，…，Tit｝至拣货台。执行任务时，机器人Ri以拣选平台为起始点，以Ti1为目标点进行路径规划。取货Ti1后，以Ti1为起始点，Ti2为目标点进行路径规划。以此类推，直到提货Tit，以Tit为起点，以拣货台为目标点，将所有目标货物移回拣货台［10］。

图1［11］为某智能仓库的结构化示例，此仓库模型可以充分利用地图空间，在模型中设计相关规则可以提高路径规划的效率。其中，22 个拣货台在左侧均匀分布，35 个标识为深灰色的货架按2 行5列分布，可将环境建模为22×33 大小的二维栅格地图。机器人的初始位置在拣货台附近随机分布，机器人可在货架之间、货架与拣货台之间的通道中同时穿梭运动。要求机器人无碰撞地从初始位置移动至目标货架的位置，将货架上的物品搬运至拣货台，完成一次拣货任务。

图1 智能仓库模型

订单分配和信息共享采用集中控制方式，机器人之间的协同路径规划采用分布式控制方式。首先，将订单信息中的所有任务利用改进遗传算法进行排序，得到最优拣货序列，然后发送到拣货台，拣货台查看所有机器人状态，为“空闲”机器人分配订单任务。各机器人得到一组顺序任务，确定目标货架位置后，进行路径规划，直到一笔订单中的所有物品都被收集起来，机器人搬运所“属”拣货台要求的货物返回该拣货台，由拣货台上的工人完成打包。同时，机器人状态从“工作”变为“空闲”，等待新的订单任务。群机器人执行的货物拣选流程见图2。

图2 任务流程

3 建模

假设机器人Ri为执行拣货任务走过路径Pi，Pi表示机器人Ri完成一次拣货任务的一个顺序集合，在机器人路径规划过程中，货架占用的网格被设置为不可达，以避免机器人与货架之间发生碰撞。这样，可能导致堵塞甚至死锁的机器人之间的碰撞有四种典型情形，见图3。若机器人之间发生情形b所示碰撞，则可按优先权高低顺序通过。但其他三种情形下，仅靠避让操作可能造成死锁。为此，设计了交通规则，规定货架之间的道路为单行道，相邻两条通道方向相反，机器人运行时，只能按规定的通道方向单行，且只能选择“上”“下”“左”“右”或“原地等待”其中之一的运动状态。

图3 碰撞类型

考虑m个机器人无碰撞完成所有任务时所走总路程最短和总时间最短，将群机器人路径规划建模为约束条件下的优化问题，见式（1）：

这里，Si表示机器人Ri完成所规划任务的路径长度，用机器人Ri完成所有任务的步数表示。

将局部路径冲突建模为栅格坐标下的优化问题，C1（Pi）表示机器人是否与货架相撞，C2（Pi，Pj）表示俩个机器人之间是否相撞，用式（2）和式（3）表示：

这里，Ri（x，y）和Ui（x，y）分别为机器人和货架占据的栅格坐标，Pi∩Pj≠ø表示机器人Ri和Rj规划的路径在时空上有交集，即机器人Ri和Rj在某时刻同时出现在某个栅格中，即二者发生相撞［12］。

4 路径规划算法

在机器人进行路径规划之前，首先对系统中的订单进行分配，将确定的目标作为路径终点。建立群机器人的任务规划模型，使用融合K-means聚类的改进遗传算法对任务目标进行排序整理后，确定目标节点的最优遍历序列，得到最优拣选任务顺序。再用改进A*算法规划各机器人的多任务目标路径矩阵。然后用预约表化解局部动态冲突，得到最优路径。

4.1 改进遗传算法

路径规划需要的信息，主要是目标任务位置。目标任务规划的目的是使机器人在根据订单任务进行路径规划和提货时避免绕道，使总距离最小化。首先对种群进行编码，然后用K-means聚类算法把种群按机器人数进行聚类，用遗传算法中的选择、交叉和变异操作，重复迭代后得到最优或次优遍历序列，即得到最优拣选任务顺序。

4.1.1 种群初始化

种群编码方法采用实数编码。对于一组有n个目标的任务，将其编码为从2到n+1的实数，并将相应的拣货台位置编码为实数1。从实数1到n+1，随机生成k个个体的种群，个体基因数为n+1。由于机器人在接到订单任务后将以拣选台为出发点，提取货物后还要返回拣选台，因此将种群中每个个体的第一个基因设置为拣货台位置1。同时，设置遗传算法的迭代次数、交叉概率和变异概率。

将n个目标按机器人数量分成m组，规定每组任务由一个机器人完成。通过K-means 聚类把n个目标点按距离关系分成m组，建立式（4）、（5）所示的规划模型，优化目标为分在同一组内的任意两点间的行走距离之和最小。

其中，i=1，…，n，j=1，…，m。

4.1.2 适应度函数设计

假设机器人Ri有t个拣货目标任务，将拣货目标随机排列，得到机器人Ri的拣货顺序为Ti=｛Ti1，…，Tit｝，其中任意两个分拣节点Tix，Tiy之间的路径为C（Tix，Tiy）。用改进A*算法计算各任务目标点之间的距离长度为Ci（Tx，Ty），得到遗传算法中适应度函数Z，见式（6）。

这里，m表示机器人个数，L表示群机器人中最慢的一个机器人完成其全部任务走过的路径长度。

4.1.3 遗传算法

遗传算法主要有三个关键操作，分别是选择操作、交叉操作和变异操作。选择操作可以留下优势的个体，交叉操作通过交换两个个体的基因序列产生新个体，变异操作则通过使个体基因的某个序列突变产生新个体。通过这三种操作，选择出优势的群体基因。

1）选择操作

采用轮盘赌的方法进行选择操作，选择的概率根据个体的适应度函数值大小来决定，适应度值越大，选择该个体的概率就越大；适应度值越小，选择该个体的概率就越小。如某个体适应度为fi，种群大小为N，则该个体被选择的概率可用式（7）求得：

2）交叉操作

采用单点交叉法，对第1）步选择操作筛选出来的个体进行随机配对，设置交叉概率，配对的依据即按照交叉概率。交叉操作是将配对的组合其中一个个体的某一个基因和组合中另一个个体的某个基因互换。由于基因序列中第1 个位置代表拣货台，拣货台的位置始终是不变的，所以交叉时设置基因序列1的位置不变。

3）变异操作

设置变异概率，在交叉操作后的个体中依据变异概率进行个体的选择，变异操作就是将某个个体的某个基因变异为其他的基因。因为要保证任务对应的编码数字不能重复出现，所以采用对随机选择的个体中的某两个基因进行交换操作。

4.2 节点间路径规划

机器人将按照目标规划一条高效且无碰撞的拣货路线，基本想法是使用A*算法来计算任意两个目标点间的路径长度，在目标点间建立一条路线，按照任务目标点的遍历次序，对其进行规划，找出一条为成员机器人创建的全局路径，并且这条路径要保证机器人之间没有路径冲突。解决冲突的方式是用预约表法消解，保证所有成员机器人的所有路径序列之间没有冲突。

4.2.1 改进A*算法

A*算法是一种在路径规划中常用的启发式搜索算法，可以用来求解两点间的最短路径。算法过程如下：算法从起始节点开始利用估算代价函数依次向外估算相邻节点的路径代价，根据估算路径代价对临近节点进行排序，然后选择最优的临近节点进行下一步的搜索直至目标点。应用到栅格地图中，机器人将从开始栅格出发，每次选择下一步将要移动的栅格时，都会计算出相邻栅格的估算代价；然后移动至估算代价最小的栅格。机器人重复上述步骤，直到移动至目标栅格［13］。估算代价函数用式（8）计算：

这里，g（s）表示机器人从起始栅格移动到当前栅格s的真实代价；h（s）表示机器人从当前栅格s移动到目标栅格的启发估算代价。

一般地，路径规划中的代价指距离代价，本文用曼哈顿距离作为估算函数的代价。曼哈顿距离如式（9）所示。

式中，s.x和s.y分别表示当前栅格s的x轴坐标和y轴坐标，goal.x和goal.y分别表示目标栅格goal的x轴坐标和y轴坐标。

当机器人在真实的仓库中行走时，它将在转弯时需要更长的时间，因此机器人在路径长度相同但弯道数不同的路径上行走时，弯道越少，所需的时间就越少。故修改估算函数估算的代价为时间代价，得到时间代价估算函数g'（s）和h'（s），用式（10）和式（11）计算。

考虑转弯代价时间，改进后的A*算法的估算代价函数用式（12）计算。

式中，tturn代表转弯额外花销的时间，q代表转弯个数。

4.2.2 预约表设计

针对图3 所示的b 类碰撞，通过预约表来避免。预约表中记录各栅格的状态，如果栅格被占用，则机器人ID 会写入预约表的相应位置，如表1所示。该系统可以根据预约表的查询，提前得到相应时间点上的网格的状态。如果栅格中没有任何机器人的ID，表示在相应的时间内没有任何机器人占据此网格，那么机器人可以进入该栅格；如果栅格中有某个机器人的ID，表示在相应的时间有其他的机器人占据了这个网格，那么这个网格就被看作是一个障碍物，机器人不可进入该栅格。预约表是实时变化的，机器人每走一个步长，系统就会根据当前仓库中机器人占用栅格的情况更新预约表［15］。

表1 预约表

5 算法流程

集成K-means聚类算法、改进的遗传算法和改进的A*算法，得到伪码描述的本文算法［14］，见算法1。首先利用K-means聚类算法将所有任务目标按机器人个数进行分组，按分组给种群编码；然后，依照改进A*算法计算各任务目标之间的路径长度，并转化为遗传算法中的适应度函数，经过遗传算法中的选择操作、交叉操作和变异操作，然后迭代若干代，得到的个体即为最优个体，也急速最优的任务序列。任务规划完成后，根据改进A*算法在仓库中进行路径规划，群机器人按照路径规划好的路线依次执行任务，利用交通规则和预约表避免群机器人之间发生碰撞，群机器人完成所有拣货任务后，得到所消耗的总时间和所有机器人走过的总路程。

路径规划算法流程见图4。

图4 路径规划算法流程图

6 仿真

为验证本文方法的有效性，采用图1 所示的仓库地图模型，将本文算法（算法1）与基于传统遗传算法的路径规划方法（算法2）、基于交通规则和预约表的A*算法（算法3）、基于交通规则和预约表的改进A*算法（算法4）进行比较。仿真实验在Matlab 2020a环境中进行。实验设计如下：

1）比较相同规模群机器人执行不同规模任务情形，设机器人数10，任务数依次为50，100，150，200，250，300，比较机器人完成所有任务的总消耗时间和总行走路程。

2）比较相同任务数由不同规模群机器人执行情形，设任务数300，机器人数分别为10，20，30，40，50，比较机器人完成所有任务的总消耗时间和总行走路程。

因为所用算法是一种启发式算法，所以在相同的参数下，实验的结果并不完全一致。所以，每组实验算法都独立地运行了50 次并取平均数作为实验结果。

图5 为4 种路径规划算法下10 个机器人完成不同数量任务需要的总时间。机器人数量维持不变时，运行的总时间随任务数增加而增加。相较于其他路径规划算法，算法1 能有效减少系统运行的总时间，这是因为算法1 中融入聚类算法，把距离近的任务聚集成一类，弥补了其他算法任务分配的不足，随着任务数的增加，聚类算法的效果也就越明显。

图5 群机器人完成不同数量任务所花费的总时间

图6 为在4 种路径规划算法下10 个机器人完成不同数量任务所行走的总路程。由图可知，在机器人数量一定时，任务数量越多，机器人完成任务所走总路程也越多。从实验结果可以看出，相较于算法3 和算法4，算法2 在路径规划前先采用遗传算法进行分配任务，可以在一定程度上减少系统运行的总路程。算法1 在遗传算法中融入聚类算法后，可以减少机器人在做远距离任务时的路径浪费，有效缩短机器人行走的总路程。

图6 群机器人完成不同数量任务所行走的总路程

图7 为在4种路径规划算法下不同数量机器人完成300 个任务所需要的总时间。由图可知，在任务数量不变的情况下，随着机器人的数量增加，机器人完成任务所需总时间在不断减少。相较于其他算法，算法1 仍然有效地缩短了机器人完成所有任务所需要的时间。随着机器人的数量增多，总时间下降的趋势逐渐变缓，这是因为机器人数量越多，群机器人在做任务过程中产生的路径冲突就越多，导致群机器人需要一部分的时间来解决冲突，造成总时间趋势下降缓慢的现象。

图7 不同数量机器人完成任务所花费的总时间

图8 显示了不同数量机器人在4种路径规划算法下完成分配任务所行走的总路程。群机器人完成任务行走的总路程随着群机器人数量的变化而不定的变化。使用本文提出的算法1 后，仍然比其他算法行走更少的路程。可以看出，在群机器人数量由10 增加到20 的阶段，群机器人执行任务的总路程随着机器人数量的增多而快速减少。但是当群机器人数量超过20 时，群机器人总行走路程会缓慢上升。这是由于随着群机器人规模增大，路径冲突可能性随之增大，机器人为了避开路径冲突而选择绕路，导致牺牲一部分路径代价。

图8 不同数量机器人完成任务所行走的总路程

综上所述，采用20个机器人来执行300个任务将减少群机器人执行任务的总时间，同时也能避免过多机器人产生路径冲突造成总路程的增加，提高智能仓库系统效率，节约智能仓库资源。

统计4种算法在最大规模组合条件下（即50个机器人完成300 个任务）总耗时的最优值、平均值和方差，见表2。从统计结果可以看出，本文算法（算法1）的总耗时最优值和平均值均低于其他算法；而方差数据显示，算法1和算法2的稳定性不如算法3 和算法4，这是为优化目标顺序牺牲了算法稳定性。另外，本文算法的稳定性高于传统遗传算法，算法有效性和稳定性具有优势。

表2 算法有效性和稳定性数据分析表

7 结语

针对智能仓库群机器人路径规划问题，提出一种基于两层架构的群机器人路径规划方法。在遗传算法中融合聚类算法，为机器人分配任务；在智能仓库中制定交通规则并设计预约表，避免机器人碰撞。集成多任务目标规划和机器人路径规划算法后，通过仿真实验验证了算法的可行性和高效性。但是对于一个完整的智能仓库来说，也可以从货物的排列，货物的分配等方面进行分析，从多个角度来提升智能仓库的运作效率。本文仅针对每组任务的货物排列顺序进行了规划，同时假设每组订单任务数相同，没有考虑到动态分配的情况。因此，未来将考虑允许系统根据货物情况随机分配每组任务订单的数目，结合机器人的任务分配，研究智能仓库中的群机器人路径规划问题。