考虑能耗的多AGV系统路径冲突解决策略

宋栓军， 吕 森

(1.西安工程大学 机电工程学院， 陕西 西安 710048；2.西安工程大学 西安市现代智能纺织装备重点实验室， 陕西 西安 710048)

随着电商、快递等行业的高速发展，企业对大规模的自动引导小车(automated guided vehicle，AGV)的需求扩大，多AGV系统常出现冲突问题[1]。AGV系统中的冲突问题主要表现为超过一辆AGV所占用时间和空间发生重叠[2]。

为了解决AGV系统中的突出问题，部分学者对静态算法进行了改进,引入动态机制和冲突解决策略以满足作业需求[3]。王琛[4]和梁承姬等[5-6]先规划出最短路径,根据时间窗预测冲突,对路径进行调整，最终实现无冲突路径规划。姜辰凯等[7]根据时间窗预测冲突，对优先级较低的AGV重新进行路径规划。Hu Y J等[8]将A*算法与时间窗原理相结合，按时间顺序规划每辆AGV的路径，该方法虽然能有效地解决冲突，但并未考虑是否对AGV系统的整体效率产生影响。另一部分学者采用具备多步前瞻性的主动冲突解决算法。Zhong M S等[9]建立了混合整数规划模型，使AGVs的延迟时间最小。Liu C B等[10]采用单向有向图方法和AGV路径规划的A*算法，有效地解决了AGVs的冲突问题。Yuan Z H等[11]先规划AGV全局路径，然后提出了动态快速探索随机树算法，降低了路径冲突的发生率。Zhao Y L等[12]利用共享资源点的动态预留来改变AGV的运动状态，避免碰撞和死锁。曹小华等[13]提出基于冲突预测的多AGV避碰决策优化方法，求解某一时刻碰撞小车的多AGV避碰决策组合优化问题，建立主动冲突解决模型，寻求对于系统而言的最优，然而大多以时间最短或距离最短为目标。但在现实中，小车能耗的浪费导致AGV小车充电次数的增加，继而影响小车的效率。能耗作为影响小车搬运效率的一项重要因素，对于整个AGV系统长期的搬运效率而言更为重要。张中伟等[14]建立了以运输距离和能耗为优化目标的节能单 AGV 路径规划模型。张浩杰等[15]通过构建机器人动力学模型及其在运动过程中的能耗模型,实现对路径的能耗计算。刘贵杰等[16]针对传统路径优化算法中“距离最短能耗非最低”的问题，规划出一条能耗最优的路径。以上文献均以能耗为目标或考虑能耗规划出一条所需能耗最低的单机器人移动路径，但在多AGV系统中，小车完成任务所必须的能耗(最优路径下的能耗)虽然占极大部分，然而多AGV系统在冲突解决过程中的能耗是提高AGV搬运效率的关键。

综上所述，目前解决多AGV系统中可能存在的冲突问题，多采用以时间最小、路程最短为目标，然而得到的冲突解决策略组合并未考虑小车载质量不同时对策略的影响，可能存在负载大的小车行走路程较长、负载小的小车行走距离反而较短的情况，从而导致部分小车耗电过快、能耗不平衡；因此课题组构建了受负载和时间所控制的能耗计算模型，并以总能耗最低为目标，建立多AGV系统路径的冲突消解模型。

1 多AGV系统路径冲突判定

课题组研究的仓库环境路况为双向双车道，假设某一时间段内所有AGV都在运行，且均靠右行驶。仓库环境如图1(a)所示，其中黑色方框为货架，白色方框为AGV可行走的路径。课题组将其简化成如图1(b)所示环境拓扑地图G=(V,A)，其中节点集合V={1,2,…,M}，节点坐标矩阵记为(x,y)M×2。边集合A={(i,j);i,j∈V,i≠j}。拓扑地图虽然能有效表示出各AGV所经过的路径，但无法直观地表示出AGV行走的时间与位置情况，因此在二维拓扑图中引入时间维，如图1(c)所示。

图1 环境地图Figure 1 Environment map

