The research described in this thesis stems from ROBOCARE1, a three year research project aimed at developing software and robotic technology for providing intelligent support for elderly people. This thesis deals with two problems which have emerged in the course of the project’s development: Multi-agent coordination with scarce resources. Multi-agent planning is concerned with automatically devising plans or strategies for the coordinated enactment of concurrently executing agents. A common realistic constraint in applications which require the coordination of multiple agents is the scarcity of resources for execution. In these cases, concurrency is affected by limited capacity resources, the presence of which modifies the structure of the planning/coordination problem. Specifically, the first part of this thesis tackles this problem in two contexts, namely when planning is carried out centrally (planning from first principles), and in the context of distributed multi-agent coordination. Domain modeling for scheduling applications. It is often the case that the products of research in AI problem solving are employed to develop applications for supporting human decision processes. Our experience in ROBOCARE as well as other domains has often called for the customization of prototypical software for real applications. Yet the gap between what is often a research prototype and a complete decision support system is seldom easy to bridge.The second part of the thesis focuses on this issue from the point of view of scheduling software deployment.Overall, this thesis presents three contributions within the two problems mentioned above. First, we address the issue of planning in concurrent domains in which the complexity of coordination is dominated by resource constraints. To this end, an integrated planning and scheduling architecture is presented and employed to explore the structural trademarks of multi-agent coordination problems in function of their resource-related characteristics. Theoretical and experimental analyses are carried out revealing which planning strategies are most fit for achieving plans which prescribe efficient coordination subject to scarce resources.We then turn our attention to distributed multi-agent coordination techniques (specifically, a distributed constraint optimization (DCOP) reduction of the coordination problem). Again, we consider the issue of achieving coordinated action in the presence of limited resources. Specifically, resource constraints impose n-ary relations among tasks. In addition, as the number of n-ary relations due to resource contention are exponential in the size of the problem, they cannot be extensionally represented in the DCOP representation of the coordination problem. Thus, we propose an algorithm for DCOP which retains the capability to dynamically post n-ary constraints during problem resolution in order to guarantee resource-feasible solutions. Although the approach is motivated by the multi-agent coordination problem, the algorithm is employed to realize a general architecture for n-ary constraint reasoning and posting.Third, we focus on a somewhat separate issue stemming from ROBOCARE, namely a software engineering methodology for facilitating the process of customizing scheduling components in real-world applications. This work is motivated by the strong applicative requirements of ROBOCARE. We propose a software engineering methodology specific to scheduling technology development. Our experience in ROBOCARE as well as other application scenarios has fostered the development of a modeling framework which subsumes the process of component customization for scheduling applications. The framework aims to minimize the effort involved in deploying automated reasoning technology in practise, and is grounded on the use of a modeling language for defining how domain-level concepts are grounded into elements of a technology-specific scheduling ontology.

代理者（Agent）是一個自主性的軟體程式，可以幫助代表人類在網際網路上從事各種的電子化服務（E-Service）。由於目前多代理者系統缺少了安全管理的機制，以致於目前為止代理者代表人類在網上從事活動的行為還不被大家接受。因此，我們提出了一套以代理者為導向的公鑰匙架構（Agent-Oriented Public Key Infrastructure, APKI），各式各樣的數位憑證被產生、儲存、註銷及驗證，以滿足不同存取控制的需求。例如，代理者的認證是以代理者身份憑證為基礎，而授權的部分則以授權憑證或屬性憑證來做驗證。透過這些數位憑證，我們可以在虛擬網路上的代理者之間建立一條信任路徑，一個安全的電子化服務的實際應用範例將會以此架構實作及呈現出來，以驗證我們所提架構的可行性。 / Agent is autonomous software that mediates e-service for human on the Internet. The acceptance of agent-mediated e-service (AMES) is very slow for the lacking of security management infrastructure for multi-agent system. Therefore we proposed an agent-oriented public key infrastructure (APKI) for multi-agent e-service. In this APKI, a taxonomy of digital certificates are generated, stored, verified, and revoked to satisfy different access and delegation control purposes. Agent identity certificate was designed for agent’s authentication whereas attributed and agent authorization certificates were proposed for agent’s authorization and delegation. Using these digital certificates, we establish agent trust relationships on the cyberspace. A trusted agent-mediated e-service scenario will be shown to demonstrate the feasibility of our APKI.

