Robert C. Holte

ICAPS Conference 2022 Conference Paper

Beam Search: Faster and Monotonic

• Sofia Lemons
• Carlos Linares López
• Robert C. Holte
• Wheeler Ruml

Beam search is a popular satisficing approach to heuristic search problems that allows one to trade increased computation time for lower solution cost by increasing the beam width parameter. We make two contributions to the study of beam search. First, we show how to make beam search monotonic; that is, we provide a new variant that guarantees nonincreasing solution cost as the beam width is increased. This makes setting the beam parameter much easier. Second, we show how using distance-to-go estimates can allow beam search to find better solutions more quickly in domains with non-uniform costs. Together, these results improve the practical effectiveness of beam search.

IJCAI Conference 2020 Conference Paper

Combining Direct Trust and Indirect Trust in Multi-Agent Systems

• Elham Parhizkar
• Mohammad Hossein Nikravan
• Robert C. Holte
• Sandra Zilles

To assess the trustworthiness of an agent in a multi-agent system, one often combines two types of trust information: direct trust information derived from one's own interactions with that agent, and indirect trust information based on advice from other agents. This paper provides the first systematic study on when it is beneficial to combine these two types of trust as opposed to relying on only one of them. Our large-scale experimental study shows that strong methods for computing indirect trust make direct trust redundant in a surprisingly wide variety of scenarios. Further, a new method for the combination of the two trust types is proposed that, in the remaining scenarios, outperforms the ones known from the literature.

SoCS Conference 2019 Conference Paper

Error Analysis and Correction for Weighted A*'s Suboptimality

• Robert C. Holte
• Rubén Majadas
• Alberto Pozanco
• Daniel Borrajo

Weighted A* (wA*) is a widely used algorithm for rapidly, but suboptimally, solving planning and search problems. The cost of the solution it produces is guaranteed to be at most W times the optimal solution cost, where W is the weight wA* uses in prioritizing open nodes. W is therefore a suboptimality bound for the solution produced by wA*. There is broad consensus that this bound is not very accurate, that the actual suboptimality of wA*

AAAI Conference 2019 Conference Paper

On the Optimal Efficiency of Cost-Algebraic A*

• Robert C. Holte
• Sandra Zilles

Edelkamp et al. (2005) proved that A*, given an admissible heuristic, is guaranteed to return an optimal solution in any cost algebra, not just in the traditional shortest path setting. In this paper, we investigate cost-algebraic A*’s optimal efficiency: in the cost-algebraic setting, under what conditions is A* guaranteed to expand the fewest possible states? In the traditional setting, this question was examined in detail by Dechter & Pearl (1985). They identified five different situations in which A* was optimally efficient. We show that three of them continue to hold in the cost-algebraic setting, but that one does not. We also show that one of them is false, it does not hold even in the traditional setting. We introduce an alternative that does hold in the cost-algebraic setting. Finally, we show that a well-known result due to Nilsson does not hold in the general cost-algebraic setting but does hold in a slightly less general setting.

ICAPS Conference 2018 Conference Paper

MS-Lite: A Lightweight, Complementary Merge-and-Shrink Method

• Gaojian Fan
• Robert C. Holte
• Martin Müller 0003

Merge-and-shrink is a general framework for creating abstraction heuristics. In this paper we present two new variations of merge-and-shrink: MS-lite and DM-HQ. MS-lite is an extremely fast merge-and-shrink that maintains only the smallest abstractions that preserve local heuristic information. MS-lite has complementary strength over other merge-and-shrink methods due to its efficiency. In addition, we show that MS-lite has little dependence on merging strategies and its eager shrinking strategy can lead to better heuristics for some planning tasks. DM-HQ features a merging criterion that utilizes information about heuristic quality to make the merging decisions. Our experiments show that combining DM-HQ and MS-lite dramatically outperforms the current state-of-the-art merge-and-shrink method by solving 75 more tasks on an International Planning Competition (IPC) benchmark set of 1499 tasks.

IJCAI Conference 2017 Conference Paper

Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions

• Jingwei Chen
• Robert C. Holte
• Sandra Zilles
• Nathan R. Sturtevant

It is well-known that any admissible unidirectional heuristic search algorithm must expand all states whose f-value is smaller than the optimal solution cost when using a consistent heuristic. Such states are called “surely expanded” (s. e. ). A recent study characterized s. e. pairs of states for bidirectional search with consistent heuristics: if a pair of states is s. e. then at least one of the two states must be expanded. This paper derives a lower bound, VC, on the minimum number of expansions required to cover all s. e. pairs, and present a new admissible front-to-end bidirectional heuristic search algorithm, Near-Optimal Bidirectional Search (NBS), that is guaranteed to do no more than 2VC expansions. We further prove that no admissible front-to-end algorithm has a worst case better than 2VC. Experimental results show that NBS competes with or outperforms existing bidirectional search algorithms, and often outperforms A* as well.

AIJ Journal 2017 Journal Article

MM: A bidirectional search algorithm that is guaranteed to meet in the middle

• Robert C. Holte
• Ariel Felner
• Guni Sharon
• Nathan R. Sturtevant
• Jingwei Chen

