复杂工业品仓储环境无人机盘库任务规划

潘 楠，陈启用，刘海石，孙雨轩，安裕强，潘地林

(1.昆明理工大学 民航与航空学院，云南 昆明 650500；2.昆明理工大学 材料科学与工程学院，云南 昆明 650500；3.昆明理工大学 信息工程与自动化学院，云南 昆明 650500；4.红云红河集团有限责任公司 物流中心，云南 昆明 650202；5.昆明智渊测控科技有限公司，云南 昆明 650500)

0 引言

烟草工业企业需要经常对成品、原辅物料等进行盘点，以保证进销存管理软件中的数据与实际库存相符，只有确保物资库存系统数据与实际库存的一致，才能进行库存的合理分析，从而结合年度施工计划和采购周期合理安排正确的采购与生产活动。原料及辅料库的布局十分复杂，人工盘点效率较低，而且由于盘库属于劳动密集型工作，工人在盘点过程中常常由于工作疲劳会登记错误[ 1]，这为烟草工业企业的生产与采购活动带来不便。

无人机具有灵活性高、适用性广、信息化高、非接触等特点，而射频识别(Radio Frequency Identification, RFID)作为一种非接触式的信息采集技术，具有自动识别、安全性高、非接触等特点，已广泛应用于各大物流企业。基于此，无人机上安装阅读器设备，可自动对已粘贴标签的货物进行盘点，而且体积小、效率高、能耗低、盘点准确。因此，无人机结合高精度便携式RFID阅读器将成为智慧仓储的一大应用趋势[2-3]。

由于应用于仓储环境挂载阅读器的无人机重量较大，其最大制约因素为无人机(Unmanned Aerial Vehicle, UAV)的有效续航时间，为了保证盘点任务能在无人机最大续航时间内顺利完成，在执行任务过程中，一条能耗最小的航迹至关重要。因此在UAV+RFID阅读器盘库技术中，UAV航迹规划是需要解决的关键问题。航迹规划的目的是为UAV在采集货物信息过程中安排出从空间一个点到另一个点的可行飞行航迹，以保证无人机盘点准确率为前提，在满足无人机有效续航时间等各种约束条件下，尽可能快速、节能地完成盘点任务。

随着自主系统的发展，航迹规划已成为相关人员的重点研究内容，涌现了大量的无人机航迹规划算法，主要包括传统经典算法以及现代智能算法[4]。对于空间较小的航迹规划等小规模问题如A*算法[5]，传统经典算法可以快速、准确地找到可飞行航迹，当处理三维空间或搜索空间较大时，其计算量急剧增加，寻优时间快速增长，求解速度极其缓慢，具有一定的局限性。因此，现阶段解决无人机航迹规划问题的算法主要为现代智能算法[6-9]。其中，作为现代智能算法的差分进化算法(Differential Evolution Algorithm, DE)及其改进算法已广泛应用于无人机航迹规划中[10-12]，而粒子群算法作为成熟的启发式算法亦广泛应用于无人机航迹规划中[9，13-14]。文献[15]基于三维空间中的无人机航迹规划问题，设计了一种基于贪婪策略和等级制度的鲸鱼优化算法(Whale Optimization Algorithm, WOA)，实验结果表明该算法的性能优于粒子群等传统的智能优化算法。

在无人机航迹规划的部分研究中，存在模型过于简化等问题，没有考虑到UAV飞行过程中的资源消耗量不仅与飞行航迹长度有关，还与飞行过程中的受力有关[16]；在进行算法的改进时仅考虑算法的逼近性，没有考虑算法的均匀性；在无人机搭载高精度便携式RFID阅读器的盘库航迹规划研究中存在工作场景单一、约束条件过少等问题[17]。通过以上研究发现，尽管研究背景多种多样，但是其均旨在提高应用于无人机航迹规划算法的收敛精度以及收敛速度，避免其陷入局部最优，没有进行无人机航迹规划数学模型的改进。

复杂工业品仓库三维环境无人机盘库任务规划涉及对多维变量的求解，缩小了解空间，这要求算法具有较强的全局搜索能力。而且仓库条件复杂，如货物堆放杂乱、室内其他障碍物的阻碍等，对无人机的飞行有众多限制，进一步缩小了解空间。另外，无人机自身性能和搭载设备也为问题的求解增加了难度，这是一个复杂且耦合的优化问题。生命周期群搜索算法(Life-cycle Swarm Optimization, LSO)[18]作为一种新的群体智能算法，对比粒子群等算法在处理优化问题时，具有收敛速度快、收敛精度高等优点，已应用于简单环境中的航迹规划问题[19]。虽然，生命周期群搜索算法在对复杂函数进行寻优时具有较好的全局收敛性和鲁棒性，但其在求解本文复杂三维环境下无人机路径规划问题的过程中，容易陷入早熟，传统差分进化算法亦存在同样的问题。因此，本文将生命周期群搜索算法与差分进化算法相结合，利用差分进化算法的变异性并引入轮盘赌策略和种群分级制度策略，提高了生命周期群搜索算法的全局搜索能力，避免了生命周期群搜索算法在处理本文复杂三维环境下航迹规划问题容易陷入早熟的问题。

