"The Crossword puzzle (CP) is a simple problem to illustrate the formalization process of a problem into a CSP. The problem is to place words of a dictionary in a given structure satisfying certain constraints. The variables are the rows and columns in the crossword, and their values are the words in a dictionary."
– Marc Torrens. An Application using the JCL: The Air Travel Planning System. Diploma Thesis, 1997, Chapter 1, Section 1.2.1.
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.
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.
Hofmann, Till (RWTH Aachen University) | Mataré, Victor (FH Aachen University for Applied Sciences) | Schiffer, Stefan (RWTH Aachen University, FH Aachen University for Applied Sciences) | Ferrein, Alexander (FH Aachen University for Applied Sciences) | Lakemeyer, Gerhard (RWTH Aachen University)
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.
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.
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.