基于非明显操纵机制的移动群智感知任务分配方法
本发明属于移动群智感知,更为具体地讲,涉及一种基于非明显操纵机制的移动群智感知任务分配方法。
背景技术:
1、移动群智感知(mobile crowdsensing, mcs)系统通过用户携带的移动终端、车载终端、可穿戴设备或其他联网感知设备采集城市环境、交通状态、通信质量、公共安全等数据。任务发布方通常在任务发布平台上设置若干兴趣点(point of interest, poi)或任务区域,并给出任务时间、空间范围和预算约束。图1是基于基于兴趣点的移动群智感知过程示意图。如图1所示,平台首先发布多个具有时空约束的感知任务,移动用户根据自身轨迹与执行成本提交报价及路线信息,平台随后在预算约束下选择合适的用户执行任务,并根据任务完成情况向用户支付报酬。
2、在实际工程场景中,该类系统同时面临以下特点:1.用户轨迹具有空间和时间异质性,不同用户对同一任务的贡献价值不同;2.任务数据存在重叠,先执行用户和后执行用户对系统产生的边际贡献不同;3.平台预算有限,需要在总预算内完成用户选择、用户执行顺序排序和支付生成;4.用户报价具有策略性,用户可能通过调整报价影响自身是否被选择以及获得的支付;5.现有机制主要采用占优激励相容机制,该机制要求用户在任何策略性报价下的收益均不超过诚实报价时的收益,容易导致系统选择空间过窄,从而降低整体感知价值。
3、现有移动群智感知任务分配和激励方法通常包括贪心选择、阈值支付、关键支付、在线招募和基于深度学习的分配支付模型等。这些方法在工程落地时存在如下问题:
4、1.传统手工设计方法的分配效率和优化能力有限。传统方法通常依赖人工设计的贪心规则、阈值规则或启发式策略,在用户规模较大、任务复杂且资源受限的场景下,难以充分利用用户之间的异质性与组合关系,因而难以获得高效的分配结果。
5、2.基于深度学习的机制与顺序次模感知价值的结合仍面临挑战。深度学习能够通过数据驱动学习复杂的分配策略,提高大规模场景下的决策效率。然而,现有学习式分配方法通常输出连续的选择得分或分配概率,且不显式生成用户执行顺序,因而难以刻画逐步选择中的边际感知价值变化,也难以将顺序次模结构直接融入可训练的分配网络。目前尚缺乏联合学习用户选择与执行顺序并显式建模顺序次模感知价值的方法。
6、3.深度学习式机制难以从结构上保证经济学特性。现有方法通常将预算约束、个体理性或激励约束作为损失函数中的惩罚项,使模型在训练过程中近似满足相应性质。然而,这种软约束难以保证模型在任意实际输入下始终满足预算可行性、个体理性和合理支付等要求,在分布外场景下可能产生超预算或不合理支付结果。
7、4.传统机制设计主要基于占优激励相容机制(dsic),该机制要求过强且可能牺牲实际效率。传统机制要求用户在任意竞争环境下都能通过完备推理识别诚实报告为最优策略,这对实际mcs用户的认知能力提出了过高要求,同时过强的激励约束也可能压缩可行分配空间,限制平台对用户异质性和轨迹信息的利用。
技术实现思路
1、本发明的目的在于克服现有技术的不足,提供一种基于非明显操纵机制的移动群智感知任务分配方法,针对移动群智感知反向拍卖场景,提出一种基于非明显可操纵机制(not obviously manipulable,简称nom)的任务分配系统,保留对用户策略行为的稳定性约束,通过极端对手配置校验,限制用户通过明显操纵行为获得更优收益,并且采用顺序任务分配和预算裁剪,在预算可行、用户参与理性和分配效率之间取得工程化平衡。
2、为了实现上述发明目的,本发明基于非明显操纵机制的移动群智感知任务分配方法包括以下步骤:
3、s1:构建顺序次模组合优化网络,包括用户评分模块,停止决策单元,松弛网络,资源开销计算模块,候选分配集合生成模块和全局预算裁剪模块,其中:
4、用户评分模块用于根据迭代轮次中每个活跃兴趣点的用户状态矩阵生成用户优先级分数向量并发送至候选分配集合生成模块,,表示最大迭代次数,,表示用户数量,,表示兴趣点数量,表示迭代轮次的活跃兴趣点集合,;表示迭代轮次时每个用户对于每个兴趣点的状态特征,其表达式如下:
5、,
6、其中,表示向量拼接,表示用户声明的对兴趣点任务的资源开销,表示用户对兴趣点任务的贡献价值,表示兴趣点的剩余需求用户数量,表示兴趣点任务已选用户数量,表示已选用户对兴趣点任务的平均资源开销,表示已选用户对兴趣点任务的平均贡献价值,表示剩余资源预算;
7、表示用户对于每个兴趣点的优先级分数;
8、停止决策单元用于根据迭代轮次中每个活跃兴趣点的已分配状态向量生成停止分数并发送至候选分配集合生成模块;的表达式如下:
9、;
10、松弛网络用于根据用户状态矩阵生成资源开销分数向量并发送至资源开销计算模块;
11、资源开销计算模块用于根据兴趣点对应的用户声明资源开销向量和资源开销分数向量生成资源开销向量并发送至候选分配集合生成模块;
12、候选分配集合生成模块用于根据活跃兴趣点的用户优先级分数向量、停止分数和资源开销向量生成迭代轮次的候选分配集合并发送至全局预算裁剪模块,候选分配集合生成的具体方法如下:
13、根据资源开销向量获取每个活跃兴趣点的候选用户集合:
14、;
15、对用户优先级分数向量进行修正,得到修正后的用户优先级分数向量:
16、;
17、将修正后的用户优先级分数向量和停止分数拼接得到动作特征,然后采用gumbel-softmax函数对动作特征进行处理,得到动作分数向量,,表示为兴趣点选择用户的得分,表示停止选择用户的得分;
18、如果得分,兴趣点停止选择用户,否则选择动作分数中最大值对应的用户与兴趣点构成任务-用户对,并添加至候选分配集合;
19、全局预算裁剪模块用于根据资源预算对候选分配集合进行裁剪,得到最终分配集合;其裁剪方法如下:
20、首先根据候选分配集合中每个候选任务-用户对的优先级分数从大到小对候选任务-用户对进行排序,随后采用贪心选择策略,依次选择高分数候选任务-用户对进行资源开销累加,直到资源预算约束无法继续满足,返回最终分配集合;
21、状态更新模块用于根据分配集合进行状态更新,具体方法为:对于分配集合中每个任务-用户对,令分配标识,资源开销,将用户添加至兴趣点的执行序列;同时更新分配集合中每个兴趣点的剩余需求用户数量,剩余资源预算;当有兴趣点在迭代轮次停止选择用户或者剩余需求用户数量,将其从活跃兴趣点集合中删除得到活跃兴趣点集合;当活跃兴趣点集合或,顺序次模组合优化网络停止运行;
22、s2:采集若干移动群智感知任务场景样本对顺序次模组合优化网络进行训练,得到训练好的顺序次模组合优化网络;
23、s3:获取当前移动群智感知任务场景下每个兴趣点的需求用户数量,每个用户对兴趣点任务的贡献价值,用户声明的对兴趣点任务的资源开销,以及所有感知任务信息的资源预算;
24、s4:判断当前移动群智感知任务场景是否有用户满足极端对手配置,如果存在满足极端对手配置的用户,进入步骤s5,否则进入步骤s6;
25、s5:调用闭式分配规则执行任务-用户配对分配;
26、s6:调用顺序次模组合优化网络执行任务-用户分配,其中,初始化兴趣点的剩余需求用户数量,已选用户数量,已选用户对兴趣点任务的平均资源开销、平均贡献价值,剩余资源预算。
27、本发明基于非明显操纵机制的移动群智感知任务分配方法,构建包括用户评分模块,停止决策单元,松弛网络,资源开销计算模块,候选分配集合生成模块和预算裁剪模块的顺序次模组合优化网络,采集若干移动群智感知任务场景样本对顺序次模组合优化网络进行训练,得到训练好的顺序次模组合优化网络,获取当前移动群智感知任务场景下的兴趣点任务信息和用户信息,如果有用户满足极端对手配置,则调用闭式分配规则执行任务-用户配对分配,否则调用顺序次模组合优化网络执行任务-用户分配。
28、本发明具有以下有益效果:
29、1)本发明提出了一种面向移动群智感知反向拍卖的非明显操纵机制框架。首次将非明显操纵(not obviously manipulable, nom)这一弱激励稳定性概念系统性地引入带预算约束的移动群智感知反向拍卖场景,在不依赖严格激励相容约束的前提下,为复杂环境中的机制稳定性与系统效率之间提供了一种新的权衡方式;
30、2)本发明提出了一种面向顺序次模价值结构的可微顺序次模组合优化网络,不同于现有学习型机制设计方法大多采用连续分配变量或概率化分配方式逼近离散分配过程,顺序次模组合优化网络是一种可微顺序选择网络,能够以逐步决策方式直接生成用户的离散0/1选择结果与执行顺序,从而在网络层面显式建模顺序依赖的边际价值递减特性,并实现对离散顺序组合优化过程的端到端表示。同时,该网络通过结构化资源开销计算模块与预算裁剪模块,在网络层面直接保证个体理性与预算可行性;
31、3)在上述可微顺序选择网络基础上,本发明进一步引入基于极端对手配置的结构化nom机制模块,实现了满足非明显操纵(nom)性质的学习型反向拍卖机制,不同于现有主要依基于事后遗憾优化(regret optimization)或激励约束惩罚项的方法,本发明通过机制结构直接保证弱激励稳定性,而深度学习模块仅负责优化系统分配效率;
32、4)实验结果表明,本发明在不同用户规模、任务规模及预算条件下均能够取得更高的系统总价值,并显著优于传统贪心机制与基于严格dsic的深度学习机制;进一步的用户行为分析表明,用户通过偏离真实资源开销难以在最好与最坏收益层面获得明显优势,验证了本发明对显性策略操纵行为的有效抑制能力。
版权声明:本站专利文献数据主要来源于国家知识产权局等公开渠道,由 技术新讯 进行整理汇编。页面设计及数据汇编的著作权归本站所有。全部内容仅供个人学习、科研评估与技术交流参考,严禁用于任何商业用途(包括但不限于直接生产制造、技术转让、倒卖数据等)。
免责条款:专利技术具有时效性,本站不对资料的绝对准确性、完整性和可实施性提供任何明示或暗示的担保。因参考本站内容造成的直接或间接损失,本站不承担相关法律责任。若您认为本站内容有侵权问题,请及时提供权属证明与我们联系,本站将在核实后依法处理。反馈意见:yyfuon@163.com