一种基于广义可能性决策过程的可达性博弈方法

摘要: 本发明涉及计算机应用与计算智能,尤其涉及一种基于广义可能性决策过程的可达性博弈方法。背景技术:1、二人回合制博弈图是计算机科学领域用于系统建模、问题分析的主流正...
一种基于广义可能性决策过程的可达性博弈方法

本发明涉及计算机应用与计算智能,尤其涉及一种基于广义可能性决策过程的可达性博弈方法。

背景技术:

1、二人回合制博弈图是计算机科学领域用于系统建模、问题分析的主流正则模型,可模拟反应式系统组件交互行为与系统规范约束;现有研究分别提出基于模态µ演算的公理推理博弈求解方案、有界博弈语义模型,同时衍生出双回合随机博弈图、马尔可夫决策过程、模糊博弈图等拓展模型,分别用于量化随机系统性能、刻画单一类型不确定性决策场景。

2、传统博弈图默认博弈各方能够完整掌握状态转移结果,严苛的信息完备假设难以适配现实决策场景;概率随机博弈仅能处理具备精确已知概率分布的随机不确定性,模糊博弈图仅可单独建模信息模糊、数据不相容类问题,两类模型仅能适配单一类型不确定信息。而实际医疗诊疗、工业系统调度等决策场景普遍同时存在未知行为、模糊评估、多重未知扰动叠加的复合不确定性,现有模型无法同步融合可能性分布与随机不确定特征开展统一建模;同时现有方案缺少规范化的二人对抗可达博弈形式化定义,无法量化博弈双方抵达目标状态的可能性真值,难以区分最大化、最小化可达可能性的差异化最优策略,也未从理论层面证明博弈模型存在确定性获胜结果,求解得到的决策方案稳定性、可解释性较差,无法为决策者提供精准、贴合真实环境的决策依据。

3、因此,针对上述提出的问题,本发明提出一种基于广义可能性决策过程的可达性博弈方法。

技术实现思路

1、为了克服现有博弈模型仅能处理单一类型不确定性、无法融合多重模糊与随机信息、缺少标准化可达博弈求解框架且无法确定稳定最优对抗策略的问题,本发明提出一种基于广义可能性决策过程的可达性博弈方法,用于统一刻画复合不确定环境下二人对抗决策过程并求解双方确定性最优无记忆获胜策略。

2、本发明的技术方案为:一种基于广义可能性决策过程的可达性博弈方法,包括以下步骤:

3、s1、构建广义可能性决策过程博弈图gpdpg,所述gpdpg为八元组;

4、其中s为可数非空状态集,,、分别为博弈方1、博弈方2的状态子集;

5、act为可数非空动作集合;

6、为博弈方i动作指派函数,限定状态下可用动作;

7、为可能性转移函数,表征博弈方i在指定状态、动作下跳转至下一状态的可能性真值,i=1,2;

8、其中,gpdpg满足完全性约束:对任意、 ,至少存在一个状态,使得;若s、act、原子命题集ap均为有限集,则gpdpg为有限博弈图;

9、s2,基于gpdpg、预设目标状态集,构造广义可能性决策过程可达博弈gpdprpg;定义无记忆策略,满足,将gpdprpg在策略(,)下退化生成完全广义可能性kripke结构fully gpksgs;

10、s3,计算fully gpks中任意有限/无限路径抵达目标集r的可能性真值(π),取全部路径真值上确界得到路径可达可能性t();

11、s4,采用tarski-knaster不动点定理构造单调函数f(y),求解函数f(y)最小不动点(s)作为博弈方1获胜真值,求解(s)作为博弈方2获胜真值;通过不动点唯一性证明gpdprpg具备确定性,满足,;

12、s5,基于获胜真值划分博弈状态区域(r)、(r),其中:

13、;

14、;

15、两区域互不相交且覆盖全部状态集s;

16、s6,构建距离函数f(s)反向递归构造博弈双方最优无记忆策略,博弈方1执行最大化可达可能性的最大可能性策略,博弈方2执行最小化可达可能性的最小可能性策略;

17、s7,将最优无记忆策略代入医疗对抗决策场景gpdpg模型,迭代计算各状态获胜真值,输出最优决策动作方案。

18、作为优选,述步骤s1中的gpdpg包括三类退化判定规则:

19、一,若,,且仅存在唯一满足,则gpdpg退化为经典博弈图;

20、二,当仅单一博弈方任意状态仅存在一个可执行动作时,gpdpg退化为广义可能性kripke结构;

21、三,若,为单元素集合,则gpdpg为fully gpks。

22、作为优选,所述步骤 s3 中路径可能性真值计算规则为:

23、一,若初始状态,则;

24、二,若路径长度n∈n且路径终点,则;

25、三,其余情形下;路径可达可能性,其中p、分别为无限路径集、有限路径集。

26、作为优选,所述步骤s4中单调函数f(y)分段定义为:

27、

28、函数f(y)单调保序,基于tarski-knaster定理求得最小不动点(s)为博弈方1全局获胜真值。

29、作为优选,所述步骤 s4 中博弈双方获胜真值定义为:

30、

31、通过数学归纳法证明任意状态均满足,判定gpdprpg具备博弈确定性。

32、作为优选,所述步骤s5划分的博弈状态区域满足约束:对任意,

33、;为博弈方1可达可能性不低于阈值r的获胜状态集合,为博弈方2将可达可能性控制在阈值r以下的对抗状态集合。

34、作为优选,所述步骤 s6 中距离函数定义为:

35、;

36、基于距离函数递归构造博弈方1最优无记忆策略:

37、;

38、。

39、作为优选,所述步骤s7医疗对抗决策场景建模实施流程包括:

40、t1,将病人设为博弈方1、病菌设为博弈方2,划分三类身体状态对应,病菌对抗状态对应;

41、t2,定义动作集合,通过动作指派函数、绑定各状态可选动作;

42、t3,录入各动作对应的可能性转移真值、,设定康复目标状态集;

43、t4,代入不动点公式计算各状态获胜真值v(s)与距离函数f(s),输出分疗程最优治疗动作。

44、本发明的有益效果:

45、1.本发明融合广义可能性决策过程与可达博弈统一建模模糊、多重未知复合不确定性,克服传统概率博弈仅适配已知随机分布、模糊博弈仅处理单一信息不相容问题的局限,可贴合真实复杂决策环境完成量化推演,解决现有模型只能处理单一类型不确定信息的问题。

46、2.本发明构建标准化gpdprg形式化框架,配套完整路径可达可能性真值计算体系,弥补现有技术缺少规范化二人对抗可达博弈定义、无法量化目标抵达可能性的短板,实现博弈可达结果数值化度量。

47、3.本发明依托tarski-knaster不动点定理严格证明gpdp可达博弈具备确定性,任意状态下双方获胜可能性值唯一相等,解决现有方案求解结果不稳定、可解释性差的问题,保障决策输出结果唯一可靠。

48、4.本发明划分不交且全覆盖的博弈胜负状态区域,论证博弈双方最优无记忆策略存在性并给出构造逻辑,无需复杂历史依赖策略即可求解最优对抗方案,大幅降低博弈求解计算复杂度,弥补现有技术无法区分最大、最小可能性最优策略的不足。

49、5.本发明理论模型可直接落地医疗对抗等实际决策场景,依托模型参数直接迭代输出最优执行方案,兼顾理论完备性与工程实用性,解决传统博弈模型难以直接落地复杂不确定决策业务的问题。