Using a normative organisational model to specify and manage an institution for multi-agent systems Benjamin Gâteau a a CITI/CRP Henri Tudor – G.-D. of Luxembourg benjamin.gateau@tudor.lu Abstract Nowadays multi-agent applications are more and more openness. That brings the risk to deal with to autonomous agents i.e. agents not respecting the society rules. To insure a coherent behaviour the application require tools to control and regulate the system overall functioning. Moreover they should provide the system with mechanisms to enforce global laws on the autonomous agents operating in it. This paper presents an institution multi-agent layer called S YNAI. Implemented with different agents, the institution functioning is itself specified as a normative organisation model making explicit how the overall system should be controlled. Using an iTV game application, we illustrate how such a specification is useful to help the agents to function in the system. 1 Introduction Nowadays, multi-agent technologies’ applications are faced to an increasing openness. Being composed of heterogeneous and autonomous agents, they require tools to control and regulate the system overall function- ing. Moreover they should provide the system with mechanisms to enforce global laws on the autonomous agents operating in the system. In this paper we present S YNAI, a multi-agent layer dedicated to the rights and duties management and enforcement of autonomous agents within an organisation. This layer belongs to the electronic insti- tution environment called M ABELI 1 . It is composed of generic institutional agents, supervisors, aiming at controlling and enforcing the domain agents functioning according to the specified normative organisation expressed with the normative organisation model called MOISEInst . Whereas supervisor agents are ded- icated to the system control, the domain agents implement the application functionalities. The supervisor agents themselves operate under the control of a normative organisation that structures and constrains their control behaviour on the domain agents. All along the paper, we illustrate the use of M ABELI with an iTV game issued from the European ITEA Jules Verne Project. We show how this multimedia game can be modelised and controlled with such a plat- form. This paper is organised as follows: section 2 presents an motivations overview for using an explicit normative organisational model to specify S YNAI, the multi-agent institution platform with MOISEInst , normative organisation model. Its use is illustrated with the iTV application. The succeeding sections present the other main component of the Electronic Institution namely S YNAI, the arbitration system. We describe the institutional agents organisation and how the supervisors arbitrate an organisation by respect- ing their own organisation specification Finally, before concluding, section 5 compares our work to other approaches. 1 Multi-Agent Based ELectronic Institution 2 Motivations In the recent past, multi-agent technologies have been developed and deployed in different applications. Most of these efforts have been largely supported by the existence of multi-agent platforms like JADE [1] or FIPA-OS [12]. These platforms have demonstrated the generic services needs and utility for supporting the execution of multi-agent applications such as Agent Management System, Directory Facilitator. The recent developments in the domain (e.g. electronic commerce [2]) have shown the requirement to enrich those services to provide multi-agent applications with institution platforms. The main purpose was to in- sure and promote the user’s trust in the system functioning by controlling agents during their transactions. In human societies institutions define the game rules [11]. These rules enclose all kinds of informal or formal constraints that human beings use to interact. Current multi-agent approaches to institution propose these rules modelling through normative systems [10] that are interpreted by agents that enforce the application’s agents to follow them and not to violate them. Game Player Application GEOGRAPHY In what European city would you find the famous Tivoli Gardens? (1) Oslo (3) Copenhagen (2) Amsterdam (4) Stockholm User Interface Normative Organisation (MoiseInst) Game SS NS CS FS Institution (Synai) Avatar Institution wrapper Multi-agent platform Institution agent Figure 1: Global view of the e-Institution for iTV In the same trend, the work described in this paper is applied to an Interactive Games application (see Fig. 1): a “questions – answers” TV game show opposing a real players’ team present on the TV scene, to a televiewers’ team interacting from home into the game with the help of the Avatars, i.e. software agents. Each Avatar is under its respective televiewer control. The quizmaster is also supported by a virtual assis- tant. His role is to regulate the game. As in all collective games, the aim is to promote a collective behaviour among the the same team’s players. An explicit organisation states the roles involved in the game. A set of rules (norms) represents the game rules, the sanctions and rewards in use during the game. However, since avatars are autonomous agents, they can be autonomous with respect to these constraints, e.g. a televiewer is able to decide to answer whereas it is not his turn and to take the risk to be punished. An institution has been thus defined in order to control, regulate and reward or punish agents when they respect or not the key Player Role Abstract Role GameMaster 1..1 inheritance BasicPlayer Chief Group composition 1..1 Links intra-group inter-group History Geo Science Sport OrgCandidate acquaintance 1..1 1..1 1..1 1..1 * authority 4..4 communication 1..1 Team Game compatibility Figure 2: Avatars scenario Structural Specification organisation and norms. Two kinds of agents have been designed: domain agents, avatars controlled by the users, and supervi- sor agents aiming at managing the organisation and enforcing the game rules on the domain agents. They are organised into two layers: (i) the multiagent interactive game in which domain agents as avatars, op- erate on behalf of their user, (ii) S YNAI2 an institution multiagent platform dedicated to the organisation management and to its control by the mean of the supervisor agents. Both kinds of agents (supervisor and domain) are organised and constrained according to a normative organisation described with the MOISEInst normative organisation description language [5]. Agents are thus able to reason on the organisation and con- straints. They have the possibility to decide to take it into account or not. The institution platform reads this specification in order to supervise and control the agents as well as be informed about its own organisation specification. Before focusing on the presentation of the S YNAI specification, we shortly describe MOISEInst . 3 Normative organisation description language MOISEInst [5, 6] is used to define what we call an organisation specification (OS) with the help of four specifications3 : structural specification (SS), functional specification (FS), contextual specification (CS) and normative specification (NS). 3.1 Structural specification The structural specification (SS) expresses a set of roles, groups and links that build the organisation struc- ture (cf. Figure 2). For instance, a “Team” group is composed of the following roles: “History”, “Geo”, “Sport”, “Science” and “Chief”. These roles inherit from “BasicPlayer” or “Player” roles that are abstract, i.e. roles which are not adoptable by agents. Cardinality and compatibility links express constraints on the way agents play roles in groups. For instance, cardinality ‘1..1’ on the composition link ensures constraints that, in a “Team” group instance, roles can be adopted by only one agent at the same time. A compatibility link between “BasicPlayer” and “Chief”, allows the same agent to play those two roles or those roles spe- cializations. Thus, according to this specification, one agent may have the possibility to play at most two of those five roles. In order to avoid that five agents play the five “Team” roles, we express a cardinality ‘4..4’ for the group “Team”, stating that any well formed instance of this group may contain four and only four agents. 2 SYstem of Normative Agents for Institution. 3 A BNF definition of SS and FS are available in [7] and of CS and NS in [5] OrgEnter Scheme Functional Scheme Emotion Scheme key g1: Team joined g1m1 g2m2 g8m13 g2: Game played goalmissions g2a: All questions handled sequence OrgExit Scheme g2b: Question handled g2am2 g4: Topic handled g3m3 g81m14 g82m15 g5: Answer evaluated g3: Team quit Question Scheme Score Scheme Sanction Scheme choice parallelism g2bm4 g7m11 g6m9 g41: "History" topic handled g411: "History" question asked g6: Sanction applied g412: "History" question answered g61: Player ejected m12 m12 g42: "Geo" topic handled g71 g72 g62: Team disqualified g421: "Geo" question asked g4m4 g5m4 Score g61m10 g62m10 Score g7: Score changed g422: "Geo" question answered Scheme Scheme g71: Score increased g72: Score decreased g8: Emotion shown g43: "Sport" topic handled g81: Be happy g431: "Sport" question asked g82: Be sad g41m4 g42m4 g43m4 g44m4 g432: "Sport" question answered g44: "Science" topic handled g441: "Science" question asked g442: "Science" question answered g411m4g412m5,m16 g421m4g422m6,m16 g431m4g432 m7,m16 g441m4 g442 m8,m16 Figure 3: Avatars scenario Functional Specification Communication and authority links structure the different roles. For instance, all roles inheriting from “Player” can communicate between them, and the “Chief” has the authority on all “BasicPlayer”, which means that all roles inheriting from this role are under the “Chief” authority . “OrgCandidate” is the first role played by every agents coming in the organisation that is why it could be played by a lot of agents at the same time. “OrgCandidate” does not participate in the game (activity to answer question). According to available roles adoptable in the “Team”, agents could change to join the group. “GameMaster” is the role played by the only one presenter assistant. 3.2 Functional specification The functional specification (FS) specifies the global expected system functioning in terms of goals/subgoals that agents operating in it should achieve (cf. Figure 3). The goal decomposition trees are organised into dif- ferent social schemes which may be reused within other social schemes. For instance the Question Scheme has “question handled” as root goal and its plan is a sequential achievement of goals “g4”, “g5” and of “Score Scheme”. The “OrgEnter Scheme” (resp. “OrgExit Scheme”) defines the principal behaviours for entering (resp. leaving) an organisation. We also define a scheme relating to the customization of the sanc- tions by specifying that apply a sanction is a choice between the ejection of a player, the disqualification of the team or the modification of the score. At last, we can also define scheme relating to Avatars 3D rendering with goals to show a happy or sad face for instance making possible the norms definition relating to that. 3.3 Contextual specification To tackle with the applications situatedness in evolving environment, a contextual specification (CS) cap- tures design-time constraints on the organisation evolution as a set of contexts and transitions between them (cf. Figure 4). A context expresses a state in which an agent playing a role has to respect specific rules (see below the norms expression). Transitions define change from one context to another context given different events occurrence. For instance, in our application, it is used to express the different game rounds that impose change to the rules. Here the CS starts with a synchronous state “Begin” which allows the televiewer to connect to the system. A macro-context “Game” is decomposed into three rounds sub-contexts. This global context will be used to define the basic game rules while the three round sub-contexts will be used to define the corresponding specific rules. The “Game” context is also decomposed into two sub-contexts defining the players turn. A round sub-context and a turn sub-context can be active at the same time. Let us notice that the macro-context is active in all its sub-contexts. The rules defined in the “Game” context are thus inherited in sub-contexts and are still valid. Finally the last state is the context in which Avatars quit their team. chgRd chgRd endG key Round1 Round2 Round3 Begin initial context avT hmT beginG final context chgT MyTurn NotMyTurn context Context endG chgT End Event Game endG endG transition Figure 4: Avatars scenario Contextual Specification 3.4 Normative specification Finally, the normative specification (NS) glues all specifications in a coherent and normative organisation. It expresses permissions, obligations and prohibitions of missions referring to the goals of the FS in the context of elements of the SS (roles or groups). Missions group goals into coherent sets according to the way the designer wants to assign them to roles or groups for their achievement. A norm in NS (cf. Figure 5) is specified with an id, a context, a bearer, a deontic operator referring to a mission and a deadline. Figure 5: Avatars scenario Normative Specification The Avatars scenario NS displayed on the Fig. 5 uses functions defined in the MOISEInst meta-model. The N1 validation condition (nb(T eam) < max(T eam)) is composed of two functions representing the agent number already in the Team group and the maximum of agents allowed in the Team. This norm expresses the fact that the Team must not be full in order to allow an agent entry. Concerning the norms N17 and N18, the function violated() return true if the norm in parameter is not respected. The detection is done by S YNAI agents. We explain how in section 4. This specification can define norms as well as their sanction. A sanction is a norm with a violation condition. The norms issuer is the role which supervises the norm respect. Users who specify their own application modelling do not know how the arbitration works. That is why they have to set the issuer up to “Supervisor” role. The S YNAI layer decides automatically what agents supervise what norms. Our model does not provide solution to check if the norms are coherent ones compared to the others. In our example, potential conflicts can occur between norms N15 and N09 because they oblige agents playing role in the “Team” group to accomplish and to not accomplish the mission m16. We have the same between norms N15 and N14, N8 and N9, and N8 and N14. To avoid agents having to make a choice between con- flictual norms to respect, we specify a priority order denoted by a w. in the table. 1 is the higher priority. To abrogate conflictual norms we decrease N9 and N14 priority order. The norms allow us to define and constrain the game functioning as well as what happens at the beginning and at the end of the game. The four first norms in Fig. 5 define when it is possible to join and to leave the team. Global game rules are expressed as functioning norms. For instance Prohibition for “Player” role to answer a question during the game represented by N08 authorizes concerned roles during rounds to answer questions. N09 and N14 oblige the “Player” and the “Chief” roles to answer all questions during the first and third rounds. Four norms for each role in the second round allow concerned roles to answer question. 4 S YNAI Institution platform normative organisation 4.1 Requirements Domain agents play the game by acting in an Organisation specified by the designer in the OS described in the previous section. As depicted on the left of Fig. 6, an Organisation is an Organisation Specification instantiation which means that agents adopt roles and commit on mission according to the OS. This speci- fication aims at constraining their behaviour. However being autonomous (under an user control) they can decide to not respect the specification stated in the OS. An agent can adopt a role in the Organisation which is not authorize in the OS. If the Organisation is not consistent with the OS, the Organisation is considered as incoherent. calls method Instantiation Instantiation Organisation Inst Manager Ag sends msgs ContextA Group ContextB SS CS ContextC Structure calls method Struct Org Active Contexts Manager Agent1 context id w. Game N03 1 condition null issuer bearer Team deOp mission Begin N01 1 nb(Team)