基于Plant Simulation的多机器人协作分拣系统仿真分析*

秦德金，周临震，，肖海宁

(1. 江苏大学机械工程学院，江苏 镇江 212013；2. 盐城工学院机械工程学院，江苏 盐城 224051)

0 引言

随着机器人技术的快速发展, 基于多移动机器人协作的自动化物料系统在自动化仓储、港口运输、制造车间等领域[1]的应用愈加广泛。移动机器人路径规划算法是多移动机器人协作系统运行的关键，其优劣将直接影响移动机器人的效率和智能化水平[2]。目前，已有不少实现移动机器人路径规划的算法，如：遗传算法[3]、蚁群算法[4]、Dijkstra算法[5]、A*算法[6]等。然而，这些算法多数是针对单个移动机器人的路径规划算法，一般以最小化移动机器人路径总路程或行程时间为目标，若将该类方法直接用于多移动机器人时，不仅极易导致多移动机器人路径分布的不均衡，进而增加局部交通拥堵风险[7]。而且多数未考虑移动机器人间的碰撞及因路径相向冲突引发的死锁现象[8]，最终影响了多移动机器人协作系统的整体效率和智能化水平。

其次，随着多机器人系统规模的日益增大，使得多移动机器人协作系统的分析难度与日俱增。传统系统验证方法一般基于数学抽象，通过对实体模型进行简化，建立抽象的多机器人优化数学模型[9-10]，但建立过程中的大量简化，使得所建立的数学模型可能与实际系统相距较远。因此，为了提高准确度，可以建立计算机仿真模型，通过仿真模型，方案设计人员可以在方案论证阶段，对多移动机器人协作系统的运动过程进行仿真，分析在不同场景下各种算法的可行性，最大限度地节省人力、物力和时间[11]。

针对上述情况，本文首先以某应用于快递包裹分拣作业的多移动机器人协作系统为例，构建了多机器人协作分拣系统仿真模型；然后，为了提高多机器人路径分布的均衡性，对经典Dijkstra算法进行改进, 提出了一种综合考虑路程、转弯次数和交通流量的多目标优化Dijkstra算法；其次，为了综合多机器人间的避碰与作业区共享需求，设计了一种基于栅格点动态分配的交通管理方法；最后，利用构建的仿真模型对提出的多目标优化Dijkstra算法和分拣系统效率进行了分析。

1 业务流程及仿真需求

以某应用于快递包裹分拣作业的多移动机器人协作系统为例，其布局如图1所示。

1. 入库传送带 2.分拣作业区 3.移动机器人 4.出库传送带 5.停靠区

具体包括：①入库传送带：位于场地四周，用于将需要分拣的包裹送入分拣作业区；②分拣作业区域：分拣作业区采用栅格地图[11]来描述，栅格地图一般由一系列等距的导引标线组成，标线的交点称为栅格点。移动机器人只能沿导引标线行驶，或在栅格点上临时停靠；③移动机器人：从入库传送带装载待分拣的包裹，沿调度系统为其规划的路径行驶，将包裹送至指定出库传送带；④出库传送带：用于将完成分拣的包裹从作业区送至各指定区域，等待物流运输车送至各地；⑤停靠区：用于机器人停靠及充电。

单个移动机器人的分拣作业流程如图2所示。

图2 单个移动机器人分拣作业流程

单个移动机器人的分拣流程如下：

步骤1：系统开始运行后，机器人等待调度系统为其分配新的分拣任务，接收到新的分拣任务后，转步骤2。

步骤2：机器人在交通管理模块的协调下沿由路径规划模块规划的最优路径运行，待到达目的地后，转步骤3。

步骤3：判断任务类型，若是分拣任务，转步骤4；若为充电任务，转步骤5。

步骤4：根据分拣作业要求完成快递包裹的装卸操作，判断电量是否不足，若电量不足则将停靠区设为目的地，转步骤2。若电量充足则转步骤6。

步骤5：在停靠区充电，充电结束转步骤6。

步骤6：判断系统中是否有未完成的分拣任务，若有，则转步骤1；若无，则结束。

2 仿真模型

2.1 对象模型

在该系统中主要有栅格点、机器人行走路径、移动机器人等对象。根据各对象的运行特性在Plant Simulation中选择的仿真对象介绍如下：

(1)栅格点：栅格点为移动机器人在作业区域中的临时停靠点，为了便于控制和采集数据，采用Station对象表示栅格点。

(2)导引标线：软件中可以表示导引标线的对象有双向型和单向型Trcak两种，由于移动机器人可以沿导引标线双向行驶，因此本次建模采用双向Track表示移动机器人的导引标线。

