-This paper puts forward a normative framework for computational societies which enables the handling of incomplete knowledge about normative relations. In particular, attempts to perform a social action are evaluated as permitted, prohibited (i.e. not permitted) or pending for execution (i.e. neither permitted nor prohibited). This latter category of attempts can eventually be resolved as permitted or prohibited attempts using the speech acts allow and forbid. We make use of the support for incompleteness of action language K in the formalisation of the framework. The proposal will be illustrated with some scenarios drawn from the management of university courses.
Empowerments and permissions are two common normative
devices in the design of computational societies [
This paper challenges this last assumption for the case of permissions. In particular, it considers those situations in which the designers of the computational society do not have enough knowledge so as to generate a complete set of permission rules for certain classes of actions. For instance, let us consider a computational society designed to support the management of university courses. As part of the resulting specification, empowerment and permission rules are defined which partially regulate the social processes of the application domain, namely assignments, examinations, tutoring, lecturing, and so forth. In particular, the following norms concerning the creation of assignment groups will be considered. Firstly, empowerment to set up a working group for some assignment is granted to any student of the course who has not yet passed that assignment. The attempt of setting up an assignment group will be permitted if, and only if, the assignment has been published, the specified submission deadline has not yet passed and the student is not participating in any other working group for that assignment. Alternatively, instead of setting up her own working group, a student may join a working group set up by another colleague in order to collaborate with him. Empowerment conditions for joining assignment groups coincide with those identified for the setting up of new groups. Some of the permission conditions for setting up working groups are also relevant, although only as necessary conditions. In particular, if some student attempts to join some working group and the corresponding submission deadline passed or she is already participating in another working group, then the attempt will be prohibited (i.e. not permitted). If none of these conditions hold, then there are no grounds for prohibiting the attempt. However, this does not mean that there are grounds for permitting the execution of the social action, since the ultimate decision on the permission or prohibition of the attempt lies with the initiator of the group (i.e. the student who set up the group). Thus, sufficient conditions for permitting or prohibiting the joining action can not be specified in advance by the designer of the society. In these scenarios, it would be very convenient to give the initiator of the group the possibility of either allowing or forbidding the corresponding social action so that the attempt is eventually permitted or prohibited.
This paper puts forward a formal model of permission which
enables the representation of incomplete information about
the normative status of social action attempts, such as the
one commented above. Moreover, it formalises the meaning
of the speech acts allow and forbid in the context of the
previous model. In order to proceed with this formalization,
we build on the notions of empowerment and permissions
reported in [
The rest of the paper is structured as follows. Firstly, the most salient features of action language K for the purpose of this paper will be reviewed. Then, the general framework for social action processing will be introduced, describing the major features of the action description in language K. Next, the speech acts of allowing and forbidding will be formalised. Last, the major differences with previous work will be discussed and current work briefly described.
Action languages are formal techniques for representing
and reasoning about the performance of actions in dynamic
domains. The semantics of action languages is given in terms
of transition systems, namely graphs whose states and arcs
represent, respectively, the possible configurations of the
domain and its evolution due to the concurrent execution of a set
of actions. Commonly, action languages such as C+ describe
transitions between states of the physical world, i.e. states
which represent complete configurations of the domain, where
each fluent is necessarily either true or false. In contrast, action
language K [
An action description in language K is composed of a set of fluent and action declarations, a set of causation rules and a set of executability conditions:
A fluent or action p is declared using an expression of the form:
p(X1,: : :,Xn) requires t1,: : :,tn where Xi are variables and ti are positive literals (i.e., true atoms) which specify the types of the corresponding variables1.
Causation rules are expressions of the form:
caused f if B after A If the subexpression f is a fluent literal, the causation rule expresses that f is known to be true in the current state if B holds in the current state and A also holds in the preceding state. The subexpressions B and A are actually sequences of literals, possibly prefixed with the default (or weak) negation operator not. The expression not f holds if f is not known to be true, whereas the expression not f holds if f is not known to be false. If both expressions hold then the truth value of f is unknown.
The subexpression B can only refer to type or fluent predicates, whereas A can also refer to action predicates. If sequences B and A are empty, the corresponding if and after parts can be dropped from the expression. If the after part is empty the rule is called static, otherwise the causation rule is dynamic. Moreover, if f is the atom false , the causation rule represents an static (resp. dynamic) integrity constraint which allows us to filter out from the transition system ill-formed states (resp. transitions). Dynamic rules can be used to represent the non-executability conditions and effects of actions. In particular, the following macro rule is a shorthand of a dynamic constraint to represent that condition B blocks the execution of action a [10, sec. 2]: nonexecutable a if B Executability statements are primitive (i.e. not macro) expressions of the form
executable a if B This kind of declaration expresses that action a is eligible for execution in any state of knowledge in which B holds. If we want the execution of action a to be not only possible but also mandatory, then a dynamic constraint can be declared. Since this a common requirement, this paper introduces the following macro rule which allows us to declare B as a sufficient condition for executing a: executable a if B executed a if B , caused false after not a, B
Departing from its original motivation, action language K will be used in this paper for describing transitions between states of institutional worlds, rather than states of knowledge of some planning agent. In particular, the technical apparatus of language K will be exploited to represent institutional states where some normative fluents (e.g., permissions) may have an inherent, non-epistemic indeterminacy. In software engineering terms, the dynamic domain to be modeled is thus the social middleware infrastructure in charge of the management of the institutional state of the computational society, rather than the software components participating as agents in the society. The corresponding action description is partitioned in several sub-specifications corresponding to the different types of social entities of the computational society, namely social interactions, agents and social actions. A complete account of this specification, however, is beyond the scope of this paper2. Instead, the focus here will be on the major features concerning the processing of social actions.
The institutional state of computational societies is hierarchically structured in terms of a tree of social interactions. The root of this tree, or top-level interaction, represents the social context within which the whole agent activity takes place; the other sub-interactions represent the social contexts for particular joint activities (i.e. social processes). For instance, assignment groups are represented by social interactions which are sub-interactions of courses, another type of social interaction. Social interactions may be initiated within the context of some other interaction, and eventually finished by the social middleware. The conditions which cause the execution of these actions are, in general, dependent on the type of interaction.
Thus, university courses are automatically initiated when the new academic year begins, and assignment groups are initiated when some student successfully declares its initiation through the performance of the set up social action – in accordance with the empowerment and permission rules of the society. In this latter case, the initiator of the social interaction can be defined as the performer of the set up action.
2But see the C+ version [
i n t e r a c t i o n ( I ) , i n t e r a c t i o n s t a t e ( S ) . 3 c o n t e x t i ( I1 , I 2 ) requires 4
i n t e r a c t i o n ( I 1 ) , i n t e r a c t i o n ( I 2 ) . 5 i n i t i a t o r ( I , A) requires 6
i n t e r a c t i o n ( I ) , a g e n t (A ) . 7 . . . 8 actions : 9 i n i t i a t e ( I1 , I 2 ) requires 10
i n t e r a c t i o n ( I 1 ) , i n t e r a c t i o n ( I 2 ) . 11 . . . 12 always : 13 nonexecutable i n i t i a t e ( I1 , I 2 ) if 14
s t a t e i ( I1 , open ) . 15 caused s t a t e i ( I1 , open ) after 16
i n i t i a t e ( I1 , I 2 ) . 17 caused c o n t e x t i ( I1 , I 2 ) after 18
i n i t i a t e ( I1 , I 2 ) . 19 . . . 20
Listing 1. K-specification of social interactions
Listing 1 shows some relevant features of the specification in language K of social interactions. In particular, it shows the declaration of fluents state i , context i and initiator , which represent, respectively, the run-time state of social interactions (either open or closed, values of the interaction state predicate defined elsewhere), its interaction context and the possible initiator. Also shown is the declaration of the initiate action together with its non-executability conditions and effects (lines 14–19). These rules are declared within the scope of the always section, since they apply to every possible institutional state.
Agents are software components which interact through the social middleware as members of a given social interaction context, with the purpose of achieving some goal. In order to do so, they are empowered to perform social actions such as setting up new interactions, joining existing interactions, and so forth. For instance, the purpose of students is to pass the course to which they belong as members. In order to achieve this goal, students are empowered to set up working groups or to join existing ones in order to carry out some mandatory assignment. In case that the purpose of agents is too complex, its whole activity may be arranged in terms of a role-playing hierarchy of further agents. Thus, the activity of students within the context of working groups is represented by a new kind of agent role played by the course student. Agent roles are played and abandoned by the social middleware according to certain conditions. For instance, a course student role is automatically abandoned as soon as the agent passes the subject; a working group student is automatically created for the initiator of the working group, and for any student who successfully manage to join a pre-exiting working group.
Listing 2 partially shows the K-specification of the agent fluents : s t a t e a (A, S ) requires
a g e n t (A) , a g e n t s t a t e ( S ) . c o n t e x t a (A, I ) requires
a g e n t (A) , i n t e r a c t i o n ( I ) . p l a y e r ( A1 , A2 ) requires a g e n t ( A1 ) , a g e n t ( A2 ) 1 2 3 4 5 6 7 . . . 8 actions : 9 p l a y (A, I ) requires 10 i n t e r a c t i o n ( I ) , a g e n t (A ) . 11 p l a y f o r ( A1 , A2 , I ) requires 12 a g e n t ( A1 ) , a g e n t ( A2 ) , i n t e r a c t i o n ( I ) . 13 . . . 14 always : 15 nonexecutable p l a y (A, I ) if 16 s t a t e a (A, p l a y i n g ) . 17 caused s t a t e a (A, p l a y i n g ) after 18 p l a y (A, I ) . 19 caused c o n t e x t a (A, I ) after 20 p l a y (A, I ) . 21 executed p l a y ( A1 , I ) if 22 p l a y f o r ( A1 , A2 , I ) . 23 caused p l a y e r ( A1 , A2 ) after 24 p l a y f o r ( A1 , A2 , I ) . 25 . . . 26
Listing 2. K-specification of agents type, which includes the declaration of general fluents and actions shared by any kind of agent. Particularly, it shows the declaration of the fluents state a , context a and player , which represent the run-time state of agents (playing or abandoned), the social interaction context to which the agent belongs and its player agent, respectively. Also, it shows the declaration of the actions play and play for . The former one causes some agent to be created within some social interaction context. The general specification only includes its non-executability condition and effect (lines 16–21). The action play for causes some agent to be played (line 22) for a particular player agent (line 24).
The activity of agent components within a multiagent society manifest itself through the performance of attempts. This external action allows an agent component to perform a given social action, namely to say something, manipulate the environment or observe the current state of some social entity. Due to lack of space, this paper will refer only to speech acts and, particularly, to declarations such as set up and join. Nevertheless, the processing of attempts by the social middleware is independent of the kind of social action. This process takes into account the empowerments and permission rules of the society. In particular, empowerments shall represent the institutional capabilities of agents, i.e. which social actions a given agent is capable of performing; permissions shall denote the circumstances under which these institutional capabilities can be exercised. Attempts by agent components are processed according to the following procedure: If the agent is empowered to perform the specified social action, then the attempt will be taken into account; otherwise, i.e. either if it is known for certain that the agent is not empowered, or it can not be concluded that it is empowered, the external action will be dismissed. In this latter case, the institutional state of the multiagent society will not be altered at all.
If the agent is empowered to perform the action, but it is known that the specified performer is not permitted to perform it (i.e. it is prohibited), then the process is finished with a prohibited attempt status. On the contrary, if the agent is both empowered and permitted, then the social action is performed by the middleware. The effects caused through this execution depend on the kind of social action being performed.
If the agent is empowered to perform that action, but it is neither known that the action is permitted nor prohibited, then the social action is kept in a pending state. This state will be eventually resolved into a performed or prohibited state as soon as it is known whether the action is permitted or prohibited.
This procedure is formalised as part of the social action type specification, whose major features are shown in listing 3. The signature of this specification includes the action declaration attempt (Act,A), which represents the attempt made by some agent component A to perform the social action Act. This action is exogenous, i.e. its cause is to be found outside the system being modeled; correspondingly, it is unconditionally declared as executable (cf. line 20).
The different scenarios described above concerning the processing of attempts are modeled through different groups of static and dynamic rules. Firstly, if the intended agent is empowered to perform the social action then it will be declared as its performer (line 22), irrespective of the permission status. Empowerments, permissions and the performers of social actions, are represented by the fluents empowered, permitted and performer, respectively. If the agent attempting to perform the social action is empowered then the social action will be brought about in the next state to one of three execution states (represented by the fluent state sa ): pending, prohibited or performed (the possible values of the type predicate social action state ).
Firstly, if it is known that the action is not permitted (i.e. permitted(Act,A)) then the resulting state will be prohibited (line 24).
Secondly, if it is permitted then the action will be performed (line 27). Execution of actions is represented by the action perform, whose only effect at this level of abstraction is the change in the run-time execution state (line 39).
Last, if the social action is neither known to be permitted nor prohibited, then the social action is kept in a pending execution state in the resulting system state (line 30). Eventually, the circumstances may change in such a way that the social action is known to be permitted fluents : 1 s t a t e s a ( Act , S ) requires 2 s o c i a l a c t i o n ( Act ) , 3 s o c i a l a c t i o n s t a t e ( S ) . 4 c o n t e x t s a ( Act , I ) requires 5 s o c i a l a c t i o n ( Act ) , i n t e r a c t i o n ( I ) . 6 p e r f o r m e r ( Act , A) requires 7 s o c i a l a c t i o n ( Act ) , a g e n t (A ) . 8 empowered ( Act , A) requires 9 s o c i a l a c t i o n ( Act ) , a g e n t (A ) . 10 p e r m i t t e d ( Act ) 11 requires s o c i a l a c t i o n ( Act ) . 12 . . . 13 actions : 14 a t t e m p t ( Act , A) requires 15 s o c i a l a c t i o n ( Act ) , a g e n t (A ) . 16 p e r f o r m ( Act ) requires 17 s o c i a l a c t i o n ( Act ) . 18 always : 19 executable a t t e m p t ( Act , A ) . 20 . . . 21 caused p e r f o r m e r ( Act , A) after 22 a t t e m p t ( Act , A) , empowered ( Act , A ) . 23 caused s t a t e s a ( Act , p r o h i b i t e d ) after 24 a t t e m p t ( Act , A) , empowered ( Act , A) , 25 p e r m i t t e d ( Act ) . 26 executed p e r f o r m ( Act ) if 27 a t t e m p t ( Act , A) , empowered ( Act , A) , 28 p e r m i t t e d ( Act ) . 29 caused s t a t e s a ( Act , p e n d i n g ) after 30 a t t e m p t ( Act , A) , empowered ( Act , A) , 31 n o t p e r m i t t e d ( Act ) , n o t p e r m i t t e d ( Act ) . 32 . . . 33 caused s t a t e s a ( Act , p r o h i b i t e d ) after 34 s t a t e s a ( Act , p e n d i n g ) , p e r m i t t e d ( Act ) . 35 executed p e r f o r m ( Act ) if 36 s t a t e s a ( Act , p e n d i n g ) , p e r m i t t e d ( Act ) . 37 . . . 38 caused s t a t e s a ( Act , p e r f o r m e d ) after 39 p e r f o r m ( Act ) . 40
Listing 3. K-specification of social actions or prohibited. In those cases, the social action will be resolved to the execution or the prohibition states by the corresponding rules (lines 34–37). Otherwise, the social action will persist until the performer agent is abandoned (i.e. its run-time state is changed to abandoned) or the interaction context is closed.
IV. FORBIDDING AND ALLOWING SOCIAL ACTIONS Those social actions pending for execution will be resolved as prohibited or permitted attempts as soon as the rules of the society enables a definite conclusion on its permission status. As a complementary mechanism, particularly useful in the absence of general rules, run-time agents may also change the permission status through the speech acts allow and forbid3.
3Of course, since allow and forbid are speech acts, their performance is also governed by the corresponding empowerment and permission rules. For instance, initiators of assignment groups are unconditionally empowered and permitted to allow other students to join their groups. In other application domains, however, it may happen, for instance, that some agent is required to allow other agent to allow some other agent to do something. fluents : n e w r o l e ( J o i n , A) requires j o i n ( J o i n ) , a g e n t (A ) . 1 2 3 . . . 4 always : 5 executed p l a y f o r ( A1 , A2 , I ) if 6 j o i n ( J o i n ) , p e r f o r m ( J o i n ) , 7 c o n t e x t s a ( J o i n , I ) , 8 p e r f o r m e r ( J o i n , A2 ) , n e w r o l e ( J o i n , A1 ) . 9 . . . 10
Listing 4. K-specification of the join social action This section provides a formal account of the meaning of these speech acts and illustrates the formalisation of the assignment group scenario with the execution of a planning query. To account for a complete example, besides the allow and forbid speech acts, the join declaration will also be formalised.
The specification of a new type of social action t1 proceeds, firstly, by declaring a rule social_action(x) :t_1(x). This rule establishes that any entity of the new type shall be regarded as a social action, so that the rules which define the general structure and dynamics of social actions (cf. listing 3) are applicable for entities of that type. Secondly, new fluents representing the additional arguments of the new social action type must be declared. Last, new rules for representing the post-conditions of the performance of the new type of action, as well as their additional non-executability conditions, etc., have to be declared as well.
For instance, listing 4 shows the formalisation of the join declaration. By performing this speech act, the speaker declares that a new role is played within some interaction by it. The interaction and the speaker are represented by generic fluents of social actions, namely context sa and performer. The new role to be played is declared as a new fluent, new role, pertaining to this kind of speech act. The rest of the specification includes the particular effects associated to the execution of this kind of declaration, which are indirectly achieved through the internal action play for (cf. listing 3).
Figure 5 shows the partial specification of the allow speech act. In this case, the generic social action specification is extended with the new fluent action a , which represents the social action targeted by the allow speech act. The specification includes a condition which establishes that the social action to be allowed must be pending for execution (line 6). The effect of performing the allow action is to explicitly cause that the social action is permitted (9). The specification of the forbid speech act is similar to the one shown in listing 5. The only major difference pertains to its post-condition, which in this case resorts to the strong negation operator, i.e. caused p e r m i t t e d ( Act ) after f o r b i d ( F o r b i d ) , p e r f o r m ( F o r b i d ) , a c t i o n f ( F o r b i d , Act ) fluents : a c t i o n ( Allow , Act ) requires
a l l o w ( Allow ) , s o c i a l a c t i o n ( Act ) .
. . . always : nonexecutable a t t e m p t ( Allow , A) if a l l o w ( Allow ) , a c t i o n ( Allow , Act ) , n o t s t a t e s a ( Act , p e n d i n g ) . caused p e r m i t t e d ( Act ) after a l l o w ( Allow ) , p e r f o r m ( Allow ) , a c t i o n ( Allow , Act ) .
This section illustrates the semantics of the previous speech
acts through a simplified implementation of the working group
scenario. This implementation, shown in listing 6, features a
consistent situation where the top-level interaction represents
the university course to which two student agents, s1 and s2,
belong as members. The university course has a single working
group wg1, previously set up by student s1. The activity of this
student within the working group is represented by the role
s11. The query posed to the DLVk planner (an implementation
of action language K as a front end to the DLV answer set
programming framework [
The output of the DLVk planner is shown below. As expected, the first action that needs to be performed is an attempt by agent s2 to join the working group. Two additional objects have to be declared in the scenario in order for this action to be performed: a join social action, join1, and the agent to be played within the working group, s21. These objects initially belong to the pool of objects which are available for the planning process4. Since the student is empowered to perform the join action but no permission rules are declared, the attempt to perform it results in a pending status. The next state features an attempt by agent s11 to allow the performance of the join action, namely to perform action allow1. Since this 4Formally, these are objects which have no state, e.g. agents which are being neither played nor have been abandoned. agent is both empowered and permitted to perform that social action, the permissions to execute the join1 action are in effect in the next state. This, in turn, causes the performance of the join action and the consequent playing of the student agent within the working group.
STATE 0: state_a(s2,playing) state_i(wg1,open)
empowered(s2,join1) new_role(join1,s21) ...
ACTIONS: attempt(join1,s2) STATE 1: state_sa(join1,pending) performer(join1,s2) empowered(s11,allow1) permitted(allow1) action_a(allow1,join1) ...
ACTIONS: attempt(allow1,s11) perform(allow1) STATE 2: state_sa(allow1,performed) state_sa(join1,pending) performer(join1,a1) permitted(join1) ...
ACTIONS: perform(join1) play_for(s21,s2,wg1) play(s21,wg1) STATE 3: state_a(s21,playing) player(s21,s2) context_a(s21,wg1) ...
The model of empowerment and permission put forward
in this paper contrasts with other approaches based on ASP
[
Secondly, the strong negation operator allows the designer to explicitly declare prohibition rules, whereas other approaches have to resort to the default “everything which is not permitted, is prohibited”, which may not always be adequate. In particular, explicit prohibitions are very convenient in order to represent necessary conditions of permission rules. For instance, the following rule states that a necessary condition to join some working group is that the deadline for submitting the corresponding assignment has not passed yet: caused p e r m i t t e d ( J o i n ) if c o n t e x t s a ( J o i n ,W) , w o r k i n g g r o u p (W) , a s s i g n m e n t (W, A) , d e a d l i n e (W, D) , c u r r e n t t i m e ( T ) , D<T .
The assignment group scenario also served to illustrate a situation where empowerments and permission rules concerning a single type of social action are, respectively, complete and incomplete. This represents a good case in favour of the distinction between empowerments and permissions, which some approaches neglect (dispensing with one of the two notions).
Lastly, two normative social actions, allow and forbid, are
smoothly introduced within the normative framework in order
to handle those situations of incomplete normative knowledge.
The semantics proposed for these actions is aimed at particular
cases that can not be solved using the general normative
knowledge of the society. This ad-hoc character tallies well
with the natural language meaning of the corresponding
English speech act verbs [
The normative framework reported in this paper is part of
a larger research project aimed at the specification of a
language for programming social applications [
The authors would like to thank the anonymous reviewers for their detailed comments. Research sponsored by the Spanish MICINN, project TIN2006-15455-C03-03.