Related Problems: Rubik's cube, N-Puzzle and Misspelling Type: Utility Description: A Pattern Database stores a collection of solutions to sub-problems that must be achieved to solve the problem. While we normally think of a heuristic as a function computed by an algorithm, any function can also be computed by a table lookup, given sufficient memory. In fact, for reasons of efficiency, heuristic functions are commonly precomputed and stored in memory. In the case of the N-Puzzle, the tiles occupying certain locations are unspecified (blank). A pattern database (PDB): is the set of all patterns which can be obtained by permutations of a target pattern.

The big news on March 12 of this year was of the Go-playing AI-system AlphaGo securing victory against 18-time world champion Lee Se-dol by winning the third straight game of a five-game match in Seoul, Korea. After Deep Blue's victory against chess world champion Gary Kasparov in 1997, the game of Go was the next grand challenge for game-playing artificial intelligence. Go has defied the brute-force methods in game-tree search that worked so successfully in chess. In 2012, Communications published a Research Highlight article by Sylvain Gelly et al. on computer Go, which reported that "Programs based on Monte-Carlo tree search now play at human-master levels and are beginning to challenge top professional players." AlphaGo combines tree-search techniques with search-space reduction techniques that use deep learning.

Apple's Siri, Microsoft's Cortana and all the search algorithms out there today show that robots are often the first point of contact for marketers trying to reach customers. For those concerned about a robot takeover, remember that artificial intelligence (AI) can be a marketer's best friend. Robots, unlike people, are consistent. They are good at tracking and delivering high-quality results which save us time, money and effort. Robots ultimately answer to us, making them effective helpers upon which we can increasingly rely.

The development of problem solvers for configuration tasks is one of the most successful and mature application areas of artificial intelligence. The provision of tailored products, services, and systems requires efficient engineering and design processes where configurators play a crucial role. Because one of the core competencies of Siemens is to provide such highly engineered and customized systems, ranging from solutions for medium-sized and small businesses up to huge industrial plants, the efficient implementation and maintenance of configurators are important goals for the success of many departments. For more than 25 years the application of constraint-based methods has proven to be a key technology in order to realize configurators at Siemens. This article summarizes the main aspects and insights we have gained looking back over this period. In particular, we highlight the main technology factors regarding knowledge representation, reasoning, and integration which were important for our achievement. Finally we describe selected key application areas where the business success vitally depends on the high productivity of configuration processes.

Best-first search algorithms such as A* need to apply tie-breaking strategies in order to decide which node to expand when multiple search nodes have the same evaluation score. We investigate and improve tie-breaking strategies for cost-optimal search using A*. We first experimentally analyze the performance of common tie-breaking strategies that break ties according to the heuristic value of the nodes. We find that the tie-breaking strategy has a significant impact on search algorithm performance when there are 0-cost operators that induce large plateau regions in the search space. Based on this, we develop two new classes of tie-breaking strategies. We first propose a depth diversification strategy which breaks ties according to the distance from the entrance to the plateau, and then show that this new strategy significantly outperforms standard strategies on domains with 0-cost actions. Next, we propose a new framework for interpreting A* search as a series of satisficing searches within plateaus consisting of nodes with the same f-cost. Based on this framework, we investigate a second, new class of tie-breaking strategy, a multi-heuristic tie-breaking strategy which embeds inadmissible, distance-to-go variations of various heuristics within an admissible search. This is shown to further improve the performance in combination with the depth metric.

The classification of MRI images according to the anatomical field of view is a necessary task to solve when faced with the increasing quantity of medical images. In parallel, advances in deep learning makes it a suitable tool for computer vision problems. Using a common architecture (such as AlexNet) provides quite good results, but not sufficient for clinical use. Improving the model is not an easy task, due to the large number of hyper-parameters governing both the architecture and the training of the network, and to the limited understanding of their relevance. Since an exhaustive search is not tractable, we propose to optimize the network first by random search, and then by an adaptive search based on Gaussian Processes and Probability of Improvement. Applying this method on a large and varied MRI dataset, we show a substantial improvement between the baseline network and the final one (up to 20\% for the most difficult classes).

