The interpretation of Nuclear Magnetic Resonance (NMR) spectra to produce a 3D protein structure is a difficult and time consuming task. The 3D structure is important because it largely determines the properties of the protein. Therefore, knowledge of the 3D structure can aid in the understanding of its biological function and perhaps lead to modifications which have an enhanced therapeutic activity. An NMR experiment produces a large 2D data spectrum. The important part of the spectrum consists of thousands of small cross peaks and the interpretation task is to associate a pair of hydrogen nuclei with each peak. Manual interpretation takes many months and there is considerable interest in providing (semi-) automatic tools to speed up this process. The interpretation is difficult because the number of combinations can quickly swamp the human mind and the spectrum suffers from peaks overlapping and random noise effects. ASSASSIN (A Semi-automatic Assignment System Specialising In Nmr) is a distributed problem solving system that has been implemented in the identification of peaks associated with the hydrogen nuclei at the end of long side chains. These results are then passed onto the structural assignment stage. The structural assignment stage is a feedback loop which involves the interpretation of a spectrum and the generation of preliminary structural models. These models can then be used to simplify further analysis of the spectrum. ASSASSIN uses a constraint manager implemented in CHIP to analyse this data more quickly and thoroughly than a human. The results of this work reveal that a constraint based approach is well suited to the NMR domain where the problems can be easily represented and solved efficiently.

No description available.

Many real-life problems such as distributed meeting scheduling, mobile frequency allocation and resource allocation can be solved using multi-agent paradigms. Distributed constraint satisfaction problems (DisCSPs) is a framework for describing such problems in terms of related subproblems, called a complex local problem (CLP), which are dispersed over a number of locations, each with its own constraints on the values their variables can take. An agent knows the variables in its CLP plus the variables (and their current value) which are directly related to one of its own variables and the constraints relating them. It knows little about the rest of the problem. Thus, each CLP is solved by an agent which cooperates with other agents to solve the overall problem. Algorithms for solving DisCSPs can be classified as either systematic or local search with the former being complete and the latter incomplete. The algorithms generally assume that each agent has only one variable as they can solve DisCSP with CLPs using “virtual” agents. However, in large DisCSPs where it is appropriate to trade completeness off against timeliness, systematic search algorithms can be expensive when compared to local search algorithms which generally converge quicker to a solution (if a solution is found) when compared to systematic algorithms. A major drawback of local search algorithms is getting stuck at local optima. Significant researches have focused on heuristics which can be used in an attempt to either escape or avoid local optima. This thesis makes significant contributions to local search algorithms for DisCSPs. Firstly, we present a novel combination of heuristics in DynAPP (Dynamic Agent Prioritisation with Penalties), which is a distributed synchronous local search algorithm for solving DisCSPs having one variable per agent. DynAPP combines penalties on values and dynamic agent prioritisation heuristics to escape local optima. Secondly, we develop a divide and conquer approach that handles DisCSP with CLPs by exploiting the structure of the problem. The divide and conquer approach prioritises the finding of variable instantiations which satisfy the constraints between agents which are often more expensive to satisfy when compared to constraints within an agent. The approach also exploits concurrency and combines the following search strategies: (i) both systematic and local searches; (ii) both centralised and distributed searches; and (iii) a modified compilation strategy. We also present an algorithm that implements the divide and conquer approach in Multi-DCA (Divide and Conquer Algorithm for Agents with CLPs). DynAPP and Multi-DCA were evaluated on several benchmark problems and compared to the leading algorithms for DisCSPs and DisCSPs with CLPs respectively. The results show that at the region of difficult problems, combining search heuristics and exploiting problem structure in distributed constraint satisfaction achieve significant benefits (i.e. generally used less computational time and communication costs) over existing competing methods.

Risk is a game in which traditional Artificial-Intelligence methods such as for example iterative deepening and Alpha-Beta pruning can not successfully be applied due to the size of the search space. Distributed problem solving in the form of a multi-agent system might be the solution. This needs to be tested before it is possible to tell if a multi-agent system will be successful at playing Risk or not. In this thesis the development of a multi-agent system that plays Risk is explained. The system places an agent in every country on the board and uses a central agent for organizing communication. An auction mechanism is used for negotiation. The experiments show that a multi-agent solution indeed is a prosperous approach when developing a computer based player for the board game Risk. / I brädspelet Risk är det svårt att använda traditionella Artificiell-Intelligens-metoder eftersom sökrymden är extremt stor. Lösningen till detta kan vara att använda distribuerad problemlösning i form av ett multi-agent system. Detta måste testas innan man kan säga om ett multi-agent system är framgångsrikt, eller ej, i att spela Risk. Denna uppsats går igenom utvecklingen av ett multi-agent system som spelar Risk. Systemet placerar en agent i varje land på brädet och använder en central agent för att organisera kommunikationen. En auktionsmekanism används vid förhandlingar. Experimenten visar att ett multi-agent system är en framgångsrik infallsvinkel vid utveckling av en datorbaserad spelare för brädspelet Risk.

