Decomposition is an effective technique for solving discrete Constraint Optimization Problems (COPs) with low tree-width. On problems with high treewidth, however, existing decomposition algorithms offer little advantage over branch and bound search (B&B). In this paper we propose a method for exploiting decomposition on problems with high treewidth. Our technique involves modifying B&B to detect and exploit decomposition on a selected subset of the problem’s objectives. Decompositions over this subset, generated during search, are exploited to compute tighter bounds allowing B&B to prune more of its search space. We present a heuristic for selecting an appropriate subset of objectives—one that readily decomposes during search and yet can still provide good bounds. We demonstrate empirically that our approach can significantly improve B&B’s performance and outperform standard decomposition algorithms on a variety of high tree-width problems.

Designing high-performance algorithms for computationally hard problems is a difficult and often time-consuming task. In this work, we demonstrate that this task can be automated in the context of stochastic local search (SLS) solvers for the propositional satisfiability problem (SAT). We first introduce a generalised, highly parameterised solver framework, dubbed SATenstein, that includes components gleaned from or inspired by existing high-performance SLS algorithms for SAT. The parameters of SATenstein control the selection of components used in any specific instantiation and the behaviour of these components. SATenstein can be configured to instantiate a broad range of existing high-performance SLSbased SAT solvers, and also billions of novel algorithms. We used an automated algorithm configuration procedure to find instantiations of SATenstein that perform well on several well-known, challenging distributions of SAT instances. Overall, we consistently obtained significant improvements over the previously best-performing SLS algorithms, despite expending minimal manual effort.

The rectangle packing problem consists of finding an enclosing rectangle of smallest area that can contain a given set of rectangles without overlap. Our algorithm picks the x-coordinates of all the rectangles before picking any of the y-coordinates. For the x-coordinates, we present a dynamic variable ordering heuristic and an adaptation of a pruning algorithm used in previous solvers. We then transform the rectangle packing problem into a perfect packing problem that has no empty space, and present inference rules to reduce the instance size. For the y-coordinates we search a space that models empty positions as variables and rectangles as values. Our solver is over 19 times faster than the previous state-of-the-art on the largest problem solved to date, allowing us to extend the known solutions for a consecutive-square packing benchmark from N=27 to N=32.

Alpha-Beta is the most common game tree search algorithm, due to its high-performance and straightforward implementation. In practice one must find the best trade-off between heuristic evaluation time and bringing the subset of nodes explored closer to a minimum proof graph. In this paper we present a series of structural properties of minimum proof graphs that help us to prove that finding such graphs is NP-hard for arbitrary DAG inputs, but can be done in linear time for trees. We then introduce the class of fastest-cut-first search heuristics that aim to approximate minimum proof graphs by sorting moves based on approximations of sub-DAG values and sizes. To explore how various aspects of the game tree (such as branching factor and distribution of move values) affect the performance of Alpha-Beta we introduce the class of ``Prefix Value Game Trees'' that allows us to label interior nodes with true minimax values on the fly without search. Using these trees we show that by explicitly attempting to approximate a minimum game tree we are able to achieve performance gains over Alpha-Beta with common extensions.

Many local search algorithms are based on searching in the k-exchange neighborhood. This is the set of solutions that can be obtained from the current solution by exchanging at most k elements. As a rule of thumb, the larger k is, the better are the chances of  finding an improved  solution. However,  for inputs of size n,  a naive brute-force search of the k-exchange neighborhood requires n (O(k)) time, which is not practical even for very small values of k. We show that for several classes of sparse graphs, like planar graphs, graphs of bounded vertex degree and graphs excluding some fixed graph as a minor, an improved solution in the k-exchange neighborhood for many problems can be found much more efficiently.  Our algorithms run in time O(T(k)*n c ), where T is a function depending on k only and c is a constant independent of k.  We demonstrate the applicability of this  approach on different  problems like r-Center, Vertex Cover,  Odd Cycle Transversal, Max-Cut, and  Min-Bisection.  In particular, on planar graphs, all our algorithms searching for a k-local improvement run in time O(2 (O(k) ) * n (2) ), which is polynomial for k=O(log n). We also complement the algorithms with complexity results indicating that brute force search is unavoidable in more general classes of sparse graphs.

Monte Carlo tree search has brought significant improvements to the level of computer players in games such as Go, but so far it has not been used very extensively in games of strongly imperfect information with a dynamic board and an emphasis on risk management and decision making under uncertainty. In this paper we explore its application to the game of Kriegspiel (invisible chess), providing three Monte Carlo methods of increasing strength for playing the game with little specific knowledge. We compare these Monte Carlo agents to the strongest known minimax-based Kriegspiel player, obtaining significantly better results with a considerably simpler logic and less domain-specific knowledge.

Many problems have a huge state space and no good heuristic to order moves so as to guide the search toward the best positions. Random games can be used to score positions and evaluate their interest. Random games can also be improved using random games to choose a move to try at each step of a game. Nested Monte-Carlo Search addresses the problem of guiding the search toward better states when there is no available heuristic. It uses nested levels of random games in order to guide the search. The algorithm is studied theoretically on simple abstract problems and applied successfully to three different games: Morpion Solitaire, SameGame and 16x16 Sudoku.

To harness modern multi-core processors, it is imperative to develop parallel versions of fundamental algorithms. In this paper, we present a general approach to best-first heuristic search in a shared-memory setting. Each thread attempts to expand the most promising open nodes. By using abstraction to partition the state space, we detect duplicate states without requiring frequent locking. We allow speculative expansions when necessary to keep threads busy. We identify and fix potential livelock conditions in our approach, verifying its correctness using temporal logic. In an empirical comparison on STRIPS planning, grid pathfinding, and sliding tile puzzle problems using an 8-core machine, we show that A* implemented in our framework yields faster search than improved versions of previous parallel search proposals. Our approach extends easily to other best-first searches, such as Anytime weighted A*.

The Canadian Traveler Problem (CTP) is a navigation problem where a graph is initially known,  but some edges may be blocked with a known probability.  The task is to minimize travel effort of reaching the goal. We generalize CTP to allow for remote sensing actions, now requiring minimization  of the sum of the travel cost and the remote sensing cost. Finding optimal policies for both versions is intractable. We provide optimal solutions for special case graphs. We then develop a framework that utilizes heuristics to determine when and where to sense the environment in order to minimize total costs. Several such heuristics, based on the expected total cost are introduced.  Empirical evaluations show the benefits of our heuristics and support some of the theoretical results.

Real-time heuristic search algorithms are used for planning by agents in situations where a constant-bounded amount of deliberation time is required for each action regardless of the problem size.  Such algorithms interleave their planning and execution to ensure real-time response. Furthermore, to guarantee completeness, they typically store improved heuristic estimates for previously expanded states.  Although subsequent planning steps can benefit from updated heuristic estimates, many of the same states are expanded over and over again.   Here we propose a variant of the A* algorithm, Time-Bounded A* (TBA*), that guarantees real-time response. In the domain of path-finding on video-game maps TBA* expands an order of magnitude fewer states than traditional real-time search algorithms, while finding paths of comparable quality. It reaches the same level of performance as recent state-of-the-art real-time search algorithms but, unlike these, requires neither state-space abstractions nor pre-computed pattern databases.