The paper considers solving the multiple sequence alignment, a combinatorial challenge in computational biology, where several DNA RNA, or protein sequences are to be arranged for high similarity. The proposal applies randomized Monte-Carlo tree search with nested rollouts and is able to improve the solution quality over time. Instead of learning the position of the letters, the approach learns a policy for the position of the gaps. The Monte-Carlo beam search algorithm we have implemented has a low memory overhead and can be invoked with constructed or known initial solutions. Experiments in the BAliBASE benchmark show promising results in improving state-of-the-art alignments.

In this paper we treat the problem of feature selection in unsupervised learning as a state-space search problem. We introduce three different heuristic functions and perform extensive experiments on datasets with tens, hundreds, and thousands of features. Namely, we test different search algorithms using the heuristic functions we introduce. Our results show that the heuristic search approach for feature selection in unsupervised learning problems can be far superior than traditional baselines such as PCA and random projections.

Spacecraft missions to small celestial bodies face sensitive, strongly non-Keplerian dynamics that motivate the employment of automated sampling-based trajectory planning. However, the scarcity of onboard computing resources necessitates careful formulation of heuristics for efficiently searching the reachable sets, which exhibit complex and finely-detailed structure. We examine a global search heuristic that combines aspects of simulated annealing and hill-climbing to locate sparse regions of the planning domain that simultaneously satisfy numerous geometric and timing constraints associated with remote sensing objectives for points of interest on the central body surface. Subsequently, we demonstrate the use of a receding-horizon implementation of this maneuver-planning strategy to produce mission profiles that fulfill sets of such goals.

The traditional approach for solving Constraint satisfaction Problems (CSPs) is searching the Assignment Space in which each state represents an assignment to some variables. This paper suggests a new search space formalization for CSPs, the Partial Domain Search Tree (PDST). In each PDST node aunique subset of the original domain is considered, values are excluded from the domains in each node to insure that a given set of constraints is satisfied. We provide theoretical analysis of this new approach showing that searching the PDST is beneficial for loosely constrained problems. Experimental results show that this new formalization is a promising direction for future research. In some cases searching the PDST outperforms the traditional approach by an order of magnitude. Furthermore, PDST can enhance Local Search techniques resulting in solutions that violate up to 30% less constraints.

For some two-player games (e.g. Go), no accurate and inexpensive heuristic is known for evaluating leaves of a search tree. For other games (e.g. chess), a heuristic is known (sum of piece values). For other games (e.g. Hex), only a local heuristic — one that compares children reliably, but non-siblings poorly — is known (cell voltage drop in the Shannon/Anshelevich electric circuit model). In this paper we introduce a search algorithm for a two-player perfect information game with a reasonable local heuristic. Sibling Conspiracy Number Search (SCNS) is an anytime best-first version of Conspiracy Number Search based not on evaluation of leaf states of the search tree, but — for each node — on relative evaluation scores of all children of that node. SCNS refines CNS search value intervals, converging to Proof Number Search. SCNS is a good framework for a game player. We tested SCNS in the domain of Hex, with promising results. We implemented an 11-by-11 SCNS Hex bot, DeepHex. We competed DeepHex against current Hex bot champion MoHex, a Monte-Carlo Tree Search player, and previous Hex bot champion Wolve, an Alpha-Beta Search player. DeepHex widely outperforms Wolve at all time levels, and narrowly outperforms MoHex once time reaches 4min/move.

Real-time heuristic search addresses the setting in which planning andacting can proceed concurrently. We explore the use of metareasoning at two decision points within a real-time heuristic search. First, if the domain has an `identity action' that allows the agent to remain in the same state and deliberate further, when should this action be taken? Second, given a partial plan that extends to the lookahead frontier, to how many actions should the agent commit? We show that considering these decisions carefully can reduce the agent's total time taken to arrive at a goal in several benchmark domains, relative to the current state-of-the-art. The resulting algorithm can dynamically adjust the way it interleaves planning and acting, between greedy hill-climbing and A*, depending on the problem instance.

Most work in heuristic search focused on path finding problems in which the cost of a path in the state space is the sum of its edges' weights. This paper addresses a different class of path finding problems in which the cost of a path is the product of its weights. We present reductions from different classes of multiplicative path finding problems to suitable classes of additive path finding problems. As a case study, we consider the problem of finding least and most probable paths in a Markov Chain, where path cost corresponds to the probability of traversing it. The importance of this problem is demonstrated in an anomaly detection application for cyberspace security. Three novel anomaly detection metrics for Markov Chains are presented, where computing these metrics require finding least and most probable paths. The underlying Markov Chain is dynamically changing, and so fast methods for computing least and most probable paths are needed. We propose such methods based on the proposed reductions and using heuristic search algorithms.

In empirical studies we observed that caching can have very little impact in reducing the search effort in Branch and Bound search over context-minimal OR spaces. For example, in one of the problem domains used in our experiments we reduce only by 1% the number of nodes expanded when using caching in context-minimal OR spaces. By contrast, we reduce by 74% the number of nodes expanded when using caching in context-minimal AND/OR spaces on the same instances. In this work we document this unexpected empirical finding and provide explanations for the phenomenon.

The traditional focus of combinatorial search research is to speed up the search algorithm. An alternative, however, is to create a sparser representation of the search space. This relates to the idea of spanners from graph theory. These are subgraphs which retain paths between any two vertices of the original graph while guaranteeing a maximum stretch in path length. In practice, the path degradation of graph spanners is significantly smaller than the theoretical bound. Even so, expected path degradation of graph spanners is typically not studied. This work focuses on grid path-finding to propose an algorithm that constructs a grid spanner, where analysis for the obstacle-free case shows that significant performance gains can be achieved with a small decrease in expected path quality. This is an important first step towards studying the expected performance of spanners. Experiments on game maps show that expected path quality with obstacles is only sometimes marginally lower than that in the obstacle-free case and that a significant reduction in the size of the search space can be achieved.

In the last decade the emphasis on improving the operational performance of domain independent automated planners has been in developing complex techniques which merge a range of different strategies. This quest for operational advantage, driven by the regular international planning competitions, has not made it easy to study, understand and predict what combinations of techniques will have what effect on a planner’s behaviour in a particular application domain. In this paper, we consider two machine learning techniques for planner performance improvement, and exploit a modular approach to their combination in order to facilitate the analysis of the impact of each individual component. We believe this can contribute to the development of more transparent planning engines, which are designed using modular, interchangeable, and well-founded components. Specifically, we combined two previously unrelated learning techniques, entanglements and relational decision trees, to guide a “vanilla” search algorithm. We report on a large experimental analysis which demonstrates the effectiveness of the approach in terms of performance improvements, resulting in a very competitive planning configuration despite the use of a more modular and transparent architecture. This gives insights on the strengths and weaknesses of the considered approaches, that will help their future exploitation.