On-demand service composition among autonomous self-interested software agents in open environments

Service-oriented computing (SOC) has evolved in recent years as a major paradigm for programming distributed software systems. SOC proposes a unified standards-based approach to leverage new levels of interoperability and automation to the implementation of business processes across heterogeneous applications and across organisational boundaries. The core principle of SOC is to enable business process automation through service composition, that is by combining several existing services into a new composite service. Although the concept of service composition is a core principle of SOC, it still requires more research to instantiate it. Prevailing service composition solutions in industry are workflow-driven. They are focused on ensuring full control over business processes at predictable costs. These benefits are, however, achieved at the expense of a major shortcoming: workflow-driven approaches are of rigid hard-coded nature. They typically utilise design-time service composition only, making resulting implementations vulnerable to unforeseen dynamic changes in the environment or to the business processes themselves. While workflow-driven approaches are suitable for application within a single organisation, more agile and flexible solutions are necessary for facilitating inter-organisational service composition, especially among autonomous peers with, in general, variable relationships and dependencies. These peers may experience volatile network conditions or leave and enter environments at will. Moreover, peers typically do not disclose their potentially conflicting private information and perform autonomous decentralised decisionmaking while competing for limited resources or collaborating to gain profits. The resulting complex environments spanned by such peers are known as open environments. They exhibit the characteristics of partial observability, non-determinism and dynamics, which together imply that no single peer can impose full control nor obtain complete knowledge at any time during the service composition process. The central problem addressed in this thesis is the dynamic composition of services in open environments which may evolve in a number of application scenarios, e.g. in volatile ad hoc and peer-to-peer networks or in dynamic on-demand e-business settings. Given its characteristics, the problem of dynamic service composition has been intensively studied by the software agent community because the concept of software agents provides a natural metaphor for modelling the aforementioned peers. Software agents are autonomous goal-oriented problem-solvers that interact based on decentralised reasoning and decision-making. A system of multiple software agents matches the characteristics of open environments due to agent autonomy and decentralisation and thus facilitates the modelling of dynamic service composition in open environments as agent-based collaborative problem-solving. This hypothesis forms the foundation of this thesis. A review of related agent-based approaches, however, reveals limitations in their applicability in open environments that usually result in closed systems despite the intrinsic similarities stressed above. The apparent gap stems from the absence of a universal software agent definition in general and the inconsistent use of a particular definition for modelling the fundamental building blocks of the software agent paradigm. Both problems are well known and have been repeatedly argued in related literature as major obstacles to a large-scale adoption of agent technology in industry. The aim of this thesis is to provide an agent-based approach to the problem of dynamic service composition in open environments according to a uniform software-engineeringlike definition and use of the fundamental building blocks of the software agent paradigm. The contributions of this thesis are: A detailed analysis of a concrete interpretation of the weak notion of agency and the subsequent derivation of a software agent component type that lays the foundation of a uniform agent-based software engineering approach. The resulting fundamental building blocks establish multiagent systems as open systems that exhibit the characteristics of open environments. They also utilise service-oriented design principles in support of a successful mapping of the problem of service composition in open environments into the software agent domain. The concept and design of a multiagent coalition formation framework models ondemand service composition in open environments as collaborative problem-solving in an open market. In this open market, supply and demand confront each other as equal-righted autonomous peers in the form of service consumer agents and service provider agents. The design of the respective multiagent system is influenced by a number of concepts such as decentralisation, on-demand service provision, selforganisation, emergence and market-based control; The implementation of the multiagent coalition formation framework facilitates coalition formation among service provider agents with lightweight interaction protocols and decentralised multi-attribute utility-based decision-making based on clientdefined quality-of-service (QoS) requirements and private preferences. It shapes an on-demand approach to dynamic service composition in open environments; A validation of the multiagent coalition formation framework is provided with a demo application for demonstrating dynamic service composition in the domain of travel planning; The experimental evaluation of the dynamic behaviour of the multiagent coalition formation process investigates non-functional properties such as termination, completeness, stability and scalability. It further identifies the conditions under which an optimal/good solution can be achieved despite the non-deterministic behaviour of interacting autonomous self-interested software agents; and A critical analysis of design and implementation issues of the multiagent coalition formation framework documents inherent difficulties and limitations of the software agent paradigm when based on the weak notion of agency. These shortcomings stem from the weak notion's complexity that is implied by the combination of characteristics of concurrent systems, real-time systems, asynchronous messaging, efficient message multicasting and local decision-making under uncertainty.