Constraint-Based Reasoning


C3: From Arc-Consistency to 2-Consistency

AAAI Conferences

Arc consistency algorithms are widely used to prune the search space of Constraint Satisfaction Problems (CSPs). Since many researchers associate arc consistency with binary normalized CSPs, there is a confusion between the notion of arc consistency and 2-consistency.


Efficient SAT Techniques for Absolute Encoding of Permutation Problems: Application to Hamiltonian Cycles

AAAI Conferences

We study novel approaches for solving of hard combinatorial problems by translation to Boolean Satisfiability (SAT). Our focus is on combinatorial problems that can be represented as a permutation of n objects, subject to additional constraints. In the case of the Hamiltonian Cycle Problem (HCP), these constraints are that two adjacent nodes in a permutation should also be neighbors in the original graph for which we search for a Hamiltonian cycle. We use the absolute SAT encoding of permutations, where for each of the n objects and each of its possible positions in a permutation, a predicate is defined to indicate whether the object is placed in that position. For implementation of this predicate, we compare the direct and logarithmic encodings that have been used previously, against 16 hierarchical parameterizable encodings of which we explore 416 instantiations. We propose the use of enumerative adjacency constraints--that enumerate the possible neighbors of a node in a permutation-- instead of, or in addition to the exclusivity adjacency constraints--that exclude impossible neighbors, and that have been applied previously. We study 11 heuristics for efficiently choosing the first node in the Hamiltonian cycle, as well as 8 heuristics for static CNF variable ordering. We achieve at least 4 orders of magnitude average speedup on HCP benchmarks from the phase transition region, relative to the previously used encodings for solving of HCPs via SAT, such that the speedup is increasing with the size of the graphs.


[R] Training Recurrent Neural Networks as a Constraint Satisfaction Problem • r/MachineLearning

@machinelearnbot

Obviously not the paper author, but this looks quite interesting. Mostly the fact that it finds all the local minima and can thus select the global minimum from them is nice. Though it would have been nice to see what the tradeoff is in terms of computational space and time complexity compared to error backpropagation.


Constraint-Based Online Transformation of Abstract Plans into Executable Robot Actions

AAAI Conferences

In this paper, we are concerned with making the execution of abstract action plans for robotic agents more robust. To this end, we propose to model the internals of a robot system and its ties to the actions that the robot can perform. Based on these models, we propose an online transformation of an abstract plan into executable actions conforming with system specifics. With our framework, we aim to achieve two goals. First, modeling the system internals is beneficial in its own right in order to achieve long term autonomy, system transparency, and comprehensibility. Second, separating the system details from determining the course of action on an abstract level leverages the use of planning for actual robotic systems.






Unifying DAGs and UGs

arXiv.org Machine Learning

We introduce a new class of graphical models that generalizes Lauritzen-Wermuth-Frydenberg chain graphs by relaxing the semi-directed acyclity constraint so that only directed cycles are forbidden. Moreover, up to two edges are allowed between any pair of nodes. Specifically, we present local, pairwise and global Markov properties for the new graphical models and prove their equivalence. We also present an equivalent factorization property. Finally, we present a causal interpretation of the new models.


Information Assisted Dictionary Learning for fMRI data analysis

arXiv.org Machine Learning

Extracting information from functional magnetic resonance images (fMRI) has been a major area of research for many years, but is still demanding more accurate techniques. Nowadays, we have a plenty of available information about the brain-behavior that can be used to develop more precise methods. Thus, this paper presents a new Dictionary Learning method that allows incorporating external information regarding the studied problem, through a novel sets of constraints. Finally, we apply this proposed method to synthetic fMRI data, where several tests show an improvement in the performance compared with other common techniques.