Organizational Self-Design in Semi-dynamic Environments Sachin Kamboj ∗ and Keith S. Decker Department of Computer and Information Sciences University of Delaware Newark, DE 19716 {kamboj, decker}@cis.udel.edu ABSTRACT Organizations are an important basis for coordination in multiagent systems. However, there is no best way to organize and all ways of organizing are not equally effective. Attempting to optimize an organizational structure depends strongly on environmental features including problem characteristics, available resources, and agent capabilities. If the environment is dynamic, the environmental conditions or the problem task structure may change over time. This precludes the use of static, design-time generated, organizational structures in such systems. On the other hand, for many real environments, the problems are not totally unique either: certain characteristics and conditions change slowly, if at all, and these can have an important effect in creating stable organizational structures. Organizational-Self Design (OSD) has been proposed as an approach for constructing suitable organizational structures at runtime. We extend the existing OSD approach to include worthoriented domains, model other resources in addition to only processor resources and build in robustness into the organization. We then evaluate our approach against the contract-net approach and show that our OSD agents perform better, are more efficient, and more flexible to changes in the environment. Categories and Subject Descriptors I.2.11 [Distributed Artificial Intelligence]: Multiagent systems General Terms Algorithms, Design, Performance, Experimentation 1. INTRODUCTION In this paper, we are primarily interested in the organizational design of a multiagent system - the roles enacted by the agents, ∗Primary author is a student the coordination between the roles and the number and assignment of roles and resources to the individual agents. The organizational design is complicated by the fact that there is no best way to organize and all ways of organizing are not equally effective [2]. Instead, the optimal organizational structure depends both on the problem at hand and the environmental conditions under which the problem needs to be solved. The environmental conditions may not be known a priori, or may change over time, which would preclude the use of a static organizational structure. On the other hand, all problem instances and environmental conditions are not always unique, which would render inefficient the use of a new, bespoke organizational structure for every problem instance. Organizational Self-Design (OSD) [4, 10] has been proposed as an approach to designing organizations at run-time in which the agents are responsible for generating their own organizational structures. We believe that OSD is especially suited to the above scenario in which the environment is semi-dynamic as the agents can adapt to changes in the task structures and environmental conditions, while still being able to generate relatively stable organizational structures that exploit the common characteristics across problem instances. In our approach (as in [10]), we define two operators for OSD - agent spawning and composition - when an agent becomes overloaded, it spawns off a new agent to handle part of its task load/responsibility; when an agent lies idle for an extended period of time, it may decide to compose with another agent. We use TÆMS as the underlying representation for our problem solving requests. TÆMS [11] (Task Analysis, Environment Modeling and Simulation) is a computational framework for representing and reasoning about complex task environments in which tasks (problems) are represented using extended hierarchical task structures [3]. The root node of the task structure represents the high-level goal that the agent is trying to achieve. The sub-nodes of a node represent the subtasks and methods that make up the highlevel task. The leaf nodes are at the lowest level of abstraction and represent executable methods - the primitive actions that the agents can perform. The executable methods, themselves, may have multiple outcomes, with different probabilities and different characteristics such as quality, cost and duration. TÆMS also allows various mechanisms for specifying subtask variations and alternatives, i.e. each node in TÆMS is labeled with a characteristic accumulation function that describes how many or which subgoals or sets of subgoals need to be achieved in order to achieve a particular higherlevel goal. TÆMS has been used to model many different problemsolving environments including distributed sensor networks, information gathering, hospital scheduling, EMS, and military planning. [5, 6, 3, 15]. The main contributions of this paper are as follows: 1. We extend existing OSD approaches to use TÆMS as the underlying problem representation, which allows us to model and use OSD for worth-oriented domains. This in turn allows us to reason about (1) alternative task and role assignments that make different quality/cost tradeoffs and generate different organizational structures and (2) uncertainties in the execution of tasks. 2. We model the use of resources other than only processor resources. 3. We incorporate robustness into the organizational structures. 2. RELATED WORK The concept of OSD is not new and has been around since the work of Corkill and Lesser on the DVMT system[4], even though the concept was not fully developed by them. More recently Dignum et. al.[8] have described OSD in the context of the reorganization of agent societies and attempt to classify the various kinds of reorganization possible according to the the reason for reorganization, the type of reorganization and who is responsible for the reorganization decision. According to their scheme, the type of reorganization done by our agents falls into the category of structural changes and the reorganization decision can be described as shared command. Our research primarily builds on the work done by Gasser and Ishida [10], in which they use OSD in the context of a production system in order to perform adaptive work allocation and load balancing. In their approach, they define two organizational primitives - composition and decomposition, which are similar to our organizational primitives for agent spawning and composition. The main difference between their work and our work is that we use TÆMS as the underlying representation for our problems, which allows, firstly, the representation of a larger, more general class of problems and, secondly, quantitative reasoning over task structures. The latter also allows us to incorporate different design-to-criteria schedulers [16]. Horling and Lesser [9] present a different, top-down approach to OSD that also uses TÆMS as the underlying representation. However, their approach assumes a fixed number of agents with designated (and fixed) roles. OSD is used in their work to change the interaction patterns between the agents and results in the agents using different subtasks or different resources to achieve their goals. We also extend on the work done by Sycara et. al.,[13] on Agent Cloning, which is another approach to resource allocation and load balancing. In this approach, the authors present agent cloning as a possible response to agent overload - if an agent detects that it is overloaded and that there are spare (unused) resources in the system, the agent clones itself and gives its clone some part of its task load. Hence, agent cloning can be thought of as akin to agent spawning in our approach. However, the two approaches are different in that there is no specialization of the agents in the formerthe cloned agents are perfect replicas of the original agents and fulfill the same roles and responsibilities as the original agents. In our approach, on the other hand, the spawned agents are specialized on a subpart of the spawning agent"s task structure, which is no longer the responsibility of the spawning agent. Hence, our approach also deals with explicit organization formation and the coordination of the agents" tasks which are not handled by their approach. Other approaches to OSD include the work of So and Durfee [14], who describe a top-down model of OSD in the context of Cooperative Distributive Problem Solving (CDPS) and Barber and Martin [1], who describe an adaptive decision making framework in which agents are able to reorganize decision-making groups by dynamically changing (1) who makes the decisions for a particular goal and (2) who must carry out these decisions.The latter work is primarily concerned with coordination decisions and can be used to complement our OSD work, which primarily deals with task and resource allocation. 3. TASK AND RESOURCE MODEL To ground our discussion of OSD, we now formally describe our task and resource model. In our model, the primary input to the multi-agent system (MAS) is an ordered set of problem solving requests or task instances, < P1, P2, P3, ..., Pn >, where each problem solving request, Pi, can be represented using the tuple < ti, ai, di >. In this scheme, ti is the underlying TÆMS task structure, ai ∈ N+ is the arrival time and di ∈ N+ is the deadline of the ith task instance1 . The MAS has no prior knowledge about the task ti before the arrival time, ai. In order for the MAS to accrue quality, the task ti must be completed before the deadline, di. Furthermore, every underlying task structure, ti, can be represented using the tuple < T, τ, M, Q, E, R, ρ, C >, where: • T is the set of tasks. The tasks are non-leaf nodes in a TÆMS task structure and are used to denote goals that the agents must achieve. Tasks have a characteristic accumulation function (see below) and are themselves composed of other subtasks and/or methods that need to be achieved in order to achieve the goal represented by that task. Formally, each task Tj can be represented using the pair (qj, sj), where qj ∈ Q and sj ⊂ (T ∪ M). For our convenience, we define two functions SUBTASKS(Task) : T → P(T ∪ M) and SUPERTASKS(TÆMS node) : T ∪ M → P(T), that return the subtasks and supertasks of a TÆMS node respectively2 . • τ ∈ T, is the root of the task structure, i.e. the highest level goal that the organization is trying to achieve. The quality accrued on a problem is equal to the quality of task τ. • M is the set executable methods, i.e., M = {m1, m2, ..., mn}, where each method, mk, is represented using the outcome distribution, {(o1, p1), (o2, p2), ..., (om, pm)}. In the pair (ol, pl), ol is an outcome and pl is the probability that executing mk will result in the outcome ol. Furthermore, each outcome, ol is represented using the triple (ql, cl, dl), where ql is the quality distribution, cl is the cost distribution and dl is the duration distribution of outcome ol. Each discrete distribution is itself a set of pairs, {(n1, p1), (n2, p2), ..., (nn, pn)}, where pi ∈ + is the probability that the outcome will have a quality/cost/duration of nl ∈ N depending on the type of distribution and Pm i=1 pl = 1. • Q is the set of quality/characteristic accumulation functions (CAFs). The CAFs determine how a task group accrues quality given the quality accrued by its subtasks/methods. For our research, we use four CAFs: MIN, MAX, SUM and EXACTLY ONE. See [5] for formal definitions. • E is the set of (non-local) effects. Again, see [5] for formal definitions. • R is the set of resources. • ρ is a mapping from an executable method and resource to the quantity of that resource needed (by an agent) to schedule/execute that method. That is ρ(method, resource) : M × R → N. 1 N is the set of natural numbers including zero and N+ is the set of positive natural numbers excluding zero. 2 P is the power set of set, i.e., the set of all subsets of a set The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) 1229 • C is a mapping from a resource to the cost of that resource, that is C(resource) : R → N+ We also make the following set of assumptions in our research: 1. The agents in the MAS are drawn from the infinite set A = {a1, a2, a3, ...}. That is, we do not assume a fixed set of agents - instead agents are created (spawned) and destroyed (combined) as needed. 2. All problem solving requests have the same underlying task structure, i.e. ∃t∀iti = t, where t is the task structure of the problem that the MAS is trying to solve. We believe that this assumption holds for many of the practical problems that we have in mind because TÆMS task structures are basically high-level plans for achieving some goal in which the steps required for achieving the goal-as well as the possible contingency situations-have been pre-computed offline and represented in the task structure. Because it represents many contingencies, alternatives, uncertain characteristics and runtime flexible choices, the same underlying task structure can play out very differently across specific instances. 3. All resources are exclusive, i.e., only one agent may use a resource at any given time. Furthermore, we assume that each agent has to own the set of resources that it needseven though the resource ownership can change during the evolution of the organization. 4. All resources are non-consumable. 4. ORGANIZATIONAL SELF DESIGN 4.1 Agent Roles and Relationships The organizational structure is primarily composed of roles and the relationships between the roles. One or more agents may enact a particular role and one or more roles must be enacted by every agent. The roles may be thought of as the parts played by the agents enacting the roles in the solution to the problem and reflect the long-term commitments made by the agents in question to a certain course of action (that includes task responsibility, authority, and mechanisms for coordination). The relationships between the roles are the coordination relationships that exist between the subparts of a problem. In our approach, the organizational design is directly contingent on the task structure and the environmental conditions under which the problems need to be solved. We define a role as a TÆMS subtree rooted at a particular node. Hence, the set (T ∪ M) encompasses the space of all possible roles. Note, by definition, a role may consist of one or more other (sub-) roles as a particular TÆMS node may itself be made up of one or more subtrees. Hence, we will use the terms role, task node and task interchangeably. We, also, differentiate between local and managed (non-local) roles. Local roles are roles that are the sole responsibility of a single agent, that is, the agent concerned is responsible for solving all the subproblems of the tree rooted at that node. For such roles, the agent concerned can do one or more subtasks, solely at its discretion and without consultation with any other agent. Managed roles, on the other hand, must be coordinated between two or more agents as such roles will have two or more descendent local roles that are the responsibility of two or more separate agents. Any of the existing coordination mechanisms (such as GPGP [11]) can be used to achieve this coordination. Formally, if the function TYPE(Agent, TÆMS Node) : A×(T ∪ M) → {Local, Managed, Unassigned}, returns the type of the responsibility of the agent towards the specified role, then TYPE(a, r) = Local ⇐⇒ ∀ri∈SUBTASKS(r)TYPE(a, ri) = Local TYPE(a, r) = Managed ⇐⇒ [∃a1∃r1(r1 ∈ SUBTASKS(r)) ∧ (TYPE(a1, r1) = Managed)] ∨ [∃a2∃a3∃r2∃r3(a2 = a3) ∧ (r2 = r3) ∧ (r2 ∈ SUBTASKS(r)) ∧ (r3 ∈ SUBTASKS(r)) ∧ (TYPE(a2, r2) = Local) ∧ (TYPE(a3, r3) = Local)] 4.2 Organization Formation and Adaptation To form or adapt their organizational structure, the agents use two organizational primitives: agent spawning and composition. These two primitives result in a change in the assignment of roles to the agents. Agent spawning is the generation of a new agent to handle a subset of the roles of the spawning agent. Agent composition, on the other hand, is orthogonal to agent spawning and involves the merging of two or more agents together - the combined agent is responsible for enacting all the roles of the agents being merged. In order to participate in the formation and adaption of an organization, the agents need to explicitly represent and reason about the role assignments. Hence, as a part of its organizational knowledge, each agent keeps a list of the local roles that it is enacting and the non-local roles that it is managing. Note that each agent only has limited organizational knowledge and is individually responsible for spawning off or combining with another agent, as needed, based on its estimate of its performance so far. To see how the organizational primitives work, we first describe four rules that can be thought of as the organizational invariants which will always hold before and after any organizational change: 1. For a local role, all the descendent nodes of that role will be local. TYPE(a, r) = Local =⇒ ∀ri∈SUBTASKS(r)TYPE(a, ri) = Local 2. Similarly, for a managed (non-local) role, all the ascendent nodes of that role will be managed. TYPE(a, r) = Managed =⇒ ∀ri∈SUPERTASKS(r)∃ai(ai ∈ A) ∧ (TYPE(ai, ri) = Managed) 3. If two local roles that are enacted by two different agents share a common ancestor, that ancestor will be a managed role. (TYPE(a1, r1) = Local) ∧ (TYPE(a2, r2) = Local)∧ (a1 = a2) ∧ (r1 = r2) =⇒ ∀ri∈(SUPERTASKS(r1)∩SUPERTASKS(r2))∃ai(ai ∈ A)∧ (TYPE(ai, ri) = Managed) 4. If all the direct descendants of a role are local and the sole responsibility of a single agent, that role will be a local role. ∃a∃r∀ri∈SUBTASKS(r)(a ∈ A) ∧ (r ∈ (T ∪ M))∧ (TYPE(a, ri) = Local) =⇒ (TYPE(a, r) = Local) When a new agent is spawned, the agent doing the spawning will assign one or more of its local roles to the newly spawned agent (Algorithm 1). To preserve invariant rules 2 and 3, the spawning agent will change the type of all the ascendent roles of the nodes assigned to the newly spawned agent from local to managed. Note that the spawning agent is only changing its local organizational knowledge and not the global organizational knowledge. At the 1230 The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) same time, the spawning agent is taking on the task of managing the previously local roles. Similarly, the newly spawned agent will only know of its just assigned local roles. When an agent (the composing agent) decides to compose with another agent (the composed agent), the organizational knowledge of the composing agent is merged with the organizational knowledge of the composed agent. To do this, the composed agent takes on the roles of all the local and managed tasks of the composing agent. Care is taken to preserve the organizational invariant rules 1 and 4. Algorithm 1 SpawnAgent(SpawningAgent) : A → A 1: LocalRoles ← {r ⊆ (T ∪ M) | TYPE(SpawningAgent, r)= Local} 2: NewAgent ← CREATENEWAGENT() 3: NewAgentRoles ← FINDROLESFORSPAWNEDAGENT (LocalRoles) 4: for role in NewAgentRoles do 5: TYPE(NewAgent, role) ← Local 6: TYPE(SpawningAgent, role) ← Unassigned 7: PRESERVEORGANIZATIONALINVARIANTS() 8: return NewAgent Algorithm 2 FINDROLESFORSPAWNEDAGENT (SpawningAgentRoles) : (T ∪ M) → (T ∪ M) 1: R ← SpawningAgentRoles 2: selectedRoles ← nil 3: for roleSet in [P(R) − {φ, R}] do 4: if COST(R, roleSet) < COST(R, selectedRoles) then 5: selectedRoles ← roleSet 6: return selectedRoles Algorithm 3 GETRESOURCECOST(Roles) : (T ∪ M) → 1: M ← (Roles ∩ M) 2: cost ← 0 3: for resource in R do 4: maxResourceUsage ← 0 5: for method in M do 6: if ρ(method, resource) > maxResourceUsage then 7: max ← ρ(method, resource) 8: cost ← cost + [C(resource) × maxResourceUsage] 9: return cost 4.2.1 Role allocation during spawning One of the key questions that the agent doing the spawning needs to answer is - which of its local-roles should it assign to the newly spawned agent and which of its local roles should it keep to itself? The onus of answering this question falls on the FINDROLESFORSPAWNEDAGENT() function, shown in Algorithm 2 above. This function takes the set of local roles that are the responsibility of the spawning agent and returns a subset of those roles for allocation to the newly spawned agent. This subset is selected based on the results of a cost function as is evident from line 4 of the algorithm. Since the use of different cost functions will result in different organizational structures and since we have no a priori reason to believe that one cost function will out-perform the other, we evaluated the performance of three different cost functions based on the following three different heuristics: Algorithm 4 GETEXPECTEDDURATION(Roles) : (T ∪ M) → N+ 1: M ← (Roles ∩ M) 2: exptDuration ← 0 3: for [outcome =< (q, c, d), outcomeProb >] in M do 4: exptOutcomeDuration ← 0 5: for (n,p) in d do 6: exptOutcomeDuration ← n × p 7: exptDuration ← exptDuration + [exptOutcomeDuration × outcomeProb] 8: return exptDuration Allocating top-most roles first: This heuristic always breaks up at the top-most nodes first. That is, if the nodes of a task structure were numbered, starting from the root, in a breadth-first fashion, then this heuristic would select the local-role of the spawning agent that had the lowest number and breakup that node (by allocating one of its subtasks to the newly spawned agent). We selected this heuristic because (a) it is the simplest to implement, (b) fastest to run (the role allocation can be done in constant time without the need of a search through the task structure) and (c) it makes sense from a human-organizational perspective as this heuristic corresponds to dividing an organization along functional lines. Minimizing total resources: This heuristic attempts to minimize the total cost of the resources needed by the agents in the organization to execute their roles. If R be the local roles of the spawning agent and R be the subset of roles being evaluated for allocation to the newly spawned agent, the cost function for this heuristic is given by: COST(R, R ) ← GETRESOURCECOST(R − R )+GETRESOURCECOST(R ) Balancing execution time: This heuristic attempts to allocate roles in a way that tries to ensure that each agent has an equal amount of work to do. For each potential role allocation, this heuristic works by calculating the absolute value of the difference between the expected duration of its own roles after spawning and the expected duration of the roles of the newly spawned agent. If this difference is close to zero, then the both the agents have roughly the same amount of work to do. Formally, if R be the local roles of the spawning agent and R be the subset of roles being evaluated for allocation to the newly spawned agent, then the cost function for this heuristic is given by: COST(R, R ) ← |GETEXPECTEDDURATION(R−R )−GETEXPECTEDDURATION(R )| To evaluate these heuristics, we ran a series of experiments that tested the performance of the resultant organization on randomly generated task structures. The results are given in Section 6. 4.3 Reasons for Organizational Change As organizational change is expensive (requiring clock cycles, allocation/deallocation of resources, etc.) we want a stable organizational structure that is suited to the task and environmental conditions at hand. Hence, we wish to change the organizational structure only if the task structure and/or environmental conditions change. Also to allow temporary changes to the environmental conditions to be overlooked, we want the probability of an organizational change to be inversely proportional to the time since the last organizational change. If this time is relatively short, the agents are still adjusting to the changes in the environment - hence the probability of an agent initiating an organizational change should be high. Similarly, if the time since the last organizational change is relatively large, we wish to have a low probability of organizational change. To allow this variation in probability of organizational change, we use simulated annealing to determine the probability of keepThe Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) 1231 ing an existing organizational structure. This probability is calculated using the annealing formula: p = e− ΔE kT where ΔE is the amount of overload/underload, T is the time since the last organizational change and k is a constant. The mechanism of computing ΔE is different for agent spawning than for agent composition and is described below. From this formula, if T is large, p, or the probability of keeping the existing organizational structure is large. Note that the value of p is capped at a certain threshold in order to prevent the organization from being too sluggish in its reaction to environmental change. To compute if agent spawning is necessary, we use the annealing equation with ΔE = 1 α∗Slack where α is a constant and Slack is the difference between the total time available for completion of the outstanding tasks and the sum of the expected time required for completion of each task on the task queue. Also, if the amount of Slack is negative, immediate agent spawning will occur without use of the annealing equation. To calculate if agent composition is necessary, we again use the simulated annealing equation. However, in this case, ΔE = β ∗ Idle Time, where β is a constant and Idle Time is the amount of time for which the agent was idle. If the agent has been sitting idle for a long period of time, ΔE is large, which implies that p, the probability of keeping the existing organizational structure, is low. 5. ORGANIZATION AND ROBUSTNESS There are two approaches commonly used to achieve robustness in multiagent systems: 1. the Survivalist Approach [12], which involves replicating domain agents in order to allow the replicas to take over should the original agents fail; and 2. the Citizen Approach [7], which involves the use of special monitoring agents (called Sentinel Agents) in order to detect agent failure and dynamically startup new agents in lieu of the failed ones. The advantage of the survivalist approach is that recovery is relatively fast, since the replicas are pre-existing in the organization and can take over as soon as a failure is detected. The advantages of the citizen approach are that it requires fewer resources, little modification to the existing organizational structure and coordination protocol and is simpler to implement. Both of these approaches can be applied to achieve robustness in our OSD agents and it is not clear which approach would be better. Rather a thorough empirical evaluation of both approaches would be required. In this paper, we present the citizen approach as it has been shown by [7], to have a better performance than the survivalist approach in the Contract Net protocol, and leave the presentation and evaluation of the survivalist approach to a future paper. To implement the citizen approach, we designed special monitoring agents, that periodically poll the domain agents by sending them are you alive messages that the agents must respond to. If an agent fails, it will not respond to such messages - the monitoring agents can then create a new agent and delegate the responsibilities of the dead agent to the new agent. This delegation of responsibilities is non-trivial as the monitoring agents do not have access to the internal state of the domain agents, which is itself composed of two components - the organizational knowledge and the task information. The former consists of the information about the local and managerial roles of the agent while the latter is composed of the methods that are being scheduled and executed and the tasks that have been delegated to other agents. This state information can only be deduced by monitoring and recording the messages being sent and received by the domain agents. For example, in order to deduce the organizational knowledge, the monitoring agents need to keep a track of the spawn and compose messages sent by the agents in order to trigger the spawning and composition operations respectively. The deduction process is particularly complicated in the case of the task information as the monitoring agents do not have access to the private schedules of the domain agents. The details are beyond the scope of this paper. 6. EVALUATION To evaluate our approach, we ran a series of experiments that simulated the operation of both the OSD agents and the Contract Net agents on various task structures with varied arrival rates and deadlines. At the start of each experiment, a random TÆMS task structure was generated with a specified depth and branching factor. During the course of the experiment, a series of task instances (problems) arrive at the organization and must be completed by the agents before their specified deadlines. To directly compare the OSD approach with the Contract Net approach, each experiment was repeated several times - using OSD agents on the first run and a different number of Contract Net agents on each subsequent run. We were careful to use the same task structure, task arrival times, task deadlines and random numbers for each of these trials. We divided the experiments into two groups: experiments in which the environment was static (fixed task arrival rates and deadlines) and experiments in which the environment was dynamic (varying arrival rates and/or deadlines). The two graphs in Figure 1, show the average performance of the OSD organization against the Contract Net organizations with 8, 10, 12 and 14 agents. The results shown are the averages of running 40 experiments. 20 of those experiments had a static environment with a fixed task arrival time of 15 cycles and a deadline window of 20 cycles. The remaining 20 experiments had a varying task arrival rate - the task arrival rate was changed from 15 cycles to 30 cycles and back to 15 cycles after every 20 tasks. In all the experiments, the task structures were randomly generated with a maximum depth of 4 and a maximum branching factor of 3. The runtime of all the experiments was 2500 cycles. We tested several hypotheses relating to the comparative performance of our OSD approach using the Wilcoxon Matched-Pair Signed-Rank tests. Matched-Pair signifies that we are comparing the performance of each system on precisely the same randomized task set within each separate experiment. The tested hypothesis are: The OSD organization requires fewer agents to complete an equal or larger number of tasks when compared to the Contract Net organization: To test this hypothesis, we tested the stronger null hypothesis that states that the contract net agents complete more tasks. This null hypothesis is rejected for all contract net organizations with less than 14 agents (static: p < 0.0003; dynamic: p < 0.03). For large contract net organizations, the number of tasks completed is statistically equivalent to the number completed by the OSD agents, however the number of agents used by the OSD organization is smaller: 9.59 agents (in the static case) and 7.38 agents (in the dynamic case) versus 14 contract net agents3 . Thus the original hypothesis, that OSD requires fewer agents to 3 These values should not be construed as an indication of the scalability of our approach. We have tested our approach on organizations with more than 300 agents, which is significantly greater than the number of agents needed for the kind of applications that we have in mind (i.e. web service choreography, efficient dynamic use of grid computing, distributed information gathering, etc.). 1232 The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) Figure 1: Graph comparing the average performance of the OSD organization with the Contract Net organizations (with 8, 10, 12 and 14 agents). The error bars show the standard deviations. complete an equal or larger number of tasks, is upheld. The OSD organizations achieve an equal or greater average quality than the Contract Net organizations: The null hypothesis is that the Contract Net agents achieve a greater average quality. We can reject the null hypothesis for contract net organizations with less than 12 agents (static: p < 0.01; dynamic: p < 0.05). For larger contract net organizations, the average quality is statistically equivalent to that achieved by OSD. The OSD agents have a lower average response time as compared to the Contract Net agents: The null hypothesis that OSD has the same or higher response time is rejected for all contract net organizations (static: p < 0.0002; dynamic: p < 0.0004). The OSD agents send less messages than the Contract Net Agents: The null hypothesis that OSD sends the same or more messages is rejected for all contract net organizations (p < .0003 in all cases except 8 contract net agents in a static environment where p < 0.02) Hence, as demonstrated by the above tests, our agents perform better than the contract net agents as they complete a larger number of tasks, achieve a greater quality and also have a lower response time and communication overhead. These results make intuitive sense given our goals for the OSD approach. We expected the OSD organizations to have a faster average response time and to send less messages because the agents in the OSD organization are not wasting time and messages sending bid requests and replying to bids. The quality gained on the tasks is directly dependent on the Criteria/Heuristic BET TF MR Rand Number of Agents 572 567 100 139 No-Org-Changes 641 51 5 177 Total-Messages-Sent 586 499 13 11 Resource-Cost 346 418 337 66 Tasks-Completed 427 560 154 166 Average-Quality 367 492 298 339 Average-Response-Time 356 321 370 283 Average-Runtime 543 323 74 116 Average-Turnaround-Time 560 314 74 126 Table 1: The number of times that each heuristic performed the best or statistically equivalent to the best for each of the performance criteria. Heuristic Key: BET is Balancing Execution Time, TF is Topmost First, MR is Minimizing Resources and Rand is a random allocation strategy, in which every TÆMS node has a uniform probability of being selected for allocation. number of tasks completed, hence the more the number of tasks completed, the greater average quality. The results of testing the first hypothesis were slightly more surprising. It appears that due to the inherent inefficiency of the contract net protocol in bidding for each and every task instance, a greater number of agents are needed to complete an equal number of tasks. Next, we evaluated the performance of the three heuristics for allocating tasks. Some preliminary experiments (that are not reported here due to space constraints) demonstrated the lack of a clear winner amongst the three heuristics for most of the performance criteria that we evaluated. We suspected this to be the case because different heuristics are better for different task structures and environmental conditions, and since each experiment starts with a different random task structure, we couldn"t find one allocation strategy that always dominated the other for all the performance criteria. To determine which heuristic performs the best, given a set of task structures, environmental conditions and performance criteria, we performed a series of experiments that were controlled using the following five variables: • The depth of the task structure was varied from 3 to 5. • The branching factor was varied from 3 to 5. • The probability of any given task node having a MIN CAF was varied from 0.0 to 1.0 in increments of 0.2. The probability of any node having a SUM CAF was in turn modified to ensure that the probabilities add up to 14 . • The arrival rate: from 10 to 40 cycles in increments of 10. • The deadline slack: from 5 to 15 in increments of 5. Each experiment was repeated 20 times, with a new task structure being generated each time - these 20 experiments formed an experimental set. Hence, all the experiments in an experimental set had the same values for the exogenous variables that were used to control the experiment. Note that a static environment was used in each of these experiments, as we wanted to see the performance of the arrival rate and deadline slack on each of the three heuristics. Also the results of any experiment in which the OSD organization consisted of a single agent ware culled from the results. Similarly, 4 Since our preliminary analysis led is to believe that the number of MAX and EXACTLY ONE CAFs in a task structure have a minimal effect on the performance of the allocation strategies being evaluated, we set the probabilities of the MAX and EXACTLY ONE CAFs to 0 in order to reduce the combinatorial explosion of the full factorial experimental design. The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) 1233 experiments in which the generated task structures were unsatisfiable (given the deadline constraints), were removed from the final results. If any experimental set had more than 15 experiments thus removed, the whole set was ignored for performing the evaluation. The final evaluation was done on 673 experimental sets. We tested the potential of these three heuristics on the following performance criteria: 1. The average number of agents used. 2. The total number of organizational changes. 3. The total messages sent by all the agents. 4. The total resource cost of the organization. 5. The number of tasks completed. 6. The average quality accrued. The average quality is defined as the total quality accrued during the experimental run divided by the sum of the number of tasks completed and the number of tasks failed. 7. The average response time of the organization. The response time of a task is defined as the difference between the time at which any agent in the organization starts working on the task (the start time) and the time at which the task was generated (the generation time). Hence, the response time is equivalent to the wait time. For tasks that are never attempted/started, the response time is set at final runtime minus the generation time. 8. The average runtime of the tasks attempted by the organization. This time is defined as the difference between the time at which the task completed or failed and the start time. For tasks that were never stated, this time is set to zero. 9. The turnaround time is defined as the sum of the response time and runtime of a task. Except for the number of tasks completed and the average quality accrued, lower values for the various performance criteria indicate better performance. Again we ran the Wilcoxon Matched-Pair Signed-Rank tests on the experiments in each of the experimental sets. The null hypothesis in each case was that there is no difference between the pair of heuristics for the performance criteria under consideration. We were interested in the cases in which we could reject the null hypothesis with 95% confidence (p < 0.05). We noted the number of times that a heuristic performed the best or was in a group that performed statistically better than the rest. These counts are given in Tables 1 and 2. The number of experimental sets in which each heuristic performed the best or statistically equivalent to the best is shown in Table 1. The breakup of these numbers into (1) the number of times that each heuristic performed better than all the other heuristics and (2) the number of times each heuristic was statistically equivalent to another group of heuristics, all of which performed the best, is shown in Table 2. Both of these tables allow us to glean important information about the performance of the three heuristics. Particularly interesting were the following results: • Whereas Balancing Execution Time (BET) used the lowest number of agents in largest number of experimental sets (572), in most of these cases (337 experimental sets) it was statistically equivalent to Topmost First (TF). When these two heuristics didn"t perform equally, there was an almost even split between the number of experimental sets in which one outperformed the other. We believe this was the case because BET always bifurcates the agents into two agents that have a more or less equal task load. This often results in organizations that have an even Figure 2: Graph demonstrating the robustness of the citizen approach. The baseline shows the number of tasks completed in the absence of any failure. number of agents - none of which are small5 enough to combine into a larger agent. With TF, on the other hand, a large agent can successively spawn off smaller agents until it and the spawned agents are small enough to complete their tasks before the deadlines - this often results in organizations with an odd number of agents that is less than those used by BET. • As expected, BET achieved the lowest number of organizational changes in the largest number of experimental sets. In fact, it was over ten times as good as its second best competitor (TF). This shows that if the agents are conscientious in their initial task allocation, there is a lesser need for organizational change later on, especially for static environments. • A particularly interesting, yet easily explainable, result was that of the average response time. We found that the Minimizing Resources (MR) heuristic performed the best when it came to minimizing the average response time! This can be explained by the fact the MR heuristic is extremely greedy and prefers to spawn off small agents that have a tiny resource footprint (so as to minimize the total increase in the resource cost to the organization at the time of spawning). Whereas most of these small agents might compose with other agents over time, the presence of a single small agent is sufficient to reduce the response time. In fact the MR heuristic is not the most effective heuristic when it comes to minimizing the resource-cost of the organization - in fact, it only outperforms a random task/resource allocation. We believe this is in part due to the greedy nature of this heuristic and in part because of the fact that all spawning and composition operations only use local information. We believe that using some non-local information about the resource allocation might help in making better decisions, something that we plan to look at in the future. Finally we evaluated the performance of the citizens approach to robustness as applied to our OSD mechanism (Figure 2). As expected, as the probability of failure increases, the number of agents failing during a run also increases. This results in a slight decrease in the number of tasks completed, which can be explained by the fact that whenever an agent fails, its looses whatever work it was doing at the time. The newly created agent that fills in for the failed 5 For this discussion small agents are agents that have a low expected duration for their local roles (as calculated by Algorithm 4). 1234 The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) Criteria/Heuristic BET TF MR Rand BET+TF BET+Rand MR+Rand TF+MR BET+TF+MR All Number of Agents 94 88 3 7 337 2 0 0 12 85 No-Org-Changes 480 0 0 29 16 113 0 0 0 5 Total-Messages-Sent 170 85 0 2 399 1 0 0 7 5 Resource-Cost 26 100 170 42 167 0 7 6 128 15 Tasks-Completed 77 197 4 28 184 1 3 9 36 99 Average-Quality 38 147 26 104 76 0 11 11 34 208 Average-Response-Time 104 74 162 43 31 20 16 8 7 169 Average-Runtime 322 110 0 12 121 13 1 1 1 69 Average-Turnaround-Time 318 94 1 11 125 26 1 0 7 64 Table 2: Table showing the number of times that each individual heuristic performed the best and the number of times that a certain group of statistically equivalent heuristics performed the best. Only the more interesting heuristic groupings are shown. All shows the number of experimental sets in which there was no statistical difference between the three heuristics and a random allocation strategy one must redo the work, thus wasting precious time which might not be available close to a deadline. As a part of our future research, we wish to, firstly, evaluate the survivalist approach to robustness. The survivalist approach might actually be better than the citizen approach for higher probabilities of agent failure, as the replicated agents may be processing the task structures in parallel and can take over the moment the original agents fail - thus saving time around tight deadlines. Also, we strongly believe that the optimal organizational structure may vary, depending on the probability of failure and the desired level of robustness. For example, one way of achieving a higher level of robustness in the survivalist approach, given a large numbers of agent failures, would be to relax the task deadlines. However, such a relaxation would result in the system using fewer agents in order to conserve resources, which in turn would have a detrimental effect on the robustness. Therefore, towards this end, we have begun exploring the robustness properties of task structures and the ways in which the organizational design can be modified to take such properties into account. 7. CONCLUSION In this paper, we have presented a run-time approach to organization in which the agents use Organizational Self-Design to come up with a suitable organizational structure. We have also evaluated the performance of the organizations generated by the agents following our approach with the bespoke organization formation that takes place in the Contract Net protocol and have demonstrated that our approach is better than the Contract Net approach as evident by the larger number of tasks completed, larger quality achieved and lower response time. Finally, we tested the performance of three different resource allocation heuristics on various performance metrics and also evaluated the robustness of our approach. 8. REFERENCES [1] K. S. Barber and C. E. Martin. Dynamic reorganization of decision-making groups. In AGENTS "01, pages 513-520, New York, NY, USA, 2001. [2] K. M. Carley and L. Gasser. Computational organization theory. In G. Wiess, editor, Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence, pages 299-330, MIT Press, 1999. [3] W. Chen and K. S. Decker. The analysis of coordination in an information system application - emergency medical services. In Lecture Notes in Computer Science (LNCS), number 3508, pages 36-51. Springer-Verlag, May 2005. [4] D. Corkill and V. Lesser. The use of meta-level control for coordination in a distributed problem solving network. Proceedings of the Eighth International Joint Conference on Artificial Intelligence, pages 748-756, August 1983. [5] K. S. Decker. Environment centered analysis and design of coordination mechanisms. Ph.D. Thesis, Dept. of Comp. Science, University of Massachusetts, Amherst, May 1995. [6] K. S. Decker and J. Li. Coordinating mutually exclusive resources using GPGP. Autonomous Agents and Multi-Agent Systems, 3(2):133-157, 2000. [7] C. Dellarocas and M. Klein. An experimental evaluation of domain-independent fault handling services in open multi-agent systems. Proceedings of the International Conference on Multi-Agent Systems (ICMAS-2000), July 2000. [8] V. Dignum, F. Dignum, and L. Sonenberg. Towards Dynamic Reorganization of Agent Societies. In Proceedings of CEAS: Workshop on Coordination in Emergent Agent Societies at ECAI, pages 22-27, Valencia, Spain, September 2004. [9] B. Horling, B. Benyo, and V. Lesser. Using self-diagnosis to adapt organizational structures. In AGENTS "01, pages 529-536, New York, NY, USA, 2001. ACM Press. [10] T. Ishida, L. Gasser, and M. Yokoo. Organization self-design of distributed production systems. IEEE Transactions on Knowledge and Data Engineering, 4(2):123-134, 1992. [11] V. R. Lesser et. al. Evolution of the gpgp/tæms domain-independent coordination framework. Autonomous Agents and Multi-Agent Systems, 9(1-2):87-143, 2004. [12] O. Marin, P. Sens, J. Briot, and Z. Guessoum. Towards adaptive fault tolerance for distributed multi-agent systems. Proceedings of ERSADS 2001, May 2001. [13] O. Shehory, K. Sycara, et. al. Agent cloning: an approach to agent mobility and resource allocation. IEEE Communications Magazine, 36(7):58-67, 1998. [14] Y. So and E. Durfee. An organizational self-design model for organizational change. In AAAI-93 Workshop on AI and Theories of Groups and Organizations, pages 8-15, Washington, D.C., July 1993. [15] T. Wagner. Coordination decision support assistants (coordinators). Technical Report 04-29, BAA, 2004. [16] T. Wagner and V. Lesser. Design-to-criteria scheduling: Real-time agent control. Proc. of AAAI 2000 Spring Symposium on Real-Time Autonomous Systems, 89-96. The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) 1235
organization coordination multiagent system organizational structure agent spawning composition task analysis environment modeling simulation robustness task and resource allocation
organizational self-design extended hierarchical task structure organizational-self design