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

The ethical rules are many and conflicting. The main difficulty with both robot ethics and human ethics comes from the resulting contradictions that need to be overcome. In human ethics, the way those contradictions are solved strongly differs from one philosopher to another. For instance, attitudes toward lying or suicide are numerous and contrary. In the case of lying, some strictly prohibit any infringement of the truth whatsoever, even if this leads to condemning innocent people, while others try to accommodate their attitudes to situations. Similarly, some severely condemn suicide whatever are the circumstances, while others esteem persons having the courage to prefer their death when the situation impairs the human dignity. In the philosophical tradition, there are many general approaches to surmount those contradictions. For instance, consequentialism and utilitarianism analyze the consequences of actions while Kantian deontism consider the universality of individual maxims of the will. We shall present how Answer Set Programming techniques can be used to implement different ethical systems that solve logical contradictions between sets of rules.

We study a new framework for learning normal logic programs from transitions of interpretations. Given a set of pairs of interpretations (I,J) such that J=T_P(I), where T_P is the immediate consequence operator, we infer the program P. The learning framework can be applied to infer Boolean networks from basins of attraction. We also show how to incorporate background knowledge and inductive biases, then apply the framework to learning transition rules of cellular automata.

The Cybernard project is an attempt to reconstruct Claude Bernard’s empirical investigations with a computational model, using epistemological insight and artificial intelligence techniques. We first present here the previous achievements of this projects, in which a virtual lab has been proposed to model Claude Bernard experiments. In this part, we suppose that Claude Bernard had in mind what we call “kernel models” that contain the basic physiological concepts upon which Claude Bernard builds his general physiological theory. The “kernel models” provide a simplified view of physiology, where the internal environment – the so-called “milieu intérieur” –, mainly the blood, plays an essential role. According to this perspective, we assume that the “kernel models” allow Claude Bernard to make some hypotheses and to draw out their logical consequences. We shall then discuss future directions of this project, and an attempt to formalize the different reasoning steps of experimental method, focusing especially on the decision making needed to make experiment as many examples can be reconstructed from Claude Bernard experimental notes.

PRISM is a logic-based probabilistic modeling language for statistical machine learning. It can define well-known and not so well-known probabilistic models such as Bayesian networks and profile hidden Markov models in terms of PRISM programs and learns model parameters form real data by statistical inference. I report the recent expansion of PRISM's learning ability with MCMC for Bayesian inference and Viterbi training.

Topological approach tries to reason on inconsistent knowledge bases using the conventional topological operators e.g., interior, exterior, border and closure. We develop neo-Topology based on topological operators and we make major development and improvements of current Topological approach by properly introducing the "Thickness Boarder" with strong inference rules. We proof the validity of the inference rules using set operations. We demonstrate topological approach with appropriate examples.

In this presentation, we introduce an approach for reasoning about naive Bayes classifiers in which we explicitly convert them into Ordered Decision Diagrams (ODDs), which are then used to reason about the properties of these classifiers. Specifically, we present an algorithm for converting any naive Bayes classifier into an ODD, and we show theoretically and experimentally that this algorithm can give us an ODD that is tractable in size even given an intractable number of instances.

This paper proposes an approach on how to accommodate norms to an already existing architecture of rational agents. Starting from the famous BDI model, an extension of the BDI execution loop will be presented; it will address such issues as norm instantiation and norm internalization, with a particular emphasis on the problem of norm consistency. A proposal for the resolution of conflicts between newly occurring norms, on one side, and already existing norms or mental states, on the other side,will be described. While it is fairly difficult to imagine an evaluation for the proposed architecture, a challenging scenario inspired form the science-fiction literature will be used to give the reader an intuition of how the proposed approach will deal with situations of normative conflicts.

We are concerned with multi-agent systems (MAS) in dynamic environment, and focus on knowledge representation and context-aware reasoning of such systems. In dynamic environment, an agent needs to be able to manage its knowledge according to context changes. To achieve this goal, an agent has to adapt his beliefs and behaviour with respect to the current state of the world. In this work, we define a method to design agents' knowledge and reason efficiently in dynamic contexts. For this purpose, we use the expressiveness of answer set programming (ASP) and propose a method based on combinations of modules that are represented in ASP. Using meta-knowledge on these combinations, we can easily realise dynamic behaviour and meta-reasoning. We propose an algorithm to combine modules and implement the framework in an example of multi-agent systems in a dynamic world. Using experimental results, we show that modular knowledge can be used to optimise reasoning time.

