The second is causal analysis: isolate I have seen several reviewers claim that experimental evaluations what causes a performance improvement and leave everything must use problem instances that are large enough to else unchanged, hopefully leaving the uncontrolled biases take more than x time to solve, where x has varied from the same between the two conditions. Note that nothing a few seconds to many minutes. The fact that the stated in this disturbing anecdote relates to benchmark size. Both values for x have varied over two orders of magnitude is short-and long-running benchmarks were affected, and the perhaps one indication that the criterion has no firm basis, recommendation is to increase benchmark diversity, which but let's consider it in more depth. I believe that it represents requires more benchmarks, which must therefore be smaller a serious problem: I have seen a paper (not from (in order to fit into the same PhD program or yearly conference my group) proposing a novel and interesting algorithm that timescale). Large benchmarks therefore inhibit correction soundly beat the state-of-the-art by orders of magnitude rejected of measurement bias.

True distance memory-based heuristics (TDHs) were recently introduced as a way to obtain admissible heuristics for explicit state spaces. In this paper, we introduce a new TDH, the portal-based heuristic. The domain is partitioned into regions and portals between regions are identified. True distances between all pairs of portals are stored and used to obtain admissible heuristics throughout the search. We introduce an A*-based algorithm that takes advantage of the special properties of the new heuristic. We study the advantages and limitations of the new heuristic. Our experimental results show large performance improvements over previously-reported TDHs for commonly used classes of maps.

In this paper we explore a novel approach for anytime heuristic search, in which the node that is most probable to improve the incumbent solution is expanded first. This is especially suited for the "anytime aspect" of anytime algorithms - the possibility that the algorithm will be be halted anytime throughout the search. The potential of a node to improve the incumbent solution is estimated by a custom cost function, resulting in Potential Search, an anytime best-first search. Experimental results on the 15-puzzle and on the key player problem in communication networks (KPP-COM) show that this approach is competitive with state-of-the-art anytime heuristic search algorithms, and is more robust.

We present a new heuristic point-to-point shortest path algorithm based on contraction hierarchies (CH). Given an epsilon >= 0, we can prove that the length of the path computed by our algorithm is at most (1 + ε) times the length of the optimal (shortest) path. Exact CH is based on node contraction: removing nodes from a network and adding shortcuts to preserve shortest path distances. Our heuristic CH tries to avoid adding shortcuts even when a replacement path is (1+epsilon) times longer. However, we cannot avoid all such shortcuts, as we need to ensure that errors do not stack. Combinations with goal-directed techniques bring further speed-ups.

One of the latest prominent results was by Schaeffer In recent years general game playing has received an increasing et al. (2007), who were able to solve American Checkers after amount of attention, especially due to the annual more than ten years of computation and proved that the general game playing competition (Genesereth, Love, and optimal outcome is a draw. Of course, due to the domain Pell 2005) that is held at AAAI or IJCAI since 2005. In independent scenario, we cannot expect to come up with solutions general game playing the agents are provided a description for such complex games in general game playing. of a game according to certain rules and need to play it. In explicit representation, many general games are too In case of multi-player games the agents often play against complex to fit into RAM or even on a hard disk. So, to solve each other, while in case of single-player games the agent them we perform symbolic search, which utilizes binary decision tries to find a sequence of moves to reach a terminal state diagrams (BDDs) (Bryant 1986) as they decrease the where it can achieve the best reward possible. The authors memory consumption, if a good variable ordering is found. of the agents do not know which games will be played, so In this paper we will present a new approach to solve general no domain specific knowledge can be inserted.

Bounded suboptimal search algorithms attempt to find a solution quickly while guaranteeing that the cost does not exceed optimal by more than a desired factor. These algorithms generally use a single admissible heuristic both for guidance and guaranteeing solution quality. We present a new approach to bounded suboptimal search that separates these roles, consulting multiple sources of potentially inadmissible information to determine search order and using admissible information to guarantee quality. An empirical evaluation across six benchmark domains shows the new approach has better overall performance.

Branch-and-Bound search is a basic algorithm for solving combinatorial optimization problems. Here we introduce a new lower-bounding methodology that can be incorporated into any branch-and-bound solver, and demonstraint its use on the MaxSAT constraint optimization problem. The approach is to adapt a “minimum-height equivalent transformation” framework that was first developed in the context of computer vision. We present efficient algorithms to realize this framework within the MaxSAT domain, and demonstrate their feasibility by implementing them within the state-of-the-art maxsatz solver. We evaluate the solver on test sets from the 2009 MaxSAT competition; we observe a basic performance tradeoff whereby the (quadratic) time cost of computing the transformations may or may not be worthwhile in exchange for better bounds and more frequent pruning. For specific test sets, the trade-off does result in significant improvement in both prunings and overall run-time.

We introduce a new bidirectional search algorithm, Single-Frontier Bidirectional Search (SFBDS). Unlike traditional BDS which keeps two frontiers, SFBDS uses a single frontier. At a particular node we can decide to search from start to goal or from goal to start, choosing the direction with the highest potential for minimizing the total work done. We provide theoretical analysis that explains when SFBDS will work validated by experimental results.

search algorithms such as IDA* or heuristic-search planners. Our method aims to generate a strong heuristic from a given weak heuristic h 0 through bootstrapping. The "easy" problem 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 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 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 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.

Transposition tables are a well-known method for pruning duplicates in heuristic search. This paper presents a detailed analysis of transposition tables for IDA*. We show that some straightforward implementations of IDA* with transposition tables (IDA*+TT) can result in suboptimal solutions being returned. Furthermore, straightforward implementations of IDA*+TT are not complete. We identify several variants of IDA*+TT which are guaranteed to return the optimal solution, as well as a complete variant. An empirical study shows that IDA*+TT can significantly improve upon the performance of A* in domain-independent planning.