基于离散多目标布谷鸟算法的食品拣取机器人协同路径规划

刘 剑 胡祝兵 赵学超

(1. 河北石油职业技术大学，河北 承德 067000；2. 河北农业大学，河北 保定 071001)

食品制造业作为食品工业的重要基础，改进和创新生产流程能够降低材料消耗、提高效益，为企业带来巨大竞争优势[1]，为此，越来越多的食品制造加工企业将机器人与标准操作程序相结合[2]，食品机器人在质量检测、食品拣取、码垛等领域发挥着重要作用[3-4]。提高食品原料供应标准化、规范化程度，是食品企业亟需解决的重大课题之一[5]，传统人工原料分拣方式效率低、容易出错、成本很高，因此研究基于机器人的食品拣取方法具有广阔的应用前景[6-7]。

食品拣取机器人路径规划研究是当前人工智能技术研究的热点之一，涉及多学科、多领域。余晓兰等[8]对食品分拣机器人视觉伺服控制进行研究，利用改进的BP神经网络对系统的灵活性进行优化，结果表明优化后的位置精准度更高；赵相博等[9]对食品机器人正逆运动学理论进行研究，得到了搬运路径角位置、速度、加速度曲线；刘芙等[10]通过建立两层路径规划模型，采用改进的鸡群算法对模型求解，缩短了食品机器人总移动距离；张好剑等[11]以优化食品拣取顺序为目标，提出基于遗传算法的分拣路径优化方法。但是这些研究或重点聚焦单个机器人运动轨迹，或只研究单点位或少数点位间机器人拣取路径规划方法，然而，大规模网格化食品原材料仓储已成为发展趋势，如何高效实现多机器人协同食品拣取路径规划具有重要研究意义。

研究以按食品加工配方比例拣取多货位原材料问题为研究背景，拟提出一种基于离散多目标布谷鸟算法的食品拣取机器人协同路径规划方法，通过建立多目标食品拣取机器人协同路径规划模型，设计改进的离散多目标布谷鸟算法(discrete multi-objective cuckoo algorithm，DMCA)和采用改进A*算法对两两货位间最佳移动路径求解，以获取多食品拣取机器人协同最佳路径规划。

1 多目标协同路径规划模型

(1)

1.1 周期拣取原材料总重量

(2)

此时，一个周期n个机器人协同拣取的原材料总重量mtime为：

(3)

1.2 周期总移动距离

设定每个机器人从同一位置A出发，访问完货位后再返回A点，第i个(i∈[1,…,N])机器人移动路径li为：

(4)

式中：

此时，一个周期n个机器人总移动路径Ltime为：

(5)

1.3 周期总能耗

(6)

图1 能耗与访问货位、移动路径间的关系示意图

Figure 1 Schematic diagram of the relationship between energy consumption and access location and moving path

(7)

Θi反映了机器人装载重量与里程关系，也反映了能耗大小，即定义第i个(i∈[1,…,N])机器人移动能耗Ei=β×Θi，其中，β为比例系数，β与机器人自身物理性能相关(β采取试验测定的方式确定取值)。此时，一个周期n个机器人协同拣取的原材料总能耗Etime为：

(8)

1.4 多目标协同路径规划模型建立

建立以周期拣取原材料总重量mtime、周期总移动距离Ltime、周期总能耗Etime为评价指标的多目标食品拣取机器人协同路径规划模型，目标优化函数f(G)为：

(9)

从式(2)～式(8)可以看出，多机器人协同任务分配方案G(O1,O2,…,On)，即n个机器人访问货位路径规划决定了mtime、Ltime和Etime大小。为此，设计离散多目标布谷鸟算法(discrete multi-objective cuckoo algorithm，DMCA)和改进的A*算法，并对多目标协同路径规划模型进行求解，以获取最佳规划方案。

2 DMCA求解多目标协同路径规划模型

2.1 DMCA实现

布谷鸟算法(cuckoo algorithm，CA)作为一种新型启发式计算技术，被广泛应用于多维函数求解、工程优化等领域[13-17]。研究结合多目标协同路径规划模型特点，设计离散多目标布谷鸟算法(DMCA)，定义布谷鸟个体编码Xi为：

(10)

式中：

Gi——第i个路径规划方案；

由于Xi的编码位是离散变化的，为此，设计突变、同类进化、异类进化3种离散编码更新机制。

2.1.1 Pareto最优解 设定布谷鸟种群规模为Q，对于个体Xi和Xj，若满足：