(3)移动机器人：选用Transporter对象表示系统中的移动机器人模型，Transporter是一个主动移动对象，它具备动力，能够主动移动，并具备一定承载能力。

根据图1所示的模型进行布局，最终构建的仿真模型如图3所示。

图3 仿真模型图

2.2 路径规划模块的控制方法

分拣作业区由一系列栅格点和连接栅格的路径组成。Dijkstra算法是求解最短路径问题的经典算法[5]。但经典Dijkstra算法以路程最短为目标，无法考虑交通流及转弯等因素对运行时间的影响。针对这一现状，本文对经典Dijkstra算法进行改进，提出一种综合考虑路程、转弯及交通流量的多目标优化路径规划算法，其控制流程如图4所示，具体介绍如下：

图4 路径规划模块流程图

(1)栅格地图预处理

步骤1：对给定栅格地图(图1)所示中的N个栅格点按顺序编码；

步骤2：获取邻接矩阵A=[aij]N×N，其中aij表示栅格点i到栅格点j的最短距离，其取值如下：

(1)

步骤3：获取栅格点方位矩阵D=[dij]N×N，其中dij表示栅格点i到栅格点j的方位角，其取值如下：

(2)

(2)数据统计

步骤1：统计每个栅格点交通流量，构建流量矩阵F=[f(i)]1×N，其中N为图中栅格点数。f(i)为第i个栅格点的交通流量，表示移动机器人已规划路径库中经过栅格点i的机器人数量。

步骤2：根据路径库中每台移动机器人路径标识各路径允许的运行方向，标识方法如下：若路径{i,j}已在路径库中，则设置1阶邻接矩阵中的元素aij=∞，保证新规划的机器人路径中不会出现路径{j,i}，避免了俩机器人因路径相向冲突引发的死锁现象。

(3)路径规划

根据机器人的位置及目标栅格点，采用改进的Dijkstra算法规划一条从机器人当前位置至目标栅格点的最优路径，具体步骤如下：

步骤1：初始化VS、VD、最优路径矩阵p=[Psi]1×N，和权值矩阵T=[ti]1×N。集合VS中存放已搜索到与源点(机器人当前位置s)最优路径的栅格点；集合VD中存放尚需搜索的栅格点；Psi表示源点s至栅格点i的最优路径；ti表示栅格点i的权值，计算方法如下：

(3)

步骤3：更新VD中每个栅格点的权值、最优路径和一阶邻接矩阵，更新方法如下，假定VD中的栅格点为n。其新的权值tn为：

(4)

其中，θ为转向系数，计算方法如下：

(5)

其中，dmk为路径ρsk最后两个栅格点m与k间的方位角；w为转向时间系数。

步骤4：搜索VD中拥有最小权值的栅格点，不妨设其为栅格点k，将k从VD移入VS，若栅格点k=d，则已搜索到最优路径，进入步骤5，否则，转步骤3。

步骤5：输出最优路径。

2.3 交通管理模块的控制方法

可能引发机器人间碰撞的典型情况如图5所示。如图5a所示：两台机器人竞争同一栅格点，若将此栅格点同时分配给两台移动机器人，必然发生碰撞；如图5b所示：一辆移动机器人即将进入已被其他机器人占用的栅格点，若允许其进入，必然发生碰撞。造成这两种碰撞现象的根源在于系统将同一栅格点同时分配给了多台移动机器人。因此，为了实现避碰，必须保证系统中任一栅格点在同一时刻至多只能分配给一台移动机器人。其次，为了满足多机器对作业区的共享需求，避免某机器人一次分配的栅格点过多，造成系统中大量机器人的长时间等待现象。本文设计了以下栅格点动态分配规则：

规则1：每个栅格点至多只允许分配给一台移动机器人以避免机器人间发生碰撞。

规则2：每个机器人每轮至多只允许分配Nc个栅格点以满足多机器人共享作业区的需求。

(a) 栅格点竞争冲突 (b)栅格点占据冲突图5 引发机器人间碰撞的两种典型情况示意图

所提出的栅格点的动态分配交通管理方法流程如图6所示，具体步骤如下：

图6 栅格点动态分配方法流程

步骤1：标识所有栅格点及其状态：记第i个移动机器人为Ri；NR表示移动移动机器人的总数；将系统已分配给Ri的栅格点中最靠近终点的栅格点作为Ri的临时停靠点，记为FinOcc(Ri)；记从FinOcc(Ri)开始沿着路径前向第k个栅格点为NextRi(k)。完成以上信息标识后转步骤2。

步骤2：采用本文设计的栅格点动态分配规则逐一为每辆移动机器人分配栅格点，为所有移动机器人分配过栅格点后转步骤3。

