基于遗传算法的仓储机器人多目标路径规划方法

2020-07-20段晶晶袁源乙苏宇霞

物流技术 2020年6期

辜勇，段晶晶，袁源乙，苏宇霞

（武汉理工大学物流工程学院，湖北武汉 430063）

1 引言

智能仓库中移动机器人有助于促进仓库无人化操作及自动化运转。随着市场不断扩大，单个机器人难以满足日益复杂、繁多的任务需求，多机器人协同作业系统[1]应运而生，其具有更强的鲁棒性和环境适应性。其中多机器人的路径规划[2]是实现当前多机器人系统在智能仓储中应用的研究热点。智能仓库中多机器人路径规划是指，在仓库复杂动态环境下多仓储机器人能够无碰撞、快速地完成拣选任务。根据多机器人路径规划的特点，该问题可以转化为多维旅行商问题（Multidimensional Traveling Salesman Problem,MTSP）[3]。相对于旅行商问题（Traveling Salesman Problem,TSP），多个TSP的单纯叠加不能构成MTSP的全局最优解，还需要考虑多机器人相互之间的协调、避碰。因此本文提出一种基于遗传算法和A*算法相结合的混合算法解决仓储机器人多目标路径规划问题。

多机器人路径规划属于NP-hard问题，主要解决算法有：传统算法[4]、智能优化算法[5]和其它算法等。其中遗传算法[6]是一种典型的智能算法，它通过模拟生物体遗传变异得到优势种群的过程来解决问题，具有随机并行搜索能力，能够快速搜索寻找全局最优解。Bajrami,等[7]针对封闭条件下的静态和动态障碍物环境，利用遗传算法进行路径规划取得较好效果。裴以建,等[8]在遗传过程中增加插入算子、删除算子，使得机器人得到优化后的无障碍路径。但大多数算法并不适应多机器人协同系统，未从整体出发，将多机器人路径冲突与整体路径规划进行结合。

机器人行驶过程中，避免相互之间的局部动态冲突是多机器人规划的关键问题。可采用交通规则[9]规定仓库行驶方向，从而降低冲突发生数目，但牺牲了仓库通道的利用率，而且仍存在不可避免的冲突。也可采用速度调整法[10]，借助增大或降低机器人速率等策略来避开冲突，该方法对系统性能要求比较高。夏清松,等[11]通过对机器人进行优先级排序，化解不同类型路径冲突。通过以上文献分析可知，优先级法虽然简单易行、效率较高，但忽视了从减少路径冲突数目的角度考虑问题。在实际路径规划中，A*算法[12]作为一种启发式算法，通过启发函数将搜索方向指向目标点，该算法对环境信息敏感，能直接有效应对动态环境下路径规划问题，根据优先级不同可迅速调整路径。

本文从多机器人协调配合出发，利用A*算法规划各机器人两两目标点之间的最优路径，并结合不同机器人的优先级得到全局路径；然后引入改进遗传算法调整目标节点遍历序列和化解路径冲突方式，以实现多机器人路径规划全局最优。

2 环境建模

合理的仓库环境建模方法有助于后续路径规划算法的设计。本文利用栅格建模法，提出一个高效、可重构的自动化仓库模型，如图1所示。仓库由货架、拣选台、停放点和可行道路四部分组成，划分成30×30的栅格。仓库正中间摆放立体货架用来容纳仓储货物，是仓库的主体部分；仓库左侧均匀分布4个分拣台，机器人将货物搬运到这里进行分拣；仓库左下方为机器人停放点，为机器人充电或暂时停放空闲机器人。仓库中空白栅格是行驶道路，每排货架之间、每列货架之间均为单车道。

智能仓库的作业流程为：每个仓储机器人都有n个拣选任务，分布在不同的货架节点，各机器人需遍历其目标节点完成拣选任务。仓储物流机器人在收到出货指令后快速响应，拣选所需货物，然后包装出库。

图1 仓库地图模型

3 节点间路径规划

在智能仓库中，每个机器人根据目标任务，需要规划无碰撞、高效率的路径进行拣选作业。基本思路是用A*算法计算两两节点之间的路径，按照目标节点的遍历顺序，得到单个机器人的全局路径规划；然后检查机器人路径间是否存在冲突。若存在冲突，则利用优先级法化解冲突，再继续检查是否存在新冲突，直到所有路径之间无冲突产生。

3.1 A＊算法

