Multiagent Compromises, Joint Fixpoints, and Stable Models
Multiagent Compromises, Joint Fixpoints, and Stable Models
复制标题
多智能体妥协、联合固定点和稳定模型
DOI：
10.1007/3-540-45628-7_21
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
G. Gottlob
中科院分区：
文献类型：
--
作者：
F. Buccafurri;G. Gottlob
我们假设代理的需求或愿望由逻辑程序建模。在多智能体设置中，反映各种需求的妥协的智能体的联合决策对应于相应逻辑程序的合适的联合模型。本文提出了一种适用于折衷模型选择的语义：联合不动点语义。目标关节模型被定义为代理程序的(最小)关节固定点。我们研究了这种新语义的计算性质，表明确定两个(或多个)逻辑程序是否有联合不动点是NP完全的。即使对于完全肯定的逻辑程序，这一点也是正确的。我们还研究了联合不动点语义下怀疑推理和轻信推理的复杂性。前者被证明是co-NP完成的，而后者是Σ2P完成的。我们展示了如何将逻辑程序集的联合不动点计算为稳定集。
We assume the requirements or desires of an agent are modeled by a logic program. In a multi-agent setting, a joint decision of the agents, reflecting a compromise of the various requirements, corresponds to a suitable joint model of the respective logic programs. In this paper, an appropriate semantics for selecting joint models representing compromises is proposed:the joint fixpoint semantics. The intended joint models are defined to be the (minimal) joint fixpoints of the agent programs. We study computational properties of this new semantics showing that determining whether two (or more) logic programs have a joint fixpoint is NP complete. This remains true even for entirely positive logic programs. We also study the complexity of skeptical and credulous reasoning under the joint fixpoint semantics. The former is proven to be co-NP complete, while the latter isΣ2Pcomplete. We show how the joint fixpoints of a set of logic programs can be computed as stable sets.