JFLI-LIP6-NII Meeting on Efficient Methods for Reasoning and Problem Solving 2013

A Constraint Satisfaction Problem (CSP) is a fundamental problem that can formalize various applications related to Artificial Intelligence problems. An Weighted Constraint Satisfaction Problem (WCSP) is a CSP where constraints can be violated, and the aim is to find an assignment that minimizes the sum of weights of the violated constraints. Most researches have focused on developing algorithms for solving static mono-objective problems. However, many real world satisfaction/optimization problems involve multiple criteria that should be considered separately and satisfied/optimized simultaneously. Additionally, they are often dynamic, i.e., the problem changes at runtime. In this talk, we introduce a novel model for a Multi-Objective WCSP (MO-WCSP) and develop a novel algorithm based on a new solution criterion called (l, s)-Pareto solution. Furthermore, we first formalize a Dynamic MO-WCSP (DMO-WCSP). As an initial step forward developing an algorithm for solving a DMO-WCSP, we focus on the change of weights of constraints and develop the first algorithm for DMO-WCSPs. Also, we provide the complexities of our algorithms and evaluate them.

Many problems in multi-agent systems can be represented as a Distributed Constraint Optimization Problem (DCOP) where the goal is to find the best assignment to variables in order to minimize the cost. More complex problems including several criteria can be represented as a Multi-Objective Distributed Constraint Optimization Problem (MO-DCOP) where the goal is to optimize several criteria at the same time. However, many problems are subject to changes over time and need to be represented as dynamic problems. In this paper, we formalize the Dynamic Multi-Objective Distributed Constraint Optimization Problem (DMO-DCOP) and introduce the first algorithm called DMOBB to handle changes in the number of objectives. Furthermore, we propose the extension of our algorithm based on a novel criterion called s-robustness.

Distributed Constraint Optimization Problem (DCOP) is a most famous framework for modeling cooperative distributed problem solving, where the privacy is the one of most important matters. Some secure DCOP algorithms have been proposed so far, and most of them guarantee the privacy by using encryption. However the encryption has some drawbacks which may not be practical for reasons of availability. In this talk, we present a new secure DCOP algorithm which can guarantee the privacy of agent's decision without using encryption. To achieve that property, we extend a DCOP algorithm called DeQED, which search the dual space of an original problem and have a good property in the perspective of the privacy. And, we empirically show the performance of the proposed algorithm both in terms of solution quality and security.

MCnets is one of concise representations for coalitional games in characteristic form. For the game with MCnets, there has been no effective method to find the least core ("stable" payoff distributions over the agents) because naive implementations yield the linear programming problem with a huge number of constraints that grows exponential to the number of agents. In this talk, we present a constraint generation technique that would alleviate this memory issue. With this technique, we observe empirically that the least core can be computed for some MCnets instances up to 100 agents within a reasonable amount of time.

Elementary or one-dimensional cellular automata (CA) have been widely studied within the contexts of artificial intelligence, complexity science, theoretical biology, statistical mechanics and several other fields alike due to their deep capacity to simulate real phenomena. In many cases, however, the simplistic nature of CA prevents them from fully modeling many realistic scenarios. In particular, CA update synchronously, but no such central clock has ever been found to exist in biological organisms or physical systems; and furthermore, external perturbations affect how real systems evolve, but CA obey mechanical rule-following. In this talk we experimentally study the resilience of finite-size, asynchronously updated, single 1 history CA when exposed to stochastic perturbations. We define a measure of activity, explore several case studies, and apply our evaluation to all 256 rules.

Plan recognition is a task that infers a plan from an observed sequence of actions and probabilistic context free grammars (PCFGs) are available for this purpose where a sequence of actions is considered as a sentence. However when a sequence of actions is not complete, we need to compute the probability of a prefix, i.e. an initial substring of sentence which requires an infinite sum of probabilities. We recently enhanced PRISM, a logic-based language for machine learning, to be able to compute an infinite sum of probabilities, when possible, by cyclic propositional formulas. Using PRISM's this ability, we conducted classification experiments of incomplete access log data of Web sites by applying prefix probability computation to them and found that our approach outperforms other discriminative approaches using logistic regression and SVM.

In recent years, there has been an extensive interest in learning the dynamics of systems. For this purpose, a previous work proposed an algorithm that learns a logic program from interpretation transitions. However, both the run time and the memory space of this algorithm alike are exponential. In this talk, we propose a new version of this algorithm utilizing an efficient data structure based on Zero-suppressed Binary Decision Diagrams. We show empirically that using this representation we can perform the same learning task faster and using less memory space.

Generalized Assignment Problem (GAP) is one of the classic problems in combinatorial optimization problem which has been studied for over 4 decades. A goal of GAP is to find an optimal assignment(s) of goods that satisfies their individual knapsack constraints. We have introduced Generalized Mutual Assignment Problem (GMAP) which is a distributed version of GAP. We have also developed a protocol for GMAP called Distributed Lagrangian Relaxation Protocol (DisLRP), and some extended protocols based on DisLRP. In DisLRP, multiple agents search for an optimal assignment(s) cooperatively and synchronously, but there is no headquarters agent. We present a summary of the protocols and some techniques used within the protocols. And we also explain an idea of new DisLRP for GMAP.