本文采用A*算法进行路径寻优。该算法设置open表和close表，搜索过程从初始节点出发，将其相邻节点加入open表；通过估算相邻节点的路径代价f(n)，选择f(n)最小的节点更新为当前节点，加入close表；重复该过程，直到到达目标节点。f(n)的计算公式是：

其中，g(n)指从初始节点移动到当前节点n的代价，h(n)指从当前节点n移动到目标节点所需的代价。两者之和为f(n)，指经过当前节点n的总路径代价。

3.2 冲突类型及化解

本文假设：（1）仓库道路均为双向单车道，仅允许单个机器人通过，可双向行驶；（2）各机器人的行驶速度保持不变，避免相互之间发生追赶冲突；（3）机器人运行过程中不会出现意外故障；（4）每单位时间可行驶单位栅格距离，即1个单位路径长度；（5）每个机器人执行多个目标任务，且每个任务只能由单个机器人完成。

在实际过程中多个机器人同时运行作业，其中两个或多个机器人同时到达某位置，便会产生冲突。若冲突不能被及时化解消除，甚至会造成路径死锁。路径冲突可分为以下3种典型类别：（1）相向冲突：指两机器人在同车道相向行驶，其行驶方向呈180°夹角，两者在同一时刻到达某节点。若发生该冲突，任一机器人暂停都会造成路径堵塞。必须将其中一个机器人重新规划路径行驶，才能消除冲突。（2）交叉冲突：指两个机器人的行驶方向呈90°夹角，同一时刻到达交叉路口某节点。化解该冲突可采用暂停策略，例如机器人Robot1在t时刻占用冲突节点，另一个机器人Robot2暂停等待；等到t+1时刻，Robot1已经安全通过，Robot2再占用冲突节点。结果是两个机器人的总行驶路径不变，仅增加一个单位的总行驶时间。（3）复合冲突：指相向冲突和交叉冲突同一时刻在同一个节点发生。具体如图2所示。

图2 路径冲突类型

3.3 优先级

优先级是根据一定的准则或目标，给发生路径冲突的机器人指定先后顺序，有序化解路径冲突。优先级高的机器人占据冲突位置，继续按照原路径行驶；优先级低的机器人可以选择暂停，等待其他机器人行驶过后，再继续前进；优先级低的机器人也可重新规划路径，避免路径冲突的发生。化解冲突过程中，优先级的确定准则对仓库总运行效率有着重要影响。

各机器人在全局路径规划过程中，忽略其他机器人动态变化。因此不仅会与其他机器人产生冲突，而且应对路径冲突而调整路径后，会造成新的冲突。例如，在时刻t时，Robot1、Robot2、Robot3的初始规划路径如图3（a）所示，各机器人在仓库内同时向各自目标行驶。可以预见全局路径规划中，在t+2时Robot1与Robot2发生冲突，在t+5时Robot1与Robot3发生冲突。当正常行驶到t+2时，需要确定Robot1和Robot2的优先级priority，此时有两种优先级顺序：（1）priority1>priority2，那么Robot1和Robot2按照图3（b）顺序通过路口。之后在t+5时，再消除Rrobot1和Robot3之间的路径冲突，如图3（c）所示。（2）priority1

依据上述分析，本文提出围绕动态路径规划中的路径冲突数目，决定优先级大小。将某机器人在全局路径规划中与其他机器人形成的冲突数目，命名为该机器人的基本冲突数目conflict_basic。另外，假定其他机器人的路径均不变化，令该机器人作为次优先级，造成的新冲突数目称为conflict_add。因此，本文提出机器人的总冲突数目为all_conflict，由式（2）得到。该值越大，机器人的优先级越低；相反，优先级越高。

因此，解决路径冲突问题，首先应计算冲突中各机器人的总冲突数目，冲突数越小，优先级越高；若两者冲突次数相同，则随机选择某机器人作为高优先级。

4 改进遗传算法

随着目标节点的增多，仓储机器人的多目标点路径规划的复杂度也显著提升。本节利用遗传算法调节目标节点的遍历序列，根据问题的具体特征对变量进行编码，然后采用选择、交叉、变异等遗传操作，重复迭代后得到最优或次优解。

图3 消除冲突序列图

4.1 多目标任务规划建模

假设robot(i)的拣货任务有n个目标任务，将拣选目标随机排列顺序，得到分拣顺序为Ti1,Ti2,...,Tin，其中任意两个分拣节点Tix,Tiy之间的路径为Ci(Tx,Ty)。robot(i)有n!种方式遍历所有目标节点。

按照上文中A*算法计算各目标节点之间的路径，可以得到robot(i)的距离矩阵Di：

