Constraint-Based Reasoning


Effective problem solving using SAT solvers

arXiv.org Artificial Intelligence

In this article we demonstrate how to solve a variety of problems and puzzles using the built-in SAT solver of the computer algebra system Maple. Once the problems have been encoded into Boolean logic, solutions can be found (or shown to not exist) automatically, without the need to implement any search algorithm. In particular, we describe how to solve the $n$-queens problem, how to generate and solve Sudoku puzzles, how to solve logic puzzles like the Einstein riddle, how to solve the 15-puzzle, how to solve the maximum clique problem, and finding Graeco-Latin squares.


Two-step Constructive Approaches for Dungeon Generation

arXiv.org Artificial Intelligence

This paper presents a two-step generative approach for creating While research on level generation focuses on level generators dungeons in the rogue-like puzzle game MiniDungeons 2. Generation based on stochastic search [14], constraint solving [11, 12], or machine is split into two steps, initially producing the architectural learning [13], level generation in published games is mostly layout of the level as its walls and floor tiles, and then furnishing it carried out via constructive algorithms. Unlike generate-and-test with game objects representing the player's start and goal position, processes, constructive generators do not evaluate and regenerate challenges and rewards. Three layout creators and three furnishers output; for example, cellular automata and grammars can be used are introduced in this paper, which can be combined in different for constructive generation, as well as more freeform approaches ways in the two-step generative process for producing diverse dungeons such as diggers [10]. Such generators are computationally lightweight levels. Layout creators generate the floors and walls of a level, since they do not evaluate their generated output. This while furnishers populate it with monsters, traps, and treasures.


PACO: Global Signal Restoration via PAtch COnsensus

arXiv.org Machine Learning

Many signal processing algorithms break the target signal into overlapping segments (also called windows, or patches), process them separately, and then stitch them back into place to produce a unified output. At the overlaps, the final value of those samples that are estimated more than once needs to be decided in some way. Averaging, the simplest approach, tends to produce blurred results. Significant work has been devoted to this issue in recent years: several works explore the idea of a weighted average of the overlapped patches and/or pixels; a more recent approach is to promote agreement (consensus) between the patches at their intersections. This work investigates the case where consensus is imposed as a hard constraint on the restoration problem. This leads to a general framework applicable to all sorts of signals, problems, decomposition strategies, and featuring a number of theoretical and practical advantages over other similar methods. The framework itself consists of a general optimization problem and a simple and efficient \admm-based algorithm for solving it. We also show that the consensus step of the algorithm, which is the main bottleneck of similar methods, can be solved efficiently and easily for any arbitrary patch decomposition scheme. As an example of the potential of our framework, we propose a method for filling missing samples (inpainting) which can be applied to signals of any dimension, and show its effectiveness on audio, image and video signals.


Deep Reasoning Networks: Thinking Fast and Slow

arXiv.org Artificial Intelligence

We introduce Deep Reasoning Networks (DRNets), an end-to-end framework that combines deep learning with reasoning for solving complex tasks, typically in an unsupervised or weakly-supervised setting. DRNets exploit problem structure and prior knowledge by tightly combining logic and constraint reasoning with stochastic-gradient-based neural network optimization. We illustrate the power of DRNets on de-mixing overlapping hand-written Sudokus (Multi-MNIST-Sudoku) and on a substantially more complex task in scientific discovery that concerns inferring crystal structures of materials from X-ray diffraction data under thermodynamic rules (Crystal-Structure-Phase-Mapping). At a high level, DRNets encode a structured latent space of the input data, which is constrained to adhere to prior knowledge by a reasoning module. The structured latent encoding is used by a generative decoder to generate the targeted output. Finally, an overall objective combines responses from the generative decoder (thinking fast) and the reasoning module (thinking slow), which is optimized using constraint-aware stochastic gradient descent. We show how to encode different tasks as DRNets and demonstrate DRNets' effectiveness with detailed experiments: DRNets significantly outperform the state of the art and experts' capabilities on Crystal-Structure-Phase-Mapping, recovering more precise and physically meaningful crystal structures. On Multi-MNIST-Sudoku, DRNets perfectly recovered the mixed Sudokus' digits, with 100% digit accuracy, outperforming the supervised state-of-the-art MNIST de-mixing models. Finally, as a proof of concept, we also show how DRNets can solve standard combinatorial problems -- 9-by-9 Sudoku puzzles and Boolean satisfiability problems (SAT), outperforming other specialized deep learning models. DRNets are general and can be adapted and expanded to tackle other tasks.


SMT-based Constraint Answer Set Solver EZSMT+

arXiv.org Artificial Intelligence

Answer set programming (ASP) is a declarative programming paradigm for solving difficult combinatorial search problems [6]. Constraint answer set programming (CASP) is a recent development, which integrates ASP with constraint processing. Often, this integration allows one to tackle a challenge posed by the grounding bottleneck. Originally, systems that process CASP programs rely on combining algorithms/solvers employed in ASP and constraint processing [11,1].


