(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211140138.2 (22)申请日 2022.09.19 (71)申请人 南京航空航天大 学 地址 211100 江苏省南京市江宁区将军大 道29号 (72)发明人 梁哲军　谭文安　刘瑾　 (51)Int.Cl. G06Q 10/06(2012.01) (54)发明名称 基于多技能协作的空间众包 任务分配方法 (57)摘要 本发明公开一种基于多技能协作的空间众 包任务分配方法， 空间众包中存在需要一组具备 相关专业技能的工人共同协作完成的复杂任务， 对于如何为这些复杂任务分配适合工人闭队的 问题， 本发明提出了一种基于成本的贪婪方法， 该方法在 进行任务分配前， 利用工人和任务剪枝 策略删除掉不符合相关约束条件的工人任务对， 提高贪婪算法的性能； 在进行任务分配时， 贪婪 的选择一个符合相关约束条件同时使得总成本 增长最小的工人任务对， 将该任务分配给对应的 工人。 本发 明对于装修类或演出类的众包任务提 供了一种新的任务分配策略。 权利要求书3页 说明书5页 附图3页 CN 115392776 A 2022.11.25 CN 115392776 A 1.基于多技能协作的空间众包 任务分配方法， 其特 征在于， 包括以下步骤： 步骤1： 系统建模： 空间众包系统 由任务请求者、 众包平台和工人组成， 众包平台负责将 任务请求 者发布的任务分配给合 适的工人或工人组去完成； 步骤2： 检索当前众包系统中所有可分配的工人和待分配的任务， 构建工人集与任务 集； 步骤3： 利用空间索引方法(如： R ‑Tree)执行范围查询来确定在满足相关约束条件下工 人可以执行哪些任务， 构建有效的工人任务对<wi， tj>； 步骤4： 在进行任务分配前， 利用工人和任务剪枝策略删除掉不符合相关约束条件的工 人任务对， 提高任务分配算方法的效率； 步骤5： 选择使得总成本增长最小的工人任务对， 如果不止一组工人任务对， 执行步骤6 进行冲突处 理， 否则， 执 行步骤7； 步骤6： 各工人任务对之间是否存在工人或任务的交集， 如果存在， 计算对应任务或工 人的优先级， 优先级高的优先分配， 否则， 直接将工人分配给对应的任务； 步骤7： 如果所有的任务都被分配或者没有可分配的工人， 任务分配过程结束； 否则， 跳 转至步骤4， 重复执 行步骤4‑7。 2.如权利要求1所述基于多技 能协作的空间众包任务分配方法， 其特征在于， 所述步骤 1中， 本发明中技能集为D＝{d1， d2，…， dk}， 在时间戳 存在可分配的工人集 对于每个工人 拥有一个技能集合 表示工人wi在时间戳 所处的位 置， vi表示工人wi的平均移动速度， ri表示工人wi愿意移动的最远距离， aik表示工人wi和工 人wk之间的亲密度。 存在待分配的任务集为 对于每个任务 其完成 都需要一个技能集合 lj表示任务tj在时间戳 所处的位置， ej表示任务tj的截止时 间， Bj表示任务tj的预算。 3.如权利要求1所述基于多技 能协作的空间众包任务分配方法， 其特征在于， 所述步骤 2中， 在时间戳 首先检索当前众包系统中所有可分配的工人和待分配的任务， 构建工人集 与任务集 可分配的工人包括上一个时间戳未分配的工人、 完成了之前分配的任务的 工人和新出现的工人； 待分配的任务包括上一个时间戳未分配的任务和任务请求者新发布 的任务。 4.如权利要求1所述基于多技 能协作的空间众包任务分配方法， 其特征在于， 所述步骤 3中， 利用空间索引方法(如： R ‑Tree)执行范围查询来确定在满足相关约束 条件下工人可以 执行哪些任务， 构建有效的工人任务对<wi， tj)。 相关约束条件 包括距离约束、 时间约束、 差 旅成本约束和技能约束。 距离约束： 为了方便起见， 本发明使用欧几里得距离作为距离函数， 距离约束指的是工 人wi当前的位置 和任务tj的位置lj之间的距离小于等于工人最远移动距离， 即： 时间约束： 每个任务tj都有一个截止时间ej， 工人wi需要在截止时间ej前赶到任务tj的 位置lj去执行任务， 即： 差旅成本约束： 工人wi需要移动到任务tj的位置lj去执行任务， 工人的差旅费用cij应该 小于等于任务的预算成本Bj， 即cij＝Kc·dist(li， lj)≤Bj， 其中， KC是一个常量， 表示基本路权　利　要　求　书 1/3 页 2 CN 115392776 A 2程补贴。 技能约束： 每个工 人wi都拥有一个技能集Di， 每个任务tj的完成也需要 一个技能集合Dj， 为避免工人资源的浪费， 被分配的工人需要为任务 提供所需要的技能， 即： 5.如权利要求1所述基于多技 能协作的空间众包任务分配方法， 其特征在于， 所述步骤 4中， 对于工人剪枝策略， W ′j是所有可以分配给任务tj的工人集， Wj是已经分配给任务tj的 工人集， 因为每个任务tj都有一个预算Bj， 所以平台在分配任务时应当考虑任务tj的成本S (Wj)不超过任务tj的预算Bj， 即满足预算约束， 如果当前分配给任务tj的工人集合Wj的技能 集不能涵盖任务tj所需要的技能集， 则需要接着为任务tj分配新的工人wi∈(W′j‑Wj)， 如果 cij+I(Wj∪wi)＞Bj‑C(Wj)， 即分配工人wi的成本打破了预算约束， 那么， 可以将工人任务对< wi， tj>安全的删除。 对于任务剪枝策略， 如果当前分配给任务tj的工人集Wj的技能集不能涵 盖任务tj所需要的技能集， 那么需要接着为任务tj分配新的工人wi∈(W′j‑Wj)， 如果新工人 wi拥有最小的总成本增长 但cij+I(Wj∪wi)＞Bj‑C(Wj)， 即任务tj的预算不足， 那么， 可以 将所有包含tj的工人任务对<wk， tj>， wk∈Wj安全的删除。 被删除的任务 可以参与下一个时间 戳的分配+ 或者等发布者 提高预算之后再参与任务分配。 6.如权利要求1所述基于多技 能协作的空间众包任务分配方法， 其特征在于， 所述步骤 5中， 首先定义下平台总成本， 任务tj的成本S(Wj)等于被分配工人的差旅成本C(Wj)和其工 人组I(Wj)的沟通成本， 即： S(Wj)＝C(Wj)+I(Wj)， 那么， 在时间戳 平台总成本S(T)为： 接下来定义总 成本增长 在时间戳 当新分配工人wi去执行任务tj时， 总成本增长 的计算如公式所示： ΔI(Wj)＝I(Wj)‑I(Wj‑{wi}) 其中， ΔI(Wj)是工人wi分配后任务tj沟通成本的变化， D ′j是已分配给任务tj的工人集 (不包括wi)为任务tj提供的技能集。 7.如权利要求1所述基于多技 能协作的空间众包任务分配方法， 其特征在于， 所述步骤 6中， 在任务分配过程中， 如果遇到工人分配冲突即一个工人可以同时分配给多个任务， 则 需要考虑冲突任务的优先级， 采用优先级高的优先分配的策略。 对于冲突任务的优先级， 本 发明结合冲突任务的预算、 冲突任务剩余时间、 冲突任务的所需技能数来计算， 即： 其中β 代表衡量任务效益与任务紧急程度的权 重。 在任务分配过程中， 如果遇到任务分配冲突即一个任务可以同时被分配给多个工人， 则需要考虑冲突工人 的优先级， 同样采用优先级高的优先分配的策略。 对于冲突工人 的优权　利　要　求　书 2/3 页 3 CN 115392776 A 3