The Heuristic Search community has been concentrating much effort during the last decades in solving more and more efficiently the SHORTEST PATH problem (SPP). As a result, a valuable body of scientific results has been produced, mostly in the form of heuristics and search algorithms. However, not much attention has been given to other problems even if they result from slight variations of the typical problems addressed by the community. Furthermore, other communities attempt at solving hard combinatorial problems which might be well solved with heuristic search. In this paper, an attempt is presented to introduce a preliminary selection of relevant problems that goes well beyond the classical SPP.

Monte-Carlo Tree Search (MCTS) algorithms estimate the value of MDP states based on rewards received by performing multiple random simulations. MCTS algorithms can use different strategies to aggregate these rewards and provide an estimation for the states’ values. The most common aggregation method is to store the mean reward of all simulations. Another common approach stores the best observed reward from each state. Both of these methods have complementary benefits and drawbacks. In this paper, we show that both of these methods are biased estimators for the real expected value of MDP states. We propose an hybrid approach that uses the best reward for states with low noise, and otherwise uses the mean. Experimental results on the Sailing MDP domain show that our method has a considerable advantage when the rewards are drawn from a noisy distribution.

Meta-reasoning can improve numerous search algorithms, but necessitates collection of statistics to be used as probability distributions, and involves restrictive meta-reasoning assumptions. The recently suggested scheme of type systems in search algorithms is used in this paper for collecting these statistics. The statistics are then used to better estimate the unknown quantity of expected regret of computing a heuristic in Rational Lazy IDA* (RLIDA*), and also facilitate a second improvement due to relaxing one of the unrealistic meta-reasoning assumptions in RLIDA*.

Suboptimal heuristic search algorithms such as greedy best-first search allow us to find solutions when constraints of either time, memory, or both prevent the application of optimal algorithms such as A*. Guidelines for building an effective heuristic for A* are well established in the literature, but we show that if those rules are applied for greedy best-first search, performance can actually degrade. Observing what went wrong for greedy best-first search leads us to a quantitative metric appropriate for greedy heuristics, called Goal Distance Rank Correlation (GDRC). We demonstrate that GDRC can be used to build effective heuristics for greedy best-first search automatically.

Learning from experience can significantly improve the performance of search based planners, especially for challenging problems like high-dimensional planning. Experience Graph (E-Graph) is a recently developed framework that encodes experiences, obtained from solving instances in the past, into a single bounded-admissible heuristic, and uses it to guide the search. While the E-Graph approach was shown to be very useful for repetitive problems, it suffers from two issues. First, computing the E-Graph heuristic is time consuming as it maintains the bounded admissibility constraints. Second, a single heuristic can get stuck in a local minimum, and thereby, degrade the performance. In this work, we present an alternative approach to improving the runtime of search from experience, based on a recently developed search algorithm Multi-heuristic A* (MHA*). This framework provides an improvement over the E-Graph planner for two reasons: a) MHA* uses multiple heuristics simultaneously to explore the search space, which reduces the probability of getting stuck in a local minimum, and b) the heuristics in MHA* can be arbitrarily inadmissible, which makes it very easy to compute them. The paper describes the framework, explains how to compute these (inadmissible) heuristics through offline and online processing and presents experimental analysis on two domains, motion planning for a 6D planar arm and large sliding tile puzzles.

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.

Snake in the Box (SIB) is the problem of finding the longest simple path along the edges of an n -dimensional cube, subject to certain constraints. SIB has important applications in coding theory and communications. State of the art algorithms for solving SIB apply uninformed search with symmetry breaking techniques. We formalize this problem as a search problem and propose several admissible heuristics to solve it. Using the proposed heuristics is shown to have a huge impact on the number of nodes expanded and, in some configurations, on runtime. These results encourage further research in using heuristic search to solve SIB, and to solve maximization problems more generally.

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.

Fork decoupling is a recent approach to exploiting problem structure in state space search. The problem is assumed to take the form of a fork, where a single (large) center component provides preconditions for several (small) leaf components. The leaves are then conditionally independent in the sense that, given a fixed center path p, the compliant leaf moves - those leaf moves enabled by the preconditions supplied along p - can be scheduled independently for each leaf. Fork-decoupled state space search exploits this through conducting a regular search over center paths, augmented with maintenance of the compliant paths for each leaf individually. We herein show that the same ideas apply to much more general star-topology structures, where leaves may supply preconditions for the center, and actions may affect several leaves simultaneously as long as they also affect the center. Our empirical evaluation in planning, super-imposing star topologies by automatically grouping the state variables into suitable components, shows the merits of the approach.

This paper makes two pedagogical contributions. First, we describe two macrooperators for best-first search algorithms: the collapse macro where asubtree is deleted from memory and its best frontier value is stored in itsroot, and, the restore macro (the inverse of collapse) where thesubtree is restored to its previous structure. We show that many known searchalgorithms can be easily described by using these macros. The secondcontribution is an algorithm called Iterative Linear Best-first Search (ILBFS). ILBFS is equivalent to RBFS. While RBFS uses a recursive structure,ILBFS uses the regular structure of BFS with occasionally using the collapseand restore macros. ILBFS and RBFS are identical in the nodes that they visitand have identical properties. But, I believe that ILBFS is pedagogicallysimpler to describe and understand; it could at least serve as a pedagogicaltool for RBFS.