1 Introduction

Agent societies [28, 29, 36] provide a paradigm for representing the interaction of heterogeneous agents in order to reach global or individual goals, through the definition of roles, relationships, and regulations that constrain the behavior of agents inside a group of agents. Similar to the importance that societies have in human systems, societies have also been widely used as frameworks for representing, modeling, and engineering agent-based systems. It is commonly agreed that many concepts and ideas can be shared between human societies and agent-based societies [32, 33, 76]. Indeed, human societies have been used as the basis for designing and modeling agent societies [6, 73].

As has been stated in the literature long ago, the organization of a system can have a significant impact on the system’s short and long-term performance [19, 37, 42, 62, 76]. Nevertheless, most of methodologies and infrastructures that provide support for agent societies do not allow changes after its definition [21]. It has been commonly agreed by theorists of human societies that there is not a specific design that is suitable in all situations [11, 49]. Fox [33] claims that adaptation is very important for efficiency because responses of programmed societies are not appropriate in environments where uncertainty is high. Therefore, adaptation is a requirement to provide societies with capabilities in order to be able to proactively or reactively anticipate or react to different variables [43].

Similar to the importance that adaptation has in human systems, adaptation has a remarkable importance in agent societies. According to [11], agent societies can be adapted by changing the roles, knowledge, and activities of agents to suit new problem situations. Adaptation can be viewed as the mechanism that modifies the structure and behavior of the agent society, such as adding, removing, or substituting components, which are done while the system is running and without bringing it down [30].

Applications composed by collaborative and heterogeneous entities have been developed to be dynamic and self-adaptive [67, 84]. Specifically, due to the increase in the number of open agent-based applications, adaptive societies that adjust themselves to gain advantage in their current environments are likely to become increasingly more important over the next few years [47, 59]. Thus, adaptation eliminates the need to determine all possible runtime conditions a priori, which is unknown in many systems. Before this can occur, the space of organizational options must be mapped and their benefits and costs understood [42].

In the last few years, some approaches have been developed for representing and modeling adaptation in agent societies. By providing these societies with capabilities for discovering, evaluating, and representing issues related to adaptation, a process of organizational self-design can be facilitated, in which a system automates the process of selecting and adapting an organization dynamically [23, 42, 77]. This support is usually provided by current approaches for adaptation by means of frameworks and infrastructures which manage the adaptation process.

Being the adaptation in agent societies an important research focus in the last few years, it is relevant to analyze how current adaptation approaches provide support to agent designers in order to develop adaptive agent societies. Therefore, the short-term goal of this study is to describe in detail some of the most relevant existing approaches, in order to show the advantages and limitations of each one. In addition, related specially to these limitations, we can define a long-term goal related to define which research issues would be interesting to be addressed in the next future years, in order to develop agent societies that autonomously adapt and regulate themselves in response to events and changes in the environment.

This paper is organized as follows. In Sect. 2, we describe the phases that compose the adaptation life-cycle, and we define the most relevant parameters that should be analyzed for a comparison of adaptation approaches. In Sect. 3, we analyze the most relevant works in detail by comparing them according to what they provide for each phase and how this support is implemented. In Sect. 4, we discuss the current state of the art for adaptation in agent societies and point out the most relevant open issues that should be addressed in the years to come. Finally, in Sect. 5, we present some concluding remarks.

2 Adaptation in agent societies

The concept of agent society can be slightly different depending on the authors. However, common properties can be found along the literature [7, 24, 31, 36]. According to these, we can view an agent society as a flexible and robust group of interacting agents having common goals. Within the society, agents have different roles which require a set of competencies. These agents can interact with each other, identify their abilities, and request activities on behalf of others, being observed to respect social norms. Agent societies provide the basis for designing complex, structured, organized, and regulated systems. Depending on the application and the problem, each agent society model defines different requirements and uses different names to represent some of the above elements.

Adaptation in agent societies can be defined as a process that changes the society [45]. This adaptation is referred to modifications in the structure and behavior of the agent society, such as adding, removing, or substituting components, which are done while the system is running and without bringing it down [30]. These modifications are related to the organization specification, such as, roles, goals, services, norms, and the agent population, as well as changes in the relationships among these components. In this respect, the life-cycle of an adaptation can be defined as the process of analyzing the problems of the current agent society, proposing adaptation solutions, selecting and implementing an adaptation, and evaluating this process once it is applied.

Authors agree that adaptation [51, 83] and more specifically, adaptation in agent societies [45, 75], can be represented as a loop process composed by different phases. The specific definition of each phase may slightly change from one author to another. We try to use a general definition that can be adjusted to different models of agent societies, in order to cover a wide range of applications. The adaptation process starts by allowing the system to perceive information from the managed elements (resources, agents, etc.). This information is analyzed in order to assess that changes are required and one or more set of changes (adaptation solutions) are proposed. Then, a specific solution is selected and needed to be implemented, which consists of applying the changes that are required. Finally, the adaptation process is evaluated, and the loop is closed by starting again the starting phase. According to this, we define the following main phases for representing the life-cycle of an adaptation process: monitoring, design, selection, and evaluation. Frameworks that support adaptation in agent societies implicitly define issues that are related to these phases. In order to discuss the features of the most relevant approaches, we use these phases to analyze the support provided by these approaches for these phases and how this support is implemented. In the following section, we introduce a running example in order to support the discussion of these phases. Then, we present a detailed description of each phase.

2.1 A workshop management system

As a simple example to illustrate an agent society, let us consider a system for supporting the process of producing the technical program for an international workshop, which is similar to other examples used for illustrating adaptive systems [21, 65]. In this example, agents are associated to the actors involved in the process and play some specific roles inside this society (PC chairs, PC members, reviewers, etc.). Depending on the role or roles played by each agent, some services or capabilities must be provided. As an example, an agent playing the PC chair role must provide some management skills, while an agent playing the reviewer role must provide some knowledge to evaluate the submitted papers. The objective of the agent society can be defined as organizing the workshop, while agents or roles can be assigned to fulfill some sub-objectives such as the paper evaluation or the paper selection.

Interaction between agents inside the society can follow some structure, according to the interaction patterns that are defined for communication. As an example, reviewers can only interact with the PC chairs, not allowing direct interaction between two reviewers. In addition, some regulations or norms can be defined at different levels in this system. An example of these regulations can represent that a reviewer cannot evaluate a paper that is not assigned to himself.

The objective of this example is to help the reader to better understand all the features that are defined along the paper, by providing a realistic real-world example. Depending on the different approaches, some of the requirements of this example would be represented in different ways.

2.2 Monitoring

The monitoring phase defines the problems of why and when a society needs to be adapted. Monitoring is essential in order to be able to detect undesirable behavior that needs to be corrected [39], which can be triggered by changes in the environment. Theorists of human societies [10, 43, 81] define two possible categories of strategy options for adaptation: environmental determinism and organizational choice. The first option corresponds to reactive changes that are triggered by the social interaction with the environment. The second option refers to the social ability to create a voluntary response in terms of adaptation. According to these strategy options, we propose to classify the monitoring phase in agent societies by following a terminology that is more widely used in agent societies [30].

A reactive strategy occurs when the agent society automatically responds to events that cause an adaptation such as the addition or deletion of a new role, agent, etc. These events cause the agent society to make the required adjustments in order to continue to fulfill its goals. As an example, in the workshop management system, a reactive strategy could detect that some paper needs to be reallocated due to its reviewer is not available anymore. Approaches that follow this kind of adaptation focus on the need for an adaptation process to be guided by events. In contrast, a proactive strategy requires an implicit mechanism for reasoning about the current situation in order to decide that an adaptation is required. In the example of the workshop management systems, a proactive strategy could decide that a paper needs to be reallocated in order to assign it to a reviewer which is more related to the topic.

