本发明涉及智能仓储中多agv的任务分配以及执行顺序问题，具体涉及一种多agv任务分配方法。
背景技术：
1、随着智能机器人技术的不断发展，已经有越来越多的加工车间等向智能化转型，利用agv代理人工承担起自动化搬运以及装卸等任务，因此，如何合理化分配任务给agv成为一个重要的研究问题，合适的任务分配方案能够从整体上减少agv行驶距离和路线冲突问题，从而提高工作效率。
2、目前针对agv任务分配问题，一般采用智能算法或其他算法进行计算解决，其他方法对系统通讯要求过高且运算效率不够高效，蚁群算法是一种仿生算法，也是目前主要研究算法之一，蚁群算法具有分布式计算、无中心控制和分布式固溶体之间间接通信等特征，易于与其他优化算法相结合，它通过简单个体之间的写作表现出求解复杂问题的能力，被广泛运用于求解优化问题。但蚁群算法搜索时间长、易陷入局部最优且动态规划能力弱等缺陷。
技术实现思路
1、发明目的：针对背景技术中指出的问题，本发明提出了一种多agv任务分配方法，将改进的蚁群算法与kmeans算法结合，将多agv任务分配问题，通过加入对任务点聚类，转化为单个agv的任务分配问题，以及对蚁群算法进行改进，加入奖惩机制，以及动态信息素挥发因子ρ，具有提高算法效率，寻优能力，避免算法陷入局部最优解，可以提高算法求解质量的优点。
2、技术方案：本发明公开一种多agv任务分配方法，包括如下步骤：
3、步骤1：确定好待分配任务以及agv的坐标；
4、步骤2：待分配的任务数量为m个，agv的数量为n个，在蚁群算法前期加入kmeans算法，将待分配的任务按照agv的数量聚类分成n组；
5、步骤3：将分好的n组任务分配给相应的agv，再分别按照改进的蚁群算法进行计算，确认agv的任务执行顺序，使多agv执行各自任务的距离总和最小，所述改进的蚁群算法在传统的蚁群算法的基础上，对每次迭代的蚂蚁旅行路径的长度进行排序，长度短的排名靠前，并对信息素更新机制进行改进，加入奖惩机制。
6、进一步地，所述步骤2中在确定任务执行顺序前加入kmeans聚类算法，以待分配的agv的数量作为聚类点的数量，对待分配的任务点进行聚类，将多任务多agv问题，转换成单个agv任务执行顺序问题。
7、进一步地，在确定任务执行顺序前加入kmeans聚类算法，将待分配的任务按照agv的数量分成n组，其具体步骤为：
8、步骤201：确定agv数量为n，任务点集t＝{t1,t2,…,tm}，随机从任务点集t中选取n个聚类集，则待分配聚类点集μ＝{μ1,μ2,…,μn}；
9、步骤202：遍历所有剩余任务点到各个聚类点的距离，并将这些任务点分配给最近的聚类点，第b个任务的坐标为(xb,yb)，第a个聚类点的坐标为(xa,ya)，第b个任务到第a个聚类点的距离函数将这些任务点分配给距离最近的聚类点，其中μa是第a个聚类点的坐标，tb是第b个任务的坐标；
10、步骤203：计算每个聚类中所有任务点的平均值，并更新聚类点，更新聚类点的公式如下：其中μa是第a个聚类点的坐标，na是第a个聚类点的任务数量为n；
11、步骤204，当目标函数|pi+1-pi|<m，则输出算法结果；其中，pi是第i个聚类点与分配给它的任务点的平方误差，xit是算法分配给第i个聚类点中第t个任务的坐标，m是设定的终止阈值。
12、进一步地，所述步骤3中使用欧几里得距离作为执行任务所需的代价，假设任务t1的坐标为(x1,y1)，任务t2的坐标为(x2,y2)，agv从任务t1移动到t2所需消耗的代价为假设第i个agv被分配了k个任务，用集合表示第i个agv完成其被分配的任务所需的代价为其中表示第i个机器人执行从r到r+1任务消耗的代价，表示第i个机器人执行从任务k到第一个任务的代价，所有机器人完成所有任务的总代价为cost，以此为目标函数，以cost最小来进行优化。
13、进一步地，所述步骤3中信息素更新机制的具体公式为：
14、
15、在信息素更新公式中，加入精英蚂蚁，每次迭代中最优路径对应的边增加额外信息素，较差路径减少信息素的积累；
16、的具体公式可表示为：
17、的具体公式如下所示，
18、的具体公式如下所示，
19、其中，ρ表示路径上的信息素的蒸发系数，表示第k只蚂蚁在本次迭代中留在边ij上的信息素量，表示精英蚂蚁在边ij上释放的信息素增量，lbest为最佳路径的总长，rbest为本次迭代中的最优路径，lr为排名第r位的蚂蚁的旅行路径的长度，q为正常数，m为蚂蚁数量。且为防止算法过度“早熟”，将蚂蚁搜索路径上的信息素限制在[τmin,τmax]区间内，具体公式为：
20、
21、进一步地，所述步骤3中，在传统的蚁群算法的基础上，还提出一种自适应挥发因子ρ，在算法前期，ρ的取值为ρmax，但相邻三次最优解没有发生变化，那么自动调整ρ的取值，从而确保算法的全局寻优，避免算法陷入局部最优同时设定挥发系数的下限ρmin，来确保算法的收敛性，更新信息素挥发因子的公式为：
22、有益效果：
23、(1)本方案在蚁群算法前期加入kmeans算法，将待分配任务按照agv数量聚类，任务分配更加合理化，避免任务分配不均衡而导致某agv负荷过载的问题，提升了整体算法的计算速度。
24、(2)本方案通过改进蚁群算法信息素更新公式，加入奖惩机制，对每次迭代的蚂蚁旅行路径的长度进行排列，距离短的靠前。每次迭代中，路径最优可以获得额外信息素，而路径长度相对较差的减少信息素积累，使得蚂蚁更快找到最优解，使得算法收敛速度更快。
25、(3)本方案在改进蚁群算法信息素更新公式中，采用自然对数加权方式更新信息素，信息素递增较为平缓，避免出现信息素急剧增加以及将信息素限制在一定区间内，有效避免某条路径远大于其他路径，使得算法不再扩散，陷入局部最优。
26、(4)本方案改进了蚁群算法的信息素挥发因子ρ，加入判断机制以及引用线性变化，在前期确保全局搜索能力，增加解的多样性的同时，避免最优解陷入局部最优，并且设定挥发系数的下限ρmin，来确保算法后期的收敛性。
1.一种多agv任务分配方法，其特征在于，包括如下步骤：
2.根据权利要求1所述的一种多agv任务分配方法，其特征在于，所述步骤2中在确定任务执行顺序前加入kmeans聚类算法，以待分配的agv的数量作为聚类点的数量，对待分配的任务点进行聚类，将多任务多agv问题，转换成单个agv任务执行顺序问题。
3.根据权利要求2所述的一种多agv任务分配方法，其特征在于，在确定任务执行顺序前加入kmeans聚类算法，将待分配的任务按照agv的数量分成n组，其具体步骤为：
4.根据权利要求1所述的一种多agv任务分配方法，其特征在于，所述步骤3中使用欧几里得距离作为执行任务所需的代价，假设任务t1的坐标为(x1，y1)，任务t2的坐标为(x2，y2)，agv从任务t1移动到t2所需消耗的代价为假设第i个agv被分配了k个任务，用集合表示第i个agv完成其被分配的任务所需的代价为其中表示第i个机器人执行从r到r+1任务消耗的代价，表示第i个机器人执行从任务k到第一个任务的代价，所有机器人完成所有任务的总代价为cost，以此为目标函数，以cost最小来进行优化。
5.根据权利要求4所述的一种多agv任务分配方法，其特征在于，所述步骤3中信息素更新机制的具体公式为：
6.根据权利要求5所述的一种多agv任务分配方法，其特征在于，所述步骤3中，在传统的蚁群算法的基础上，还提出一种自适应挥发因子ρ，在算法前期，ρ的取值为ρmax，但相邻三次最优解没有发生变化，那么自动调整ρ的取值，从而确保算法的全局寻优，避免算法陷入局部最优同时设定挥发系数的下限ρmin，来确保算法的收敛性，更新信息素挥发因子的公式为：