Bidirectional search algorithms interleave two separate searches, a normal search forward from the start state, and a search backward from the goal. It is well known that adding a heuristic to unidirectional search dramatically reduces the search effort. By contrast, despite decades of research, bidirectional heuristic search has not yet had a major impact. Additionally, no comprehensive theory was ever devised to understand the nature of bidirectional heuristic search. In this paper we aim to close this gap. We first present MM, a novel bidirectional heuristic search algorithm. Unlike previous bidirectional heuristic search algorithms, MM's forward and backward searches are guaranteed to “meet in the middle”, i. e. never expand a node beyond the solution midpoint. Based on this unique attribute we present a novel framework for comparing MM, A*, and their brute-force variants. We do this by dividing the entire state space into disjoint regions based on their distance from the start and goal. This allows us to perform a comparison of these algorithms on a per region basis and identify conditions favoring each algorithm. Finally, we present experimental results that support our theoretical analysis.

ICAPS Conference 2017 Conference Paper

Sufficient Conditions for Node Expansion in Bidirectional Heuristic Search

• Jürgen Eckerle
• Jingwei Chen
• Nathan R. Sturtevant
• Sandra Zilles
• Robert C. Holte

In this paper we study bidirectional state space search with consistent heuristics, with a focus on obtaining sufficient conditions for node expansion, that is, conditions characterizing nodes that must be expanded by any admissible bidirectional search algorithm. We provide such conditions for front-to-front and front-to-end bidirectional search. The sufficient conditions are used to prove that the front-to-front bidirectional search algorithm BDS1 is optimally efficient, in terms of node expansion, among a broad class of bidirectional search algorithms, for a specific class of problem instances. Dechter and Pearl's well-known result on sufficient conditions for node expansion by unidirectional algorithms such as A* is shown to be a special case of our results.

ICAPS Conference 2017 Conference Paper

The Two-Edged Nature of Diverse Action Costs

• Gaojian Fan
• Martin Müller 0003
• Robert C. Holte

Diverse action costs are an essential feature of many real-world planning applications. Some recent studies have shown that diversity of action costs makes planning more difficult, and that searching using unit action costs can outperform searching the same domain with diverse action costs. In this paper, we provide experimental evidence and theoretical analysis showing that search can also benefit from action cost diversity. We show that on several IPC problems cost diversity has a positive effect (reduces search effort). We then present a theoretical analysis establishing that these positive cases are not accidental. Our main result is a "No Free Lunch" theorem showing that any negative effects of cost diversity are always perfectly counterbalanced by positive effects. Our theoretical analysis also shows that it is advantageous to have a strongly concentrated distribution of solution costs. In many domains, unit costs will give rise to a more concentrated distribution than diverse costs, but we give an example typifying domains in which the opposite is the case.

IJCAI Conference 2016 Conference Paper

Action Selection for Hammer Shots in Curling

• Zaheen Farraz Ahmad
• Robert C. Holte
• Michael Bowling

Curling is an adversarial two-player game with a continuous state and action space, and stochastic transitions. This paper focuses on one aspect of the full game, namely, finding the optimal "hammer shot, " which is the last action taken before a score is tallied. We survey existing methods for finding an optimal action in a continuous, low-dimensional space with stochastic outcomes, and adapt a method based on Delaunay Triangulation to our application. Experiments using our curling physics simulator show that the adapted Delaunay Triangulation's shot selection outperforms other algorithms, and with some caveats, exceeds Olympic-level human performance.

SoCS Conference 2016 Conference Paper

Extended Abstract: An Improved Priority Function for Bidirectional Heuristic Search

• Guni Sharon
• Robert C. Holte
• Ariel Felner
• Nathan R. Sturtevant

Bidirectional search algorithms interleave a search forward from the start state (start ) and a search backward (i. e. using reverse operators) from the goal state (goal). We say that the two searches “meet in the middle” if neither search expands a node whose g-value (in the given direction) exceeds C*/2, where C* is the cost of an optimal solution. The only bidirectional heuristic search algorithm that is guaranteed to meet in the middle under all circumstances is the recently introduced MM algorithm (Holte et al. 2016). The feature of MM that provides this guarantee is its unique priority functions for nodes on its open lists. In this short note we present MMe, which enhances MM’s priority function and is expected to expand fewer nodes than MM under most circumstances. We sketch a proof of MMe’s correctness, describe conditions under which MMe will expand fewer nodes than MM and vice versa, and experimentally compare MMe and MM on the 10-Pancake problem.

IJCAI Conference 2016 Conference Paper

Heuristic Subset Selection in Classical Planning

• Levi H. S. Lelis
• Santiago Franco
• Marvin Abisrror
• Mike Barley
• Sandra Zilles
• Robert C. Holte

In this paper we present greedy methods for selecting a subset of heuristic functions for guiding A* search. Our methods are able to optimize various objective functions while selecting a subset from a pool of up to thousands of heuristics. Specifically, our methods minimize approximations of A*'s search tree size, and approximations of A*'s running time. We show empirically that our methods can outperform state-of-the-art planners for deterministic optimal planning.

AIJ Journal 2016 Journal Article

Predicting optimal solution costs with bidirectional stratified sampling in regular search spaces

• Levi H.S. Lelis
• Roni Stern
• Shahab Jabbari Arfaee
• Sandra Zilles
• Ariel Felner
• Robert C. Holte

Optimal planning and heuristic search systems solve state-space search problems by finding a least-cost path from start to goal. As a byproduct of having an optimal path they also determine the optimal solution cost. In this paper we focus on the problem of determining the optimal solution cost for a state-space search problem directly, i. e. , without actually finding a solution path of that cost. We present an algorithm, BiSS, which is a hybrid of bidirectional search and stratified sampling that produces accurate estimates of the optimal solution cost. BiSS is guaranteed to return the optimal solution cost in the limit as the sample size goes to infinity. We show empirically that BiSS produces accurate predictions in several domains. In addition, we show that BiSS scales to state spaces much larger than can be solved optimally. In particular, we estimate the average solution cost for the 6 × 6, 7 × 7, and 8 × 8 Sliding-Tile puzzle and provide indirect evidence that these estimates are accurate. As a practical application of BiSS, we show how to use its predictions to reduce the time required by another system to learn strong heuristic functions from days to minutes in the domains tested.