Related to these strategies, the adaptation logic is used to define that an adaptation is required. This adaptation logic can be predefined, if the events that trigger this adaptation or the mechanisms for deciding that an adaptation is required are implemented at design time. Otherwise, this logic can be adaptable if it can be changed when the system is running. In the workshop management system, this logic could represent that the deadline must be extended if the number of submitted papers do not reach a minimum threshold. In a predefined logic, this threshold could not be changed at runtime, while in an adaptable logic, this could be changed depending on the number of papers already submitted.

According to other works related to adaptation in agent societies [39], the information that is acquired can be specified and used off-line or on-line in order to improve the system’s behavior. An off-line specification defines the information to be monitored at design time and cannot be changed; in contrast, an on-line specification, the information that is monitored can change depending on the requirements of the system during execution. Similarly, the information that is monitored can be used off-line or on-line.

Finally, in human societies, the decision-making process can be carried out by individuals or by their institution [43]. Similarly, we define two different implementation types for the monitoring phase: a centralized way if an agent or a specific authority is responsible for deciding that an adaptation is required; a distributed way if a pool of agents can decide that an adaptation is required either autonomously or by means of an agreement. A support for monitoring should be provided by any approach that supports adaptation. The greater dynamicity provided by this support to implement the monitoring mechanisms, the more flexibility would be provided to develop adaptive agent societies.

2.3 Design

The design phase defines the problem of how an adaptation is carried out. Once an adaptation process is required, the design phase includes an analysis of the organizational elements and an adaptation proposal that changes specific elements of the agent society. Similar to the monitoring phase, design can also be carried out in a centralized way if a single agent or a central authority is responsible for proposing the adaptation solution. A distributed design involves the participation of several agents in the adaptation solution proposal.

Depending on the specific model, current adaptation approaches provide support for changing different elements of the agent society based on the requirements of the problems that they consider.

Some authors propose a classification of adaptation types in behavioral and structural adaptation [30]. Nevertheless, a more detailed classification can be provided by including common types of changes that can be found in the literature according to the following dimensions:

  • Open system support allows changes in the agent population, that is, agents can enter or leave the system. As an example, in the workshop management system, this would be referred as allowing the entrance of new reviewers into the system due to the number of submissions that are higher than expected.

  • Emergence support allows elements that define the social behavior to be changed, that is, the addition or deletion of the roles that agents can play, social goals, etc. As an example, in the workshop management system, this would be referred as allowing the creation of a new publicity chair role, which is required to disseminate information about the workshop to the largest possible appropriate technical audience.

  • Behavioral adaptation support allows changes related to the behavior of the agents that populate the society. For example, this involves changes in the capabilities offered by an agent in order to be able to play a role. As an example, in the workshop management system, this would be referred as allowing agents to add new topics in which they are experts.

  • Functional adaptation support allows changes in how different elements of the agent society are related to each other, which affects the society functionality, such as changes in the services offered by a role or changes in the roles that agents play. As an example, in the workshop management system, this would be referred as allowing the reassignment of a paper to another reviewer when the previously assigned reviewer is not able to provide its reviews by the deadline.

  • Structural adaptation support allows changes in the relationships between elements of the agent society, which affects the social structure, such as relationships among the agents. As an example, in the workshop management system, this would be referred as allowing the interaction between two reviewers which were not previously allowed to interact to each other, in order to discuss the acceptance of a given paper.

  • Norm adaptation support allows changes in the regulations of the agent society. This support can be related to modifications in the specification of the norms that govern the agent society as well as the addition or deletion of new norms. As an example, in the workshop management example, this would be referred as extending the notification deadline due to several requests by reviewer agents.

Depending on the elements that are allowed to be changed in an adaptation process, a wide range of different solutions can be provided. Therefore, it would be desirable for an adaptation to be able to consider as many dimensions as possible. As we will see in the following sections, some adaptation approaches focus on changes in an specific dimension, while other approaches are more flexible by considering changes in several dimensions.

2.4 Selection

The selection phase defines the problem of choosing which adaptation is finally implemented. If several adaptations have been proposed in the design phase, the selection phase determines which of these proposals is applied. Similarly to previous phases, if a single agent or a central authority is responsible for this selection, we consider the selection phase to be centralized. In contrast, if several agents are involved in the selection phase (for example, by a negotiation process or by social choice), we consider the selection phase to be distributed. Depending on whether a single adaptation is designed or several designs are proposed, several criteria can be used in the design phase to guide the design, or in the selection phase to guide the selection.

In some scenarios, adaptation can be viewed as the mechanism that allows the society to achieve the social goals. As an example, this occurs when some event prevents the society to achieve its goals, and therefore, an adaptation is required to achieve a goal fulfillment. In other scenarios, according to Dignum et al. [30], adaptation is desirable if it leads to increase the utility of the system. These authors define two kinds of utilities: individual and social. Individual utility is different for each agent, while social utility can take into account the individual utility of each agent. Nevertheless, in some scenarios, an individual utility increase may not cause a direct social utility increase. What is more, an individual utility increase may have a negative impact in the society. Therefore, it is relevant to analyze whether the utility that is taken into account for the adaptation is referred to the direct benefits caused in the agents involved in the change, or whether the utility also considers indirect benefits, which are referred to other agents of the society.

The utility must take into account both the adaptation success and the cost of any change needed to achieve the adaptation from the current situation [4, 36]. Actually, other works such as Cheng et al. [22] state that the adaptation process must be also evaluated, for example, in terms of its impact in space of time.

As stated in [56], most organizational changes may encounter problems: they often take longer than expected and desired; the cost of managerial time may be increased, and there may be resistance from the people involved in the change. In order to deal with this problem, we consider that both the benefits obtained by adaptation and the costs associated with this process are important aspects that should be taken into account in order to define the suitability of an adaptation process.

According to the above criteria, we classify the dimensions used for the selection phase depending on the issues that are considered for adaptation. We include benefits and costs in separated dimensions in order to provide a global view that can be applied to different approaches. Both benefits and costs can be referred to time, money, resources, and so on, depending on which is the society focus:

  • The Goal fulfillment takes into account the fulfillment of the social goals in order to select the adaptation that is implemented. As we stated above, adaptation in this case is only focused on achieving the society’s stability by fulfilling the social goals. As an example, in the workshop management system, a selection focused on the goal fulfillment could be triggered when the agent associated with the PC chair role is not available to achieve its goals and the system needs to reallocate another agent to this role.

  • The benefits of the agent society in order to design or to select an adaptation can be classified as:

    • Direct benefits represent the benefits that are associated with the individual elements involved in the change. As an example, in the workshop management system this could be referred as how the reviewer \(a_x\) is positively affected if it is reallocated to review a different paper, for example, if the new assigned paper if more related to its research topic, its revision would be more profitable to the author.

    • Indirect benefits represent the benefits that are associated with other elements that are not involved in the change but that can be influenced by this change. As an example, in the workshop management system this could be referred as how the reviewer \(a_y\) is positively affected if the reviewer \(a_x\) is reallocated to a different paper, for example, if the reallocation of \(a_x\) causes that the paper assigned to \(a_y\) is changed by the paper previously assigned to \(a_x\), which is more related to its research topic.

  • Similarly to the benefits, costs can be divided in:

    • Direct costs represent the individual costs that are associated with the elements involved in the change. As an example, in the workshop management system this could be referred as how an agent \(a_x\) is negatively affected if it is reallocated to review a different paper, for example, if the new assigned paper if less related to its research topic, its revision would be less profitable to the author.

    • Indirect costs represent the costs that are associated to other elements that are not involved in the change but that can be influenced by this change. As an example, in the workshop management system this could be referred as how a different agent \(a_y\) is negatively affected if \(a_x\) is reallocated to a different paper, for example, if the reallocation of \(a_x\) causes that the paper assigned to \(a_y\) is changed by the paper previously assigned to \(a_x\), which is less related to its research topic.

    In addition, as we stated above, other costs related to the adaptation process can be considered:

    • Adaptation costs which allow a representation of the costs required to carry out the adaptation process, that is, to apply each change associated with the adaptation. As an example, in the workshop management system this could be referred as the time required to reallocate a new paper to the reviewer \(a_x\).

    • Computation costs which allow a representation of the costs required to compute or select the adaptation. These costs are usually represented as the time required to design an adaptation and select a solution. As an example, in the workshop management system this could be referred as the computation cost required to calculate that \(a_x\) is reallocated to review a new paper.

    Depending on how some of these criteria are considered for adaptation, the consequences of adaptation can be accurately estimated to a greater or a lesser degree. These consequences refer to how an adaptation influences the fulfillment of the goals of the system, how the adaptation influences the agent society utility (i.e., how beneficial it is for any agent of the society), and how costly the adaptation is (i.e., how each agent could be affected and how costly the process to be carried out is). Therefore, the more criteria is considered for selecting the adaptation the more specific the adaptation impact can be estimated.