Multi-agent Systems (MAS) provide an increasingly relevant field of research due to their many applications to modelling real world situations where the behaviour of many individual, self-motivated, agents must be reasoned about and controlled. The problem of agent social reasoning is central to MAS, where an agent reasons about its actions and interactions with other agents. This is the most important component of MAS, as it is the interactions, cooperation and competition between agents that make MAS a powerful approach suited for tackling many complex problems. Existing work focuses either on specific types of social reasoning or general purpose agent practical reasoning - reasoning directed toward actions. This thesis argues that social reasoning should be considered separately from practical reasoning. There are many possible benefits to this separation compared to existing approaches. Principally, it can allow general algorithms for agent implementation, analysis and bounded reasoning. This viewpoint is motivated by the desire to implement social reasoning agents and allow for a more general theory of social reasoning in agents. This thesis presents the novel Expectation- Strategy-Behaviour (ESB) framework for social reasoning, which provides a generic way to specify and execute agent reasoning approaches. ESB is a powerful tool, allowing an agent designer to write expressive social reasoning specifications and have a computational model generated automatically. Through a formalism and description of an implemented reasoner based on this theory it is shown that it is possible and beneficial to implement a social reasoning engine as a complementary component to practical reasoning. By using ESB to specify, and then implement, existing social reasoning schemes for joint commitment and normative reasoning, the framework is shown to be a suitable general reasoner. Examples are provided of how reasoning can be bounded in an ESB agent and the mechanism to allow analysis of agent designs is discussed. Finally, there is discussion on the merits of the ESB solution and possible future work.

No description available.

This thesis presents a new approach to local decision-making in multi-agent systems with varying amounts of communication. Here, local decision-making refers to action choices which are made in a decentralized fashion by individual agents based on the information which is locally available to them. The work described here is set within the multi-agent decision process framework. Unreliable, faulty or stochastic communication patterns present a challenge to these settings which usually rely on precomputed, centralised solutions to control individual action choices. Various approximate algorithms for local decision-making are developed for scenarios with and without sequentiality. The construction of these techniques is based strongly on methods of Bayesian inference. Their performance is tested on synthetic benchmark scenarios and compared to that of a more conservative approach which guarantees coordinated action choices as well as a completely decentralized solution. In addition, the method is applied to a surveillance task based on real-world data. These simulation results show that the algorithms presented here can outperform more traditional approaches in many settings and provide a means for flexible, scalable decision-making in systems with varying information exchange between agents.

We investigate the properties of a new Multi-Agent Systems (MAS) for computer-aided composition called IPCS (pronounced “ipp-siss”) the Intermediate Performance Composition System which generates expressive performance as part of its compositional process, and produces emergent melodic structures by a novel multi-agent process. IPCS consists of a small-medium size (2 to 16) collection of agents in which each agent can perform monophonic tunes and learn monophonic tunes from other agents. Each agent has an affective state (an “artificial emotional state”) which affects how it performs the music to other agents; e.g. a “happy” agent will perform “happier” music. The agent performance not only involves compositional changes to the music, but also adds smaller changes based on expressive music performance algorithms for humanization. Every agent is initialized with a tune containing the same single note, and over the interaction period longer tunes are built through agent interaction. Agents will only learn tunes performed to them by other agents if the affective content of the tune is similar to their current affective state; learned tunes are concatenated to the end of their current tune. Each agent in the society learns its own growing tune during the interaction process. Agents develop “opinions” of other agents that perform to them, depending on how much the performing agent can help their tunes grow. These opinions affect who they interact with in the future. IPCS is not a mapping from multi-agent interaction onto musical features, but actually utilizes music for the agents to communicate emotions. In spite of the lack of explicit melodic intelligence in IPCS, the system is shown to generate non-trivial melody pitch sequences as a result of emotional communication between agents. The melodies also have a hierarchical structure based on the emergent social structure of the multi-agent system and the hierarchical structure is a result of the emerging agent social interaction structure. The interactive humanizations produce micro-timing and loudness deviations in the melody which are shown to express its hierarchical generative structure without the need for structural analysis software frequently used in computer music humanization.

