Global constraints are an essential component in the efficiency of centralized constraint programming. We propose to include global constraints in distributed constraint satisfaction problem (DisCSP) and distributed constraint optimization problem (DCOP). We detail how this inclusion can be done, considering different representations for global constraints (direct, nested, binary). We explore the relation of global constraints with local consistency (both in the hard and soft cases), in particular, for generalized arc consistency (GAC). We provide experimental evidence of the benefits of global constraints on several benchmarks, both for distributed constraint satisfaction and for distributed constraint optimization.

Research on optimization in multi-agent systems (MASs) has contributed with a wealth of techniques to solve many of the challenges arising in a wide range of multi-agent application domains. Multi-agent optimization focuses on casting MAS problems into optimization problems. The solving of those problems could possibly involve the active participation of the agents in a MAS. Research on multi-agent optimization has rapidly become a very technical, specialized field. Moreover, the contributions to the field in the literature are largely scattered. These two factors dramatically hinder access to a basic, general view of the foundations of the field. This tutorial is intended to ease such access by providing a gentle introduction to fundamental concepts and techniques on multi-agent optimization.

This note considers how to modify BnB-ADOPT, a well-known algorithm for optimally solving distributed constraint optimization problems, with a double aim: (i) to avoid sending most of the redundant messages and (ii) to handle cost functions of any arity. Some of the messages exchanged by BnB-ADOPT turned out to be redundant. Removing most of the redundant messages increases substantially communication efficiency: the number of exchanged messages is - in most cases - at least three times fewer (keeping the other measures almost unchanged), and termination and optimality are maintained. On the other hand, handling n-ary cost functions was addressed in the original work, but the presence of thresholds makes their practical usage more complex. Both issues - removing most of the redundant messages and efficiently handling n-ary cost functions - can be combined, producing the new version BnB-ADOPT+. Experimentally, we show the benefits of this version over the original one.

Distributed Constraint Optimization Problems (DCOPs) can be optimally solved by distributed search algorithms, such as ADOPT and BnB-ADOPT. In centralized solving, maintaining soft arc consistency during search has proved to be beneficial for performance. In this thesis we aim to explore the maintenance of different levels of soft arc consistency in distributed search when solving DCOPs.

We have found that some messages of BnB-ADOPT are redundant. Removing most of those redundant messages we obtain BnB-ADOPT+, which achieves the optimal solution and terminates. In practice, BnB-ADOPT+ causes substantial reductions on communication costs with respect to the original algorithm.

Some distributed constraint optimization algorithms use a linear number of messages in the number of agents, but of exponential size. This is often the main limitation for their practical applicability. Here we present some distributed algorithms for these problems when they are arranged in a tree of agents. The exact algorithm, DCTE, computes the optimal solution but requires messages of size exp(s), where s is a structural parameter. Its approximate version, DMCTE(r), requires smaller messages of size exp(r), r < s, at the cost of computing approximate solutions. It provides a cost interval that bounds the error of the approximation. Using the technique of cost function filtering, we obtain DMCTEf(r). Combining cost function filtering with bound reasoning, we propose DIMCTEf, an algorithm based on repeated executions of DMCTEf(r) with increasing r. DIMCTEf uses messages of previous iterations to decrease the size of messages in the current iteration, which allows to alleviate their high size. We provide evidences of the benefits of our approach on two benchmarks.

Knowledge base (KB) refinement is a suitable technique to support expert system (ES) validation. When used for validation, KB refinement should be guided not only by the number of errors to solve but also by the importance of those errors. Most serious errors should be solved first, even causing other errors of lower importance but assuring a neat validity gain. These are the bases for IMPROVER, a KB refinement tool designed to support ES validation. IMPROVER refines ES for medical diagnosis with this classification of error importance: false negative > false positive > ordering mismatch. IMPROVER has been used to support the validation of PNEUMON-IA, a real ES on the medical domain. After refinement, the ES validity has increased substantially. Detailed evidence of this improvement is provided, as well as examples of how the refinement process was performed. © 1996 John Wiley & Sons, Inc.

We recapitulate the work done in the ESPRIT-II VALID project, the aim of which was to develop methods and tools for the Validation of Knowledge-Based Systems. the project's goal was to undertake a comprehensive approach to the problem of Validation for existing KBS. In order to do so, several methods for different Validation issues were created, and different KBS were considered. the project concrete result is a Validation environment in which different KBS can be validated. It includes a Validation toolkit comprising seven tools, ranging from inconsistency detection to KBS inspectors, that the knowledge engineer can interact with. Validation tools produced by the VALID project have been tested on existing KBS and have been useful in improving their performance. © 1994 John Wiley & Sons, Inc.