2.5 Evaluation

Adaptation approaches should also encompass techniques for monitoring and controlling the system once the adaptation is deployed [59]. The evaluation phase defines the problem of analyzing how well an adaptation has been performed. This phase provides feedback from the adaptation in order to assess whether or not the adaptation was as expected. This allows to evaluate the quality of the adaptation that was designed and selected as well as the quality of the society that was achieved, in order to take it into account for future adaptations, which increases the quality of future adaptations.

Researchers from human societies stated the relevance of a feedback process in order to achieve a successful adaptation [8, 9, 15]. This feedback helps to improve the control of new environments. According to these authors, several properties are related to this process such as the frequency of the feedback, the method (by inquiry or in time-periods), the individual that provides the evaluation, and the information or topic that is provided. Other works related to adaptive systems such as [22] define different factors that measure the criticability of the adaptation, the predictability, the overheads associated with it, and whether the system is resilient in the face of change.

All of these properties define evaluation processes. However, we propose a general classification in three general dimensions in order to differentiate which is the aim of the information obtained by this evaluation. These dimensions allow to classify a wide range of approaches depending on which of the previous phases (monitoring, design, and selection) the evaluation provides the feedback for. The techniques in which the evaluation is supported by each adaptation approach will be discussed and analyzed in the following sections.

  • An evaluation of the adaptation proposal is carried out when the approach analyzes the adaptation that has been designed depending on the requirements of the problem in order to consider this information for future adaptations. This dimension provides an evaluation that is related to the design that has been carried out, allowing past decisions to be considered in the future, if the adaptation requirement is similar. As an example, in the workshop management system this could be referred as evaluating which agents have been reallocated to which papers in order to consider this reallocation in the future, if the adaptation requirements are similar.

  • An evaluation of the adaptation process is carried out when the approach analyzes the adaptation execution in order to improve the predicted implementation of the process. This refers to issues such as whether or not the time and resources used were as expected during the implementation, if a setback appeared during this process, etc. This dimension provides an evaluation that is related to the selection that has been chosen, allowing the approach to improve the accuracy for estimating the consequences of future adaptations, and therefore, improving the selection process. As an example, in the workshop management system this could be referred as evaluating if the adaptation costs for reallocating agent \(a_x\) to review a new paper were as expected or in contrast, if this agent was reluctant to change.

  • An evaluation of the future state of the society is carried out when the approach analyzes the future state of the society that is achieved, in order to improve the predicted performance of the future society. This dimension provides an evaluation that is related to the monitoring process, allowing to improve the accuracy for estimating the performance of future modifications. As an example, in the workshop management system this could be referred as evaluating if the reallocation of agent \(a_x\) to review a new paper caused the expected benefits and costs (e.g., if the deliberation process delay was as fast as expected when the reallocation was computed).

Similarly to previous phases, the evaluation phase can be centralized if a single agent or a central authority is responsible for this phase, or distributed, if several agents are involved in this process. The greater amount of information related to the level of success of the adaptation is incorporated into the system, the more learning capabilities can be associated with the process for gaining experience from past adaptations.

3 Approaches for adaptation in agent societies

In this section, we provide an analysis of some relevant approaches to discuss their suitability in dealing with adaptation in agent societies. For each approach we describe their support for each phase of the adaptation life-cycle as well as some critical considerations. In Sect. 3.9 we show a graphical comparison between all of them in Table 9.

According to these criteria, several approaches proposed in the literature are only focused on specific phases or changes in specific dimensions. As an example, approaches such as [40, 68, 74] focus on the selection of the best role reallocation adaptation, while other works such as [48, 79] are focused on the selection of the best structural adaptation. Other works are especially focused on the monitoring phase [39] or in learning algorithms to optimize the agent interactions [2]. In addition, other approaches require a high human interaction in order to choose the adaptation decision [20].

Other well-known approaches can be analyzed since the perspective of several phases and dimensions. In the following, we analyze some of these recognized approaches.

3.1 OMACS

OMACS (organization model for adaptive computational systems) [27] (Table 1) is a metamodel for defining the adaptation at runtime in order for an agent organization to be able to achieve its goals effectively. The society model used in this approach is an organization composed by goals, roles, and agents along with additional entities called capabilities, assignments, and policies. Each role is defined to achieve a particular goal or a set of goals. Capabilities determine which agents are assigned to which roles according to the set of capabilities that are required to play each role and the capabilities possesses by each agent. Assignments define a set of agent-role-goal tuples \(\langle a,r,g\rangle \) to indicate that an agent \(a\) is assigned to play the role \(r\) in order to achieve the goal \(g\). Finally, policies specify the regulations of the system such as “one agent may only play one role at a time”.

Table 1 Adaptation phases in OMACS
Full size table

3.1.1 Monitoring

Adaptation is carried out reactively way when an event occurs and changes the state of the organization, which triggers the adaptation [63–65]. The agent that is responsible of realize these changes is the organization master, which is a specialized agent that possesses complete information about the organization and which is able to execute adaptation algorithms. The information that is required by the organization master is specified at design time but it is used on-line.

A specific kind of adaptation policy is used to describe the adaptation logic at design time. This logic defines rules that represent direct actions that are taken in order to trigger the adaptation. An example of adaptation policy can express that “if agent \(a_x\) is playing role \(r\) to achieve the goal \(g\), and \(a_x\) becomes incapable of playing it, then if agent \(a_y\) is capable of playing \(r\), it should be assigned to goal \(g\) and \(a_x\) should be de-assigned”. This reactive approach can increase the reasoning efficiency in anticipated scenarios.

3.1.2 Design

Adaptation design is carried out as a centralized process that changes the assignment of agents to roles when different events occur. Current implementation considers two types of events that change the state of the organization. On the one hand, changes in the goal set cause an adaptation: an insertion of a new goal, a goal achievement, and a goal failure. On the other hand, changes in agents also cause an adaptation: if an agent is removed from the organization, and if an agent loses a capability that negates its ability to play a role that it is assigned.

These events are specified before running the system and are responsible for causing adaptation, but they cannot be used in the design phase of the adaptation process. Therefore, the changes considered in the design phase define functional adaptation. Once a trigger occurs, general-purpose adaptation algorithms are implemented to find the appropriate assignments, which determine the design of the solution [85].

3.1.3 Selection

In order to obtain the best set of assignments that maximizes the organization’s ability to achieve its goals, functions are defined to evaluate how effective a role is in achieving a specific goal, and how effective an agent is in providing a capability. These functions return a real value that determines this effectiveness. Thus, an assignment determines how well an agent can play a role to achieve a goal. The organization assignment function computes a score that represents the goodness of the organization [26]. This is usually calculated as the sum of the scores of all the assignments. We must also point out that changes in the effectiveness of agents are not considered.

In the algorithms that are used for determining the appropriate assignments, every combination of goals, roles, and agents must be computed. In order to avoid this, the authors propose using assignment policies that restrict the range of valid solutions, such as restricting the number of roles played by a single agent. In this approach, if an optimal adaptation is found, this is automatically selected and implemented by the organization master in a centralized implementation, who sends the new assignments to agents. As an example, in [62] authors present an adaptation process that is approached as a role reallocation that determines which agent plays which role.

3.1.4 Evaluation