f1(Xi)≤f1(Xj)∧f2(Xi)≤f2(Xj)∧f3(Xi)≤f3(Xj)。

(11)

则认为Xi支配Xj，用Xi≻Xj描述。若个体Xi满足：

(12)

则Xi为Pareto最优解X*，由Pareto最优解组成的集合为Pareto最优解集R*。DMCA每次进化都会产生一个X*(t)，若X*(t)不支配R*中任意个体或不受R*中任意个体支配，则将X*(t)加入R*中。显然，R*的规模是不断扩大的，为控制R*规模，定义阀值ϑ，当R*规模超过ϑ时，依次剔除加权目标函数F最差的个体，直到满足ϑ控制要求。

(13)

式中：

ω1、ω2、ω3——加权系数。

图2 突变操作示意图Figure 2 Schematic diagram of sudden change operation

图3 同类进化更新操作示意图Figure 3 Schematic diagram of similar evolution update operation

2.1.4 异类进化更新 对种群内剩余个体Xi执行异类进化更新操作，即随机选取个体Xj(Xj∉*,Xj≠

图4 异类进化更新操作示意图Figure 4 Schematic diagram of heterogeneous evolution update operation

2.2 改进A*算法求解两两货位间路径

A*算法作为一种启发式搜索技术，利用代价函数f(V)对当前搜索区域内的节点进行筛选，以确定下一步路径节点，f(V)计算公式为：

f(V)=h(V)+g(V)，

(14)

式中：

V——可扩展节点；

h(V)——起始节点到V的实际代价；

g(V)——V到目标点的估计代价。

由于A*算法以当前节点周围4个方向的点为潜在节点，每次迭代过程中都需要对4个节点进行代价计算，计算复杂度为O(4I)(I为路径节点数)，计算复杂度较高。为此，对A*算法进行改进，以得到机器人两两货位间最佳移动路径。以货位C、D为例，机器人在网格边缘进行折线运动，选取货位C所在网格某一顶点为起始点Cstar，Ci为当前父节点(取C0=Cstar)，Ci周围网格顶点为搜索区域可扩展节点Ci,1、Ci,2、Ci,3、Ci,4，代价函数F′(Ci,j)计算公式为：

F′(Ci,j)=d(Cstar,Ci)+d(Ci,Ci,j)+F′(Ci,j)=d(Cstar,Ci)+θ(Ci,j,D)，

(15)

式中：

Ci,j——Ci的可扩展节点，j=1,2,3,4；

d(Cstar,Ci)——点Cstar到点Ci的实际移动距离，m；

θ(Ci,j,D)——点Ci,j到目标点的估计移动距离，m。

为了加快可扩展节点搜索速度，定义扩展节点判定参数Δ(Ci,j)：

(16)

若Δ(Ci,j)>90°，则认为Ci,j为不可扩展节点。图5(a) 给出了改进A*算法实现流程示意图。

2.3 多目标协同路径规划模型实现

采用DMCA算法对多目标协同路径规划函数f(G)进行求解，每个布谷鸟个体代表一种协同规划方案，种群个体分别执行突变、同类进化和异类进化操作，通过迭代更新，最终得到Pareto最优解集R*，决策者按照偏好选取R*内1个或多个解为最终的协同规划方案，图5(b)给出了多目标协同路径规划模型求解流程示意图。

图5 改进A*算法与多目标协同路径规划模型实现流程图Figure 5 Implementation flow chart of improved A* algorithm and multi-objective collaborative path planning model

3 仿真试验

3.1 实例仿真

设某企业原材料仓库为200 m×200 m的方形区域，均匀划分为400个网格，网格边长为10 m。某客户订单需11种原材料，原材料配方比例、机器人数量、机器人满载量、原材料所在货位等信息见表1。机器人从点位(100,200)出发，协同完成原材料拣取任务，采用DMCA算法对协同路径规划模型进行求解，DMCA算法参数设置：算法种群规模Q=300、算法最大迭代次数Tmax=400、λ=2、τ=2、ω1=0.25、ω2=0.4、ω3=0.35。图6给出了一个拣取周期Pareto最优解集(ϑ=11)。

表1 原材料仓储信息Table 1 Storage information of raw materials

从图6可以看出，DMCA算法得到的Pareto最优解集分布相对均匀，能够为决策者提供较好的备选规划方案。

图6 DMCA算法Pareto最优解集Figure 6 Pareto optimal solution set of DMCA algorithm

3.2 决策路径规划结果分析

采用TOPSIS评价法[18]和模糊决策方法[19]从Pareto最优解集中选取路径规划方案1，表2给出了规划方案1、极端解1(移动距离最短)、极端解2(拣取重量最大)、极端解3(距离重量乘积最小)4种决策路径规划方案结果，图7给出了极端解2下的机器人路径规划图，表3 给出了不同规划方案下采用改进A*算法和A*算法的节点间移动距离、算法运算时间对比结果。

从表2可以看出，DMCA算法给出了移动距离最短、拣取原材料重量最大和距离重量乘积最小3种极端解方案和1种根据评价法得到的规划方案，每种方案代表了不同决策偏好，极端解1方案侧重于降低总移动距离，总移动距离最小可以缩短到1 200m；极端解2方案侧重提高材料重量，最大拣取重量可以达到550kg；极端解3方案侧重降低移动能耗，距离重量乘积最小可以达到68 684m·kg；方案1中的3种评价指标更加均衡，拣取重量达到了400kg、总移动距离为1 310m、距离重量乘积为108 290m·kg。

表2 不同方案路径规划结果Table 2 Route planning results of different planning schemes

从图7可以看出，对于极端解2方案，3个机器人移动路径相对平滑，路径规划结果较为合理。

图7 极端解2下的机器人路径规划图Figure 7 Robot path planning diagram under extreme solution 2

从表3可以看出，对于4种路径规划方案，在移动距离上，采用改进A*算法得到的路径移动距离要小于采用A*算法得到的路径移动距离，例如，对于“机器人1”，改进A*算法下移动距离为480，660，370，360m，而A*算法下对应移动距离则为510，680，400，380m；在算法运算时间上，由于改进A*算法引入了扩展节点判定参数，缩小了搜索范围，很大程度地降低了算法运算复杂度，使得改进A*算法运算时间明显小于A*算法。

表3 不同规划方案下采用改进A*算法和A*算法的节点间路径规划对比Table 3 Comparison of inter node path planning using improved A* algorithm and A* algorithm under different planning schemes

3.3 对比试验

为进一步对比分析DMCA算法性能，分别采用文献[20]提出的多目标优化算法和文献[21]提出的改进多目标粒子群算法进行对比试验，图8给出了拣取重量与能耗(移动距离重量乘积)曲线图，图9给出了移动距离与能耗(移动距离重量乘积)曲线图，表4给出了极端解情况下最小总移动距离Ltime,min、最大拣取重量mtime,min、最小距离重量乘积Etime,min和算法运算时间t对比结果。

从图8可以看出，在同等拣取原材料重量下，DMCA算法得到的距离重量乘积要小于其他两种算法，表明当拣取原材料拣取重量相同时，DMCA算法规划路径的能耗更低。从图9可以看出，同等移动距离下，DMCA算法得到的距离重量乘积同样优于其他两种算法，表明DMCA算法规划路径能够以更低的能耗移动更长的距离。从表4可以看出，DMCA算法得到的移动距离、能耗、拣取重量优于其他两种算法，总移动距离缩短了约6.3%，总能耗降低了约7.5%，拣取总重量提高了约12.9%，运行时间缩短了约33.5%。综上仿真试验结果表明，通过设计离散多目标布谷鸟算法编码方式和更新进化方式，提升了算法多目标问题优化能力；采用DMCA算法对协同路径规划模型进行求解，得到的路径规划方案有效平衡了总移动距离、总能耗和拣取原材料总重量的关系，能够更好地为企业提供决策依据。

图8 拣取重量与距离重量乘积对比图Figure 8 Comparison of picking weight and distance weight product

图9 移动距离与距离重量乘积对比图Figure 9 Comparison of moving distance and distance weight product

表4 不同算法结果对比Table 4 Comparison results of different schemes

4 结论

对按食品加工配方比例拣取多货位原材料问题进行研究，提出了基于离散多目标布谷鸟算法的食品拣取机器人协同路径规划方法，建立协同路径规划模型，通过引入改进的多目标离散多目标布谷鸟算法和改进A*算法对模型进行求解，得到的Pareto最优解分布更加均匀，并且在同等拣取原材料重量、同等移动距离条件下，得到的路径规划方案能耗更低，更具决策优势，具有一定的应用推广价值。下一步，将重点研究在线动态协同路径规划方法。