Revisiting Graph Width Measures for CNF-Encodings

arXiv.org Artificial Intelligence

We consider bounded width CNF-formulas where the width is measured by popular graph width measures on graphs associated to CNF-formulas. Such restricted graph classes, in particular those of bounded treewidth, have been extensively studied for their uses in the design of algorithms for various computational problems on CNF-formulas. Here we consider the expressivity of these formulas in the model of clausal encodings with auxiliary variables. We first show that bounding the width for many of the measures from the literature leads to a dramatic loss of expressivity, restricting the formulas to such of low communication complexity. We then show that the width of optimal encodings with respect to different measures is strongly linked: there are two classes of width measures, one containing primal treewidth and the other incidence cliquewidth, such that in each class the width of optimal encodings only differs by constant factors. Moreover, between the two classes the width differs at most by a factor logarithmic in the number of variables. Both these results are in stark contrast to the setting without auxiliary variables where all width measures we consider here differ by more than constant factors and in many cases even by linear factors.


Dependency Learning for QBF

Journal of Artificial Intelligence Research

Quantified Boolean Formulas (QBFs) can be used to succinctly encode problems from domains such as formal verification, planning, and synthesis. One of the main approaches to QBF solving is Quantified Conflict Driven Clause Learning (QCDCL). By default, QCDCL assigns variables in the order of their appearance in the quantifier prefix so as to account for dependencies among variables. Dependency schemes can be used to relax this restriction and exploit independence among variables in certain cases, but only at the cost of nontrivial interferences with the proof system underlying QCDCL. We introduce dependency learning, a new technique for exploiting variable independence within QCDCL that allows solvers to learn variable dependencies on the fly. The resulting version of QCDCL enjoys improved propagation and increased flexibility in choosing variables for branching while retaining ordinary (long-distance) Q-resolution as its underlying proof system. We show that dependency learning can achieve exponential speedups over ordinary QCDCL. Experiments on standard benchmark sets demonstrate the effectiveness of this technique.


Casting Geometric Constraints in Semantic Segmentation as Semi-Supervised Learning

arXiv.org Artificial Intelligence

We propose a simple yet effective method to learn to segment new indoor scenes from an RGB-D sequence: State-of-the-art methods trained on one dataset, even as large as SUNRGB-D dataset, can perform poorly when applied to images that are not part of the dataset, because of the dataset bias, a common phenomenon in computer vision. To make semantic segmentation more useful in practice, we learn to segment new indoor scenes from sequences without manual annotations by exploiting geometric constraints and readily available training data from SUNRGB-D. As a result, we can then robustly segment new images of these scenes from color information only. To efficiently exploit geometric constraints for our purpose, we propose to cast these constraints as semi-supervised terms, which enforce the fact that the same class should be predicted for the projections of the same 3D location in different images. We show that this approach results in a simple yet very powerful method, which can annotate sequences of ScanNet and our own sequences using only annotations from SUNRGB-D.


How To Improve Supply Chains With Machine Learning: 10 Proven Ways

#artificialintelligence

Bottom line: Enterprises are attaining double-digit improvements in forecast error rates, demand planning productivity, cost reductions and on-time shipments using machine learning today, revolutionizing supply chain management in the process. Machine learning algorithms and the models they're based on excel at finding anomalies, patterns and predictive insights in large data sets. Many supply chain challenges are time, cost and resource constraint-based, making machine learning an ideal technology to solve them. From Amazon's Kiva robotics relying on machine learning to improve accuracy, speed and scale to DHL relying on AI and machine learning to power their Predictive Network Management system that analyzes 58 different parameters of internal data to identify the top factors influencing shipment delays, machine learning is defining the next generation of supply chain management. Gartner predicts that by 2020, 95% of Supply Chain Planning (SCP) vendors will be relying on supervised and unsupervised machine learning in their solutions.


Preference Reasoning in Matching Procedures: Application to the Admission Post-Baccalaureat Platform

arXiv.org Artificial Intelligence

Because preferences naturally arise and play an important role in many real-life decisions, they are at the backbone of various fields. In particular preferences are increasingly used in almost all matching procedures-based applications. In this work we highlight the benefit of using AI insights on preferences in a large scale application, namely the French Admission Post-Baccalaureat Platform (APB). Each year APB allocates hundreds of thousands first year applicants to universities. This is done automatically by matching applicants preferences to university seats. In practice, APB can be unable to distinguish between applicants which leads to the introduction of random selection. This has created frustration in the French public since randomness, even used as a last mean does not fare well with the republican egalitarian principle. In this work, we provide a solution to this problem. We take advantage of recent AI Preferences Theory results to show how to enhance APB in order to improve expressiveness of applicants preferences and reduce their exposure to random decisions.