The OMACS approach does not provide support to measure the execution of the adaptation in terms of how the process can finally be carried out or whether or not the adaptation has achieved the expectations. Since the monitoring phase is carried out by policies, metrics could be used to allow designers to make design-time tradeoffs between flexibility and computational costs. Nevertheless, there is no specific definition of costs associated with the adaptation process itself. Therefore, these metrics are difficult to measure at design time without any knowledge of how the organization will behave at runtime.

OMACS specifies different scores associated with relationships in order to provide a measurement for organization utility. The optimal assignment refers to the organization assignment function that has the highest score. However, the costs of applying changes and the impact that these changes have on the rest of the agents cannot be specified in this approach. It is assumed that an agent \(a\) being reallocated to play a role \(r\) can be carried out with a non-associated cost. Moreover, this assignment would not have any effect (positive or negative) on the rest of the population. By considering adaptation costs (material costs, resources, time, etc.), the costs for achieving the optimal assignment could be high and may not be worth the benefits obtained. In contrast, a sub-optimal assignment might be achieved with a lower cost, increasing the value of the overall process.

3.2 Moise

The Moise adaptation approach proposed by [45] (Table 2) is aimed at providing support in order to adapt an agent organization to its environment and to help it to efficiently achieve its goals. The society model used in this approach is Moise+ [44]. This model defines an organization which is composed by agents, roles, missions, and the deontic dimension. Each role represents a set of constraints that an agent follows when it plays this role. These constraints represent the structure dimension (relations between roles) and the functional dimension (missions, deontic dimension). A mission is a set of coherent goals that an agent can commit to. The deontic dimension specifies the permissions and obligations of a role in a mission. In order to carry out the adaptation process, specific roles are defined. The organization manager role is played by an agent, which is in charge of managing the adaptation process. This agent has complete information about the current state of the organization and has permission to change it. The historian role is defined to maintain information regarding the entire history of the organization. This information could be useful for the monitoring and design phases. An agent that plays this role informs the organization manager of all the social events that it has participated in. The monitor role is in charge of identifying situations that require an adaptation. Finally, the adaptation expert role is played by agents that are in charge of identifying current problems of the organization and proposing adaptation solutions.

Table 2 Adaptation phases in Moise
Full size table

3.2.1 Monitoring

In the Moise adaptation approach, adaptation is a proactive process that changes the current state of the organization into a new one [45]. The monitoring phase is implemented in a distributed way by monitor agents. These agents are able to decide that an adaptation is required based on their internal knowledge. The information required to be monitored is specified off-line but is used on-line without stopping the execution. The logic for adaptation is implemented at design time and cannot be changed during runtime. As an example, a monitor agent can realize that an adaptation is required since a request cannot be satisfied due to the production rate going below a threshold, etc.

3.2.2 Design

A wide range of possible changes is defined: the roles played by agents, the number of agents playing a role, the parameter related to an obligation, etc. When an adaptation is required, the organization manager is able to invite adaptation expert agents to propose design solutions. These agents are in charge of providing a plan of changes that modifies the current organization into a new organization. The plan of changes is composed by individual events such as adding a specific role, a mission, etc. Thus, the design phase can also be implemented in a distributed way.

3.2.3 Selection

In the case that several designs are proposed for adaptation, the organization manager is mainly responsible for carrying out the selection of the changes to finally be implemented according to the own methods of this manager. The main problem is to define the criteria for selecting the most promising proposal, which could be carried out individually by the organization manager or also in a distributed way with the participation of other agents. As an example, in [46], a voting system between experts is used to determine the design that is finally going to be implemented. In [45], a Q-learning algorithm is used to find out the decision policy, which is used in the selection phase. The selection implemented in the examples provided considers designs with the most promising improve in the benefits caused in the agents involved in the change. Some costs are also considered such as the number of roles that are required to be changed.

3.2.4 Evaluation

An evaluation phase is not explictly defined in the Moise adaptation approach. However, since the historian agent maintains information of the organization life-span, specific information about the successful performance of the organization that is achieved after adaptation, can be used by the organization manager for future adaptations [46]. There is no support for measuring how the organization has been carried out in order to estimate the success of future adaptation processes. Again, the use of agents to support these phases makes the approach so general that specific solutions must be implemented by the agent designer.

Note that, this adaptation approach provides great flexibility and can be used in a wide range of applications since individual agents are in charge of carrying out the adaptation phases. Different methods can be implemented at the agent level depending on the domain. Constraints regarding the monitoring, design, and selection phases are defined according the application requirements. Since several agents may participate in the monitoring, design, and selection phases, different mechanisms can be used to provide heterogeneous design solutions and also to select these solutions, such as case-based reasoning, learning, negotiation, etc. [1, 25]. However, this flexibility can become a drawback since specific methods are not provided by the adaptation approach itself to carry out these phases. Specifically, methods for designing solutions are not provided since they are assumed to be under the control of the adaptation expert agents. If this behavior is implemented at design time, the information regarding how the organization is performing at runtime cannot be included. Moreover, methods for measuring the goodness of an adaptation are not provided by the Moise adaptation approach. This goodness should be represent the impact that the adaptation would cause in the organization (direct and indirect benefits and costs) and the costs for applying the adaptation. This support must be implemented at the application level. As an example, in [46], three criteria are chosen for selecting a solution: the experience of each expert in past adaptations, the success of the proposals of each expert in past adaptations (which are obtained by the Historian agent), and the cost of the proposal in terms of global costs related to how many missions and roles would be deleted if the proposal is implemented.

The concept of plan of changes provided by adaptation expert agents has two main advantages. The first advantage is that defines step by step how the organization specification should be changed. Thus, when an expert proposes a plan of changes, implementation issues also have to be dealt with (add the role \(r_x\) and afterward remove the role \(r_y\), remove the role \(r_y\) and afterward add the role \(r_x\)). The second advantage is the possibility of changing only some part of the organization.

As a general conclusion, we consider that the Moise adaptation approach has the advantage that since many agents are used to provide the different phases of the adaptation process, many different adaptation solutions can be used, and, therefore, a better adaptation decision can be taken. However, the main disadvantage of this approach is that all the adaptation phases must be implemented at the agent level. Thus, the agent designer must provide his own methods and tools for the specific application.

3.3 Self-organization in task-solving environments

Kota et al. propose a self-organization approach that is mainly focused on task-solving environments (TSEs) [53–55] (Table 3). Specifically, this approach has the following properties: the adaptation process is continuous, is carried out internally, and has no central control. The society model used in this approach consists of an organization of cooperative agents that are in a TSE. Agents receive tasks, execute actions, and return a result. A TSE presents a dynamic stream of tasks that have to be performed. These tasks require services to be processed, which are provided by agents. Agents need to interact with one another in order to access services provided by other agents. In order to do this, the agents are connected with each other according to different levels of relationships: acquaintance, peer, and superior-subordinate. These relationships define the structural topology of the organization.

Table 3 Adaptation phases in TSEs
Full size table

In this approach, adaptation consists of a process that changes the structural topology of the society in order to increase the performance. These type of structural changes is a common adaptation in other kind of general networks [41, 78]. The TSE approach is aimed at enabling each pair of agents to continuously and autonomously evaluate (and change if required) their relationships based on past interactions.

3.3.1 Monitoring

Adaptation phases are carried out in a distributed way by each pair of agents. The monitoring phase is proactively carried out by each pair of agents, which evaluate their relationship by taking into account their history of interactions. The internal logic for adaptation is provided at design time. The information that is monitored is used on-line without stopping the execution and is also specified on-line since it depends on the relationships of each agent at a specific moment.

Apart from this proactive adaptation, a reactive adaptation is also supported. Agents can enter or exit the organization and can change their capabilities at predefined times. When these events occur, an adaptation is reactively triggered. Similarly to the proactive adaptation, the changes allowed to overcome these situations are related to the agent relationships. When an agent enters the organization, it needs to be related to other agent/s. In this case, the adaptation is carried out by evaluating the past interactions of the agent with other agents and predicting the utility with other agents that they have not previously have relationships with. An adaptation is also carried out reactively when an agent leaves the organization. With regard to behavioral adaptation, the gain or loss of services by agents is another kind of adaptation that is also considered. When this occurs, an adaptation is carried out by measuring the historical interactions of the agents involved in the process.