AAAI Conference 2015 Conference Paper

A Generalization of Sleep Sets Based on Operator Sequence Redundancy

• Robert C. Holte
• Yusra Alkhazraji
• Martin Wehrle

Pruning techniques have recently been shown to speed up search algorithms by reducing the branching factor of large search spaces. One such technique is sleep sets, which were originally introduced as a pruning technique for model checking, and which have recently been investigated on a theoretical level for planning. In this paper, we propose a generalization of sleep sets and prove its correctness. While the original sleep sets were based on the commutativity of operators, generalized sleep sets are based on a more general notion of operator sequence redundancy. As a result, our approach dominates the original sleep sets variant in terms of pruning power. On a practical level, our experimental evaluation shows the potential of sleep sets and their generalizations on a large and common set of planning benchmarks.

SoCS Conference 2015 Conference Paper

The Spurious Path Problem in Abstraction

• Gaojian Fan
• Robert C. Holte

Abstraction is a powerful technique in search and planning. A fundamental problem of abstraction is that it can create spurious paths, i. e. , abstract paths that do not correspond to valid concrete paths. In this paper, we define spurious paths as a generalization of spurious states. We show that spurious paths can be categorized into two types: state-independent spurious paths and state-specific spurious paths. We present a practical method that eliminates state-independent spurious paths, as well as state-specific spurious paths when integrated with mutex detection methods. We provide syntactical conditions under which our method can remove state-independent spurious paths completely. We demonstrate that eliminating spurious paths can improve a heuristic substantially, even in abstract spaces that are free of spurious states.

ICAPS Conference 2015 Conference Paper

Understanding and Improving Local Exploration for GBFS

• Fan Xie 0001
• Martin Müller 0003
• Robert C. Holte

Greedy Best First Search (GBFS) is a powerful algorithm at the heart of many state-of-the-art satisficing planners. The Greedy Best First Search with Local Search (GBFS-LS) algorithm adds exploration using a local GBFS to a global GBFS. This substantially improves performancefor domains that contain large uninformative heuristic regions (UHR), such as plateaus or local minima. This paper analyzes, quantifies and improves the performance of GBFS-LS. Planning problems with a mix of small and large UHRs are shown to be hard for GBFS but easy for GBFS-LS. In three standard IPC planning instances analyzed in detail, adding exploration using local GBFS gives more than three orders of magnitude speedup. As a second contribution, the detailed analysis leads to an improvedGBFS-LS algorithm, which replaces larger-scale local GBFS explorations with a greater number of smaller explorations.

SoCS Conference 2014 Conference Paper

A* with Lookahead Re-Evaluated

• Zhaoxing Bu
• Roni Stern
• Ariel Felner
• Robert C. Holte

A* with lookahead (AL*) is a variant of A* that performs a cost-bounded DFS lookahead from a node when it is generated. We show that the original version of AL* (AL*0) can, in some circumstances, fail to return an optimal solution because of the move pruning it does. We present two new versions, AL*1 and ELH, that we prove to always be correct and give conditions in which AL*0 is guaranteed to be correct. In our experiments with unit costs, AL*0 was usually the fastest AL* version, but its advantage was usually small. In our experiments with non-unit costs, AL*0 substantially outperforms both A* and IDA*. We also evaluate the idea of immediately expanding a generated node if it has the same f-value as its parent. We find that doing so causes AL* to require more memory and sometimes slows AL* down.

SoCS Conference 2014 Conference Paper

Non-Linear Merging Strategies for Merge-and-Shrink Based on Variable Interactions

• Gaojian Fan
• Martin Müller 0003
• Robert C. Holte

Merge-and-shrink is a general method for deriving accurate abstraction heuristics. We present two novel nonlinear merging strategies, UMC and MIASM, based on variable interaction. The principle underlying our methods is to merge strongly interacting variables early on. UMC measures variable interaction by weighted causal graph edges, and MIASM measures variable interaction in terms of the number of necessary states in the abstract space defined by the variables. The methods partition variables into clusters in which the variable interactions are strong, and merge variables within each cluster before merging the clusters. Experiment results show that our merging strategies outperform existing merging strategies in general and can produce heuristics that give perfect guidance for solving tasks that previous methods cannot even solve.

SoCS Conference 2013 Conference Paper

Optimal-Generation Variants of EPEA

• Meir Goldenberg
• Ariel Felner
• Nathan R. Sturtevant
• Robert C. Holte
• Jonathan Schaeffer 0001

It is known that A* is optimal with respect to the expanded nodes (Dechter and Pearl 1985) (D&P). The exact meaning of this optimality varies depending on the class of algorithms and instances over which A* is claimed to be optimal. A* does not provide any optimality guarantees with respect to the generated nodes. However, such guarantees may be critical for optimally solving instances of domains with a large branching factor. In this paper, we introduce two new variants of the recently introduced Enhanced Partial Expansion A* algorithm (EPEA*) (Felner et al. 2012). We leverage the results of D&P to show that these variants possess optimality with respect to the generated nodes in much the same sense as A* possesses optimality with respect to the expanded nodes. The results in this paper are theoretical. A study of the practical performance of the new variants is beyond the scope of this paper.

