本文探讨了在随机多智能体系统中采用自然策略进行PATL及PATL逻辑的模型检验问题。研究发现，当活跃联盟被限于确定性策略时，NatPATL的模型检验问题是NP完全的；在同样的限制条件下，NatPATL的复杂度则为2NEXPTIME。若不限制策略类型，则对于NatPATL的模型检验复杂度为EXPSPACE，而NatPATL*为3EXPSPACE。这是第一次将自然策略的概念从完全确定性的设置拓展到了随机环境中。自然策略提供了一种平衡的方法，既考虑了智能体有限的记忆能力，又兼顾了模型检验的复杂度，以更好地反映现实中人类行为的特征。
多智能体系统（MAS）是由多个具有自主性的智能体组成的系统，智能体之间可以相互作用以达到共同或个体的目标。交替时间逻辑（ATL）及其扩展ATL是用于描述和验证MAS中策略行为的形式化方法，特别是用来表示智能体联盟是否能够施加控制以实现某些属性。自然策略作为一种新框架，考虑了智能体的有限记忆能力，使策略更加接近真实世界中的行为模式。本文首次将自然策略应用于随机环境中的概率逻辑PATL和PATL，研究了这些逻辑在不同策略下的模型检测复杂性。结果显示，在随机MAS中，当策略被限制为确定性时，NatPATL的模型检测复杂度为NP完全，NatPATL为2NEXPTIME；而在无限制情况下，NatPATL和NatPATL的复杂度分别为EXPSPACE和3EXPSPACE。
1 自然策略
自然策略的定义
一种针对多智能体系统（MAS）中的智能体设计的策略形式，旨在描述一种简单且易于理解的行为方式。自然策略通过一系列条件-行动规则来表示，这些规则构成一个有序列表。在游戏的进行过程中，智能体会根据当前的历史选择第一个符合条件的规则执行相应的动作。这里的条件是基于布尔公式构建的正则表达式，能够描述智能体在游戏的不同阶段所观察到的命题变量序列。因此，自然策略不仅考虑了智能体的有限记忆，而且能够适应那些无法记住无限历史信息的情况。
自然策略下的PATL和PATL*模型检测复杂度
-
确定性策略：对于NatPATL，当考虑确定性自然策略时，模型检测问题是NP完全的。对于NatPATL*，当同样限制在确定性策略的情况下，模型检测的复杂度为2NEXPTIME。
-
随机性策略：不限制策略的情况下，NatPATL的模型检测复杂度为EXPSPACE。对于不受限的NatPATL*，其模型检测复杂度为3EXPSPACE。
确定性策略下的复杂度分析
-
1.NP-完全性：对于确定性自然策略下的NatPATL模型检验问题，证明表明该问题是NP-完全的。这一结论是通过展示NatPATL如何扩展了具有无记忆确定性策略的POMDPs（部分可观测马尔可夫决策过程）并结合几乎必然可达目标的状态来得出的。
-
2.POMDPs与无记忆策略：在POMDPs中，如果只允许无记忆的确定性策略，那么找到几乎必然达到目标状态的策略是一个NP-完全问题。这一结论进一步支持了NatPATL模型检验问题的NP-完全性。
随机性策略下的复杂度分析
-
1.EXPSPACE成员资格：对于允许随机性策略的NatPATL，其模型检验问题属于EXPSPACE复杂度类。
-
2.3EXPSPACE成员资格：在随机性策略情况下，对于更为复杂的NatPATL*逻辑，其模型检验问题属于3EXPSPACE复杂度类。
-
3.指数空间爆炸：随机性策略引入的概率导致了真实算术的使用，从而引发了指数空间的膨胀，这意味着任何改进可能需要全新的技术手段。
-
4.双重指数膨胀：PATL和PATL*之间的复杂度差异源于MDPs上LTL模型检验的2EXPTIME-完全性。
2 结语
文章探讨了在随机多智能体系统中应用自然策略进行PATL和PATL*逻辑模型检测的复杂性，并分析了其在不同条件下的计算难度。
论文题目： Natural Strategic Ability in Stochastic Multi-Agent Systems
论文链接： https://arxiv.org/abs/2401.12170
PS: 欢迎大家扫码关注公众号_，我们一起在AI的世界中探索前行，期待共同进步！