3.3.2 Design

Every pair of agents chooses actions to establish or dissolve their relationship in order to improve the utility function associated with this relationship. Based on their current relationship, different modifications (form peer, remove peer, form subordinate, remove subordinate) can be carried out. These represent different adaptation alternatives proposed in the design phase.

3.3.3 Selection

Each alternative of relationship modification has an associate utility function that is calculated as the expected benefits and costs associated with this alternative. Each pair of agents selects and implements the modification that maximizes the utility function of their relationship. Specific mechanisms are provided for evaluating the performance of the organization at each time step of the organization’s life-span. On the one hand, organization cost defines the resources consumed by agents in terms of messages that are sent in the whole organization. On the other hand, benefits define the speed of each agent for completing its tasks. The organization performance is measured as the difference between the benefits and costs.

The cost measurement for carrying out the adaptation is specified for each agent in terms of a communication cost, which represents the adaptation costs. Furthermore, the impact of changing a relationship between a pair of agents is measured by taking into account the tasks that would or would not been assigned to other agents if a relationship is modified. This impact is associated with an increase or decrease in the tasks received by these other agents. However, a reflexive impact that measures the indirect costs and benefits caused to other agents is not represented. This impact should be related to how a relationship modification between a pair of agents can affect the agents that are not involved in the change, that is, how these agents could allocate their own tasks if a relationship between different agents is modified. This issue is a consequence of the distributed adaptation process. Since adaptation phases are carried out for each peer, the expected benefits and costs obtained are related to the information that is known by the pairs involved in the change. Therefore, if several adaptations are carried out simultaneously between different pairs, the estimated costs and benefits might not be realistic since the structural topology may be different.

3.3.4 Evaluation

In this approach there is not an specific evaluation provided for measuring the proposal or the adaptation process. However, the performance of the future state of the organization that is achieved after adaptation is considered for future adaptations, that is, this evaluates which is the performance of the relationship after each modification.

The self-adaptive way of the TSE approach avoids a centralized implementation that could become a bottleneck. Nevertheless, since the process is not viewed from the organization perspective, the impact of each modification could be more difficult to measure than in centralized approaches, since every pair of agents does not have information about how other agents would adapt their relationship. As an example, if agents \(a_x\) and \(a_y\) form a relationship, several tasks could be allocated directly. However, other agents could also use this relationship to delegate tasks, causing an overload in \(a_x\) and \(a_y\) that would not be considered in the computation.

An adaptation viewed from the organization perspective would provide adaptation decisions that can be measured more consistently, since all the information required for adaptation is known by the whole organization. The impact associated with a relationship modification can be measured not only from the tasks that would not be allocated to other agents but also from the tasks that these other agents would allocate by taking into account this relationship modification. A distributed adaptation would provide more scalability, which would allow the applicability of the approach to problems that are composed by large agent organizations. However, more efforts have to be done in order to keep the consistence of the system when several adaptations are carried out simultaneously.

A disadvantage of this approach is that it is specifically constrained to structural adaptation and TSEs. Structural adaptation allow agents to reorganize their interactions in order to improve the utility of the whole organization. However, if other modifications were considered (e.g., changing the services provided by agents or changing the agent population in order to improve the performance), this utility might be improved since a wide range of alternatives would be considered. To the extent that we analyzed this approach, this model does not provide enough flexibility to incorporate adaptations for different dimensions. One of the main advantages of this approach is the detailed computation of the adaptation consequences, at least for the agents involved in the relationship modification. This approach provides a specific detailed measurement of the benefits and some of the costs of the adaptation such as the cost of sending messages and changing relationships. Even though, the measurement is provided at the model level, the model is focused on specific applications related to this domain, making it difficult to extend these definitions to other applications.

3.4 Autonomic electronic institutions

Autonomic electronic institutions (AEIs) [12, 13] (Table 4) provide a paradigm for adapting the regulations of Electronic Institutions in order to accomplish institutional goals. In general, AEI involves the following elements: agents playing roles within scenes in a so-called performative structure, which defines the behavior of agents according to their role; goals, which are reached through interactions among agents; and norms, which specify the regulations of the system.

Table 4 Adaptation phases in AEIs
Full size table

3.4.1 Monitoring

The monitoring phase is implemented in a proactive way, in which several institutional agents are involved. These agents are able to detect situations such as an adaptation requirement due to a norm has been violated. The information that is required to be monitored is specified off-line but it is used on-line. The logic for adaptation is predefined at design time.

3.4.2 Design

The design phase is implemented in a centralized way by the institution itself.  The changes that are considered are related to normative and structure adaptation. On the one hand, normative adaptation refers to changing the pre-conditions of a norm, its effects, or both. Since each norm is represented as a set of parameters, changing a norm is aimed at changing the values of these parameters. On the other hand, performative structure adaptation refers to changing the number of agents playing a role within each scene.

3.4.3 Selection

The institution explores the space of parameter values in order to find the configuration that provides the best degree of satisfaction of institutional goals. After obtaining which are the values that provide the best degree of satisfaction of institutional goals, these values are set by the institution. A domain-dependent fitness function is defined to measure the degree of goal accomplishment; therefore, the objective of adaptation is to better accomplish these goals. As an example, in [13], an adaptation over a traffic scenario is proposed. In this example, goals are defined as a multi-attribute function that takes into account the number of accidents, the number of traffic offenses, and so on. Each time step, the AEI simulates different configurations for the penalties and institutional agents by using a learning model. In this scenario, norm adaptation is related to changing the penalties that are applied to cars that do not follow norms, while performative structure adaptation is related to changing the number of institutional agents in charge of detecting norm violations.

Costs for adaptation are not considered in AEIs. An agent of the AEI has an associated type of maintenance cost that limits the population of agents according to the benefits that these agents provide. However, this model does not incorporate mechanisms for measuring the impact (measured in terms of costs and benefits) of modifying a norm or the costs for carrying out the adaptation process. These mechanisms would provide more accurate simulations that consider not only the best performing configuration but also the best performing configuration by taking into account the costs of applying this configuration.

3.4.4 Evaluation

With regard to the evaluation phase, this adaptation approach do not incorporate mechanisms to measure how an adaptation has been carried out. However, in [14], they propose the use of case-based reasoning by the institution, in order to apply similar adaptation proposals under similar adaptation requirements. Even though this technique allows the prediction of the AEI with specific configurations, it does not measure how the adaptation process is carried out.

3.5 2-LAMA

The two level assisted MAS architecture (2-LAMA) [17, 18] (Table 5) is another approach that provides support for adaptation. This approach was first based on the AEI approach and then was extended to fit a more general model of organization. The organization in this approach is composed of a social structure that consists of a set of roles, groups, and the relationships among agents playing certain roles that belong to certain groups, social conventions that are expressed as interaction protocols and norms, and goals that describe the purpose of the organization.

Adaptation in the 2-LAMA approach is aimed at improving the accomplishment of the goals, for example, by modifying a norm.

Table 5 Adaptation phases in 2-LAMA
Full size table

3.5.1 Monitoring

Adaptation in the 2-LAMA approach can be reactive since several events occur (e.g., if an agent enters the organization), but it can also be proactive (e.g., if a norm is considered to be adapted in order to improve the accomplishment of the organization goals). Monitoring is carried out in a distributed way between assistant agents. The information required to be retrieved is specified off-line but it is used on-line without stopping the execution. The logic for adaptation is predefined at design time. Each assistant is in charge of managing the adaptation of a subset of agents. During the monitoring phase, each assistant perceives partial information about a cluster of agents and this information is shared with other assistants in order to take the decisions.

3.5.2 Design

After the monitoring phase, each assistant provides an adaptation proposal for each different component’s related function based on the information available and the system goals. This corresponds to a distributed design phase.