AIJ Journal 2013 Journal Article

Predicting the size of IDA*ʼs search tree

• Levi H.S. Lelis
• Sandra Zilles
• Robert C. Holte

Korf, Reid and Edelkamp initiated a line of research for developing methods (KRE and later CDP) that predict the number of nodes expanded by IDA* for a given start state and cost bound. Independently, Chen developed a method (SS) that can also be used to predict the number of nodes expanded by IDA*. In this paper we improve both of these prediction methods. First, we present ϵ-truncation, a method that acts as a preprocessing step and improves CDPʼs prediction accuracy. Second and orthogonally to ϵ-truncation, we present a variant of CDP that can be orders of magnitude faster than CDP while producing exactly the same predictions. Third, we show how ideas developed in the KRE line of research can be used to improve the predictions produced by SS. Finally, we make an empirical comparison between our new enhanced versions of CDP and SS. Our experimental results suggest that CDP is suitable for applications that require less accurate but fast predictions, while SS is suitable for applications that require more accurate predictions but can afford more computation time.

SoCS Conference 2012 Conference Paper

Automatic Move Pruning Revisited

• Neil Burch
• Robert C. Holte

In this paper we show that the move pruning method we presented at SoCS last year sometimes prunes all the least-cost paths from one state to another. We present two examples exhibiting this erroneous behaviour--a simple, artificial example and a slightly more complex example that arose in last year

SoCS Conference 2012 Conference Paper

Learning Heuristic Functions Faster by Using Predicted Solution Costs

• Levi H. S. Lelis
• Shahab Jabbari Arfaee
• Sandra Zilles
• Robert C. Holte

Jabbari Arfaee, Zilles, and Holte presented the bootstrap learning system, a system that learns strong heuristic functions for state-space problems. They showed that IDA* with a bootstrap heuristic is able to quickly find near-optimal solutions in several problem domains. However, the process the bootstrap method uses to learn heuristic functions is time-consuming: it is on the order of days. In this paper we present a learning system that uses an approximation method instead of an exact one to generate the training set required to learn heuristics. We showed recently that solution costs can often be quickly and accurately predicted without having to actually find a solution. In this paper we apply this idea to speedup the process of learning heuristics. In contrast with other learning approaches that use search algorithms to solve problem instances to generate the training set, our system uses a solution cost predictor. We reduce the time required to learn strong heuristics from days to minutes on the domains tested.

SoCS Conference 2012 Conference Paper

Multimapping Abstractions and Hierarchical Heuristic Search

• Bo Pang
• Robert C. Holte

In this paper we introduce a broadly applicable method, called multimapping abstraction, that allows multiple heuristic values for a state to be extracted from one abstract state space. The key idea is to define an abstraction to be a multimapping, i. e. , a function that maps a state in the original state space to a set of states in the abstract space. We performed a large-scale experiment on several benchmark state spaces to compare the memory requirements and runtime of Hierarchical IDA* (HIDA*) using multimapping domain abstractions to HIDA* with individual domain abstractions and to HIDA* with multiple, independent domain abstractions. Our results show that multimapping domain abstractions are superior to both alternatives in terms of both memory usage and runtime.

SoCS Conference 2012 Conference Paper

Partial-Expansion A* with Selective Node Generation

• Ariel Felner
• Meir Goldenberg
• Guni Sharon
• Roni Stern
• Tal Beja
• Nathan R. Sturtevant
• Robert C. Holte
• Jonathan Schaeffer 0001

A* is often described as being 'optimal, ' in that it expands the minimum number of unique nodes. But, A* may generate many extra nodes which are never expanded. This is a performance loss, especially when the branching factor is large. Partial Expansion A* (PEA*) addresses this problem when expanding a node, n, by generating all the children of n but only storing children with the same f-cost as n. We introduce an enhanced version of PEA* (EPEA*). Given a priori domain knowledge, EPEA* only generates the children with the same f-cost as the parent. State-of-the-art results were obtained for a number of domains. Drawbacks of EPEA* are also discussed. A full version of this paper appears in the proceedings of AAAI-2012

ICAPS Conference 2012 Conference Paper

Predicting Optimal Solution Cost with Bidirectional Stratified Sampling

• Levi H. S. Lelis
• Roni Stern
• Ariel Felner
• Sandra Zilles
• Robert C. Holte

Optimal planning and heuristic search systems solve state-space searchproblems by finding a least-cost path from start to goal. As a byproduct of having an optimal path they also determine the optimal solution cost. In this paper we focus on the problem of determining the optimal solution cost for a state-space search problem directly, i. e. without actually finding a solution path of that cost. We present an efficient algorithm, BiSS, based on ideas of bidirectional search and stratified sampling that produces accurate estimates of the optimal solution cost. Our method is guaranteed to return the optimal solution cost in the limit as the sample size goes to infinity. We show empirically that our method makes accurate predictions in several domains. In addition, we show that our method scales to state spaces much larger than can be solved optimally. In particular, we estimate the average solution cost for the 6x6, 7x7, and 8x8 Sliding-Tile Puzzle and provide indirect evidence that these estimates are accurate.

SoCS Conference 2012 Conference Paper

Predicting Optimal Solution Cost with Bidirectional Stratified Sampling (Abstract)

• Levi H. S. Lelis
• Roni Stern
• Ariel Felner
• Sandra Zilles
• Robert C. Holte

