(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111381312.8 (22)申请日 2021.11.20 (71)申请人 大连理工大 学 地址 116024 辽宁省大连市甘井 子区凌工 路2号 (72)发明人 王东　杜永亮　连捷　 (74)专利代理 机构 大连星河彩舟专利代理事务 所(普通合伙) 2126 3 代理人 陈玲玉 (51)Int.Cl. G06Q 10/06(2012.01) G06Q 10/04(2012.01) (54)发明名称 一种基于任务相似度的多AGV分布式调度方 法与系统 (57)摘要 本发明提出一种基于任务相似度的多AGV分 布式调度方法与系统， 系统包括上位任务管理主 机和下位机。 上位任务管理主机通过任务相似度 将任务进行分组操作， 并且和AGV通过无线通讯 模块进行任务信息交互。 AGV之间采用分布式的 控制方法， 使用基于市场的机制对静态任务和动 态任务进行竞拍， 协商达到任务的合理分配， 由 任务管理模块对任务执行顺序进行优化， 由路径 规划模块规划单个AGV行走路径， 由冲突模块解 决多AGV的路径冲突问题， 从而实现多AGV之间的 分布式控制， 克服集中式计算量大、 效率低的缺 点， 从而提高系统的鲁棒性和运算能力， 增强系 统在复杂工作环境的生存能力， 具有较好的应用 前景。 权利要求书4页 说明书9页 附图7页 CN 114154819 A 2022.03.08 CN 114154819 A 1.一种多AGV分布式系统， 其特征在于： 该系统包括上位任务管理主机和多个同构的 AGV； 上位任务管 理主机包括任务信息管理模块和无线通讯模块A， 每个AGV包括无线通信模 块B、 任务管理模块、 竞 价模块、 路径规划模块、 冲突消解模块和任务执 行模块； 所述任务信息管理模块， 用于 接收新任务信息， 并对新任务进行相似度分组； 所述无线通信模块A和无线通信模块B， 用于实现AGV和上位任务管理主机的双向无线 通讯， 以及AGV之间的双向无线通讯； 所述竞价模块， 用于AGV之间基于市场机制进行相互协商来获取各自要执行的任务组， 从而形成分布式的任务组竞拍； 所述任务管理模块， 用于优化任务执 行顺序和动态任务的管理； 所述的任务执 行模块， 用于各个AGV按照待执 行任务列表的任务 顺序执行任务； 所述的路径规划模块， 用于为每一个AGV规划出 执行任务的最短行驶路径； 所述冲突消解模块， 用于解决多AGV路径冲突问题， AGV之间通过局部交流实现分布式 路径规划。 2.根据权利要求1所述的多AGV分布式系统， 其特征在于， 所述任务信息管理模块， 将接 收的新任务存储在待分配任务列表中， 通过任务相似度算法将待分配任务集合T分成m组， 即{T1,T2,...,Tm}。 3.根据权利要求1所述的多AGV分布式系统， 其特征在于， 所述无线通信模块A和无线通 信模块B， AGV通过TCP/IP协议接收上位任务管理主机传输的任务组信息{T1,T2,...,Tm}， AGV之间通过TCP/IP协议实现竞拍和冲突消解。 4.根据权利要求1所述的多AGV分布式系统， 其特征在于， 所述竞价模块采用模式为： 一 个AGV作为拍卖 方， 其它AGV作为竞价方， 拍卖方向竞价方广播要进行拍卖的任务组， 然后拍 卖方开始接收竞价方的轮番报价， 最后拍卖方按照竞价的结果将任务组分配给竞价 获胜的 AGV。 5.根据权利要求1所述的多AGV分布式系统， 其特征在于， 所述任务管理模块， 通过贪婪 算法对AGV待 执行任务队列中的任务执行顺序进行优化， 以此满足最小化AGV完成任务的总 行走距离； 并通过贪婪 算法对动态任务进 行管理， 将紧急任务插入到相应AGV待 执行任务队 列的下一个任务点， 作为AGV的下一个任务去执行； 将非紧急任务插入到相应AGV待执行任 务队列的最后一个任务 点， 作为AGV的最后一个任务去执 行。 6.根据权利要求1所述的多AGV分布式系统， 其特征在于， 所述的路径规划模块， 通过蚁 群算法为每一个AGV规划 一条距离最短且转弯次数最少的行驶路径， 提高任务被完成的效 率。 7.基于任务相似度的权利要求1～6任一所述多AGV分布式系统的调度方法， 其特征在 于， 包括如下步骤： 步骤1： 假设AGV的数量为m， AGV索引集合为M＝{1,2,...,m}， AGV 集合为S＝{r1,r2,..., rm}； 假设待分配任务列表中任务数为n， 任务索引集合为N＝{1,2,...,n}， 待分配任务集合 为T＝{t1,t2,...,tn}； 对地图信息进行初始化， 包括AGV的位置信息、 AGV的待执行任务列 表； 步骤2： 待分配任务列表中的任务基于任务相似度算法分为m组， 即{T1,T2,...,Tm}； 任 务相似度由式(1)和式(2)计算， 分组要满足式(3)目标函数和式(4)约束；权　利　要　求　书 1/4 页 2 CN 114154819 A 2其中， dmax表示任务ti和任务tj之间距离与任务tj和目标终点之间距离之和的最大值； 其中Tk表示第k组； cij表示任务ti和任务tj之间的曼哈顿距离； wj表示任务j距离 分拣台的曼 哈顿距离； Rij表示任务ti和任务tj之间的相似度； xik表示将任务ti是否分到第k组， 若是， xik 为1， 否则， xik为0； Tik表示将第k组分给AGV  ri， 若是， Tik为1， 否则， Tik为0； 步骤3： 上位任务管理主机通过无线通信模块A将任务组{T1,T2,...,Tm}传输给各个 AGV； 步骤4： AGV之间通过机器人竞价模块进行任务组竞拍， 基于市场机制进行相互协商， 从 而形成分布式的任务 竞拍； 步骤5： 各AGV按照自己所赢得的任务组通过贪婪算法进行任务执行顺序优化， 以此产 生最优的任务执行顺序； 通过计算AGV和任务组中各个任务之间以及任务组中各个任务之 间的曼哈顿距离， 找到距离AGV最近的任务作为AGV第一个要执行的任务， 以第一个要执行 的任务为起点， 对任务进行就近排序， 以满足最小化AGV总行走距离； 将排完序的任务列表 添加到待执 行任务队列； 步骤6： 各AGV从各自的待执行任务队列中逐一取出任务执行， 通过路径规划模块中的 蚁群算法进行路径规划， 通过冲突模块 解决多AGV之间的路径冲突问题； 步骤7： 若有动态任务出现， 设动态任务有紧急任务和非紧急任务； 动态任务为紧急任 务时， AGV之间通过市场机制的竞拍将该任务插入依据 平均相似度指标出价最高的AGV任务 队列中， 作为该AGV下一项任务被执行； 动态任务为 非紧急任务时， AGV之间通过市场机制的权　利　要　求　书 2/4 页 3 CN 114154819 A 3