Research On Multiagent Coalitional Normative Systems

Social law is an effective tool for coordinating multiagent systems, and it is also a necessary complement for the model checking technique. Generally speaking, a social law consists of an objective and a normative system—use the objective for describing the desired properties for the mutiagent system, and use the normative system for modifying the internal structure of the multiagent system in order to fulfill the objective. The aim of this dissertation is to improve the normative system in social laws, by replacing the normative systems with coalitional normative systems which have stronger normative power, enable social laws to model more complex coordinating problems. Different from the normative systems which have adopted in social laws, coalitional normative systems are not behavioral constraints imposed upon individual agents, but are constraints for the joint actions of the coalition under control. Based on this idea, we propose 2 types of coalitional normative systems, such as (basic) coalitional normative systems (CNS) and CNSs which extend the state space (CNS*). CNS* can not only make the behavioral constraints be set on coalitions, but also remember the state transition histories. Actually, this has extended the state space of the system, so we can set different behavioral constraints at the same system state according to different execution contexts, so as to improve the agility of social laws.We still use ATL language for describing objectives. But we found that in the structure obtained from a concurrent game structure (which is the semantic structure of ATL) by implementing a CNS we have to refine the interpretations for the ATL formulas. We call the resulting new logic Coordinated ATL (Co-ATL). Compared with ATL, Co-ATL has the same syntax but assume different semantic interpretations. We establish that the Co-ATL model checking problem is still a P-complete problem (just like the ATL model checking problem). In order to characterize the limitation of the normative power of CNSs, we identify two fragments of the Co-ATL language such as LC+ and LC-, corresponds to the class of strategic abilities that cannot be established and the class of strategic abilities that cannot be avoided respectively,and by which we can soundly and completely characterize the limitation of the normative power for CNS. We discuss 3 basic computational problems with respect to CNSs, such as the effectiveness checking problem, feasibility checking problem, and synthesis problem, and show that they are P-complete, NP-complete, and FNP-complete, respectively. Moreover, we define three concepts of optimality for CNS, that is, minimality, compactness, and maximum utility, and discuss the related computational complexity. With respect to CNS*, we prove that although the normative power of CNS* is strictly stronger than CNS, its limitation of normative power can also be soundly and completely characterized by LC+ and LC-, and the 3 basic computational problems are of the same complexity with that of CNS. Finally, we define a CNS synthesis algorithm based on Co-ATL model checking, and discuss some formal properties of this algorithm such as time complexity, correctness and completeness.