A number of effective techniques for constraint-based optimization can be used to generate either diverse or high-quality solutions independently, but no framework is devoted to accomplish both simultaneously. In this paper, we tackle this issue with a generic paradigm that can be implemented in most existing solvers. We show that our technique can be specialized to produce diverse solutions of high quality in the context of over-constrained problems. Furthermore, our paradigm allows us to consider diversity from a different point of view, based on generic concepts expressed by global constraints.

Many natural phenomena exhibit power law spectra. In particular, so-called 1/f α noise series with α close to 1 (also called pink noise) occur in sound, music and countless human artifacts or natural events, from the fluctuations of the flood levels of the Nile to movements of the stock market. As a consequence, many generative models for 1/f noise have been designed to produce series that look or sound “natural” or “human”. In this paper, we formulate the generation of 1/f series as a hard constraint satisfaction problem, so that 1/f noise generation can be used as an add-on to arbitrary sequence generation problems. We take inspiration from a simple yet beautiful stochastic algorithm invented by Voss and introduce the Voss constraint. We show that Voss’ algorithm can be modeled as a tree of ternary sum constraints, leading to efficient filtering. We illustrate our constraint with a melody generation problem, and show that the addition of the Voss constraint tends indeed to produce sequences whose spectrum have a 1/f distribution, regardless of the other constraints of the problem. We discuss the advantages and limitations of this approach and possible extensions.

A key challenge in solving extensive-form games is dealing with large, or even infinite, action spaces. In games of imperfect information, the leading approach is to find a Nash equilibrium in a smaller abstract version of the game that includes only a few actions at each decision point, and then map the solution back to the original game. However, it is difficult to know which actions should be included in the abstraction without first solving the game, and it is infeasible to solve the game without first abstracting it. We introduce a method that combines abstraction with equilibrium finding by enabling actions to be added to the abstraction at run time. This allows an agent to begin learning with a coarse abstraction, and then to strategically insert actions at points that the strategy computed in the current abstraction deems important. The algorithm can quickly add actions to the abstraction while provably not having to restart the equilibrium finding. It enables anytime convergence to a Nash equilibrium of the full game even in infinite games. Experiments show it can outperform fixed abstractions at every stage of the run: early on it improves as quickly as equilibrium finding in coarse abstractions, and later it converges to a better solution than does equilibrium finding in fine-grained abstractions.

In this paper, we study synthesis from logical specifications over finite traces expressed in LTLf and its extension LDLf. Specifically, in this form of synthesis, propositions are partitionedin controllable and uncontrollable ones, and the synthesis task consists of setting the controllable propositions over time so that, in spite of how the value of the uncontrollable ones changes, the specification is fulfilled. Conditional planning in presence of declarative and procedural trajectory constraints is a special case of this form of synthesis. We characterize the problem computationally as 2EXPTIME-complete and present a sound and complete synthesis technique based on DFA (reachability) games.

This paper presents an interdisciplinary project which aims at cross-fertilizing dance with artificial intelligence. It utilizes AI as an approach to explore and unveil new territories of possible dance movements. Statistical analyzes of recorded human dance movements provide the foundation for a system that learns poses from human dancers, extends them with novel variations and creates new movement sequences. The system provides dancers with a tool for exploring possible movements and finding inspiration from motion sequences generated automatically in real time in the form of an improvising avatar. Experiences of bringing the avatar to the studio as a virtual dance partner indicate the usefulness of the software as a tool for kinetic exploration. In addition to these artistic results, the experiments also raise questions about how AI generally relates to artistic agency and creativity. Is the improvising avatar truly creative, or is it merely some kind of extension of the dancer or the AI researcher? By analyzing the developed platform as a framework for exploration of conceptual movement spaces, and by considering the interaction between dancer, researcher and software, some possible interpretations of this particular kind of creative process can be offered.

Among various traditional art forms, brush stroke drawing is one of the widely used styles in modern computer graphic tools such as GIMP, Photoshop and Painter. In this paper, we develop an AI-aided art authoring (A4) system of non-photorealistic rendering that allows users to automatically generate brush stroke paintings in a specific artist's style. Within the reinforcement learning framework of brush stroke generation proposed, our contribution in this paper is to learn artists' drawing styles from video-captured stroke data by inverse reinforcement learning. Through experiments, we demonstrate that our system can successfully learn artists' styles and render pictures with consistent and smooth brush strokes.

We address a spatial conservation planning problem in which the planner purchases a budget-constrained set of land parcels in order to maximize the expected spread of a population of an endangered species. Existing techniques based on the sample average approximation scheme and standard integer programming methods have high complexity and limited scalability. We propose a fast combinatorial optimization algorithm using Lagrangian relaxation and primal-dual techniques to solve the problem approximately. The algorithm provides a new way to address a range of conservation planning and scheduling problems. On the Red-cockaded Woodpecker data, our algorithm produces near optimal solutions and runs significantly faster than a standard mixed integer program solver. Compared with a greedy baseline, the solution quality is comparable or better, but our algorithm is 10–30 times faster. On synthetic problems that do not exhibit submodularity, our algorithm significantly outperforms the greedy baseline.

In this paper, we propose a weakly supervised Restricted Boltzmann Machines (WRBM) approach to deal with the task of semantic segmentation with only image-level labels available. In WRBM, its hidden nodes are divided into multiple blocks, and each block corresponds to a specific label. Accordingly, semantic segmentation can be directly modeled by learning the mapping from visible layer to the hidden layer of WRBM. Specifically, based on the standard RBM, we import another two terms to make full use of image-level labels and alleviate the effect of noisy labels. First, we expect the hidden response of each superpixel is suppressed on the labels outside its parent image-level label set, and a non-image-level label suppression term is formulated to implicitly import the image-level labels as weak supervision. Second, semantic graph propagation is employed to exploit the cooccurrence between visually similar regions and labels. Besides, we deal with the problems of label imbalance and diverse backgrounds by adapting the block size to the label frequency and appending hidden response blocks corresponding to backgrounds respectively. Extensive experiments on two real-world datasets demonstrate the good performance of our approach compared with some state-of-the-art methods.

We increase the usefulness of Chu and Stuckey's work by automating it, that is, by developing a method to (a) automatically The exploitation of dominance relations in constraint identify symmetries for a given problem, and (b) optimization problems can lead to dramatic automatically construct the associated dominance breaking reductions in search space. We propose an automatic constraints. Note that these dominance breaking constraints method to detect some of the dominance relations are not symmetry breaking constraints, as the key element manually identified by Chu and Stuckey for is for f(σ(θ)) to be better. Further, the symmetries need to optimization problems, and to construct the associated be detected for the inherent satisfaction problem -- that is, dominance breaking constraints. Experimental the problem without the objective function -- or, otherwise, results show that the method is able to find several f(σ(θ)) will be equal to f(θ), not better.

Pruning techniques based on partial order reduction and symmetry elimination have recently found increasing attention for optimal planning. Although these techniques appear to be rather different, they base their pruning decisions on similar ideas from a high level perspective. In this paper, we propose safe integrations of partial order reduction and symmetry elimination for cost-optimal classical planning. We show that previously proposed symmetry-based search algorithms can safely be applied with strong stubborn sets. In addition, we derive the notion of symmetrical strong stubborn sets as a more tightly integrated concept. Our experiments show the potential of our approaches.