Optimal planning and heuristic search systems solve state-space searchproblems by finding a least-cost path from start to goal. As a byproduct of having an optimal path they also determine the optimal solution cost. In this paper we focus on the problem of determining the optimal solution cost for a state-space search problem directly, i. e. , without actually finding a solution path of that cost. We present an efficient algorithm, BiSS, based on ideas of bidirectional search and stratified sampling that produces accurate estimates of the optimal solution cost. Our method is guaranteed to return the optimal solution cost in the limit as the sample size goes to infinity.

SoCS Conference 2012 Conference Paper

Search-Aware Conditions for Probably Approximately Correct Heuristic Search

• Roni Stern
• Ariel Felner
• Robert C. Holte

The notion of finding a solution that is approximately optimal with high probability was recently introduced to the field of heuristic search, formalized as Probably Approximately Correct Heuristic Search, or PAC search in short. A big challenge when constructing a PAC search algorithm is to identify when a given solution achieves the desired sub-optimality with the required confidence, allowing the search to halt and return the incumbent solution. In this paper we propose two novel methods for identifying when a PAC search can halt. Unlike previous work, the new methods provided in this paper become more knowledgeable as the search progresses. This can speedup the search, since the search can halt earlier with the proposed methods and still keeping the desired PAC solution quality guarantees. Experimental results indeed show a substantial speedup of the search in comparison to the previous approach for PAC search.

SoCS Conference 2011 Conference Paper

A Polynomial-Time Algorithm for Non-Optimal Multi-Agent Pathfinding

• Mokhtar M. Khorshid
• Robert C. Holte
• Nathan R. Sturtevant

Multi-agent pathfinding, where multiple agents must travel to their goal locations without getting stuck, has been studied in both theoretical and practical contexts, with a variety of both optimal and sub-optimal algorithms proposed for solving problems. Recent work has shown that there is a linear-time check for whether a multi-agent pathfinding problem can be solved in a tree, however this was not used to actually produce solutions. In this paper we provide a constructive proof of how to solve multi-agent pathfinding problems in a tree that culminates in a novel approach that we call the tree-based agent swapping strategy (TASS). Experimental results showed that TASS can find solutions to the multi-agent pathfinding problem on a highly crowded tree with 1000 nodes and 996 agents in less than 8 seconds. These results are far more efficient and general than existing work, suggesting that TASS is a productive line of study for multi-agent pathfinding.

SoCS Conference 2011 Conference Paper

Abstract: Block A* and Any-Angle Path-Planning

• Peter Kai Yue Yap
• Neil Burch
• Robert C. Holte
• Jonathan Schaeffer 0001

We present three new ideas for grid-based path-planning algorithms that improve the search speed and quality of the paths found. First, we introduce a new type of database, the Local Distance Database (LDDB), that contains distances between boundary points of a local neighborhood. Second, an LDDB-based algorithm is introduced, called Block A*, that calculates the optimal path between start and goal locations given the local distances stored in the LDDB. Third, our experimental results for any-angle path planning in a wide varietyof test domains, including real game maps, show that Block A* is faster than both A* and the previously best grid-based any-angle search algorithm, Theta*.

SoCS Conference 2011 Conference Paper

Automatic Move Pruning in General Single-Player Games

• Neil Burch
• Robert C. Holte

Move pruning is a low-overhead technique for reducing the size of a depth first search tree. The existing algorithm for automatically discovering move pruning information is restricted to games where all moves can be applied to every state. This paper demonstrates an algorithm which handles a general class of single player games. It gives experimental results for our technique, demonstrating both the applicability to a range of games, and the reduction in search tree size. We also provide some conditions under which move pruning is safe, and when it may interfere with other search reduction techniques.

SoCS Conference 2011 Conference Paper

Faster Optimal and Suboptimal Hierarchical Search

• Michael J. Leighton
• Wheeler Ruml
• Robert C. Holte

In problem domains for which an informed admissible heuristic function is not available, one attractive approach is hierarchical search. Hierarchical search uses search in an abstracted version of the problem to dynamically generate heuristic values. This paper makes two contributions to hierarchical search. First, we propose a simple modification to the state-of-the-art algorithm Switchback that reduces the number of expansions (and hence the running time) by approximately half, while maintaining its guarantee of optimality. Second, we propose a new algorithm for suboptimal hierarchical search, called Switch. Empirical results suggest that Switch yields faster search than straightforward modifications of Switchback, such as weighting the heuristic or greedy search. The success of Switch illustrates the potential for further research on specifically suboptimal hierarchical search.

SoCS Conference 2011 Conference Paper

Improved Prediction of IDA*'s Performance via Epsilon-Truncation

• Levi H. S. Lelis
• Sandra Zilles
• Robert C. Holte

Korf, Reid, and Edelkamp launched a line of research aimed at predicting how many nodes IDA* will expand with a given cost bound. This paper advances this line of research in three ways. First, we identify a source of prediction error that has hitherto been overlooked. We call it the ``discretization effect

AIJ Journal 2011 Journal Article

Learning heuristic functions for large state spaces

• Shahab Jabbari Arfaee
• Sandra Zilles
• Robert C. Holte