为解决以有障碍的仓储环境以及大型高架仓库环境为背景的无人机盘库航迹规划问题，与现有工作不同，本文将无人机运动模型引入无人机航迹规划方案中，从做功的角度来研究无人机的能效比，以提高无人机盘库时的工作效率以及工作时长。设计了基于生命周期群搜索的混合差分进化算法，以解决无人机盘点货物时的路径规划问题。该算法保留了传统差分进化算法较强的全局收敛能力和稳健性，同时改进了生命周期群搜索算法在解决无人机路径规划这类大规模寻优问题时的鲁棒性、逼近性以及均匀性，有效提高了生命周期群搜索算法的收敛速度以及收敛精度。通过仿真表明，利用改进后的算法可有效解决复杂工业品仓库三维环境下的无人机盘库任务规划问题。

1 数学模型的建立

1.1 无人机运动模型

模型假设如下：

(1)无人机飞行过程中空气阻力系数、空气密度恒定不变，不受飞行高度影响。

(2)由于无人机飞行空间为室内仓库，因此在飞行过程中不计气流扰动，忽略风条件影响。

(3)分析无人机的受力过程中，不涉及无人机复杂运动。

(4)无人机在平飞时为匀速运动。

(5)无人机在每一段航迹的飞行过程中，竖直方向上均为匀速飞行。

(6)忽略偏航运动、滚转运动对无人机输出功率的影响。

对四旋翼无人机在空间中的三维直线运动过程进行受力分析，由文献[20]可知，在输出电压一定时，取多个样本测试，观察在不同电压下，四旋翼无人机功率载荷的最大值、最小值、均值以及标准偏差，四旋翼无人机的功率载荷可以近似看作常数。功率载荷公式为：

(1)

式中:Q为四旋翼无人机的功率载荷;∑F为无人机在电压一定的情况下的总升力。

由式(1)进一步得出结论：无人机总升力∑F与总功率P之间的关系简化之后成正比：

∑F=kP，k为常数。

(2)

无人机各运动过程受力分析如图1示。

图1中：FL,FR,FD分别为无人机在平飞、上升、下降状态下的所需要的总升力;fL，fR，fD分别为无人机在平飞、上升、下降状态下所受到的空气阻力;G为无人机的自身重力，则有：

FRj=fRj+G,

FDj=G-fDj。

(3)

当无人机以匀速v飞行时，无人机所受空气阻力

(4)

式中：c为空气阻力系数;ρ为空气密度;S为物体受力面积。

无人机在任意两个节点j-1和j之间的航迹段的飞行过程均可分解为平行于和垂直于xoy平面的两个向量。由于假设无人机在每一段航迹的飞行过程中，竖直方向上均为匀速飞行，在任意航迹段j-1→j中，无人机的航迹段向量为(xj,yj,zj)，又已知无人机平飞速度vL，则无人机的竖直方向速度为：

(5)

其中lj为两个节点j-1、j之间的航迹段长度。

1.2 约束条件

由于RFID有最大扫描范围和最大扫描角度，若要保证货物能够被扫描到，无人机的航迹将会受到影响，具体约束如下：

vRj≤vRmax;

(6)

vDj≤vDmax;

(7)

∑tj≤Tmax。

(8)

式(6)～式(8)分别为最大上升速度、最大下降速度、最长航时约束，式(8)中tj为第j段航迹飞行时间。

如图2所示为无人机搭载高精度便携式RFID阅读器对室内仓库货物盘点的示意图。其中无人机上的RFID阅读器模块通过扫描物品和货位上安装的电子标签即可达到盘点的目的，RFID阅读器最大扫描范围为Rmax，最大扫描角度为φmax。

假设第i件货物的RFID标签中心坐标Ci为(xi,yi,zi)，无人机在对第i件货物执行盘库任务时所处坐标Ui为(xi′,yi′,zi′)，则有

(9)

0≤cos(n,CiUi)≤cosφmax。

(10)

其中，在无人机盘点乱堆码的货物时(如图3)，n为垂直于地面的向量。

1.3 目标函数

由于无人机总升力∑F与总功率p之间成正比关系，可得无人机总飞行过程中能效比[21]，即单位长度航迹所消耗的能量

(11)

