The Workshop Program of the Association for the Advancement of Artificial Intelligence's Thirtieth AAAI Conference on Artificial Intelligence (AAAI-16) was held at the beginning of the conference, February 12-13, 2016. Workshop participants met and discussed issues with a selected focus -- providing an informal setting for active exchange among researchers, developers and users on topics of current interest. To foster interaction and exchange of ideas, the workshops were kept small, with 25-65 participants. Attendance was sometimes limited to active participants only, but most workshops also allowed general registration by other interested individuals.

The Workshop Program of the Association for the Advancement of Artificial Intelligence’s Thirtieth AAAI Conference on Artificial Intelligence (AAAI-16) was held at the beginning of the conference, February 12-13, 2016. Workshop participants met and discussed issues with a selected focus — providing an informal setting for active exchange among researchers, developers and users on topics of current interest. To foster interaction and exchange of ideas, the workshops were kept small, with 25-65 participants. Attendance was sometimes limited to active participants only, but most workshops also allowed general registration by other interested individuals. The AAAI-16 Workshops were an excellent forum for exploring emerging approaches and task areas, for bridging the gaps between AI and other fields or between subfields of AI, for elucidating the results of exploratory research, or for critiquing existing approaches. The fifteen workshops held at AAAI-16 were Artificial Intelligence Applied to Assistive Technologies and Smart Environments (WS-16-01), AI, Ethics, and Society (WS-16-02), Artificial Intelligence for Cyber Security (WS-16-03), Artificial Intelligence for Smart Grids and Smart Buildings (WS-16-04), Beyond NP (WS-16-05), Computer Poker and Imperfect Information Games (WS-16-06), Declarative Learning Based Programming (WS-16-07), Expanding the Boundaries of Health Informatics Using AI (WS-16-08), Incentives and Trust in Electronic Communities (WS-16-09), Knowledge Extraction from Text (WS-16-10), Multiagent Interaction without Prior Coordination (WS-16-11), Planning for Hybrid Systems (WS-16-12), Scholarly Big Data: AI Perspectives, Challenges, and Ideas (WS-16-13), Symbiotic Cognitive Systems (WS-16-14), and World Wide Web and Population Health Intelligence (WS-16-15).

A new computational paradigm has emerged in computer both Renault and Toyota have deployed online configuration science over the past few decades, which is exemplified by systems based on knowledge compilation). QBF solvers the use of SAT solvers to tackle problems in the complexity have been used in model checking, verification, debugging, class NP. Finally, function problem solvers have and engineering investment is made towards developing been used in model-based diagnosis, design debugging, highly efficient solvers for a prototypical problem CAD and bioinformatics. The cost of this investment is then on a variety of topics, including algorithms; descriptions amortized as these solvers are applied to a broader class of of implementations and/or evaluations of beyond NP problems via reductions (in contrast to developing dedicated solvers; their applications (including encodings); the complexity algorithms for each encountered problem). SAT solvers, classes they reach; and their connections to one for example, are now routinely used to solve problems in another.

Specifically, we present a top-down algorithm cn2mddg for compiling finite-domain CNs into multivalued decomposable We present and evaluate a top-down algorithm for decision graphs. The input of cn2mddg is a CN compiling finite-domain constraint networks (CNs) represented in the XCSP 2.1 format [Roussel and Lecoutre, into the language MDDG of multivalued decomposable 2009]. The output of our compilation algorithm is a representation decision graphs. Though it includes Decision-of the solutions of the CN in the language MDDG DNNF as a proper subset, MDDG offers the same key of multivalued decomposable decision graphs. MDDG is precisely tractable queries and transformations as Decision-the extension to non-Boolean domains of the language DNNF, which makes it useful for many applications. DDG [Fargier and Marquis, 2006] also known as Decision-Intensive experiments showed that our compiler DNNF [Oztok and Darwiche, 2014]: it is based on decomposable cn2mddg succeeds in compiling CNs which -nodes and (multivalued) decision nodes. Similarly are out of the reach of standard approaches based to Decision-DNNF, the MDDG language offers a number of on a translation of the input network to CNF, followed tractable queries, including (possibly weighted) solution finding by a compilation to Decision-DNNF. Furthermore, and counting, solution enumeration (solutions can be enumerated the sizes of the resulting compiled representations with polynomial delay), and optimization w.r.t. a linear turn out to be much smaller (sometimes by objective function. It also offers tractable transformations, several orders of magnitude).