Several adaptation functions are defined for updating the specific social structure and the norms of the organization. These adaptation functions evaluate the current organization in order to modify the specific components.

3.5.3 Selection

The assistants vote to select the adaptation, which is selected by agreement and implemented in a distributed way. Several criteria are used to select the specific changes in the 2-LAMA approach. As an example, in [18], assistant agents integrate two different methods based on heuristics and case-based reasoning. This approach considers adaptation costs (in time and/or resources) that should be taken into account in order to decide the adaptation frequency. Costs are computed by each assistant and are classified into different categories such as the cost of collecting the information required, the cost associated with the time and resources that are required to compute the adaptation function, or the adaptation cost of transforming the organization into the adapted one. Costs define the minimal frequency required to keep the costs below the benefits that the adaptation generates. Otherwise, a higher frequency would cause a higher associated cost and, therefore, the adaptation may not be worth it.

However, these costs are not considered in the design nor in the selection phases. As we stated above, the driving force behind the adaptation is the accomplishment of the goals. Therefore, changes are introduced with the aim of inducing greater accomplishment of the current goals regardless of the costs, as long as these take into account the adaptation frequency. As an example, in peer-to-peer scenarios [18, 80], a social structure adaptation is carried out through modifications of relationships between peers with the aim of creating the optimal network composed by the paths with the shortest latencies. However, these modifications could have associated costs that would make it more profitable to adapt to a sub-optimal network that has an associated lower cost to be adapted to. Even though it is assumed that the adaptation frequency keeps costs below benefits, there is no support for achieving the adaptation with the highest tradeoff between costs and benefits.

3.5.4 Evaluation

With regard to the evaluation phase, the 2-LAMA approach does not provide mechanisms for evaluating the degree of success of the adaptation process. However, similar to the AEI approach, the 2-LAMA approach in [18] presents an example in which assistants use case-based reasoning for proposing an adaptation solution that is based on past experience. This kind of solution has been also extended to regulate the norms of dynamic systems [66].

One of the main advantages of this adaptation approach is the support for specifying the utilities for each individual component. Heterogeneous agents can be defined since different communication capacities are defined for each peer. Furthermore, each link between a pair of agents has its own associated communication capacity, which is determined by its bandwidth. Another advantage is the consideration of different dimensions of the organization to be adapted. However, support for jointly considering changes on different dimensions simultaneously should be required.

3.6 MACODO

MACODO (middleware architecture for context-driven dynamic agent organizations) [82] (Table 6) is a middleware that provides support for the management of organization adaptation. The organizational model used in this approach is composed by agents, capabilities, roles, and laws. Capabilities are viewed as agent abilities to perform tasks. A set of capabilities is required to play a role. Finally, laws describe the dynamic adaptation of organizations and define the consistence of the system.

Table 6 Adaptation phases in MACODO
Full size table

3.6.1 Monitoring

Adaptation is reactively triggered by external events (e.g., when an agents stops playing a role) and changes in the environment (e.g., when the traffic state in the viewing range of an agent that collaborates in a traffic monitoring organization changes). Adaptation purposes are specified by means of two kinds of laws: intra-organization adaptation laws, which describe how agents can join and leave the organization (join and leave laws); and inter-organization adaptation laws, which describe the restructuring of organizations by merging and splitting organizations (merge and split laws).

A master controller agent is defined as being responsible for managing the dynamics of each organization in a centralized way. Each master controller enforces the laws that are related to the intra-organization adaptation of its organization (i.e., those that define when agents join or leave the organization). This describes the monitoring phase, which determines that an adaptation is required when a law is satisfied. The logic for adaptation is defined at design time. The information required by the master controller is specified off-line but it is used on-line.

Inter-organization adaptation requires information about more than one organization in order to enforce laws. In this kind of adaptation, masters of multiple organizations need to collaborate in a distributed monitoring phase. Each master exchanges a summary of the information regarding its organization with neighboring masters. Similar to intra-organization adaptation, the monitoring phase is implemented through laws. As an example, when a merge law is satisfied in both organizations, a negotiation is initiated between the master of each organization involved in the merge in order to select the new master of the merged organization.

3.6.2 Design

Once an intra-organization adaptation is required, the master controller is in charge of designing the adaptation solution. In the case of inter-organization adaptation, a master is selected, which carries out the actions required for the adaptation, completing the design phase. As we stated above, the changes that are supported are regarding open system support and structural adaptation.

3.6.3 Selection

The master controller that is responsible of the adaptation design, is also in charge of selecting and implementing this, which is finally carried out by updating the information regarding the organization.

In [82], a traffic example is presented to show the behavior of the middleware. In this example, master controllers decide to merge organizations when a traffic jam has arisen in the streets that they observe. Due to the environment change, agents decide to merge organizations because laws specify this condition. When the congestion starts to dissolve, agents split up the organization based on the split law. Therefore, we consider that the criteria is focused on accomplishing the organization goals when some change occurs.

In MACODO, a cost is related to communications, which is associated to the cost for merging and splitting organizations. This cost is used to evaluate the performance of the middleware. However, this cost is not taken into account to decide that an adaptation is required or to design the adaptation. As we stated above, adaptation is automatically caused when a law is triggered.

Event though a single master controller is in charge on carrying out the adaptation once it is required, we consider that phases can be also carried out in a distributed way because organizations can be viewed as sub-organizations since they can be merged. In this sense, master controllers are able to detect an adaptation requirement based on laws.

3.6.4 Evaluation

With regard to the evaluation phase, the MACODO approach does not provide mechanisms for incorporating information about the degree of success after an adaptation is carried out. Even though laws allow the organization to be adapted, these laws are defined at design time and cannot be modified depending on the information at runtime.

3.7 MAGIQUE

The approach implemented in the MAGIQUE platform [60, 61, 72] (Table 7) provides an adaptation mechanism that focus on two kinds of adaptation: individual adaptation and social adaptation. The agent society model defines an organization composed by agents, which are able to provide skills and can interact to each other according to the relationships structure, which defines the links between agents.

Table 7 Adaptation phases in MAGIQUE
Full size table

In this approach adaptation is viewed as a mechanism for improving the interaction between agents, which improves the system’s performance. The underlying adaptation mechanism is based on changing the relationships structure and the distribution of skills between agents in order to reduce the number of messages that are exchanged in the system, and the time necessary for processing a request. It is assumed that the overall system performance is an aggregation of the performance of individual agents. Therefore, if the performance of an agent increases, this does not negatively affect other agents of the system.

3.7.1 Monitoring

Monitoring in this approach is carried out in a distributed way since every agent is capable of deciding when an adaptation is required. In the current implementation, the monitoring strategy is reactive. Adaptation rules, which are specified by using thresholds, are used to trigger adaptation. These rules are predefined at design time. The information that is monitored is specified off-line but it is used on-line.

3.7.2 Design

After deciding that an adaptation is required, the design is autonomously carried out by each agent involved in the process. The elements that are considered to be changed are the relationships between agents (called acquaintances), the skills provided by agents (that can be mapped as the services that they provide), and the population of the system (by including new agents which can, in addition, learn specific skills). The decision of creating relationships and acquiring skills depends on policies that are specified by the system designer.

3.7.3 Selection

When an agent with the capabilities of designing an adaptation has carried out the design, this is automatically selected and implemented by using the API provided. The code mobility is used for learning skills.

The criteria used for selection is mainly focused on improving the benefits of the agent involved in the change, which is assumed to improve the overall performance of the whole organization as well. Therefore, indirect benefits and costs are not taken into account. In addition, there is not a model which provides support for defining the benefits that are associated with the adaptation, and this logic must be implemented by the user designer using his own metrics and techniques.

3.7.4 Evaluation

Regarding evaluation phase, there is not any kind of support for measuring how the adaptation has been carried out, except from those techniques that the agent designer implements by himself at agent level.

