Distributed constraint optimization problems (DCOPs) are a model for representing multi-agent systems in which agents cooperate to optimize a global objective. The DCOP model has two main advantages: it can represent a wide range of problem domains, and it supports the development of generic algorithms to solve them. Firstly, this paper presents some advances in both complete and approximate DCOP algorithms. Secondly, it explains that the DCOP model makes a number of unrealistic assumptions that severely limit its range of application. Finally, it points out hints on how to tackle such limitations.

Deep space missions are characterized by severely constrained communication links. To meet the needs of future missions and increase their scientific return, future space systems will require an increased level of autonomy on-board. In this work, we propose a comprehensive approach to on-board autonomy relying on model-based reasoning, and encompassing many important reasoning capabilities such as plan generation, validation, execution and monitoring, FDIR, and run-time diagnosis. The controlled platform is represented symbolically, and the reasoning capabilities are seen as symbolic manipulation of such formal model. We have developed a prototype of our framework, implemented within an on-board Autonomous Reasoning Engine. We have evaluated our approach on two case-studies inspired by real-world, ongoing projects, and characterized it in terms of reliability, availability and performance.

Multiagent planning has seen much progress with the development of formal models such as Dec-POMDPs. However, the complexity of these models—NEXP-Complete even for two agents—has limited scalability. We identify certain mild conditions that are sufficient to make multiagent planning amenable to a scalable approximation w.r.t. the number of agents. This is achieved by constructing a graphical model in which likelihood maximization is equivalent to plan optimization. Using the Expectation-Maximization framework for likelihood maximization, we show that the necessary inference can be decomposed into processes that often involve a small subset of agents, thereby facilitating scalability. We derive a global update rule that combines these local inferences to monotonically increase the overall solution quality. Experiments on a large multiagent planning benchmark confirm the benefits of the new approach in terms of runtime and scalability.

During the design of a microprocessor, Design Space Exploration (DSE) is a critical step which determines the appropriate design configuration of the microprocessor. In the computer architecture community, supervised learning techniques have been applied to DSE to build models for predicting the qualities of design configurations. For supervised learning, however, considerable simulation costs are required for attaining the labeled design configurations. Given limited resources, it is difficult to achieve high accuracy. In this paper, inspired by recent advances in semi-supervised learning, we propose the COMT approach which can exploit unlabeled design configurations to improve the models. In addition to an improved predictive accuracy, COMT is able to guide the design of microprocessors, owing to the use of comprehensible model trees. Empirical study demonstrates that COMT significantly outperforms state-of-the-art DSE technique through reducing mean squared error by 30% to 84%, and thus, promising architectures can be attained more efficiently.

Dimensionality reduction plays a vital role in pattern recognition. However, for normalized vector data, existing methods do not utilize the fact that the data is normalized. In this paper, we propose to employ an Angular Decomposition of the normalized vector data which corresponds to embedding them on a unit surface. On graph data for similarity/kernel matrices with constant diagonal elements, we propose the Angular Decomposition of the similarity matrices which corresponds to embedding objects on a unit sphere. In these angular embeddings, the Euclidean distance is equivalent to the cosine similarity. Thus data structures best described in the cosine similarity and data structures best captured by the Euclidean distance can both be effectively detected in our angular embedding. We provide the theoretical analysis, derive the computational algorithm, and evaluate the angular embedding on several datasets. Experiments on data clustering demonstrate that our method can provide a more discriminative subspace.

Slinko and White, (2008) have recently introduced a new model of coalitional manipulation of voting rules under limited communication, which they call safe strategic voting. The computational aspects of this model were first studied by Hazon and Elkind, (2010), who provide polynomial-time algorithms for finding a safe strategic vote under k-approval and the Bucklin rule. In this paper, we answer an open question of Hazon and Elkind, (2010) by presenting a polynomial-time algorithm for finding a safe strategic vote under the Borda rule. Our results for Borda generalize to several interesting classes of scoring rules.

In Model-Based Diagnosis, a diagnostic algorithm is typically used to compute diagnoses using a model of a real-world system and some observations. Contrary to classical hypothesis, in real-world applications it is sometimes the case that either the model, the observations or the diagnostic algorithm are abnormal with respect to some required properties; with possibly huge economical consequences. Determining which abnormalities exist constitutes a meta-diagnostic problem. We contribute, first, with a general theory of meta-diagnosis with clear semantics to handle this problem. Second, we propose a series of typically required properties and relate them between themselves. Finally, using our meta-diagnostic framework and the studied properties and relations, we model and solve some common meta-diagnostic problems.

Consistent word selection in machine translation is currently realized by resolving word sense ambiguity through the context of a single sentence or neighboring sentences. However, consistent word selection over the whole article has yet to be achieved. Consistency over the whole article is extremely important when applying machine translation to collectively developed documents like Wikipedia. In this paper, we propose to consider constraints between words in the whole article based on their semantic relatedness and contextual distance. The proposed method is successfully implemented in both statistical and rule-based translators. We evaluate those systems by translating 100 articles in the English Wikipedia into Japanese. The results show that the ratio of appropriate word selection for common nouns increased to around 75% with our method, while it was around 55% without our method.

Probabilistic logics which is followed by the development of the main methods that support reasoning with probability distributions, used in generalising probabilistic Boolean interaction, and, such as ProbLog, use an implicit definition finally, default logic is briefly discussed. We will use probabilistic of an interaction rule to combine probabilistic evidence Boolean interaction as a sound and generic, algebraic about atoms. In this paper, we show that way to combine uncertain evidence, whereas default this interaction rule is an example of a more general logic will be used as our language to implement the interaction class of interactions that can be described by nonmonotonic operators, again reflecting this double perspective on the logics. We furthermore show that such probabilistic logic. The new probabilistic logical framework local interactions about the probability of an atom is described in Section 3 and compared to other approaches can be described by convolution. The resulting extended in Section 4. The achievements of this research are reflected probabilistic logic supports nonmonotonic upon in Section 5. reasoning with probabilistic information.

In this context, while it methods (see, e.g., [Shehory and Kraus, 1998; Sandholm et is desirable to generate a coalition structure that al., 1999; Sen and Dutta, 2000; Dang and Jennings, 2004; maximizes the sum of the values of the coalitions, Rahwan et al., 2009b]). In this context, an important line of the space of possible solutions is often too large research is the development of anytime CSG algorithms. In to allow exhaustive search. Thus, a fundamental particular, an algorithm is "anytime" if it can return a solution open question in this area is the following: Can we at any point of time during its execution, and the quality of its search through only a subset of coalition structures, solution improves monotonically until termination. This is and be guaranteed to find a solution that is within particularly desirable in the multi-agent system context since a desirable bound β from optimum? If so, what is the agents might not always have sufficient time to run the the minimum such subset?