We investigate the use of machine learning to create effective heuristics for search algorithms such as IDA ⁎ or heuristic-search planners such as FF. Our method aims to generate a sequence of heuristics from a given weak heuristic h 0 and a set of unsolved training instances using a bootstrapping procedure. The training instances that can be solved using h 0 provide training examples for a learning algorithm that produces a heuristic h 1 that is expected to be stronger than h 0. If h 0 is so weak that it cannot solve any of the given instances we use random walks backward from the goal state to create a sequence of successively more difficult training instances starting with ones that are guaranteed to be solvable by h 0. The bootstrap process is then repeated using h i in lieu of h i − 1 until a sufficiently strong heuristic is produced. We test this method on the 24-sliding-tile puzzle, the 35-pancake puzzle, Rubikʼs Cube, and the 20-blocks world. In every case our method produces a heuristic that allows IDA ⁎ to solve randomly generated problem instances quickly with solutions close to optimal. The total time for the bootstrap process to create strong heuristics for these large state spaces is on the order of days. To make the process effective when only a single problem instance needs to be solved, we present a variation in which the bootstrap learning of new heuristics is interleaved with problem-solving using the initial heuristic and whatever heuristics have been learned so far. This substantially reduces the total time needed to solve a single instance, while the solutions obtained are still close to optimal.

SoCS Conference 2011 Conference Paper

Probably Approximately Correct Heuristic Search

• Roni Stern
• Ariel Felner
• Robert C. Holte

A* is a best-first search algorithm that returns an optimal solution. w-admissible algorithms guarantee that the returned solution is no larger than w times the optimal solution. In this paper we introduce a generalization of the w-admissibility concept that we call PAC search, which is inspired by the PAC learning framework in Machine Learning. The task of a PAC search algorithm is to find a solution that is w-admissible with high probability. In this paper we formally define PAC search, and present a framework for PAC search algorithms that can work on top of any search algorithm that produces a sequence of solutions. Experimental results on the 15-puzzle demonstrate that our framework activated on top of Anytime Weighted A* (AWA*) expands significantly less nodes than regular AWA* while returning solutions that have almost the same quality.

SoCS Conference 2011 Conference Paper

State-Set Search

• Bo Pang
• Robert C. Holte

State-set search is state space search when the states being manipulated by the search algorithm are sets of states from some underlying state space. State-set search arises commonly in planning and abstraction systems, but this paper provides the first formal, general analysis of state-set search. We show that the state-set distance computed by planning systems is different than that computed by abstraction systems and introduce a distance in between the two, dww, the maximum admissible distance. We introduce the concept of a multi-abstraction, which maps a state to more than one abstract state in the same abstract space, describe the first implementation of a multi-abstraction system that computes dww, and give initial experimental evidence that it can be superior to domain abstraction.

ECAI Conference 2010 Conference Paper

Automating Layouts of Sewers in Subdivisions

• Neil Burch
• Robert C. Holte
• Martin Müller 0003
• David O'Connell
• Jonathan Schaeffer 0001

An important part of the creation of a housing subdivision is the design and layout of sewers underneath the road. This is a challenging cost optimization problem in a continuous threedimensional space. In this paper, heuristic-search-based techniques are proposed for tackling this problem. The result is new algorithms that can quickly find near optimal solutions that offer important reductions in the cost of design and construction.

SoCS Conference 2010 Conference Paper

Bootstrap Learning of Heuristic Functions

• Shahab Jabbari Arfaee
• Sandra Zilles
• Robert C. Holte

search algorithms such as IDA* or heuristic-search planners. Our method aims to generate a strong heuristic from a given weak heuristic h0 through bootstrapping. The "easy" problem instances that can be solved using h0 provide training examples for a learning algorithm that produces a heuristic h1 that is expected to be stronger than h0. If h0 is too weak to solve any of the given instances we use a random walk technique to create a sequence of successively more difficult instances starting with ones that are solvable by h0. The bootstrap process is then repeated using hi in lieu of hi-1 until a sufficiently strong heuristic is produced. We test our method on the 15- and 24-sliding tile puzzles, the 17- and 24-pancake puzzles, and the 15- and 20-blocks world. In every case our method produces a heuristic that allows IDA* to solve randomly generated problem instances extremely quickly with solutions very close to optimal.

SoCS Conference 2010 Conference Paper

Common Misconceptions Concerning Heuristic Search

• Robert C. Holte

This paper examines the following statements about heuristic search, which are commonly held to be true: More accurate heuristics result in fewer node expansions by A* and IDA*. A* does fewer node expansions than any other equally informed algorithm that finds optimal solutions. Any admissible heuristic can be turned into a consistent heuristic by a simple technique called pathmax. In search spaces whose operators all have the same cost A* with the heuristic function h(s)=0 for all states, s, is the same as breadth-first search. Bidirectional A* stops when the forward and backward search frontiers meet. The paper demonstrates that all these statements are false and provides alternative statements that are true.

AIJ Journal 2010 Journal Article

The computational complexity of avoiding spurious states in state space abstraction

• Sandra Zilles
• Robert C. Holte

Abstraction is a powerful technique for speeding up planning and search. A problem that can arise in using abstraction is the generation of abstract states, called spurious states, from which the goal state is reachable in the abstract space but for which there is no corresponding state in the original space from which the goal state can be reached. Spurious states can be harmful, in practice, because they can create artificial shortcuts in the abstract space that slow down planning and search, and they can greatly increase the memory needed to store heuristic information derived from the abstract space (e. g. , pattern databases). This paper analyzes the computational complexity of creating abstractions that do not contain spurious states. We define a property—the downward path preserving property (DPP)—that formally captures the notion that an abstraction does not result in spurious states. We then analyze the computational complexity of (i) testing the downward path preserving property for a given state space and abstraction and of (ii) determining whether this property is achievable at all for a given state space. The strong hardness results shown carry over to typical description languages for planning problems, including sas + and propositional strips. On the positive side, we identify and illustrate formal conditions under which finding downward path preserving abstractions is provably tractable.

ECAI Conference 2008 Conference Paper

