"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.
Constrained sequential pattern mining aims at identifying frequent patterns on a sequential database of items while observing constraints defined over the item attributes. We introduce novel techniques for constraint-based sequential pattern mining that rely on a multi-valued decision diagram representation of the database. Specifically, our representation can accommodate multiple item attributes and various constraint types, including a number of non-monotone constraints. To evaluate the applicability of our approach, we develop an MDD-based prefix-projection algorithm and compare its performance against a typical generate-and-check variant, as well as a state-of-the-art constraint-based sequential pattern mining algorithm. Results show that our approach is competitive with or superior to these other methods in terms of scalability and efficiency.
Constraint answer set programming integrates answer set programming with constraint processing. System EZSMT+ is a constraint answer set programming tool that utilizes satisfiability modulo theory solvers for search. The truly unique feature of EZSMT+ is its capability to process linear as well as nonlinear constraints simultaneously containing integer and real variables.
Generalized CP-nets (gCP-nets) extend standard CP-nets by allowing conditional preference tables to be incomplete. Such generality is desirable, as in practice users may want to express preferences over the values of a variable that depend only on partial assignments for other variables. In this paper we study aggregation of gCP-nets, under the name of multiple gCP-nets (mgCP-nets). Inspired by existing research on mCP-nets, we define different semantics for mgCP-nets and study the complexity of prominent reasoning tasks such as dominance, consistency and various notions of optimality.
Soft goals in planning are optional objectives that should be achieved in the terminal state. However, failing to achieve them does not result in the plan becoming invalid. State trajectory constraints are hard requirements towards the state trajectory of the plan. Soft trajectory constraints are a combination of both: soft preferences on how the hard goals are reached, i.e., optional requirements towards the state trajectory of the plan. Such a soft trajectory constraint may require that some fact should be always true, or should be true at some point during the plan. The quality of a plan is then measured by a metric which adds the sum of all action costs and a penalty for each failed soft trajectory constraint. Keyder and Geffner showed that soft goals can be compiled away. We generalize this approach and illustrate a method of compiling soft trajectory constraints into conditional effects and state dependent action costs using LTLf and deterministic finite automata. We provide two compilation schemes, with and without reward shaping, by rewarding and penalizing different states in the plan. With this we are able to handle such soft trajectory constraints without the need of altering the search algorithm or heuristics, using classical planners.
Direction relations are some of the most commonly used spatial relations in human communication. A number of formalisms have been proposed to capture direction information, but all of them suffer from the same problem: people use direction relations as if they are binary relations (e.g. A is to the left of B) when they are in fact ternary relations (e.g. A is to the left of B when viewed from C). This implicit third piece of information that is required, but typically missing, is often referred to as the frame of reference (FoR). Given only binary direction relations without knowing the FoR means that we cannot do proper spatial reasoning (e.g. A is to the left of B and A is to the right of B are both consistent), we cannot integrate direction information from different sources, not even from the same source, and it can be difficult to understand what exactly someone means. In this paper we provide 1) the spatial constraint language DAFm that can represent and compose direction relations across different FoRs; and 2) the foundations for deciding the overall consistency. We hope our model of representing and reasoning can bring research on direction relations to another level and will finally make it possible to properly use them in a comprehensive way.
The Clustered Traveling Salesman Problem with a Prespecified Order on the Clusters, a variant of the well-known traveling salesman problem is studied in literature. In this problem, delivery locations are divided into clusters with different urgency levels and more urgent locations must be visited before less urgent ones. However, this could lead to an inefficient route in terms of traveling cost. This priority-oriented constraint can be relaxed by a rule called d-relaxed priority that provides a trade-off between transportation cost and emergency level. Our research proposes two approaches to solve the problem with d-relaxed priority rule. We improve the mathematical formulation proposed in the literature to construct an exact solution method. A meta-heuristic method based on the framework of Iterated Local Search with problem-tailored operators is also introduced to find approximate solutions. Experimental results show the effectiveness of our methods.
Technology has shaped the way on which we compose and produce music: Notably, the invention of microphones, magnetic tapes, amplifiers and computers pushed the development of new music styles in the 20th century. In fact, several artistic domains have been benefiting from such technology developments; for instance, Experimental music, nonlinear music, Electroacoustic music, and interactive music. Experimental music is composed in such a way that its outcome is often unforeseeable; for instance, it may contain random generated tones, computer-generated content, variable-duration notes and "free" content. It may also include atonal melodies and microtones. Another domain is nonlinear music, in which the scenario is divided in parts whose order can be chosen at execution time. We will use the term "nonlinear" music in that sense. Nonlinear music exists from many centuries ago; for instance, Mozart's minuets in which the order of work's musical material was determined by coin-tosses. Electroacoustic music was originated by the incorporation of electronic sound production into compositional practice.
First this report presents a restricted set of finite transducers used to synthesise structural time-series constraints described by means of a multi-layered function composition scheme. Second it provides the corresponding synthesised catalogue of structural time-series constraints where each constraint is explicitly described in terms of automata with registers.
Procedural content generation via machine learning (PCGML) is typically framed as the task of fitting a generative model to full-scale examples of a desired content distribution. This approach presents a fundamental tension: the more design effort expended to produce detailed training examples for shaping a generator, the lower the return on investment from applying PCGML in the first place. In response, we propose the use of discriminative models (which capture the validity of a design rather the distribution of the content) trained on positive and negative examples. Through a modest modification of WaveFunctionCollapse, a commercially-adopted PCG approach that we characterize as using elementary machine learning, we demonstrate a new mode of control for learning-based generators. We demonstrate how an artist might craft a focused set of additional positive and negative examples by critique of the generator's previous outputs. This interaction mode bridges PCGML with mixed-initiative design assistance tools by working with a machine to define a space of valid designs rather than just one new design.
The performance of enumerating all solutions to an instance of Langford's Problem is sensitive to the model and the search strategy. In this paper we compare the performance of a large variety of models, all derived from two base viewpoints. We empirically show that a channelled model with a static branching order on one of the viewpoints offers the best performance out of all the options we consider. Surprisingly, one of the base models proves very effective for propagation, while the other provides an effective means of stating a static search order.