-One of the current challenges of Service tem for the composition and the orchestration of services Oriented Engineering is to provide instruments for dealing in a distributed and open environment. with dynamic and unpredictable environments and chang- MUSA aims at providing run-time modification of ing user requirements. Traditional approaches based on the flow of events, dynamic hierarchies of services and static workflows provide little support for adapting at run- integration of user preferences together with a selftimMe UthSeAflo w(Moifddalcetwivaitriees.for User-driven Service Adapta- adaptive system for execution activities that is also able tion) is a holonic multi-agent system for the self-adaptive to monitor unexpected failures and to reschedule in order composition and orchestration of services in a distributed to optimize the flow. environment. Self-adaptation is based on the intuition to break the static constraints of a classic workflow model by decouI. INTRODUCTION pling the 'what' (the outcome the workflow requires to be addressed) from the 'how' (the way this result can be obtained) [4].
In the last decade web-services have gained
industrywide acceptance as the universal standard for enterprise
application integration [
To date, BPEL is one of the most used standards for implementing the orchestration of services. Even if workflow-based languages are greatly supported by industry and research, their approach reveals being static and not easy to extend for supporting some advanced features as, for example, run-time modification of the flow of events, dynamic hierarchies of services, integration of user preferences and, moreover, it is not easy to provide a system for run-time execution, rescheduling and monitoring of activities that is also able to deal with unexpected failures and optimization.
Recently, the research community on services has been very active in defining techniques, methods and middleware for supporting dynamic execution model for workflows.
This paper presents MUSA (Middleware for Userdriven Service Adaptation) 1, a holonic multi-agent sys
user analyst coomnmtoiltomgeynt goal injection
POD GOALS
WHAT bridge ontology commitment dev team capability deploy and maintenance HOW service provider service provider service provider
TASKS
CAPABILITIES explicit in the system thus breaking the strict coupling A user-goal is a desired change in the state of among activities of the workflow; holonic system, for the world an actor wants to achieve. In the proposed implementing a dynamic and re-configurable architecture approach a goal describes the starting state and the final of autonomous and proactive agents.; self-adaptation, for states in terms of states of the world. It is therefore generating smart and dynamic plans as response to user- necessary to make a sharp distinction between BDI requests and to unpredictable events of the environment. goals and user-goals. A user-goal is injected into the
The whole system has been implemented by using system at run-time (and therefore it not known a-priori
JASON [
The running example used along the whole paper coded into the agent. Another difference is that an agent
concerns the domain of Travel Services. The system is automatically committed to fulfill all its BDI goals,
acts as a smart tour operator for composing simple whereas it owns a higher level of autonomy with respect
services provided in a local area as, for example, flights, to user-goals [
The papers is organized as follows: Section II dis- A goal model is a directed graph where nodes are cusses the languages for injecting goals and deploy- goals and edges are AND/OR Refinement or Influence ing capabilities into the system. Section III provides relationships. In a goal model there is exactly one root details about the dynamic and distributed architecture goal, and there are no refinement cycles. A goal model that emerges for addressing a user-request. Section IV is an analysts instrument to create dependencies among illustrates the core algorithm for allowing the agent to goals. reason on goals and capabilities and for creating plans. A capability describes a concrete trajectory in terms Finally, Section V reports some considerations about the of states of the world the system may intentionally use to approach. address a given result. Every agent knows its capabilities together with the way these can be employed. The effect II. DECOUPLING GOALS AND SERVICES of a capability is an endogenous evolution of the state of the world (a function that takes a state of world and produces a new state of world). The capability can be pursued only if a given pre-condition is true whereas the post-condition must be true after the capability has been successfully executed.
MUSA exploits BDI reasoning since it offers the required level of abstraction to build an autonomous and self-aware agent. In particular self-awareness is intended as the ability of agents to recognize their own capabilities (getting knowledge of their preconditions and effects), and to conduct some reasoning over them.
The Belief-Desire-Intention (BDI) model was developed
at the Stanford Research Institute during the activities of
the Rational Agency project [
In order to make the system able to reason on userrequests and available capabilities a solution is to elect goals and capabilities as first-class entities as it will be described in this section.
A state of the world is informally described as a set of non-contradictory first order facts with the assumption that everything that is not explicitly declared is assumed to be false. This is dynamically maintained by the agents of the system as the result of their perceptions and deductions.
In order to decouple user-goals from web-services,
MUSA provides GoalSPEC [
The core element of the metamodel is the Goal (desired by some subject). It is composed of a Trigger Condition and a Final State. The trigger condition is an event that must occur in order to start acting for addressing the goal. The final state is the desired state of the world that must be addressed. The Subject describes
TO VISIT PALERMO AT LEAST 2
DAYS
TO VISIT SICILY FOR 1 WEEK
AND
TO VISIT AGRIGENTO
TO VISIT SYRACUSE
AND TO VISIT GREEK TEMPLE
TO ATTEND
GREEK TRAGEDY agent_goal( %TO VISIT SICILY FOR 1 WEEK params( [curr_date] , [
category(curr_date, datetime)]), tr_condition( in(curr_date, date(2015,7,16), date(2015,7,23))), final_state( be_visiting(sicily) ), herbert ) ... agent_goal( %TO VISIT SYRACUSE params( [t] , [
category(t, integer)]), tr_condition( be_at(syracuse) ), final_state( and([visited(syracuse,t),
t>1] ), ) herbert b) the name of the involved person, role or group of persons that owns the responsibility to address the goal.
In the domain of the Travel Service, GoalSPEC allows the user to describe the kind of travel she desires. Examples of GoalSPEC productions are listed below:
visited(Palermo) OR visited(Catania)
DD < 20) THE user SHALL enjoyed(beach)
In AI, the need for representing software agent’s
actions in order to implement reasoning directed towards
action is a long-dated issue [
We use a ‘robotic-planning-like’ approach to address user-goals, in which the Capability is the internal representation of an atomic unit of work that a software agent may use for addressing changes in the state of the world. A Capability is made of two components: an abstract description (a set of beliefs that makes an agent aware of owning the capability and able to reason on its use), and a concrete implementation (a set of plans for executing the job).
We defined a template for providing the abstract
description of a capability as a refinement of that presented
in [
FLIGHT_BOOKING CAPABILITY
The template is made of the following elements: • Name is the unique label used to refer to the capability • InputParams is the definition of the input variables necessary for the execution. • OutputParams is the definition of the output variables produced by the execution. • Constraints is an optional (logical or structural) constraints on input/output variables. • Pre-Condition is a condition that must hold in the current state of the world in order to execute the capability. • Post-Condition is a condition that must hold in the final state of the world in order to assert the capability has been profitable. • Evolution is a function that describes how the capability will impact the state of the world as consequence of its execution.
By reasoning on the abstract side (input/output/precondition...) the agent may decide when to use the capability. An example of abstract description is provided in Table I.
On the other side, the concrete implementation encapsulates the code for interacting with the real service by using SOAP and WSDL through the HTTP/HTTPS protocol. The implementation of a capability for dealing web-services is made of three parts: the calculate evolution, the dispose service and the compensate service.
The calculate evolution protocol is used when composing the whole plan to address a goal; at this stage the agent has to configure the capability for a specific context. This means to establish input/output parameters to generate a contract with other agents it is collaborating with. More details will be in Section IV-B when illustrating the algorithm for the Goal/Capability Deliberation. For instance, the calculate evolution for the flight booking searches for flights (Figure 3) that are compatible with a given goal, i.e those flights that match with a given DptPlace, DptDate, ArrPlace and PassNumber.
The dispose service and the compensate service protocols will be used for orchestration and self-adaptation purposes (see Section IV-C).
After that a plan has been established for the execution, the orchestration phase generates, through the dispose service, the actual value for the user, i.e the usergoal fulfillment. For instance, the dispose protocol for the flight booking service actually book the specified flight and produces a ticket for the user.
However a plan may be subject to changes for several purposes. The Self-Adaptation Loop monitors for failures or new goals that may affect the running plan. When a plan changes at run-time, it could be the case that some services that have been disposed are no more useful in the new plan. The proper way to proceed is to use the compensate service protocol in order to terminate the contract with a service. For instance, the compensate service for the flight booking tries to cancel the user booking for a specified flight.
The previous sections have illustrated how goals and capabilities grounds on the state of the world and therefore, under the surface, they employ first-order predicates.
In MUSA the Problem Ontology Diagram (POD) [
An ontology is the specification of a conceptualization
made for the purpose of enabling knowledge sharing and
reuse [
This artifact aims at producing a set of concepts,
predicates and actions and at creating a semantic network
in which these elements are related to one another.
The representation is mainly human-oriented but it is
particularly suitable for developing cognitive system
that are able of storing, manipulating, reasoning on,
and transferring knowledge data directly in first-order
predicates [
Grounding goals and capability abstract description on the same ontology is fundamental to allow the system to adopt a proactive means-end reasoning to compose plans. By committing to the same ontology, capabilities and goals can be implemented and delivered by different development teams and at the same time enabling a semantic compatibility between them.
More details on the POD are in [
SELF-ADAPTATION
Holons provide an elegant and scalable method to guarantee knowledge sharing, distributed coordination and robustness.
Holon is a Greek term for indicating something that
is simultaneously a whole and a part [
A holon is a system (or phenomenon) which
is an evolving self-organizing structure,
consisting of other holons [
Many concrete things in nature are organized as a holarchy (the recursive structure generated by holons and sub-holons). An example of concrete holon is an organ that is a part of an organism, but a whole with regard to the cells of which it is comprised. The human mind uses holarchies for organizing abstract concepts too. An example is a word that is part of a sentence, but a whole with regard to the letters that compose it.
A holon has not necessarily the same properties of its parts, as well as if a bird can fly, its cells can not. Holon is therefore a general term for indicating a concrete or abstract entity that has its own individuality, but at the same time, it is embedded in larger wholes.
holon level N level N-1 level N-2
its larger wholes. And since a holon also contains parts, it is similarly influenced by, and influences these parts: information flows bidirectionally between smaller and larger systems.
The problem of service composition may be observed
as a phenomenon of holon formation [
A holonic multi agent system is a software system made of autonomous holons where the holon is defined recursively (see Figure 4). The holon at generic level N is made of holons a level N-1 kept together by a commitment relationship. The resulting structure is a holarchy, i.e. a hierarchical structure generated by holons and subholons where the base case is the agent representing the atomic holon (it is not further decomposable in subholons).
In MUSA the commitment function that glues together all the sub-holons to form a super-holon is given by the injected GoalSPEC. The user-goals represent the common objective that the holons have to address.
The holon formation is an emergent phenomenon. This section provides details about the static structure of each holon of the system whereas dynamic aspects of holon 2) it maintains the current state of the world, obtained formation and execution are given in Section IV. through the perception of all the sub-holons and
In MUSA all the agents are (atomic) holons, however it checks for the integrity of the holon structure aggregations of holons (in super-holons) may emerge at (verifying all sub-holons are active); run-time for managing composed services. A holarchy 3) even if each worker maintains its autonomy, the is formed as the recursive replication of the same basic head influences their activity i) by guaranteeing schema. This template defines that each holon of the their coordination and synchronization, or ii) by system may contain sub-holons playing one of the three deciding for the re-organization of the holon strucroles: service-broker, state-monitor or goal-handler. ture as a consequence of failures or unexpected
The service broker is the role in charge of establishing events.
a relationship with one or more end points of a remote
service. The candidate service-broker owns the capability IV. PROACTIVE MEANS-END REASONING
for managing the conversation with the party that pro- This section illustrates dynamic aspects of the
formavides the service (for example the flight booking shown tion of holons according to the structural rules specified
in Figure 3). The service broker must also be able to in Section III-A. The key for dynamically generating
catch exceptions and failures and to raise the need for holons is what we call Proactive Means-End
Reasonself-adaptation. ing [
The state monitor is the role responsible for monitor- autonomously decide how to combine their available ing the user environment (both physical and simulated, capabilities and therefore how to generate holons. including persons acting inside). The state of the world is an abstraction for the operative context in which services A. Goal Model Decomposition and Holon Formation are going to be provided. The perception of the state Section II-A has introduced the language for goal of the world is often necessary for invoking services. injection. However a goal is rarely injected into the This role is in charge of providing the service broker system as an isolated entity. More frequently the user with the configuration of input/output parameters for will use more goals to specify its request: a goal model, properly invoking a service. It is also responsible of i.e. a set of correlated goals to be injected at the same analyzing inconsistencies in the state of the world, due time. to unfeasible beliefs that could generate service failures. Given a goal model (G, R) where groot ∈ G is the top
The goal handler is responsible for the interpretation goal of the hierarchy, the Goal Model Decomposition of the GoalSPEC and for the recruitment of the service- algorithm explores the hierarchy, starting from groot brokers and state monitors to form a valid holon. The in a top-down fashion. The objective is to trigger the recruitment is based on a procedure called Means-End formation of one or more holons able to address the Reasoning (detailed in Section IV) in which service- root goal. The algorithm is recursive and it exploits brokers and state monitors are selected on the base AND/OR decomposition relationships to deduct a goal of capabilities they offer for addressing a desired state addressability by observing its sub-goals. of the world. During service execution, this role is We used δj and Δk = h.i to respectively denote a also responsible to check the goal life-cycle (active, single capability and a task. A task is generally provided addressed, failed). by a holon. We also introduce {.} to indicate a (complete
In terms of governance, the goal handler and each or partial) solution for addressing a generic goal gi where service broker and state monitor are simple workers, but the ‘dot’ is a placeholder for a list of tasks that can be at the moment of the holon formation the head of the alternatively used for the fulfillment of gi. holon is elected according to a mechanism of trust and An example of solution for a goal has the followreputation (that is out the scope of this paper). The head ing form: {hδ1, δ2, . . . , δni, hδ1, δ2, . . . , δmi} or the more has three supplementary responsibilities: compact: {Δ1, Δ2} where Δ1 = hδ1, δ2, . . . , δni and 1) it is responsible to represent the whole holon to Δ2 = hδ1, δ2, . . . , δmi. To address the goal the system the outside (other holons), thus if service-brokers can alternatively execute Δ1 or Δ2. and state monitors have been selected for a set Figure 5 illustrates how the three roles interact. Once of capabilities δ1, δ2, . . . then the head offers to a goal gi is injected, the goal-handler checks whether the the outside the composition of these capabilities goal is a leaf goal or not. If it is not then the goal-handler (namely a task) denoted as Δ = hδ1, δ2, . . .i); proceeds with a top-down recursive decomposition. For (goal handler) goal published [goal IS NOT leaf] loop [FOR EACH sub-goal]
DECOMPOSE goal
PUBLISH sub-goal each sub-goal, the goal-handler injects again it, marking the relationship to its parent. After that, the goal-handler waits for solutions for all the sub-goals, and then it organizes the composed solution for gi by triggering the corresponding holon formation.
• If the relationship is an AND decomposition the result is the permutation of all the solutions found for each child node. If gA is AND-decomposed in two sub-goals gB and gC , where {Δ1, Δ2} is the solution of gB and {Δ3} is the solution of gC , then the solution of gA is {hΔ1, Δ3i, hΔ2, Δ3i}. • If the relationship is an OR decomposition the result is the union of all the solutions found for each child node. If gA is OR-decomposed in two sub-goals gB and gC , where {Δ1, Δ2} is the solution of gB and {Δ3} is the solution of gC , then the solution of gA is {Δ1, Δ2, Δ3}.
Otherwise, if the goal is a leaf node of the goal model, then the Goal/Capability Deliberation sub-procedure is called.
The Goal/Capability Deliberation algorithm fronts the problem of combining more available capabilities from state-monitors and service-brokers for addressing a goal: given a initial state of the world, a set of capabilities and a goal, the problem is to discover a set of capabilities which composition may address the goal.
MUSA currently adopts an approach based on a search algorithm that simulates the formation of a holon and therefore the execution of various combinations of agent capabilities (see Figure 6). In this phase the servicebroker adopts the calculate evolution protocol of the capabilities it owns. This protocol allows the agent to customize the capability in order to establish if it can be used for the specific injected goal. For instance the flight booking capability is customized by searching a flight from a departure place to a destination in a given date/time (see Section II-B). When a complete solution is discovered the algorithm may still continue to search other solutions. It stops after the number of solutions is greater than NS (a system constant) or when time exceeds a threshold and returns all the discovered solutions.
Exploring all possible solutions for addressing a user- decentralized software, made of a number of autonomous goal is a NP-complete problem. The complexity is re- agents, each able to perceive the environment and to duced by putting some constraints during the exploration act as a broker for some web-services (of which it of the space of solutions. Colored zones of Figure 6 knows description, end points and business logic); and represent invalid solutions that can be discarded. In iii) holons are agents or (temporary) group of agents: addition, considering pre/post conditions, only a limited each with its own individuality. number of capabilities can be exploited at each step of Self-adaptiveness is the ability of the whole multithe algorithm, making the execution more scalable and agent system to dynamically adapt its behavior to the affordable. execution context. This is done by each individual agent,
The space exploration algorithm compares partial so- through the dynamical execution of its own capabilities, lutions thus to explore firstly the most promising ones, according to a shared plan and to contingent perceptions. according to the number of sub-goals that are already fulfilled and to a set of domain metrics indicating the gdloombaalinqmuaeltirtiycsoftosecrovniscied.erT, hfeoruisnesrtacnacne stpheecmifyaxwimhuicmh mrpeeraoasnaoscn-tiievnnegdholon-fomaticoonmsmocitiamlent budget or the kind of transportation to use. failure monitor goal injection capability execution environment execution cycle monitoring unexpected
state
In the domain of the Travel Services, the service execution has the duration of the user’s travel. Service
For a formal description of the Proactive Means-End broker will book all necessary flights, hotels, ticket
Reasoning details are provided in [
Going back to Figure 5, when one (or more) solutions in the user’s mobile device, acquires the user’s position, exist for the root goal of the injected goal model, then and it may also be used for changing the travel plan at one or more holons have been formed for addressing the run-time. goal model. One is selected for starting the activities and Self-Adaptation. Thanks to the work of stateeventually addressing the goals. The selection of a plan monitors, the head of the holon is continuously updated may follow many criteria. For instance in the domain of about the state of the services and it is able to discover the travel, the criterion we adopted is the total cost of when something is going wrong by comparing percepthe travel. tions with expected states of the world. When a service fails, or when a goal can not be addressed then the head C. The Self-Adaptation Loop role of the corresponding sub-holon raises an event of
So far the following assumptions holds: i) services are failure, that is cause of an adaptation. delivered over the internet by service providers; as usual, In the running example the adaptation is triggered these are accessible through standards protocols (i.e. by the user who modified her goals (by informing the WSDL and SOAP); ii) the system is a distributed and system to change the travel plan).
The adaptation is treated by the system as a reorganization of the holonic architecture. The reorganization produces a temporary dis-assembly of the holon and the re-execution of the Proactive Means-End Reasoning procedures but considering the new situation (failures, service availability or new user goals) for generating a new solution.
Before starting the new solution, each holon executes the compensate protocols of the capabilities that are no more in the new plan. After that the complete service orchestration activity starts again.
Holonic multi-agent systems provide a flexible and reconfigurable architecture to accommodate environment changes and user customization. MUSA is a middleware where the autonomous and proactive collaboration of autonomous agents allows a dynamic (re-)organization of the behavior in order to address user-requests and/or unexpected events. The novelty is that the desired service composition is encapsulated in run-time goal-models that, when injected into the system, trigger a spontaneous emergence of new holarchies devoted to orchestrate the required services.
MUSA have been employed for i) executing dynamic workflows in small/medium enterprises (IDS Project 2), ii) automatic mash-up of cloud applications (OCCP Project3, iii) merging protocols for emergency (SIGMA Project4).
algorithm for the means-end reasoning, 2) extending the goal language for including uncertainty and norms, 3) an automatic learning approach more robust to ontological discrepancies or language incoherence.
The research was funded by the Autonomous Region of Sicily, Project OCCP (Open Cloud Computing Platform), within the Regional Operative Plans (PO-FESR) of the EU Community.