This paper presents a framework to tackle combinatorial optimization problems using neural networks and reinforcement learning. We focus on the traveling salesman problem (TSP) and train a recurrent network that, given a set of city coordinates, predicts a distribution over different city permutations. Using negative tour length as the reward signal, we optimize the parameters of the recurrent network using a policy gradient method. We compare learning the network parameters on a set of training graphs against learning them on individual test graphs. Despite the computational expense, without much engineering and heuristic designing, Neural Combinatorial Optimization achieves close to optimal results on 2D Euclidean graphs with up to 100 nodes. Applied to the KnapSack, another NP-hard problem, the same method obtains optimal solutions for instances with up to 200 items.

This work proposes a unified heuristic algorithm for a large class of earliness-tardiness (E-T) scheduling problems. We consider single/parallel machine E-T problems that may or may not consider some additional features such as idle time, setup times and release dates. In addition, we also consider those problems whose objective is to minimize either the total (average) weighted completion time or the total (average) weighted flow time, which arise as particular cases when the due dates of all jobs are either set to zero or to their associated release dates, respectively. The developed local search based metaheuristic framework is quite simple, but at the same time relies on sophisticated procedures for efficiently performing local search according to the characteristics of the problem. We present efficient move evaluation approaches for some parallel machine problems that generalize the existing ones for single machine problems. The algorithm was tested in hundreds of instances of several E-T problems and particular cases. The results obtained show that our unified heuristic is capable of producing high quality solutions when compared to the best ones available in the literature that were obtained by specific methods. Moreover, we provide an extensive annotated bibliography on the problems related to those considered in this work, where we not only indicate the approach(es) used in each publication, but we also point out the characteristics of the problem(s) considered. Beyond that, we classify the existing methods in different categories so as to have a better idea of the popularity of each type of solution procedure.

It is well known that the global optimum of a MDP with finite state and action sets can be obtained through methods based on dynamic programming. Unfortunately, these techniques are known to suffer from the curse of dimensionality, which makes them infeasible for many real-world problems of interest. As a result, most research in the reinforcement learning and control theory literature has focused on obtaining approximate or locally optimal solutions. There exists a broad spectrum of such techniques, including approximate dynamic programming methods, tree search methods, local trajectory-optimization techniques, such as differential dynamic programming and iLQG, and policy search methods. In this talk I shall provide an introduction to policy search methods, which are a family of algorithms that have proven extremely popular in recent years, and which have numerous desirable properties that make them attractive in practice.

The most well known and ubiquitous clustering problem encountered in nearly every branch of science is undoubtedly $k$-means: given a set of data points and a parameter $k$, select $k$ centres and partition the data points into $k$ clusters around these centres so that the sum of squares of distances of the points to their cluster centre is minimized. Typically these data points lie $\mathbb{R}^d$ for some $d\geq 2$. $k$-means and the first algorithms for it were introduced in the 1950's. Since then, hundreds of papers have studied this problem and many algorithms have been proposed for it. The most commonly used algorithm is known as Lloyd-Forgy, which is also referred to as "the" $k$-means algorithm, and various extensions of it often work very well in practice. However, they may produce solutions whose cost is arbitrarily large compared to the optimum solution. Kanungo et al. [2004] analyzed a simple local search heuristic to get a polynomial-time algorithm with approximation ratio $9+\epsilon$ for any fixed $\epsilon>0$ for $k$-means in Euclidean space. Finding an algorithm with a better approximation guarantee has remained one of the biggest open questions in this area, in particular whether one can get a true PTAS for fixed dimension Euclidean space. We settle this problem by showing that a simple local search algorithm provides a PTAS for $k$-means in $\mathbb{R}^d$ for any fixed $d$. More precisely, for any error parameter $\epsilon>0$, the local search algorithm that considers swaps of up to $\rho=d^{O(d)}\cdot{\epsilon}^{-O(d/\epsilon)}$ centres at a time finds a solution using exactly $k$ centres whose cost is at most a $(1+\epsilon)$-factor greater than the optimum. Finally, we provide the first demonstration that local search yields a PTAS for the uncapacitated facility location problem and $k$-median with non-uniform opening costs in doubling metrics.