在各机器人遍历目标节点的基础上，化解局部路径冲突，才能得到可行的全局路径长度，继而转化为遗传算法中目标函数Z，即：

式中，L表示多机器人消除局部路径冲突后，完成全部目标任务所需的路径长度；v表示机器人匀速行驶速度。twait表示各机器人为解决路径冲突所耗费的总等待时间。

4.2 符号矩阵编码法

常见编码方式包括二进制编码法、矩阵编码法、浮点编码法、符号编码法等。符号编码法是指将个体染色体的基因值取为符号集，如{A1,A2,...,B1,B2,...}。矩阵编码法是指用矩阵的形式表示染色体基因。

根据问题特性，结合符号编码和矩阵编码的优点，创新编码方式，提出符号矩阵编码法。一方面，本问题中多目标节点各不相同，具有唯一性，可采用符号代表目标任务节点；另一方面，每个机器人的任务已分配完成，相互之间独立，利用矩阵将多个机器人的目标节点进行组合排列。

将robot(i)的n个目标节点随机分布排列为其中共有m个robot，可以组成单个染色体，即：

式中，chrom(k)表示第k个染色体，是m×n维矩阵，每一行表示单个机器人的目标任务节点。

4.3 遗传操作

在遗传过程中，“选择”操作选择优势个体、“交叉”操作交换个体的染色体基因、“变异”操作指个体染色体基因突变，产生新个体。这三种遗传操作帮助优势群体基因存活下来。与此对应的是选择算子、交叉算子和变异算子。

（1）选择操作。本文利用轮盘赌选择法，根据各个个体的适应度大小来决定该个体基因保留的可能性，适应度越大，被选择的概率就越大；反之亦然。某个体适应度为fi，种群大小为NP，则它被选择的概率为：

（2）交叉算子。常见交叉算子主要有：单点交叉、两点交叉、多点交叉等。由于本文中每个个体染色体包含多个目标节点，每个robot的目标节点为一行，行与行之间不相同。因此选择多点交叉算子。即在个体染色体矩阵编码中的每行都选择交叉点，然后两两个体配对交叉。

（3）变异算子。本文采用实值变异方式，把相应的基因用取值范围内的其他随机基因代替。

4.4 算法流程图

针对仓储机器人群的多目标点路径规划，融合改进优先级策略和遗传算法，可以得到本文的算法流程。首先建立各个移动机器人关于目标节点的路径信息表；然后依照改进优先级法计算总行驶时间，并转化为遗传算法中种群的个体适应度；对种群进行选择、交叉、变异操作；经过数次迭代，得到最优个体，即为最优路径规划结果。如图4所示。

图4 流程图

5 模型仿真实验

为验证本文算法改进的有效性，在图1仓库地图模型的基础上，将本文提出的基于遗传算法的仓储机器人多目标路径规划方法（简称算法1）与基于常规优先级法的路径规划算法[11]（简称算法2）以及交通规则下的路径规划算法[9]（简称算法3）进行比较，证明基于遗传算法的仓储机器人多目标路径规划算法能有效提高多仓储机器人系统的运行效率。其中算法2和算法3均为目前普遍使用的先规划最短路径，再进行动态路径规划的算法。

仿真实验基于相同数量的机器人，运用不同规划算法，执行不同任务数量，比较算法的路径规划长度和行驶时间。机器人数量为5，目标任务数量依次为15，20，25，30，35，40。其中算法1由于基于遗传算法，每次运行结果可能不尽相同。因此每个任务量都运行100次后，选择众数作为算法1的实验结果。算法的路径长度对比结果如图5所示。

图5 不同算法的路径长度比较

首先比较不同算法规划的路径长度。总的来说，随着任务量的增加，总路径长度均呈上升趋势。在任务量较少时，路径之间的冲突较少，算法1和算法2的路径长度几乎没有差别，算法3因交通限制致使绕路行驶，导致路径较长。随着任务量逐渐增加，算法1逐渐优于算法2。这是由于路径冲突数目的增加，算法1通过计算冲突数目和路径长度，调整了目标节点的序列，从而有效缩短了路径长度。算法3随任务量的增加，多机器人之间由于交通规则存在，路径冲突对其影响不大，所以路径长度增长缓慢，后期优于算法2。

对3种算法的行驶时间进行比较，具体如图6所示。总趋势和图5的路径长度趋势相似，呈上升态势。由于算法1能有效减少路径冲突数目，且路径长度并没有太大变化，从而节约了更多的时间，因此在总行驶时间方面的优势更加明显。