The main disadvantage of this approach is that the adaptation phases must be implemented by the system designer according to his own techniques and methodologies. As we stated above, a reactive monitoring is provided. However, adaptation could be considered to be carried out in a proactive way if the agent designer implements an underlying reasoning mechanism at agent level. In addition, if the adaptation is taken individually without considering indirect benefits and costs, this may cause different consequences as expected. In the examples given by the authors, the agent designer should consider how the addition of a link can affect other agents (these agents may take in turn some advantage or disadvantage that is not considered).

3.8 Adaptation in agent-organized networks

Gaston and DesJardins [34] (Table 8) propose an adaptation approach for agent-organized networks (AONs) that is based on an agent team formation model. This model provides a dynamic environment in which agents form teams in a distribute way in order to accomplish the tasks that are received in the network. The society model defines an AON as a set of agents, which represent the nodes of the network, relationships between agents, which represent the adjacency matrix of the network, and skills, which are assigned to be provided by agents in order to perform tasks.

The adaptation that is considered in this approach is focused on allowing agents to modify their current relationships in order to improve the performance. Agents use local information in order to decide which links to delete and which to create.

Table 8 Adaptation phases in AONs
Full size table

3.8.1 Monitoring

Monitoring is carried out in a distribute way by any agent of the network. The monitoring strategy is proactive since each agent decides whether or not to adapt its links, according to its reasoning mechanism, which in the work [34] is based on a probability indicator. As agents remove their links and add new ones, we can consider that the information that is monitored can be specified on-line depending on the current set of links. In contrast, the adaptation logic (which is referred to the performance measurement) is predefined at design time.

3.8.2 Design

Once an agent has decided that an adaptation is required, this agent is in charge of designing the adaptation. In the AON, this is referred at deciding which link is removed and which link is added, based on estimations of performance increase. Therefore, the design is also distributed. As we stated above, the elements that are allowed to be changed in this approach are the relationships between agents, which correspond to an structural adaptation.

3.8.3 Selection

After the design is proposed, this is automatically selected and implemented. The criteria used for this selection is based on the improvement of the performance, which is measured as the percentage of tasks for which teams successfully form. This improvement does not take into account how the link modification would affect other elements of the organization. As the same authors state, each agent has only a partial vision of the system and therefore, it is not possible to know all the information and how a change would influence. This model could be applied in scenarios in which an individual performance increase would be directly related to an organizational performance increase. The costs related to the application of the changes and to the reasoning process are not considered.

3.8.4 Evaluation

In this adaptation model, there is not a support for evaluation. The same authors present in [16] an evaluation model for improving the team joining process. In this work, authors embedded agents in fixed network structures and focus on learning team joining policies. These policies improve the aggregate performance of the network. However, this learning model does not consider adaptation (modifications in the agent relationships). A similar learning approach would be interesting in order to select or predict the effect in the whole organization of adding and removing relationships, by defining policies for creating and deleting relationships.

One of the main problems of taking adaptation decisions that are based on local information is, as the authors claim, that local information provides a partial view of the system that may cause to take incorrect decisions, which cause an organizational performance decrease. In addition, if two agents decide to change their relationships simultaneously, the adaptation benefit could not finally be as it was expected.

3.9 Comparison

Based on the analysis carried out, we summarize the main features of the analyzed approaches in Table 9. This table shows the different phases of the adaptation life-cycle based on the parameters defined in Sect. 2.

Table 9 Comparison of adaptation approaches
Full size table

4 Discussion and open challenges

Given the analysis detailed in Sect. 3, there are some considerations that could be of great interest in future developments. We point out some of these issues below.

4.1 Monitoring

Detecting the adaptation requirement is a crucial phase for adaptive agent societies. There are some approaches that implement monitoring strategies as predefined rules that are triggered when some specified change occurs (OMACS, MACODO). Other approaches provide this phase through evaluations of the performance in time intervals during the organization life-cycle (TSEs), or also when a condition is accomplished such as in the 2-LAMA approach. Nevertheless, the rules that regulate the adaptation requirement are usually predefined at design time and cannot be changed while the organization is running. This forces designing systems in which the requirements for determining the adaptation must be known in advance, preventing the development of applications in which these requirements are not specifically known or which could even be different throughout the organization’s life-span. Furthermore, the useful information required to be monitored in this phase is also usually specified off-line, before running the system.

It would be interesting for the next generation of adaptive agent societies to have support that allow the dynamic specification of the rules that trigger a reactive adaptation. As stated in [3], adaptive systems may cause monitoring requirements to also change. Thus, dynamic support that can adapt to these changes becomes essential in order to develop real adaptive agent societies. As an example, in the proposed workshop management system, a reactive adaptation can be required when an agent reviewer exits the system, which requires a reallocation of its assigned papers to other reviewers. However, this can be dependent (and also change) of execution factors. As an example, a restriction could be added at runtime which causes to not reallocate the specific paper if it has already two reviews. This support would provide more flexibility to dynamic systems, specially in scenarios in which is difficult to specify at design time the logic for adaptation.

Furthermore, this support should also consider changes in the relevant information that monitored. Thus, depending on the changing requirements of the system, the information required can change throughout the agent society’s life-span. Static mechanisms that do not consider changes regarding which information needs to be monitored may result useful in small application domains with a priori well-known organizational structures, but they would not be suitable for large-scale or complex systems. As the number of agents in the society and their complexity grows, much more information is exchanged between agents. Most of this information could be not useful at every moment of the execution and only contributes to considerably increase the traffic in the system, specifically in approaches in which a middleware or centralizing entity is the responsible of adaptation deliberation or implementation. Therefore, an adaptive approach should apply not only to the behavior and structure of the system but also to the design of the monitoring system [71], specially when dealing with the management of complex systems over long periods of time.

4.2 Design

We have shown that several dimensions that we identified in Sect. 2.3 are separately covered by current approaches. This fact can be viewed through how this phase is implemented in each approach. Some of the current works focus on problems that approach adaptation in its functional dimension such as the OMACS approach, which changes the assignment of agents to roles. Other approaches deal with problems that require structural changes such as the works related with TSEs, AONs, or MAGIQUE. Other approaches such as AEI or 2-LAMA are specialized in changes in the regulations of the system. Note that there is not much open system support provided by current approaches, and what there is is usually part of the other adaptation support. As an example, the MACODO approach considers agents that can enter or leave the organization along with a support for inter-organizational adaptation.

All the surveyed approaches cover changes in different dimensions separately. However, we identified a lack of support in current approaches for behavior and specification adaptation. This means that the skills of agents are static and are not considered to evolve over time within the agent society context. In other words, agents are not able to learn new capabilities or to degrade the utility of the capabilities that they offer. The MAGIQUE approach considers code mobility as the learning mechanism. However, this support must be provided at agent level by the agent designer. Furthermore, agent societies are not able to acquire new functionalities by means of the emergence of new roles (for example, as combinations of skills) or the deletion of old roles that are not effective.

As an example, in the workshop management system, this support would allow to develop systems in which reviewers are able to change the topics in which their are experts depending on the reviews. What is more, the dynamicity in the capabilities provided by agents may cause that new capabilities can emerge, for example, a new topic which represents the interdisciplinary work of two trending topics.

As stated in [59], building systems with emergent behavior capabilities is important for increasing the robustness, autonomy, openness, and dynamism of the system. The application of some interesting principles adopted by human systems may facilitate the development of new models and mechanisms for agent societies that support the evolution of agent capabilities as well as the capabilities of the society. This could require using team learning or concurrent learning techniques to provide agents with the capabilities of discovering behaviors of other agents in the context of agent society [70].

Another remarkable consideration should be made regarding the support for a simultaneous adaptation in diferent dimensions. Most of the current approaches usually focus on changes in a specific dimension of the agent society such as the roles played by agents, the relationships between agents, or the norms of the system. However, few approaches consider several dimensions to be adapted at the same time. As an example, in the workshop management example, this would provide support to evaluate the tradeoff between adding new reviewers due to the high number of submissions, or reallocating all the submissions among the current reviewers. This support should consider the benefits and costs of each alternative.