步骤3：等待所有移动机器人通过已分配栅格点，并停留在临时停靠栅格点后，返回步骤1，重新对所有移动机器人进行栅格点分配。

3 仿真分析

利用构建的多移动机器人协作系统仿真模型进行以下仿真分析：①分析路径规划算法在不同优化目标组合下的系统性能；②系统最大日分拣任务量分析；③根据以上分析结果，确定系统在给定日分拣任务量下的最佳移动机器人数量。

3.1 路径规划算法在不同优化目标组合下的系统性能

以系统在各机器人数下所能实现的单位小时分拣任务量为评价指标，分析系统在三种优化目标组合下的系统性能，三种优化目标组合分别为：

(1)路程—仅以路程最短为优化目标，该目标为经典Dijkstra算法的优化目标。

(2)路程+转弯—考虑转弯时间的行程时间最短。

(3)路程+转弯+流量—本文所提出的改进的多目标优化路径规划算法。

三种优化目标组合在不同移动机器人数量下的性能表现如图7所示。当机器人数量少于10台时，由于机器人密度较低，各机器人间出现路径冲突的概率较小，因此三种优化目标的单位小时完成任务数无明显差异。随着机器人数量的增多，各机器人间发生路径冲突的概率显著增加，若仅以最小化路程为目标，极易出现多移动机器人的路径分布的不均衡，进而出现局部交通拥堵，如图7所示，在该优化目标下单位小时完成的任务数最少。而本文所提出的多目标优化路径规划算法在任何数量的机器人下均能够完成最多的分拣任务，尤其当系统内机器人数多于20台时，其优势更为明显。这表明本文所提出的多目标优化路径规划算法能够提升多机器人路径分布的均衡性，从而提升系统分拣效率。

图7 系统在各机器人数下所能实现的单位小时分拣任务数

3.2 系统最大日分拣任务量分析

因此，如图7所示，虽然采用本文所提出的多目标优化路径规划算法在机器人数量在40时，系统所能实现的分拣任务数最多，然而，由图8可知此时单个机器人所能实现的每小时平均任务数为51个，少于机器人数为30时的69个。因此，综合单个移动机器人的效率，系统最佳的机器人数量为30台，此时系统能够实现的最大单位小时分拣任务数为2010个。以日工作8小时为例，采用本文所提出的多目标优化路径规划算法能够达到的最大日分拣任务量约为16 000个。

图8 单个机器人所能实现的单位小时平均分拣任务数

3.3 给定日分拣任务量下最佳移动机器人数量分析

如图8所示，随着系统中机器人数量的提升，单个机器人所能实现的单位小时平均分拣任务数呈现下降趋势，尤其当系统中的移动机器人数量超过30时，下降明显。这一现象表明，随着机器人数量的提升，机器人间的路径冲突概率上升，增加了交通拥堵风险，最终降低了系统分拣效率，因此，系统中的机器人数量并非越多越好。反之，机器人配置数量不足又无法满足系统的分拣能力要求。有必要根据系统日分拣任务数需求，确定最佳的移动机器人数量，利用构建的仿真模型，系统在给定分拣任务需求下的完工时长如表1所示。

分拣系统维护人员可参照表1，根据日分拣任务数需求，选择合适的机器人数量。以日分拣任务数12 000为例，当投入系统中的机器人数量为20台时，需运行8.54 h才能完成分拣任务，若为25台，则需7.07 h。因此，以日工作8 h为例，投入的最佳机器人数量应为21～25台。

表1 给定日分拣任务量下的完工时长

4 结束语

本文以某应用于快递包裹分拣作业的多移动机器人协作系统为例，构建了多机器人协作分拣系统仿真

模型；为了提高多机器人路径分布的均衡性，对经典Dijkstra算法进行改进，提出了一种综合考虑路程、转弯次数和沿途各栅格点交通流量的多目标优化Dijkstra算法；并设计了一种基于栅格点动态分配的交通管理方法以兼顾多机器人间的避碰及作业区共享需求；最后利用构建的模型对所提出的多目标优化路径规划算法及系统性能进行了分析，分析结果表明：与经典 Dijkstra算法相比，本文所提出的多目标优化路径规划算法，能够显著提升多机器人路径分布的均衡性，从而提升多机器人系统的分拣效率。另外，仿真结果表明随着机器人数量的提升，机器人间的路径冲突概率上升，增加了交通拥堵风险，单个移动机器人单位小时平均分拣任务数呈现下降趋势，因此，有必要根据系统日分拣任务数需求，动态调整最佳的移动机器人数量。