Many real world problems involve multiple criteria that should be considered separately and optimized simultaneously. A Multi-Objective Distributed Constraint Optimization Problem (MO-DCOP) is the extension of a mono-objective Distributed Constraint Optimization Problem (DCOP) and a centralized Multi-Objective Constraint Optimization Problem (MO-COP). A DCOP is a fundamental problem that can formalize various applications related to multi-agent cooperation. In a MO-COP, various complete, incomplete and interactive algorithms have been developed. On the other hand, in a MO-DCOP, B-MOMS is the only existing (incomplete) algorithm. In this paper, we develop a novel complete algorithm for MO-DCOP. The characteristics of this algorithm are as follows: (i) it is the first complete algorithm which can guarantee to find a Pareto solution, (ii) it is based on a pseudo-tree, which is a widely used graph structure in complete DCOP algorithms, (iii) it utilizes the simplest and the most widely used classical method to find the Pareto solutions of a Multi-Objective Optimization Problem (MOOP), and (iv) the complexity of this algorithm is determined by the induced width of problem instances. Furthermore, we develop an incomplete algorithm for MO-DCOP which is based on a solution criterion called p-optimality. This algorithm can provide the upper bounds of the absolute/ relative errors of the solution, which can be obtained a priori/posteriori, respectively.

Graphical games (GG) provide compact representations of multiplayer games involving large populations of agents when influences among them have some locality property. The notion of pure Nash equilibrium (PNE), not requiring randomized strategies, is a fundamental stability concept. However, recent results show that for many natural topologies, a PNE is very unlikely to exist when the number of agents is large, which challenges the relevance of PNE in large GG. We investigate here how far we can get from the notion of individual stability catched by the concept of PNE, by only requiring agents to be almost in best-response (ε-Nash), or by requiring almost all agents to be in best-response. We study these approximated notions of PNE for different topologies, including graphs with unbounded treewidth, like grids. This makes the problem computationnally very challenging and requires the use and detailed comparison of several algorithmic solutions. Our results reveal surprisingly good asymptotic properties, tempering the claim that individual stability is not a relevant notion for large GG. Finally, as approximated PNE provide various tradeoffs between stability and social utility maximization, we propose an approach to construct a minimal-size e-covering of all feasible pareto-dominant tradeoffs.

In many applications of distributed problem solving, the agents may want to optimize a global objective while preserving their privacy and security. This problem can be formalized as the Distributed Constraint Optimization Problem (DCOP). This paper presents a new incomplete DCOP algorithm called DeQED (Decomposition with Quadratic Encoding to Decentralize). DeQED is based on the Divide-and-Coordinate (DaC) framework, where the entire problem is divided into the sub-problems on agents and the agents try to resolve disagreement on variables by communication. One notable feature of DeQED is that, without resorting to preprocessing such as decomposition and compilation, the agents can naturally deal with complex local problems by calling a WCSP solver. In the experiments we observed that DeQED significantly outperformed other incomplete DCOP algorithms for instances with one variable per agent. Moreover,we also observed that DeQED converges to better solutions than the one with preprocessing for instances with complex local problems.

The need to minimize the down-time of services and production processes calls for systems that are able to autonomously detect, isolate, diagnose and repair faults that may occur. Self-healability has been so far studied whether in a simple-fault context or in centralized systems. In this talk, we present an approach to allow distributed systems to be self-healing in a multiple-fault context.

Many researchers of different fields are interested in building resilient systems that can absorb shocks and recover from damages caused by unexpected large-scale events, such as the 3.11 earthquake; however, no formal definition of resilience exists. In this paper, we set out to establish a new challenging research discipline that we call "systems resilience", which provides a set of unified design principle for building resilient systems, and define a dynamic constraint-based agent model called SR-model, which allows us to evaluate properties of the system such as resistance, recoverability, resilience, functionability, and stability under a dynamic environment.