可得无人机盘点过程中时效比，即单位货物的盘点时间

(12)

因此，本文的目标函数为：

y=minK·T。

(13)

2 算法描述

2.1 算法基本原理

生命周期群搜索算法通过模拟自然界生物生长的各个过程，不断迭代进化并向着个体适应度更优的方向移动，实现了算法的寻优过程。本文在此基础上引入差分进化算法，采用种群分级制度，对适应度值较低的个体进行差分进化，提出了基于生命周期群搜索的混合差分进化算法(hybrid Differential Evolution algorithm based on Life-cycle Swarm Optimization algorithm, LSO-DE)，以此来对模型进行求解。

设航迹点个数为D，种群个体数即种群规模为Nmax，对于本文模型，种群个体可表示为Xi={(x1,y1,z1),(x2,y2,z2),…,(xD,xD,xD)}(i=1,2,…,Nmax)。

对于基本差分进化算法，其主要过程包括种群初始化、变异、交叉和选择：

(1)差分进化种群初始化

在解空间中对个体Xi中的每个航迹点(xi,yi,zi)(i=1,2,…,D)进行均匀随机初始化。

(2)差分进化变异操作

通过差分策略实现变异操作：

(14)

(3)差分进化交叉操作

(15)

其中:r0为0～1之间的随机数;cr为交叉概率，cr∈[0,1]。

(4)差分进化选择操作

采用贪婪策略实现选择操作：

(16)

生命周期群搜索算法主要实现过程包括种群初始化、个体生长发育。其中个体生长发育包括混沌趋化操作、同化操作和换位操作。

(1)种群初始化

在解空间中，按照个体位置上下限Bup和Blow随机生成初始种群。

(2)混沌趋化操作

Xi+1=μXi(1-Xi)。

(17)

(3)同化操作

对于种群中其他个体，将以一定的概率执行同化操作或换位操作。设个体觅食方式选择同化操作的概率为Pas，若个体在一次觅食中产生的随机数在Pas内，则进行同化操作。

同化是指种群内采取社会觅食方式的个体的觅食路径受最优个体影响，追随群内最优个体进行搜索，公式如下：

(18)

(4)换位操作

若个体在一次觅食中产生的随机数在Pas外，则进行换位操作。执行换位操作的个体采取独立觅食的方式，公式如下：

(19)

本文在传统差分进化算法的基础上进行了一定改进，改进后再与生命周期群搜索算法混合，增强混合算法的性能。具体改进如下：

传统差分进化算法利用贪婪策略进行选择操作，使得种群中总是保留最优个体，在某些情况下，采用贪婪策略会丢失其他个体所保留的位置信息，不利于算法的全局寻优。本文参考自然界的自然选择行为，对传统差分进化算法的选择算子作出改进，将子代合并到亲代中组成新种群，个体适应度值归一化之后利用轮盘赌的方法淘汰数目为超过种群规模上限的数量的个体。

2.2 LSO-DE混合算法求解模型基本步骤

(1)算法参数初始化和种群初始化

对算法涉及到的参数进行初始化，包括最大迭代次数Gmax,种群规模Nmax,变异算子F,路径点个数NP，个体觅食方式选择同化操作的概率Pas。

由于本文三维环境模型中障碍物较多，在初始种群时，若对种群个体随机初始化，将造成大量个体的航迹点落在障碍物内，导致初始个体适应度值的较差，影响算法的寻优。为尽量避免这种情况的发生，本文采用RRT(rapid-exploration random tree)算法对路径进行初始化，获得Nmax个与障碍物无碰撞的初始路径，为了保证个体路径点个数相等，方便算法寻优，采用多项式拟合的方法对初始航迹点组成的初始路径进行分段拟合后等距分割取D个点。

(2)更新全局极值

计算种群中每个个体的适应度函数值，将当前种群最优适应度(函数)值与历史最优适应度值进行比较，若当前种群最优适应度值优于历史最优适应度值，则更新全局极值。

(3)生命周期群搜索更新策略的个体位置更新

将每条路径的航迹点集合作为一个个体，采用生命周期群搜索算法的混沌趋化操作、同化操作和换位操作更新个体位置。

(4)种群分级

为了使种群个体的生长更加趋于多样性，按种群平均适应度值Oavg将种群进行分级并执行差分进化操作。若个体适应度值小于Oavg，表示该个体代表的解较差，即归入差等种群，反之则归入优等种群中,

(20)

式中O为种群适应度值总和。分级后，计算差等种群的个体数和个体适应度值，设差等种群的个体数为M。

(5)差等种群进化与合并

1)变异。随机选中差等种群中的3个个体，按式(14)执行变异操作。

(21)