Essa dissertação apresenta um mecanismo para incorporar autonomia de planejamento em modelos organizacionais multiagentes. Para tanto, propõe-se um modelo formal para representar a presença e ausência de autonomia de planejamento, utilizando dois tipos de objetivos: procedurais e declarativos. O modelo é implementado na plataforma JaCaMo na qual se realiza um estudo de caso de uma organização, onde coexistem agentes que possuem ou não possuem autonomia de planejamento. / This dissertation presents a mechanism to incorporate planning autonomy in multiagent organizational models. Therefore, we propose a formal model to represent presence or absence of planning autonomy, using two types of objectives: procedural and declarative ones. The model is implemented using the JaCaMo platform, in which an organization case study is proposed, where agents who have or do not have planning autonomy co-exist.

Essa dissertação apresenta um mecanismo para incorporar autonomia de planejamento em modelos organizacionais multiagentes. Para tanto, propõe-se um modelo formal para representar a presença e ausência de autonomia de planejamento, utilizando dois tipos de objetivos: procedurais e declarativos. O modelo é implementado na plataforma JaCaMo na qual se realiza um estudo de caso de uma organização, onde coexistem agentes que possuem ou não possuem autonomia de planejamento. / This dissertation presents a mechanism to incorporate planning autonomy in multiagent organizational models. Therefore, we propose a formal model to represent presence or absence of planning autonomy, using two types of objectives: procedural and declarative ones. The model is implemented using the JaCaMo platform, in which an organization case study is proposed, where agents who have or do not have planning autonomy co-exist.

Multi-agent systems (MAS) are emerging as a promising paradigm for conceptualizing, designing and implementing large-scale heterogeneous software systems. The key advantage of looking at components in such systems as autonomous agents is that as agents they are capable of flexible self-organization, instead of being rigidly organized by the system's architect. However, self-organization is like evolution-it takes a lot of time and the results are not guaranteed. More often than not, the system's architect has an idea about how the agents should organize themselves-what types of organizations they should form. In our work, we tried to solve the problem of modelling organizations and their roles in a MAS, independent of the particular agent platform on which the MAS will eventually run. First and foremost, we have proposed a metamodel for expressing platform-independent organization models. Furthermore, we have implemented the proposed metamodel for the Jade agent platform as a module extending this framework. Finally, we have demonstrated the use of our module by modelling three specific organizations: remote function invocation, arithmetic expression evaluation and sealed-bid auction. Our work shows how to separate the behaviour acquired through a role from the behaviour intrinsic to an agent. This...

Models are frequently used to represent complex systems in order to test the systems before they are deployed. Some of the most complicated models are those that represent multi-agent systems (MAS), where there are multiple decision makers. Brahms is an agent-oriented language that models MAS. Three major qualities affect the behavior of these MAS models: workframes that change the state of the system, communication activities that coordinate information between agents, and the schedule of workframes. The primary method to test these models that exists is repeated simulation. Simulation is useful insofar as interesting test cases are used that enable the simulation to explore different behaviors of the model, but simulation alone cannot be fully relied upon to adequately cover the test space, especially in the case of non-deterministic concurrent systems. It takes an exponential number of simulation trials to uncover schedules that reveal unexpected behaviors. This thesis defines a coverage metric to make simulation more meaningful before verification of the model. The coverage metric is divided into three different metrics: workframe coverage, communication coverage, and schedule coverage. Each coverage metric is defined through static analysis of the system, resulting in the coverage requirements of that system. These coverage requirements are compared to the logged output of the simulation run to calculate the coverage of the system. The use of the coverage metric is illustrated in several empirical studies and explored in a detailed case study of the SATS concept (Small Aircraft Transportation System). SATS outlines the procedures aircraft follow around runways that do not have communication towers. The coverage metric quantifies the test effort, and can be used as a basis for future automated test generation and active test.