Compressing Pattern Databases with Learning

• Mehdi Samadi
• Maryam Siabani
• Ariel Felner
• Robert C. Holte

A pattern database (PDB) is a heuristic function implemented as a lookup table. It stores the lengths of optimal solutions for instances of subproblems. Most previous PDBs had a distinct entry in the table for each subproblem instance. In this paper we apply learning techniques to compress PDBs by using neural networks and decision trees thereby reducing the amount of memory needed. Experiments on the sliding tile puzzles and the TopSpin puzzle show that our compressed PDBs significantly outperforms both uncompressed PDBs as well as previous compressing methods. Our full compressing system reduced the size of memory needed by a factor of up to 63 at a cost of no more than a factor of 2 in the search effort.

AIJ Journal 2008 Journal Article

Duality in permutation state spaces and the dual search algorithm

• Uzi Zahavi
• Ariel Felner
• Robert C. Holte
• Jonathan Schaeffer

Geometrical symmetries are commonly exploited to improve the efficiency of search algorithms. A new type of symmetry in permutation state spaces, duality, is introduced. Each state has a dual state. Both states share important attributes such as their distance to the goal. Given a state S, it is shown that an admissible heuristic of the dual state of S is an admissible heuristic for S. This provides opportunities for additional heuristic evaluations. An exact definition of the class of problems where duality exists is provided. A new search algorithm, dual search, is presented which switches between the original state and the dual state when it seems likely that the switch will improve the chance of reaching the goal faster. The decision of when to switch is very important and several policies for doing this are investigated. Experimental results show significant improvements for a number of applications, for using the dual state's heuristic evaluation and/or dual search.

ICAPS Conference 2008 Conference Paper

The Compression Power of Symbolic Pattern Databases

• Marcel Ball
• Robert C. Holte

The heuristics used for planning and search often take the form of pattern databases generated from abstracted versions of the given state space. Pattern databases are typically stored as lookup tables with one entry for each state in the abstract space, which limits the size of the abstract state space and therefore the quality of the heuristic that can be used with a given amount of memory. In the AIPS-2002 conference Stefan Edelkamp introduced an alternative representation, called symbolic pattern databases, which, for the Blocks World, required two orders of magnitude less memory than a lookup table to store a pattern database. This paper presents experimental evidence that Edelkamp's result is not restricted to a single domain. Symbolic pattern databases, in the form of Algebraic Decision Diagrams, are one or more orders of magnitude smaller than lookup tables on a wide variety of problem domains and abstractions.

AIJ Journal 2006 Journal Article

Maximizing over multiple pattern databases speeds up heuristic search

• Robert C. Holte
• Ariel Felner
• Jack Newton
• Ram Meshulam
• David Furcy

A pattern database (PDB) is a heuristic function stored as a lookup table. This paper considers how best to use a fixed amount (m units) of memory for storing pattern databases. In particular, we examine whether using n pattern databases of size m / n instead of one pattern database of size m improves search performance. In all the state spaces considered, the use of multiple smaller pattern databases reduces the number of nodes generated by IDA*. The paper provides an explanation for this phenomenon based on the distribution of heuristic values that occur during search.

AAAI Conference 2005 Conference Paper

Effective Short-Term Opponent Exploitation in Simplified Poker

• Bret Hoehn
• Robert C. Holte

Uncertainty in poker stems from two key sources, the shuffled deck and an adversary whose strategy is unknown. One approach is to find a pessimistic game theoretic solution (i. e. a Nash equilibrium), but human players have idiosyncratic weaknesses that can be exploited if a model of their strategy can be learned by observing their play. However, games against humans last for at most a few hundred hands so learning must be fast to be effective. We explore two approaches to opponent modelling in the context of Kuhn poker, a small game for which game theoretic solutions are known. Parameter estimation and expert algorithms are both studied. Experiments demonstrate that, even in this small game, convergence to maximally exploitive solutions in a small number of hands is impractical, but that good (i. e. better than Nash or breakeven) performance can be achieved in a short period of time. Finally, we show that amongst a set of strategies with equal game theoretic value, in particular the set of Nash equilibrium strategies, some are preferable because they speed learning of the opponent’s strategy by exploring it more effectively.

AAAI Conference 2005 Conference Paper

Software Testing by Active Learning for Commercial Games

• Gang Xiao
• Robert C. Holte

As software systems have become larger, exhaustive testing has become increasingly onerous. This has rendered statistical software testing and machine learning techniques increasingly attractive. Drawing from both of these, we present an active learning framework for blackbox software testing. The active learning approach samples input/output pairs from a blackbox and learns a model of the system’s behaviour. This model is then used to select new inputs for sampling. This framework has been developed in the context of commercial video games, complex virtual worlds with highdimensional state spaces, too large for exhaustive testing. Beyond its correctness, developers need to evaluate the gameplay of a game, properties such as difficulty. We use the learned model not only to guide sampling but also to summarize the game’s behaviour for the developer to evaluate. We present results from our semi-automated gameplay analysis by machine learning (SAGA-ML) tool applied to Electronics Arts’ FIFA Soccer game.

AAAI Conference 2004 Conference Paper

Compressing Pattern Databases

• Ariel Felner
• Robert C. Holte

A pattern database is a heuristic function stored as a lookup table which stores the lengths of optimal solutions for instances of subproblems. All previous pattern databases had a distinct entry in the table for each subproblem instance. In this paper we investigate compressing pattern databases by merging several adjacent entries into one, thereby allowing the use of pattern databases that exceed available memory in their uncompressed form. We show that since adjacent entries are highly correlated, much of the information is preserved. Experiments on the sliding tile puzzles and the 4-peg Towers of Hanoi puzzle show that, for a given amount of memory, search time is reduced by up to 3 orders of magnitude by using compressed pattern databases.