Belief revision games (BRGs) are concerned with the dynamics of the beliefs of a group of communicating agents. BRGs are "zero-player" games where at each step every agent revises her own beliefs by taking account for the beliefs of her acquaintances. Each agent is associated with a belief state defined on some finite propositional language. We provide a general definition for such games where each agent has her own revision policy, and show that the belief sequences of agents can always be finitely characterized. We then define a set of revision policies based on belief merging operators. We point out a set of appealing properties for BRGs and investigate the extent to which these properties are satisfied by the merging-based policies under consideration.

This paper is concerned with knowledge compilation (KC), a family of approaches developed in AI for more than twenty years. Knowledge compilation consists in pre-processing some pieces of the available information in order to improve the computational efficiency (especially, the time complexity) of some tasks. In this paper, the focus is laid on three KC topics which gave rise to many works: the development of knowledge compilation techniques for the clausal entailment problem in propositional logic, the concept of compilability and the notion of knowledge compilation map. The three topics, as well as an overview of the main results from the literature, are presented. Some recent research lines are also discussed.

Chavira and Darwiche 2008; Apsel and Brafman 2012)) and forms of planning (see e.g., (Palacios et al. 2005; It and more importantly the variable elimination rule (replacing proves useful when the problem under consideration (e.g., in the input CNF formula all the clauses containing a the satisfiability issue) can be solved more efficiently when given variable x by the set of all their resolvents over x) or the input formula has been first preprocessed (of course, the blocked clause elimination rule (removing every clause the preprocessing time is taken into account in the global containing a literal such that every resolvent obtained by resolving solving time). Some preprocessing techniques are nowadays on it is a valid clause).

Valued decision diagrams (VDDs) are data structures that represent functions mapping variable-value assignments to non-negative real numbers. They prove useful to compile cost functions, utility functions, or probability distributions. While the complexity of some queries (notably optimization) and transformations (notably conditioning) on VDD languages has been known for some time, there remain many significant queries and transformations, such as the various kinds of cuts, marginalizations, and combinations, the complexity of which has not been identified so far. This paper contributes to filling this gap and completing previous results about the time and space efficiency of VDD languages, thus leading to a knowledge compilation map for real-valued functions. Our results show that many tasks that are hard on valued CSPs are actually tractable on VDDs.

Counting the models of a propositional formula is a key issue for a number of AI problems, but few propositional languages offer the possibility to count models efficiently. In order to fill the gap, we introduce the language EADT of (extended) affine decision trees. An extended affine decision tree simply is a tree with affine decision nodes and some specific decomposable conjunction or disjunction nodes. Unlike standard decision trees, the decision nodes of an EADT formula are not labeled by variables but by affine clauses. We study EADT, and several subsets of it along the lines of the knowledge compilation map. We also describe a CNF-to-EADT compiler and present some experimental results. Those results show that the EADT compilation-based approach is competitive with (and in some cases is able to outperform) the model counter Cachet and the d-DNNF compilation-based approach to model counting.

The knowledge compilation map introduced by Darwiche and Marquis takes advantage of a number of concepts (mainly queries, transformations, expressiveness, and succinctness) to compare the relative adequacy of representation languages to some AI problems. However, the framework is limited to the comparison of languages that are interpreted in a homogeneous way (formulae are interpreted as Boolean functions). This prevents one from comparing, on a formal basis, languages that are close in essence, such as OBDD, MDD, and ADD. To fill the gap, we present a generalized framework into which comparing formally heterogeneous representation languages becomes feasible. In particular, we explain how the key notions of queries and transformations, expressiveness, and succinctness can be lifted to the generalized setting.