Adaptation in agent societies usually involves changes that are focused on different dimensions such as organizing structures, coordination mechanisms, or work practices [5, 69]. Therefore, adaptation should consider different dimensions in order to increase the range of adaptation possibilities. In this line, the 2-LAMA approach provides an interesting view of adaptation since several dimensions can considered for adaptation. Even though adaptation in the work of [18] is only considered for structural and normative dimensions, the assistance layer provided by this approach would increase the number of dimensions considered for adaptation. However, adaptation in different dimensions should require a greater level of integration. In the current implementation of 2-LAMA, these changes are not considered simultaneously. Norm adaptation is considered at specific intervals of time, and structural adaptation is only considered each time an agent has completed a reception. Thus, the 2-LAMA approach would need to provide support for evaluating changes in different dimensions simultaneously and not at different moments with no dependence.

This implementation would require a greater level of integration between all the changes that can occur and their consequences. Thus, adaptation in several dimensions requires evaluating the interdependences of changes that could be applied simultaneously. As an example, a norm modification can influence a structural adaptation and vice-versa. The Moise approach can consider changes regarding different dimensions. However, the delegation of design and selection phases to individual agents limits this approach to methodologies provided by the designer.

Therefore, adaptation decisions that are dependent on several dimensions would require more complex deliberation processes that assess the suitability of the adaptation. Future adaptation approaches should provide a higher level of integration between changes in different dimensions and their interdependence.

4.3 Selection

With regard to the criteria used to estimate the adaptation suitability, we observe that costs related to adaptation have not usually been taken into account to take adaptation decisions. As stated in [30], an adaptation process should provide some kind of increase in utility. However, as far as we are concerned, this utility should take into account not only the gain in utility but also the costs of carrying out the adaptation. Some approaches do consider certain costs; however, these costs are not accurately estimated. One of the approaches that provides a measurement of several implications of a change is the approach of TSEs. This approach measures the impact of changing a relationship between a pair of agents not only in terms of benefits but also in terms of some costs. Thus, this approach evaluates how the load of agents can be changed depending on the relationship modification. However, as we stated in Sect. 3.3, since the adaptation approach is completely carried out in a distributed way by each pair of agents, the estimation of the implications that a change could cause in the rest of the population of agents is difficult to measure. Only the tasks related to the agents involved in the change that would or would not be delivered to other agents are considered. In the 2-LAMA framework, several costs are also considered for adaptation. However, these costs are only used to define the adaptation frequency. This approach would require considering the adaptation impact for selecting the adaptation.

As we have shown, current approaches usually assume that a relationship modification between a pair of agents or a change in the role played by an agent do not have implications in the rest of the population and can be carried out without requiring additional costs (time, resources, etc.) [13, 27, 60]. However, as in human societies, not every change in an agent society has the same implications in terms of costs or has the same impact in the whole society.

As an example, in the workshop management system, this is referred as considering not only the benefits of adding reviewers into the society, or reallocating the papers assigned, or creating a new role. This refers to also consider how changes affect other elements of the society in terms of benefits and costs. As an example, the reallocation of a paper to the most confident reviewer of this topic may cause several reallocations that are negative for the society. All of these positive and negative impacts along with other costs that are associated with how much time requires to carry out each reallocation could be represented by cost-aware approaches.

Therefore, it would be interesting for future approaches to provide mechanisms that use metrics for an accurate evaluation of the adaptation implications (positive and negative). These evaluations should consider not only the agents involved in the change but also how a change can influence the performance of the rest of the agents of the society, as well as the costs associated with carrying out the adaptation process itself.

4.4 Evaluation

The adaptation phase that has probably received the least attention by researchers is the evaluation phase. It is a general assumption by theorists of human societies that these societies learn from experience by means of the changes that take place in their history [38, 52, 58]. Similarly, the importance of evaluating the adaptation process seems to be clear in agent societies. Feedback provides important information about whether changes have been implemented as intended. This is important for agent societies to be able to develop responses that reuse old solutions to problems [38, 50].

Current approaches do not invest very much effort in evaluating the adaptation process due to the difficulties associated with solving this problem. It is assumed that when the adaptation is carried out, the process is implemented as expected (without any setback or indirect consequences). Indeed, many approaches such as OMACS or MACODO concentrate on applying a solution to a problem, which is triggered by predefined rules, assuming that the adaptation solves the problem for which it was proposed and no revision of the mechanism that estimates the solution is required at execution time. Few approaches such as 2-LAMA consider that past information related to the adaptation decisions to be considered in the future. This approach uses case-based reasoning for deciding similar adaptation solutions to similar problems that were solved in the past. Nevertheless, an effective evaluation of the adaptation process is not provided by any approach. This effective evaluation should not only be useful to trigger the adaptation, but it should also adjust the parameters that estimate the adaptation consequences (in terms of benefits and costs) based on how the adaptation has been applied.

Information provided by the historian agent proposed by Moise in [46] is an interesting approach to determine which design solution is more suitable based on the performance of past design solutions. Although solutions to provide an effective evaluation may be dependents on the specific domain, more efforts are needed to better understand the adaptation life-cycle in order to incorporate information regarding the adaptation application in future adaptation considerations.

Related to the example of the workshop management system, a stronger evaluation support would determine whether or not the reallocation of a paper to another reviewer caused the benefits and costs as expected. If not, the system should learn in order to improve the prediction accuracy for future adaptations or could also adapt other elements (e.g., the society learns that when some paper reallocation is required, the notification deadline must be also extended).

In addition, the evaluation should also provide a feedback regarding the costs (time, resources, etc.) required to carry out the adaptation. Learning can also be applied to other dimensions of the evaluation. It can be difficult to predict the impact of a change in advance. However, information regarding how the estimation of similar changes was in the past could be useful to improve this prediction accuracy.

5 Conclusions

In this paper, we have analyzed some of the most relevant contributions related to adaptation in agent societies, detailing the adaptation models that were used as well as how this support is provided and implemented. The specification of each phase of the life-cycle of the adaptation process presented in Sect. 2 allows us to compare the different approaches according to what they provide and what they do not provide. We have analyzed in detail the most relevant approaches (OMACS, Moise, TSE, AEI, 2-LAMA, MACODO, MAGIQUE, and AON), offering a general overview of the different phases of the adaptation life-cycle.

The criteria that we used to define the dimensions in Section 2 was based on properties that emerge from human organizations as well as properties that are defined by relevant works of the agents research area. More detailed properties could be found in specific phases, such as whether the cost is represented in a time domain or in a resource domain. Nevertheless, the objective of this classification was to provide a set of general parameters and dimensions that can be used to compare a wide range of approaches.

The short-term goal of this review paper is to provide a detailed analysis of the most relevant existing approaches, in order to show the advantages and limitations of each one. In addition, the open challenges that have been pointed out in Section 4 can help system designers in order to develop new frameworks and adaptation models to overcome the main limitations of current approaches. Some of these challenges can be highly dependent on the domain while other could be addressed to provide general solutions:

  • New monitoring approaches to support dynamic specification of the rules or methods that trigger an adaptation process as well as the dynamic specification of the information required to be analyzed during the monitoring phase.

  • New models that allow agents to dynamically change their capabilities within the context of the agent society. This support would be extended to emergent social behavior.

  • New design techniques that consider several dimensions to be adapted simultaneously in the adaptation process. This issue would require estimating the interdependence of changes in different dimensions.

  • New models that estimate a detailed measurement of the impact that a change has on the rest of the elements of the agent society. This impact should be measured not only in terms of benefits but also in term of costs.

  • New evaluation support that measures the degree of success of an adaptation once it has been applied. This evaluation should consider how the adaptation has been carried out and how it improves the accuracy of the estimation.

In order to resolve some of these open issues, future research works are encouraged to invest their effort in this area of adaptation in agent societies. The final goal of these works should be to provide models, infrastructures, and tools that support adaptation through complex deliberation processes, which are able to predict the consequences of changes as well as to evaluate the quality of the process.