第k辆小车执行任务的路径为Rk(Sk，Lk)；自身质量与载质量之和为mk；其中Sk(x，y)与Lk(x，y)分别为第k辆小车路径起始点与终止点，其中1≤k≤n。小车以速度V匀速行驶。小车与通过路口均可看作质点，由此计算出路径Rk(Sk，Lk)下的通过各节点时间为：T=[T1，T2，…，Tm]。

(1)

则认为第k辆小车与第k+1辆小车的路线同一时间在节点M存在干涉。

课题组的研究是在双向双车道且靠右行驶的路况上进行的，经式(1)判定存在干涉的节点，如小车数量小于3时，有可能不发生冲突。图2所示的3种情况为干涉节点不发生冲突的情况，除此3种情况之外，其他干涉的情况均认定为冲突。

图2 路口不冲突示意图Figure 2 Schematic diagram of no conflicts at intersections

时间窗T下的冲突集合为C={C1,C2,…,Cq}，1≤q≤M,Cq储存了节点q的冲突属性，主要包括冲突时间及冲突小车编号k。

2 考虑能耗的冲突解决策略优化

为应对可能产生的冲突，课题组提出等待与绕道2种冲突解决措施，并提出预测各种解决措施下能耗的计算模型，构建了以系统能耗最低为目标的AGV冲突消解模型，最终优选出系统能耗最低的冲突解决策略。

2.1 能耗计算模型

为降低能耗分析难度，课题组从运动角度对AGV消耗的能耗进行分析。AGV的能耗主要包括待机能耗和运动能耗2种。其中待机能耗相对固定，贯穿于整个运动过程，主要包括小车上控制系统、监测系统以及散热系统的总能耗，具体表现为其额定功率之和P。AGV运动过程中存在着空气阻力、车轮与地面的摩擦阻力，由于速度较低，所以空气阻力忽略不计。小车运动状态下，驱动电机提供的力仅维持克服摩擦力做功。那么克服摩擦力做的功为：

W=μmgL/α。

(2)

式中：μ为滑动摩擦因数，m为小车与运载的货物质量之和，g为重力加速度，L为小车行走的距离，α为行走驱动功率因数。

小车完成任务过程中的能耗

E=(μmgL/α)+(L/V)×P,

(3)

在此基础上提出2种冲突消解措施下的能耗计算方法。

1) 等待措施。若第k辆小车到达冲突节点M时有n″辆小车等待通过，第k辆小车等待时间

(4)

f(x,y)=|x-xl|+|y-yl|。

(5)

局部路径评价方法是用局部路径替换原路径中对应的片段，然后进行评价，评价函数如式(3)所示。其中L为该局部路径替换路径片段后的总长，以评价的函数值对局部路径集进行排序，在选择局部路径时，先选取评价函数值最小的局部路径替换原路径部分片段。小车绕道策略下的新路径比原路径多消耗的能耗

(6)

式中ΔL为绕道策略下新路径比原路径多出的长度。

2.2 冲突消解模型

s.t.

(7)

(8)

m0≤mk≤m0+Q;

(9)

(10)

(11)

优化目标为第k辆小车完成任务过程中所有等待与绕道策略下所需的能耗最低，具体计算如式(7)所示。约束条件式(8)表示小车完成运送任务后所剩的电量不低于最低安全电量，约束条件式(9) 表示AGV负载不能超过其最大载质量。

3 算例分析

为验证课题组提出方法的有效性，采用MATLAB 2018a版进行编程实现。建立80 m×60 m的仓库拓扑地图如图3所示，地图中路口节点个数M为60，节点36～53、节点18～35和节点57～58的距离为20 m，其余各节点间距离均为10 m。

图3 环境拓扑地图Figure 3 Environmental topological map

设置小车参数如表1所示。在参数相同的情况下以4辆小车进行仿真实验，将本研究冲突解决方式与基于贪心算法的冲突解决方式进行对比。基于贪心算法的冲突解决方式在当前看来是最好的冲突解决策略，该方式只注重于当前的决策对系统的影响，不考虑后续是否可能会产生更多的冲突。