Risk is a game in which traditional Artificial-Intelligence methods such as for example iterative deepening and Alpha-Beta pruning can not successfully be applied due to the size of the search space. Distributed problem solving in the form of a multi-agent system might be the solution. This needs to be tested before it is possible to tell if a multi-agent system will be successful at playing Risk or not. In this thesis the development of a multi-agent system that plays Risk is explained. The system places an agent in every country on the board and uses a central agent for organizing communication. An auction mechanism is used for negotiation. The experiments show that a multi-agent solution indeed is a prosperous approach when developing a computer based player for the board game Risk. / I brädspelet Risk är det svårt att använda traditionella Artificiell-Intelligens-metoder eftersom sökrymden är extremt stor. Lösningen till detta kan vara att använda distribuerad problemlösning i form av ett multi-agent system. Detta måste testas innan man kan säga om ett multi-agent system är framgångsrikt, eller ej, i att spela Risk. Denna uppsats går igenom utvecklingen av ett multi-agent system som spelar Risk. Systemet placerar en agent i varje land på brädet och använder en central agent för att organisera kommunikationen. En auktionsmekanism används vid förhandlingar. Experimenten visar att ett multi-agent system är en framgångsrik infallsvinkel vid utveckling av en datorbaserad spelare för brädspelet Risk.

In this research, a multi-agent system called KMAS is presented that models an environment of intelligent, autonomous, rational, and adaptive agents that reason about trust, and adapt trust based on experience. Agents reason and adapt using a modification of the k-Nearest Neighbor algorithm called (k X n) Nearest Neighbor where k neighbors recommend reputation values for trust during each of n interactions. Reputation allows a single agent to receive recommendations about the trustworthiness of others. One goal is to present a recommendation model of trust that outperforms MAS architectures relying solely on direct agent interaction. A second goal is to converge KMAS to an emergent system state where only successful cooperation is allowed. Three experiments are chosen to compare KMAS against a non-(k X n) MAS, and between different variations of KMAS execution. Research results show KMAS converges to the desired state, and in the context of this research, KMAS outperforms a direct interaction-based system.

Este trabalho consiste no projeto e implementação de uma ferramenta de monitoração para um núcleo de resolução distribuída de problemas denominado dpsk+p. Tal núcleo permite que diversos agentes, desenvolvidos em diferentes linguagens que suportam o paradigma de objetos, compartilhem dados e métodos entre si, de modo a cooperarem no processo de resolução de determinado problema. A ferramenta de monitoração é baseada em eventos de comunicação e controle entre agentes, utilizando a técnica de animação de processos para efeito de exibição dos resultados. Além disso, propõe um método eficiente de exibição do fluxo de comunicação em sistemas baseados em memória compartilhada, aproveitando a compacidade presente nas hierarquias de classes que compõem um sistema orientado a objetos.PCS. / This work consists of the design and implementation of a monitoring facility for an object-oriented distributed problem solving kernel named DPSK+P. This kernel allows both data and method sharing between agents, that may have been developed in different object-oriented programming languages, so that they can cooperate in a problem solving activity. The monitoring facility is based on control and communication events, and its exhibition of results uses process animation techniques. It also presents an efficient framework for the exhibition of the communication flow in shared memory based systems, which profiles the existing compactness in object-oriented class hierarchies.

Este trabalho consiste no projeto e implementação de uma ferramenta de monitoração para um núcleo de resolução distribuída de problemas denominado dpsk+p. Tal núcleo permite que diversos agentes, desenvolvidos em diferentes linguagens que suportam o paradigma de objetos, compartilhem dados e métodos entre si, de modo a cooperarem no processo de resolução de determinado problema. A ferramenta de monitoração é baseada em eventos de comunicação e controle entre agentes, utilizando a técnica de animação de processos para efeito de exibição dos resultados. Além disso, propõe um método eficiente de exibição do fluxo de comunicação em sistemas baseados em memória compartilhada, aproveitando a compacidade presente nas hierarquias de classes que compõem um sistema orientado a objetos.PCS. / This work consists of the design and implementation of a monitoring facility for an object-oriented distributed problem solving kernel named DPSK+P. This kernel allows both data and method sharing between agents, that may have been developed in different object-oriented programming languages, so that they can cooperate in a problem solving activity. The monitoring facility is based on control and communication events, and its exhibition of results uses process animation techniques. It also presents an efficient framework for the exhibition of the communication flow in shared memory based systems, which profiles the existing compactness in object-oriented class hierarchies.

Resource allocation problems have been widely studied according to various scenarios in literature. In such problems, a set of resources must be allocated to a set of agents, according to their own preferences. Self-organization issues in telecommunication, scheduling problems or supply chain management problems can be modeled using resource allocation problems. Such problems are usually solved by means of centralized techniques, where an omniscient entity determines how to optimally allocate resources. However, these solving methods are not well-adapted for applications where privacy is required. Moreover, several assumptions made are not always plausible, which may prevent their use in practice, especially in the context of agent societies. For instance, dynamic applications require adaptive solving processes, which can handle the evolution of initial data. Such techniques never consider restricted communication possibilities whereas many applications are based on them. For instance, in peer-to-peer networks, a peer can only communicate with a small subset of the systems. In this thesis, we focus on distributed methods to solve resource allocation problems. Initial allocation evolves step by step thanks to local agent negotiations. We seek to provide agent behaviors leading negotiation processes to socially optimal allocations. In this work, resulting resource allocations can be viewed as emergent phenomena. We also identify parameters favoring the negotiation efficiency. We provide the negotiation settings to use when four different social welfare notions are considered. The original method proposed in this thesis is adaptive, anytime and can handle any restriction on agent communication possibilities.