Self-organisation and self-evolution is evident in physics, chemistry, biology, and human societies. Despite the existing literature on the topic, we believe self-organisation and self-evolution is still missing in the IT tools we are building and using. Instead of creating numerous rigid systems, we should aim at providing tools for creating self-evolving systems that adapt to the ever evolving community's needs. This paper proposes a roadmap for self-evolution by presenting a set of building blocks, which we refer to as community charters. The paper also presents an approach for each of these blocks, helping build the rst prototype for self-evolving communities.
Whilst many approaches have been proposed for de ning and implementing
communities (such as using the notion of organisations [8] or institutions [
We argue that just like human communities, e-communities (de ned by their software) also need to self-evolve. Instead of creating numerous rigid systems, what we should aim at instead is providing tools for creating self-evolving systems that adapt to the community's needs. We believe di erent communities should be governed by di erent rules. These rules should be an ever evolving set resulting from the aspirations of its members. Furthermore, for the community's rules to be e ective, they need to be tailored to the speci c character traits of the community members as well as considering some other external in uences. We note that in this paper we talk about self-evolution, as opposed to evolution, since we are interested evolution that is designed and directed by the community itself.
This paper proposes a roadmap for self-evolving communities. It proposes a set of building blocks needed for self-evolution, and we refer to these building blocks as the community charter. The paper also presents an approach for each of these blocks, helping us build the rst prototype for self-evolving communities.
We say communities are formed around certain goals that community members are interested in ful lling. Their evolution is driven by the ful lment (or unful llment) and the evolution of these goals. Their fall is usually triggered either by the ful lment or the abandoning of such goals by community members.
In addition to goals, we say interactions are another fundamental constituent of communities. A community, by de nition, is a group of interacting peers (where peers may be a combination of humans, agents, and services). Interactions are the backbone that glues a community together. Without interactions, a community is simply a number of individuals. However, we say a community's interactions should aim at ful lling its goals. Otherwise, either its interactions are ine ective, or its goals have not been properly thought-out.
Between goals and interaction protocols lie the community's norms. Norms may be thought of as describing the declarative rules, i.e. statements that describe what a rule is without going into the details of how to implement it. Norms provide generic guidelines that help ful l the community's goals, and the interaction protocols (or the procedural rules) should be designed to abide by these norms.
As such, we propose to de ne a community by its charter, which we say is composed of the community's goals, norms, and interaction protocols. The concept of such a charter maps with the notion of traditional human communities, which are usually de ned by their mission statement (the goals), their bylaws (the norms), and their standard operating procedures (the interaction protocols) [7].
Finally, we say unful lled goals can be one automated way for triggering evolution, suggesting a aw with the charter's components. Di erent elements of the charter may be modi ed during the evolution stage in the hope that a more coherent charter is achieved.
The remainder of this paper elaborates further on each of the charter's three components in Sections 2, 3, and 4, respectively. Section 5 then provides a brief insight on how the proposed model helps promote self-evolution, before concluding with Section 6. 2
A community usually has a general goal which may then be divided into more concrete sub-goals. In human communities, these are de ned by the community's mission statement.
For instance, we consider the u-Help community, whose software platform is used \for building a community of helpful people and supports them in nding volunteers for day-to-day tasks" [9]. Although the illustrative application for uHelp is to allow parents nd volunteers for picking their children up from school or babysitting them, u-Help may be applied to any community with any needs for services. The u-Help community's mission statement may be paraphrased accordingly: To help community members exchange services in a community with high needs for such services.
This general mission statement may then be divided into more concrete goals, whose ful lment may be veri ed:
G1. To ensure the community's needs for services are being addressed G2. To ensure the satisfaction of requesters (i.e. to ensure good quality of service) G3. To ensure the satisfaction of volunteers
These goals are de ned by the community members that establish this community. Although goals may evolve over time like any other charter component, their evolution is usually much less frequent in comparison with the evolution of norms, and interaction protocols. This is because communities are essentially viewed as de ned by their goals. 2.1
In multiagent system, goals have been studied extensively as being part of an agent's belief-desire-intention (BDI) model [12]. In such models, goals are viewed as the desires that the agent adopts for active pursuit. When an agent commits to a speci c plan for achieving a given goal, then the goal becomes an intention.
In this paper, we do not discuss agent goals, but community goals. Di erent approaches and/or languages may be adopted for the speci cation of these goals. We say one way to specify a goal is as a tuple:
hGId; GSpeci cation; GDescriptioni where GId is the goal's unique identi er, GSpeci cation is the goal's speci cation in rst-order logic, and GDescription is the description of the goal in text, which may be used to aid human users understand which goals have been ful lled or not during the evolution stage of a community (we assume community members may be a mix between agents and human users).
Goal Speci cation Example. The uHelp community's goals may be speci ed as: hG1; 9R0 R (8r 2 R0 9m 2 M volunteer(r) = m ^ majority(R0;R)); \The majority of requests had volunteers to carry them out00i hG2; 9R0 R (8r 2 R0 9m 2 M volunteer(r) = m ^ pstvRate(m;r) ^ majority(R0;R)); \The majority of requesters are happy with the volunteers' performance00i hG3; 9R0 R (8r 2 R0 9m 2 M requester(r) = m ^ pstvRate(m;r) ^ majority(R0;R)); \The majority of volunteers believe the requests are reasonable/doable00i where, M is the set of all community members, R is the set of all requests for help that community members have issued, majority(R0; R) implies that the elements of set R0 constitute a majority with respect to the elements of the set R, requester(r) = m speci es that the community member m requested help with task r, volunteer(r) = m speci es that the community member m has volunteered (and been assigned) to ful l the request r, and pstvRate(m; r) describes that the community member m has been positively rated for task r. If m was a volunteer, then positively rating a volunteer will describe the requester's satisfaction with the volunteer's performance. If m was a requester, then positively rating a requester will describe the volunteer's belief that the request was for a reasonable (or doable) task with a reasonable deadline.
We note that in this speci c example, goal G2 subsumes goal G1, and hence, the community's set of goals may be reduced to goals fG2; G3g. 2.2
We say the unful llment of community's goals is one of the triggers for selfevolution. When such a situation arises, community members should be alerted by the system, which would then suggest that the charter may need to be revised as it is failing to ful l its goals. Of course, there may be other triggers speci ed by the norms and interaction protocol, which we do not discuss here, such as stating which members are allowed to initiate evolution.
When to check for the satisfaction of community goals is also something that needs to be speci ed by the interaction protocol. For instance, should this check happen on a daily basis? Should it happen every time a new set of 100 requests is issued? This is an issue to be decided by the community itself (or those members who are given the right to do so) and speci ed accordingly by the interaction protocol.
Nevertheless, we say the minimum requirement for implementation is for interaction protocols to be capable of calling the goal satisfaction checker. Section 5 elaborates further on this. 3
Norms describe the rights and duties of community members. We say there are two di erent types of norms, those that are regimented by the interaction protocol, and those that are enforced by other means (such as punishments and rewards) as they cannot be regimented by the interaction protocol. An example of the former is the norm that states that a buyer cannot rate the seller more than once, and the system prevents the buyer to do so. An example of the latter is the norm that states that only people with su cient credit can bid, where the credit is private information that cannot be accessed and assessed by the system. 3.1
Regimented Norms Speci cation Although numerous logics have been
proposed in the literature [
In this paper, we propose to specify regimented norms in a simpli ed deonticbased approach:
hN ormId; N ormT ype; Agents; Action; Conditioni where N ormId is the norm's unique identi er, N ormT ype = fpermissible; omissible; obligatory; impermissible; optionalg speci es the type of the norm (we de ne the main ve deontic operators of the Traditional Scheme [11] that describe what is: permissible, omissible, obligatory, impermissible, and optional), Agents describes the set of agent roles that this norm applies to, Action speci es the action the norm addresses, and Condition speci es the circumstances under which the norm holds. Of course, as with goals, one may add a descriptive eld to norms to aid humans in comprehending the norms they are discussing or voting on. Although this would raise a security concern of how to make sure the text properly describes the logic.
Regimented Norms Example. As an example, we specify a couple of norms from an existing service exchange community, the Time Bank community of the Castlehaven Community Association (www.castlehaven.org.uk). The norm description (and number) is taken from the community's time bank community rules [17]. 3. Volunteers can live outside Camden and join the Time Bank to join in activities and help those who live in the Time Bank area.
h3; permissible; member(V ); volunteer(V; T ask);
live outside T B area(V )i 5. Everyone who requests help from the Time Bank will be put on a waiting list.
h5; obligatory; system; put on waiting list(T ask);
request(R; T ask) ^ :live outside T B area(R)i Regimented norm (3.) states that if a member (member(V )) lives outside the Time Bank area (live outside T B area(V )), then he is permitted to volunteer for a task (volunteer(V; T ask)). Regimented norm (5.) states that if a requester R requests help with some task T ask (request(R; T ask)) and the requester lives within the Time Bank area (:live outside T B area(R)), then the system is obliged to accept the task by putting it on the waiting list (put on waiting list(T ask)).
Verifying Norm Regimentation Naturally, when norms need to be regimented by the interaction protocol, there should be means for automatically verifying this regimentation each time the norms or the interaction protocols change. As such, we say there is a need for automatic veri cation, which should happen once at the formation of the community and then again after each evolution.
Automated theorem proving or model checking are popular approaches with rich existing literature [16]. We propose to use the model checker of [14] that can help verify on the y whether the norms speci ed in the proposed syntax above are satis ed in an interaction model speci ed in LCC [15], which is a lightweight process calculus for specifying multiagent interactions. Naturally, other languages may be used for specifying both the norms and the interaction model and other model checkers may be used for veri cation. However, in such cases, an appropriate translator is needed to translate the chosen language into the input language of the chosen model checker. 3.2
Enforced Norms Speci cation Enforced norms are norms that cannot be
regimented by the system. They are then enforced by alternative methods, such
as applying sanctions (punishments and rewards). Sanctions usually apply to
prohibitions and obligations. As such, while other modal logics may be used for
specifying regimented norms, enforced norms usually rely on deontic logic [
Although any of the existing logics may be chosen, in this paper, we propose
to specify enforced norms by extending the speci cation of regimented norms
with sanctioning information. The proposed approach follows the same style as
regimented norms and is coherent with many existing approaches [
Reward; P unishment; Deadlinei
As in the case of regimented norms: N ormId is the norm's unique identi er, Agents describes the set of agent roles that this norm applies to, Action speci es the action the norm addresses, and Condition speci es the circumstances under which the norm holds and it is speci ed in rst order logic. However, N ormT ype 2 fimpermissible; obligatoryg is now restricted to obligations and forbiddances only, as we shortly explain. Reward and P unishment specify the rewards and punishments that an agent receives if they abide to or break the norm, respectively. Last, Deadline speci es the deadline for an action to be prohibited or obligatory. The use of deadlines is clari ed further in Section 3.2.
Concerning the restriction of the norm type to obligations and prohibitions, we say enforced norms rely on the concept of sanctions, and sanctions are usually assigned not to permissible actions that one is free to perform or not, but to negative permissions that describe what one is not permitted to perform. The concept of punishment and reward only makes sense when addressing negative permissions. We note that when de ning deontic operators, one can pick any of the operators to be the basic operator, and the remaining operators may be de ned in terms of the chosen basic operator. To illustrate our argument, we choose the permissible operator to be the basic operator, as such: omissible impermissible obligatory optional
permissible = permissible : = : permissible = : permissible : = permissible _ permissible : As enforced norms focus on negative permissions only, then the two operators that describe negative permissions are prohibitions (describing impermissible actions) and obligations.
A Note on Sanctions. It may be argued that punishment and reward is not always the right approach for motivating the abidance to norms. Furthermore, what may be considered a punishment for one may be viewed as a reward for another. In this paper, we label post-conditions as rewards or punishments, although they may simply be interpreted as the post-conditions of abiding with or breaking the norm.
Enforced Norms Example. As an example, we specify the following two norms: 1. Volunteers are penalised by losing credit if they do not ful l their duties on time.
h1; obligatory; volunteer(V ); ful l duty(V; T ask); assigned duty(T ask; V ); gain points(T ask); lose points(T ask); deadline(T ask)i 2. Requesters are not allowed to ask for tasks that are paid.
h2; impermissible; requester(R); request help(R; T ask); paid service(T ask); nil; prohibited to request(N ext 10 days); nili
The rst enforced norm states that if a task has been assigned to a volunteer V (assigned duty(T asl; V )) then the volunteer is obliged to perform this task (ful l duty(V; T ask)) within the task's deadline (deadline(T ask)). If he succeeds, then he is rewarded by gaining a certain number of points (gain points(T asks)); and if he fails, he is punished by losing a certain number of points (lose points(T aks)).
The second enforced norm states that a requester R is forbidden to request help (request help(R; T ask)) if the requested task is a paid service (paid service(T ask)). This rule has no deadline (nil); i.e. it holds forever. Requesters are not rewarded for not requesting help with paid services (nil), but punished if they do by being prohibited by the system from requesting any help over the next 10 days (prohibited to request(N ext 10 days)).
Ensuring Norm Enforcement Several approaches exist that propose norm
enforcement mechanisms [
OnEvent: Constraint C of norm n is satisfied for
Do: Instantiate norm n for agent OnEvent:
performs action A and there exists an instantiated norm n on 's action A Do: If norm n is of type impermissible Then
Agent is punished and the instantiated norm is deleted Else
Agent is rewarded and the instantiated norm is deleted OnEvent: Deadline of instantiated norm n passes
Do: If norm n is of type impermissible Then
The corresponding agent is rewarded and the instantiated norm is deleted Else
The corresponding agent is punished and the instantiated norm is deleted
We note that the system responsible for the execution of interactions should also be responsible for the norm enforcement algorithm, as it needs to keep track of which conditions are being satis ed, which actions are performed, and which deadlines have passed.
Interaction protocols describe the operational rules governing the interaction
between community members. In abstract terms, they may be speci ed via
labelled transition systems or nite state machines. In multiagent systems, several
approaches have been used that one is free to choose from, such as using process
calculi [15], electronic institutions [
We say any approach may be adopted, as long as a model checker can verify the speci ed interaction protocols against regimented norms. In this paper, however, we choose the lightweight coordination calculus (LCC) [15] as it is a process calculus that is used both in the speci cation of multiagent systems as well as in the execution of their interactions, and more importantly, it is the language of [14]'s model checker. We believe that having the executable interaction model fed directly to the model checker avoids the complexity of modelling the system in another language and the possibility of introducing errors in doing so. Interaction Protocol Example. Figure 2 provides an example of an interaction protocol, where the nodes present the state of a process (or agent). The protocol states that there can either be a number of volunteers and requesters playing at the same time (note that one agent may play more than one instance for more than one role at the same time), or a number of voters discussing the evolution of the community. Note that jj describes the parallel operator in process calculus. As an example, we explain the voter's role, and we leave it to the reader to interpret the rest of the speci cation, as we believe the names of the agent roles and actions are self-expressive.
The voter's protocol states that when an agent plays the role of a voter, rst, it will receive a message stating the unsatis ed goal g1 that has initiated the evolution stage (get unsatis ed goal(g1)). Then, either the voter suggests a change x in the charter (suggest change(x)), or it receives a suggested change x by some other voter (get suggested change(x)). In the rst case, it will wait for others to vote on its suggested change, before receiving the nal result r of the vote (get result(x; r)). In the latter case, it can either vote v (vote(x; v)), or it can abstain from voting (abstain(x)). In both cases it will then be informed of the nal voting result r (get result(x; r)). As the arrows illustrate, the protocol may loop several times with di erent voters suggesting new changes and voting on the suggestions, before the nal charter ch is agreed upon and the voter is informed (get nal charter(ch)).
The reader familiar with process calculi may note that mapping this speci cation into a process calculus such as LCC becomes straightforward. 5
The interaction protocols are expected to specify the details of evolution. They should specify when does evolution take place and how does the system trigger evolution (such as when goals are not satis ed), which community members are allowed to suggest evolution (such as permitting the community's president to trigger evolution whenever he sees t), the minimum number of people required to discuss evolution (such as stating that at least 30% of the community should be present for discussing evolution), or who can suggest changes and how evolution is discussed and agreed upon (such as following some prede ned voting mechanism).
Ideally, there would be speci c processes dedicated for evolution. That is if we are thinking of interaction protocols speci ed in a process calculus. For instance, if one uses electronic institutions to model interaction protocols, then one would think of a dedicated evolution scene. In the example presented by Figure 2, the dotted processes, states, and actions are those related to evolution. The processes de ning the voters' roles illustrate how voters may vote on recommended changes. And it is the goal check(g1) action in the requester's role that is responsible for initiating evolution. Although, we note that for simpli cation, the conditions that control the ow are omitted.
Naturally, there is the crucial issue of de ning how the interaction needs to be paused at a safe state from which it can be resumed after evolution is completed. We leave this open issue for future research. However, we say after evolution takes place and a new charter is agreed upon, all community members need to be informed of the new charter. 6
This paper argues the need for self-evolving communities. We believe self-evolution is still missing in the IT tools we are building and using. And we say that instead of creating numerous rigid systems, we should aim at providing tools for creating self-evolving systems that adapt to the ever evolving community members' needs.
The paper proposes a roadmap for self-evolving communities. It proposes a set of building blocks, which we refer to as the community charter, and presents a concrete approach for each of the proposed building blocks, which helps build the initial prototype for self-evolving communities. We say a community charter should de ne: (1) the community's goals, (2) the community's norms, and (3) the interaction protocols, which include the evolution protocols.
One proposed approach for triggering evolution is for the system to signal unful lled goals, suggesting the modi cation of the charter's various components in a way that helps address these unful lled goals. Future work could also make use of the research on emergence and self-organisation in multiagent systems.
Finally, we note that our ongoing research considers semantics to be a fundamental component of any charter. For instance, unful lled community goals might be the result of misunderstandings at the semantic level. In this line of work, where community members are expected to propose and discuss new goals, norms, and/or interaction protocols, ensuring that all members comprehend these elements in a consistent manner becomes a major and crucial challenge. 7
This work is supported by the PRAISE project (funded by the European Commission under the FP7 STREP grant number 318770), the CBIT project (funded by the Spanish Ministry of Science & Innovation under the grant number TIN201016306), and the Agreement Technologies project (funded by CONSOLIDER CSD 2007-0022, INGENIO 2010). 7. Heimlich, J.E., Dresbach, S.H.: Written documents for community groups: Bylaws and standard operating procedures. Fact Sheet on Community Development, Ohio State University Extension, online: http://ohioline.osu.edu/cd-fact/co-bl. html; Last accessed on 03 October 2013 8. Horling, B., Lesser, V.: A survey of multi-agent organizational paradigms.
Knowl. Eng. Rev. 19(4), 281{316 (Dec 2004), http://dx.doi.org/10.1017/ S0269888905000317 9. Koster, A., Madrenas-Ciurana, J., Osman, N., Schorlemmer, W.M., Sabater-Mir, J., Sierra, C., Jonge, D.D., Fabregues, A., Puyol-Gruart, J., Garcia-Calves, P.: uhelp: Supporting helpful communities with information technology. In: Ossowski, S., Toni, F., Vouros, G.A. (eds.) Proceedings of the 1st Int. Conf. on Agreement Technologies. CEUR Workshop Proceedings, vol. 918, pp. 378{392. CEUR-WS.org (2012) 10. Lpez, F.y., Luck, M., dInverno, M.: A normative framework for agent-based systems. Computational & Mathematical Organization Theory 12(2-3), 227{250 (2006), http://dx.doi.org/10.1007/s10588-006-9545-7 11. McNamara, P.: Making room for going beyond the call. Mind 105(419), 415{450 (1996), http://mind.oxfordjournals.org/content/105/419/415.abstract 12. Meyer, J.J., Broersen, J., Herzig, A.: BDI logics. In: Ditmarsch, H.v., Halpern, J., van der Hoek, W., Kooi, B. (eds.) Handbook of Logics for Knowledge and Belief.
College Publications, http://www.collegepublications.co.uk/ (2013) 13. Modgil, S., Faci, N., Meneguzzi, F., Oren, N., Miles, S., Luck, M.: A framework for monitoring agent-based normative systems. In: Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 1. pp. 153{160. AAMAS '09, International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC (2009), http://dl.acm.org/citation.cfm?id= 1558013.1558034 14. Osman, N.: Runtime Veri cation of Deontic and Trust Models in Multiagent Interactions. PhD thesis, School of Informatics, the University of Edinburgh, Edinburgh, UK (2008) 15. Robertson, D.: A lightweight coordination calculus for agent systems. In: Leite, J.a., Omicini, A., Torroni, P., Yolum, p. (eds.) Declarative Agent Languages and Technologies II, Lecture Notes in Computer Science, vol. 3476, pp. 183{197. Springer Berlin Heidelberg (2005), http://dx.doi.org/10.1007/11493402_11 16. Robinson, A., Voronkov, A. (eds.): Handbook of automated reasoning. Elsevier
Science Publishers B. V., Amsterdam, The Netherlands, The Netherlands (2001) 17. Time bank joining form. Castlehaven Community Association (May 2013), online: http://www.castlehaven.org.uk/static/uploads/documents/timebank_ Application_form_May_2013.docx; Last accessed on 03 October 2013