表1 AGV参数Table 1 AGV parameters

给定小车载质量与路径如表2所示，各小车路径的时空图如图4所示。得出结果如表3～4所示，2种冲突解决方式下的路径时空图如图5所示。

表2 AGV起始路径Table 2 Starting path of AGV

表3 冲突节点以及冲突AGV的解决措施Table 3 Conflict nodes and resolution measures of conflict AGV

图4 各AGV路径时空图Figure 4 Time and space diagram of AGV

由表3可得各AGV在冲突节点采取的措施，对应的路径如图5所示。由图5可以得出基于能耗的冲突解决方式下仅仅有2辆车在路径冲突时等待，而基于贪心算法的冲突解决方式下有3辆小车在路径冲突时等待。表4所示为在表3的措施下每辆AGV完成任务的时间、距离以及能耗，可以观察到课题组提出的冲突解决方式与基于贪心算法的冲突解决方式的总距离相同，但总能耗与总时间相对较低。由表3知2种冲突解决方式下所选的冲突解决措施均为等待,根据式(3)可知载质量只对运动能耗产生影响，而等待过程中运动能耗为0，所以基于贪心算法的冲突解决方式随机选择小车通过冲突节点的顺序，由此而导致多发生了一次冲突。此外表3验证了本研究优化目标中的能耗计算方式能兼顾负载与路径长度，得到的冲突解决策略下各AGV的能耗较为均衡。

表4 2种冲突解决方式下的各数据对比Table 4 Data comparison under two conflict resolution methods

图5 2种冲突解决方式下路径时空图Figure 5 Path time-space diagram under two conflict resolution methods

为进一步对验证本研究提出的方法，用20台AGV与30台AGV各进行30次试验。每次随机生成起始点与终止点，在负载与电量相同情况下，用遗传算法进行规划。20台AGV时，2种策略下的总能耗对比如图6所示。完成任务总时间、距离以及总能耗如表5所示。由表5可知2种冲突解决方式下每次试验的总路程均为2 000 m，基于能耗的冲突解决方式的能耗均低于基于贪心算法的能耗，本研究解决冲突的绕道措施较为灵活，进行绕道时，选择的局部路径在长度上可能与原路径相同，基于能耗的冲突解决方式能兼顾整个系统运行过程，因此相较于基于贪心算法的解决方式所消耗的能耗更低。

图6 20台AGV时2种冲突解决方式下的总能耗对比Figure 6 Total energy consumption comparison of 20 AGVs under two conflict resolution methods

表5 20台AGV时2种冲突解决方式下的数据对比

30台AGV时，2种策略下的总能耗对比如图7所示，完成任务总时间、距离以及总能耗如表6所示。由表6可得到2种冲突解决方式下每次试验的总路程均为3 000 m，基于能耗的冲突解决方式的能耗均低于基于贪心算法的能耗。且由表5和表6得出随着AGV数量的增多，基于能耗的冲突解决方式与基于贪心算法的冲突解决方式所需的总能耗之差在增大。

表6 30台AGV 2种冲突解决方式下的数据对比Table 6 Data comparison of 30 AGVs undertwo conflict resolution methods

图7 30台AGV时2种冲突解决方式下进行试验的总能耗对比Figure 7 Total energy consumption comparison of test under two conflict resolution methods with 30 AGVs

4 结语

针对多AGV系统中可能存在的路径冲突问题，课题组构建的能耗计算模型受负载和时间所控制，并以能耗最低作为冲突消解模型的评判标准，能综合考虑时间与负载对冲突解决策略的影响，相比于传统以时间为目标更符合现实中AGV运行情况。课题组提出的方法在冲突解决方式中采用绕道策略，较为灵活简单，能有效找寻出合理的局部路径，经仿真证明课题组提出方法在随着AGV数量增加而导致的路况复杂的情况下，依旧能有效得到合理的冲突解决策略组合。在未来工作中可以引入任务优先级，在综合考虑任务优先级与小车电量情况下进行规划，获取均衡的冲突解决策略组合。