当r5<0.5时，则生成以父体基因为主的子代个体，否则生成以母体基因为主的子代体。其中F2为随机搜索系数。

3)选择。计算子代与亲代个体的适应度值，并将其适应度值进行归一化操作。为保证差等种群执行差分进化后种群数量不变，计算目前子代与亲代个体总数与差等种群规模M的差值ΔN。采用利用轮盘赌的方式，筛选出M数量的个体，剩余的ΔN数量的个体被淘汰。

4)种群合并。将进化后的差等种群与优等种群进行合并，保证原始种群个体数不变。

(6)退出条件

判断当前是否达到最大迭代次数，如果达到，则输出最优个体的位置，否则返回步骤(2)。

算法流程如图4所示。

3 仿真实验研究

在某大型烟草工业集团的原辅物料仓库中，工作人员需要经常性的对仓库中的原辅物料进行盘点，保证进销存管理软件中的数据与实际库存相符。原辅物料仓库布局十分复杂，采集这类仓库内的货物信息的困难很大。本文依据某集团的某原辅物料仓库现场的环境信息(如图3)进行物理建模，其中原辅物料仓库信息如表1所示，原辅物料仓库的环境模型如图5所示。

表1 仓库信息表

为验证本文所提算法的可行性以及有效性，选取近年来在路径规划领域提出的WOA、DE以及LSO算法进行对比。实验室自制四旋翼无人机的参数如表2所示，其搭载RFID阅读器最大扫描范围为4 m，最大扫描角度为120°。

表2 无人机参数表

3.1 原辅物料仓库环境下仿真实验研究

如图6～图9所示为LSO-DE算法、DE算法、LSO算法、WOA算法在一次运行中对原辅物料仓库的盘点路线图。如图10所示为4个算法在一次运行中目标函数值随迭代次数变化曲线，图11为4个算法各运行30次目标函数平均值随迭代次数变化曲线。如表3所示为4个算法一次运行中的货物信息采集结果，表4为4个算法各运行30次的平均货物信息采集结果。

表3 原辅物料仓库环境下4个算法的货物信息采集结果

表4 原辅物料仓库环境下4个算法各运行30次的平均货物信息采集结果

3.2 仿真实验分析

从图10和图11中可以看出，DE算法、LSO算法、WOA算法以及LSO-DE算法均具有较强的寻优能力。图10中，利用LSO-DE算法得出的优化航迹，在对原辅物料仓库进行货物信息提取时得出的最优适应度值为1.006，而DE算法的最优适应度值为1.060，LSO算法的最优适应度值为1.079，WOA算法的最优适应度值为1.147。因此，可以得出结论，LSO-DE算法收敛速度最快，收敛精度最高，优化效果最好。

从表4中可以得出，利用本文所提出的LSO-DE算法得出的优化航迹，对原辅物料仓库进行货物信息提取时，30次运行过程中平均货物提取率为91.67%，平均货物提取时间为0.123 0 s/箱，均优于其他3个算法。可以得出结论，在烟草工业企业原辅物料仓库较复杂的巡检环境中，无论从哪个指标看，利用LSO-DE算法所得出的结果均为最优。

从得出的结果分析，在引入DE算法之后，LSO算法的全局搜索能力明显增强，表明通过种群分级制度，DE算法和LSO算法的个体生长发育策略能进行很好的融合。同时，轮盘赌策略改进后的DE算法的变异能力有效地避免了LSO算法在处理本文复杂三维环境下航迹规划问题容易陷入早熟的问题。

因此，可以得出结论：本文算法在发现最优值方面，相比于DE算法、LSO算法和WOA算法，能力较强，逼近性、均匀性较好，在对此类多约束条件下的盘库无人机航迹规划问题的处理中，LSO-DE算法更有竞争力。

4 结束语

为提高无人机搭载高精度便携式RFID阅读器的盘库效率以及安全系数，同时有效降低盘库过程中无效的飞行航迹长度以减少能耗，本文提出了LSO-DE算法，对盘库无人机航迹规划展开了研究。本文所建立的无人机航迹规划模型，从做功的角度来研究无人机的能效比和时效比，可有效提高无人机盘库时的工作效率以及工作时长。通过DE算法、LSO算法和WOA算法与LSO-DE算法进行对比的结果表明，本文所提算法能力较强，逼近性、均匀性较好，更能适用于复杂工业品仓库无人机盘库任务规划。本文研究的航迹规划模型考虑了无人飞行器性能约束，并利用LSO-DE算法对模型求解得到了一条切实可行的航迹，但需要指出的是，在得到航迹信息后，仍需要有一名飞控手来对装备RFID阅读器的无人机进行操控。未来，将对仓库进行更为精准的建图与定位，面向盘库无人机自主飞行展开更为深入的研究工作。