ICAPS Conference 2004 Conference Paper

Multiple Pattern Databases

• Robert C. Holte
• Jack Newton
• Ariel Felner
• Ram Meshulam
• David Furcy

A patterndatabase is a heuristic function stored as a lookup table. This paper considers how best to use a fixed amount (m units) of memory for storing pattern databases. In particular, we examine whether using n pattern databases of size m=n instead of one pattern database of size m improves search performance. In all the domains considered, the use of multiple smaller pattern databases reduces the number of nodes generated by IDA*. The paper provides an explanation for this phenomenon based on the distribution of heuristic values that occur during search.

ICML Conference 2000 Conference Paper

Exploiting the Cost (In)sensitivity of Decision Tree Splitting Criteria

• Chris Drummond
• Robert C. Holte

AAAI Conference 1999 Conference Paper

A Space-Time Tradeoff for Memory-Based Heuristics

• Robert C. Holte
• István T. Hernádvölgyi
• University of Ottawa

A memory-basedheuristic is a function, h(s), stored in the form of a lookup table (pattern database): h(s) is computedby mappings to an indexand then retrieving the appropriate entry in the table. (Korf1997)conjecturesfor search using memory-based heuristics that m¯ t is a constant, wheremis the size of the heuristic’s lookuptable andt is search time. In this paperwepresent a methodfor automatically generating memorybased heuristics anduse this to test Korf’s conjecture in a large-scale experiment. Ourresults confirmthat there is a direct relationship between mand t.

AAAI Conference 1996 Conference Paper

Hierarchical A*: Searching Abstraction Hierarchies Efficiently

• Robert C. Holte
• R. M. Zimmer

Abstraction, in search, problem solving, and planning, works by replacing one state space by another (the “abstract” space) that is easier to search. The results of the search in the abstract space are used to guide search in the original space. For instance, the length of the abstract solution can be used as a heuristic for A* in searching in the original space. However, there are two obstacles to making this work efficiently. The first is a theorem (Valtorta, 1984) stating that for a large class of abstractions, “embedding abstractions, ” every state expanded by blind search must also be expanded by A* when its heuristic is computed in this way. The second obstacle arises because in solving a problem A* needs repeatedly to do a full search of the abstract space while computing its heuristic. This paper introduces a new abstraction-induced search technique, “Hierarchical A * ” that gets around both of, these difficulties: first, by drawing from a different class of abstractions, “homomorphism abstractions, ” and, secondly, by using novel caching techniques to avoid repeatedly expanding the same states in successive searches in the abstract space. Hierarchical A* outperforms blind search on all the search spaces studied.

ICML Conference 1995 Conference Paper

Theory and Applications of Agnostic PAC-Learning with Small Decision Trees

• Peter Auer
• Robert C. Holte
• Wolfgang Maass 0001

AIJ Journal 1990 Journal Article

Concept learning and heuristic classification in weak-theory domains

• Bruce W. Porter
• Ray Bareiss
• Robert C. Holte

This paper describes a successful approach to concept learning for heuristic classification. Almost all current programs for this task create or use explicit, abstract generalizations. These programs are largely ineffective for domains with weak or intractable theories. An exemplar-based approach is suitable for domains with inadequate theories but raises two additional problems: determining similarity and indexing exemplars. Our approach extends the exemplar-based approach with solutions to these problems. An implementation of our approach, called Protos, has been applied to the domain of clinical audiology. After reasonable training, Protos achieved a competence level equaling that of human experts and far surpassing that of other machine learning programs. Additionally, an “ablation study” has identified the aspects of Protos that are primarily responsible for its success.

IJCAI Conference 1989 Conference Paper

Concept Learning and the Problem of Small Disjuncts

• Robert C. Holte
• Liane E. Acker
• Bruce W. Porter

MFCS Conference 1989 Conference Paper

Pinwheel Scheduling With Tow Distinct Numbers

• Robert C. Holte
• Louis E. Rosier
• Igor Tulchinsky
• Donald A. Varvel

Abstract “The Pinwheel” is a real-time scheduling problem based on a problem in scheduling satellite ground stations but which also addresses scheduling preventive maintenance. Given a multiset of positive integers A = { a 1, a 2, .. ., a n }, a schedule S for A is an infinite sequence over {1, 2, .. ., n } such that any subsequence of length a i (1 ≤ i ≤ n ) contains at least one i. Schedules can always be made cyclic; that is, a segment can be found that can be repeated indefinitely to form an infinite schedule. Interesting questions include determining whether schedules exist, determining the minimum cyclic schedule length, and creating an online scheduler. The “density” of an instance is defined as \(d = \sum\nolimits_{i = 1}^n {1/a} _i\). It has been shown that any instance with d > 1. 0 cannot be scheduled. In the present paper we limit ourselves to instances in which A contains elements having only two distinct values. We prove that all such instances with d ≤ 1. 0 can be scheduled, using a scheduling strategy based on balancing. The schedule so created is not always of minimum length, however. We use a related but more complicated method to create a minimum-length cyclic schedule, and prove its correctness. The former is computationally easier to obtain but not necessarily minimal. The latter, although still obtainable in polynomial time, requires significantly more computation. In addition, we show how to use either method to produce a fast online scheduler. Thus, we have solved completely the three major problems for this class of instances.