Stefan Edelkamp

AAMAS Conference 2026 Conference Paper

Imperfect-Information Games on Quantum Computers: A Case Study in Skat

• Ulrich Armbrüster
• Stefan Edelkamp
• Gabriel Maresch
• Erik Schulze

We demonstrate how quantum computing can provide a promising framework for addressing imperfect information games, using the popular German card game Skat as a case study. Our approach employs quantum registers to encode the game’s hidden and public information, alongwithtailoredquantumgatestomodelthegame’s progress while respecting its rules. To evaluate player decisions, we introduce a score operator that projects the quantum state onto the winning subspace, enabling the estimation of winning probabilities via quantum algorithms such as quantum counting. This allows the efficient exploration of alternative strategies and potential improvements in computational speed compared to classical methods. By maximizing the payoff function, our framework yields actionable recommendations for optimal play. As classical computation faces severe limitations due to the exponential complexity of the game tree, we discuss the specific structural properties of Skat that may give rise to a quantum advantage once the problem size surpasses classical feasibility.

IROS Conference 2024 Conference Paper

Multi-Robot Multi-Goal Mission Planning in Terrains of Varying Energy Consumption

• Jáchym Herynek
• Stefan Edelkamp

This paper considers planning missions for a fleet of robots with limited energy. Each robot has size, heading, and velocity and its motion is described by non-linear differential equations. The dynamics of movements, existing obstacles, multiple robots, and waypoints are additional challenges, as the combined task and motion planning procedure prevents collisions. On their long-term missions, robots have to visit several waypoints in a cost-minimizing manner to satisfy the overall mission task. The robots consume energy and have to be recharged. The framework guides expanding a motion tree via a state projection to a discrete problem, whose solutions serve as search heuristics. Our experiments highlight that despite all these challenges, even sizable problem tasks can be solved even for complex environments.

NeurIPS Conference 2023 Conference Paper

Optimize Planning Heuristics to Rank, not to Estimate Cost-to-Goal

• Leah Chrestien
• Stefan Edelkamp
• Antonin Komenda
• Tomas Pevny

In imitation learning for planning, parameters of heuristic functions are optimized against a set of solved problem instances. This work revisits the necessary and sufficient conditions of strictly optimally efficient heuristics for forward search algorithms, mainly A* and greedy best-first search, which expand only states on the returned optimal path. It then proposes a family of loss functions based on ranking tailored for a given variant of the forward search algorithm. Furthermore, from a learning theory point of view, it discusses why optimizing cost-to-goal h* is unnecessarily difficult. The experimental comparison on a diverse set of problems unequivocally supports the derived theory.

AAAI Conference 2022 Conference Paper

Competing for Resources: Estimating Adversary Strategy for Effective Plan Generation

• Lukáš Chrpa
• Pavel Rytíř
• Rostislav Horčík
• Stefan Edelkamp

Effective decision making while competing for limited resources in adversarial environments is important for many real-world applications (e. g. two Taxi companies competing for customers). Decision-making techniques such as Automated planning have to take into account possible actions of adversary (or competing) agents. That said, the agent should know what the competitor will likely do and then generate its plan accordingly. In this paper we propose a novel approach for estimating strategies of the adversary (or the competitor), sampling its actions that might hinder agent’s goals by interfering with the agent’s actions. The estimated competitor strategies are used in plan generation such that agent’s actions have to be applied prior to the ones of the competitor, whose estimated times dictate the deadlines. We empirically evaluate our approach leveraging sampling of competitor’s actions by comparing it to the naive approach optimising the make-span (not taking the competing agent into account at all) and to Nash Equilibrium (mixed) strategies.

SoCS Conference 2022 Conference Paper

Deep RRT

• Xuzhe Dang
• Lukás Chrpa
• Stefan Edelkamp

Sampling-based motion planning algorithms such as Rapidly exploring Random Trees (RRTs) have been used in robotic applications for a long time. In this paper, we propose a method that combines deep learning with RRT* method. We use a neural network to learn a sample strategy for RRT*. We evaluate Deep RRT* in a collection of 2D scenarios. The results demonstrate that our algorithm could find collision-free paths efficiently and fast, and can be generalized to unseen environments.

SoCS Conference 2022 Conference Paper

Effective Planning in Resource-Competition Problems by Task Decomposition

• Lukás Chrpa
• Pavel Rytír
• Andrii Nyporko
• Rostislav Horcík
• Stefan Edelkamp

Effective planning while competing for limited resources is crucial in many real-world applications such as on-demand transport companies competing for passengers. Planning techniques therefore have to take into account possible actions of an adversarial agent. Such a challenge that can be tackled by leveraging game-theoretical methods such as Double Oracle. This paper aims at the scalability issues arising from combining planning techniques with Double Oracle. In particular, we propose an abstraction-based heuristic for deciding how resources will be collected (e. g. which car goes for which passenger and in which order) and we propose a method for decomposing planning tasks into smaller ones (e. g. generate plans for each car separately). Our empirical evaluation shows that our proposed approach considerably improves scalability compared to the state-of-the-art techniques.

PRL Workshop 2022 Workshop Paper

Heuristic Search Planning with Deep Neural Networks using Imitation, Attention and Curriculum Learning

• Leah Chrestien
• Tomáš Pevný
• Stefan Edelkamp
• Antonín Komenda

Learning a well-informed heuristic function for hard planning domains is an elusive problem. Although there are known neural network architectures to represent such heuristic knowledge, it is not obvious what concrete information is learned and whether techniques aimed at understanding the structure help in improving the quality of the heuristics. This paper presents a network model that learns a heuristic function capable of relating distant parts of the state space via optimal plan imitation using the attention mechanism which drastically improves the learning of a good heuristic function. To counter the limitation of this method in the creation of problems of increasing difficulty, we demonstrate the use of curriculum learning, where newly solved problem instances are added to the training set, which, in turn, helps to solve problems of higher complexities and far exceeds the performances of all existing baselines including classical planning heuristics. We demonstrate its effectiveness on grid-type PDDL domains.

ICAPS Conference 2022 Conference Paper

Optimal Mixed Strategies for Cost-Adversarial Planning Games

• Rostislav Horcík
• Álvaro Torralba
• Pavel Rytír
• Lukás Chrpa
• Stefan Edelkamp

This paper shows that domain-independent tools from classical planning can be used to model and solve a broad class of game-theoretic problems we call Cost-Adversarial Planning Games (CAPGs). We define CAPGs as 2-player normal-form games specified by a planning task and a finite collection of cost functions. The first player (a planning agent) strives to solve a planning task optimally but has limited knowledge about its action costs. The second player (an adversary agent) controls the actual action costs. Even though CAPGs need not be zero-sum, every CAPG has an associated zero-sum game whose Nash equilibrium provides the optimal randomized strategy for the planning agent in the original CAPG. We show how to find the Nash equilibrium of the associated zero-sum game using a cost-optimal planner via the Double Oracle algorithm. To demonstrate the expressivity of CAPGs, we formalize a patrolling security game and several IPC domains as CAPGs.

SoCS Conference 2021 Conference Paper

Adversary Strategy Sampling for Effective Plan Generation

• Lukás Chrpa
• Pavel Rytír
• Rostislav Horcík
• Jan Cuhel
• Anastasiia Livochka
• Stefan Edelkamp

Effective plan generation in adversarial environments has to take into account possible actions of adversary agents, i. e. , the agent should know what the competitor will likely do. In this paper we propose a novel approach for estimating strategies of the adversary, sampling actions that interfere with the agent

ECAI Conference 2020 Conference Paper

Representing and Reducing Uncertainty for Enumerating the Belief Space to Improve Endgame Play in Skat

• Stefan Edelkamp

In most fully observable board games, current AIs outperform expert play. For partially observable trick-taking card games, however, human experts still play consistently better. This paper proposes efficient knowledge representation and reasoning algorithms for the internationally played three-player card game Skat by representing, progressing, enumerating, evaluating and voting for the possible worlds, each player refers to as his/her knowledge about the other players’ and the Skat cards. By using expert rules, elicited from statistical information in millions of games, this knowledge is accumulated in the first few tricks in order to reduce the uncertainty in the players’ belief. In the so-called endgame, after five to six rounds of trick play, refined exploration algorithms suggest cards that lead to improved play. The proposed AIs have been tested both in reconsidering recorded human games, and in interactive play.

SoCS Conference 2019 Conference Paper

Challenging Human Supremacy in Skat

• Stefan Edelkamp

After impressive successes in deterministic and fully-observable board games to significantly outclass humans, game playing research shifts towards non-deterministic and imperfect information card games, where humans are still persistently better. In this paper we devise a player that challenges human supremacy in Skat. We provide a complete player for playing selected variants of the game, with effective solutions for bidding and Skat putting, extracting knowledge from several million games. For trick play we combine expert rules with engineered tree exploration for optimal open card play. For dealing with uncertainty especially in Ouvert games we search the belief space.

AIJ Journal 2017 Journal Article

Efficient symbolic search for cost-optimal planning

• Álvaro Torralba
• Vidal Alcázar
• Peter Kissmann
• Stefan Edelkamp

In cost-optimal planning we aim to find a sequence of operators that achieve a set of goals with minimum cost. Symbolic search with Binary Decision Diagrams (BDDs) performs efficient state space exploration in terms of time and memory. This is crucial in optimal settings, in which large parts of the state space must be explored in order to prove optimality. However, the development of accurate heuristics for explicit-state search in recent years have left symbolic search techniques in a secondary place. In this article we propose two orthogonal improvements for symbolic search planning. On the one hand, we analyze and compare different methods for image computation in order to efficiently perform the successor generation on symbolic search. Image computation is the main bottleneck of symbolic search algorithms so an efficient computation is paramount for efficient symbolic search planning. On the other hand, we study how to use state-invariant constraints to prune states in symbolic search. This is essential in regression search but it is yet to be exploited in symbolic search planners. Experiments with symbolic bidirectional uniform-cost search and symbolic A ⁎ search with PDBs show remarkable performance improvements on most IPC benchmark domains. Overall, with the help of our improvements, symbolic bidirectional search outperforms explicit-state search with state-of-the-art heuristics such as LM-cut across many different domains.

SoCS Conference 2017 Conference Paper

Solving Graph Optimization Problems in a Framework for Monte-Carlo Search

• Stefan Edelkamp
• Eike Externest
• Sebastian Kühl
• Sabine Kuske

In this paper we solve fundamental graph optimization problems like Maximum Clique and Minimum Coloring with recent advances of Monte-Carlo Search. The optimization problems are implemented as single-agent games in a generic state-space search framework, roughly comparable to what is encoded in PDDL for an action planner.

AAAI Conference 2015 Conference Paper

BDDs Strike Back (in AI Planning)

• Stefan Edelkamp
• Peter Kissmann
• Alvaro Torralba

The cost-optimal track of the international planning competition in 2014 has seen an unexpected outcome. Different to the precursing competition in 2011, where explicit-state heuristic search planning scored best, advances in the state-set exploration with BDDs showed a significant lead. In this paper we review the outcome of the competition, briefly looking into the internals of the competing systems.

SoCS Conference 2015 Conference Paper

Monte-Carlo Tree Search for the Multiple Sequence Alignment Problem

• Stefan Edelkamp
• Zhihao Tang 0004

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.

ICAPS Conference 2014 Conference Paper

Symbolic and Explicit Search Hybrid through Perfect Hash Functions - A Case Study in Connect Four

• Stefan Edelkamp
• Peter Kissmann
• Martha Rohte

This work combines recent advances in AI planning under memory limitation, namely bitvector and symbolic search. Bitvector search assumes a bijective mapping between state and memory addresses, while symbolic search compactly represents state sets. The memory requirements vary with the structure of the problem to be solved. The integration of the two algorithms into one hybrid algorithm for strongly solving general games initiates a BDD-based solving algorithm, which consists of a forward computation of the reachable state set, possibly followed by a layered backward retrograde analysis. If the main memory becomes exhausted, it switches to explicit-state two-bit retrograde search. We use the classical game of Connect Four as a case study, and solve some instances of the problem space-efficiently with the proposed hybrid search algorithm.

ICAPS Conference 2013 Conference Paper

Transition Trees for Cost-Optimal Symbolic Planning

• Álvaro Torralba
• Stefan Edelkamp
• Peter Kissmann

Symbolic search with binary decision diagrams (BDDs) often saves huge amounts of memory and computation time. In this paper we propose two general techniques based on transition relation trees to advance BDD search by refining the image operator to compute the set of successors. First, the conjunction tree selects the set of applicable actions through filtering their precondition. Then, the disjunction tree combines each transition result. Transition trees are used to combine several transition relations, speeding up BDD search. Experiments with bidirectional symbolic blind and symbolic A* search on planning benchmarks are reported showing good performance on most IPC 2011 domains.

MFCS Conference 2012 Conference Paper

In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses

• Jingsen Chen
• Stefan Edelkamp
• Amr Elmasry
• Jyrki Katajainen

Abstract We show how to build a binary heap in-place in linear time by performing ~ 1. 625 n element comparisons, at most ~ 2. 125 n element moves, and ~ n / B cache misses, where n is the size of the input array, B the capacity of the cache line, and ~ f ( n ) approaches f ( n ) as n grows. The same bound for element comparisons was derived and conjectured to be optimal by Gonnet and Munro; however, their procedure requires Θ( n ) pointers and does not have optimal cache behaviour. Our main idea is to mimic the Gonnet-Munro algorithm by converting a navigation pile into a binary heap. To construct a binary heap in-place, we use this algorithm to build bottom heaps of size \(\Theta(\lg n)\) and adjust the heap order at the upper levels using Floyd’s sift-down procedure. On another frontier, we compare different heap-construction alternatives in practice.

ECAI Conference 2012 Conference Paper

Symbolic A * Search with Pattern Databases and the Merge-and-Shrink Abstraction

• Stefan Edelkamp
• Peter Kissmann
• Álvaro Torralba

The efficiency of heuristic search planning crucially depends on the quality of the search heuristic, while succinct representations of state sets in decision diagrams can save large amounts of memory in the exploration. BDDA* - a symbolic version of A* search - combines the two approaches into one algorithm. This paper compares two of the leading heuristics for sequential-optimal planning: the merge-and-shrink and the pattern databases heuristic, both of which can be compiled into a vector of BDDs and be used in BDDA* . The impact of optimizing the variable ordering is highlighted and experiments on benchmark domains are reported.

ICAPS Conference 2011 Conference Paper

Exploiting the Computational Power of the Graphics Card: Optimal State Space Planning on the GPU

• Damian Sulewski
• Stefan Edelkamp
• Peter Kissmann

In this paper optimal state space planning is parallelized by exploiting the processing power of a graphics card. The two exploration steps, namely selecting the actions to be applied and generating the successors, are performed on a graphics processing unit. Duplicate detection, however, is delayed to be executed on the central processing unit. Multiple cores are employed to bypass main memory latency. To increase processing speed for exact duplicate detection, the hash tables are lock-free. Moreover, a bucket-based representation enhances the concurrent distribution of frontier states. The planner supports cost-first exploration and is able to deal with a considerable fraction of current PDDL, including numerical state variables, complex objective functions, and goal preferences. It can maximize the net-benefit. Experimental findings show visible performance gains especially for larger benchmark problems.

AAAI Conference 2011 Conference Paper

Improving Cost-Optimal Domain-Independent Symbolic Planning

• Peter Kissmann
• Stefan Edelkamp

Symbolic search with BDDs has shown remarkable performance for cost-optimal deterministic planning by exploiting a succinct representation and exploration of state sets. In this paper we enhance BDD-based planning by applying a combination of domain-independent search techniques: the optimization of the variable ordering in the BDD by approximating the linear arrangement problem, pattern selection for improved construction of search heuristics in form of symbolic partial pattern databases, and a decision procedure for the amount of bidirection in the symbolic search process.

AAAI Conference 2011 Conference Paper

On the Complexity of BDDs for State Space Search: A Case Study in Connect Four

• Stefan Edelkamp
• Peter Kissmann

Symbolic search using BDDs usually saves huge amounts of memory, while in some domains its savings are moderate at best. It is an open problem to determine if BDDs work well for a certain domain. Motivated by finding evidences for BDD growths for state space search, in this paper we are concerned with symbolic search in the domain of CONNECT FOUR. We prove that there is a variable ordering for which the set of all possible states – when continuing after a terminal state has been reached – can be represented by polynomial sized BDDs, whereas the termination criterion leads to an exponential number of nodes in the BDD given any variable ordering.

SoCS Conference 2010 Conference Paper

GPU Exploration of Two-Player Games with Perfect Hash Functions

• Stefan Edelkamp
• Damian Sulewski
• Cengizhan Yücel

In this paper we improve solving two-player games by computing the game-theoretical value of every reachable state. A graphics processing unit located on the graphics card is used as a co-processor to accelerate the solution process. We exploit perfect hash functions to store the game states efficiently in memory and to transfer their ordinal representation between the host and the graphics card. As an application we validate Gasser

SoCS Conference 2010 Conference Paper

Layer-Abstraction for Symbolically Solving General Two-Player Games

• Peter Kissmann
• Stefan Edelkamp

In this paper we propose a new algorithm for solving general two-player turn-taking games that performs symbolic search utilizing binary decision diagrams (BDDs). It consists of two stages: First, it determines all breadth-first search (BFS) layers using forward search and omitting duplicate detection, next, the solving process operates in backward direction only within these BFS layers thereby partitioning all BDDs according to the layers the states reside in. We provide experimental results for selected games and compare to a previous approach. This comparison shows that in most cases the new algorithm outperforms the existing one in terms of runtime and used memory so that it can solve games that could not be solved before with a general approach.

ICAPS Conference 2010 Conference Paper

Perfect Hashing for State Space Exploration on the GPU

• Stefan Edelkamp
• Damian Sulewski
• Cengizhan Yücel

This paper exploits parallel computing power of graphics cards to accelerate state space search. We illustrate that modern graphics processing units (GPUs) have the potential to speed up breadth-first search significantly. For a bitvector representation of the search frontier, GPU algorithms with one and two bits per state are presented. Efficient perfect hash functions and their inverse are explored in order to achieve enhanced compression. We report maximal speed-ups of up to a factor of 27 wrt. single core CPU computation.

IJCAI Conference 2009 Conference Paper

• Stefan Edelkamp
• Peter Kissmann

This paper studies the solving of finite-domain action planning problems with discrete action costs and soft constraints. For sequential optimal planning, a symbolic perimeter database heuristic is addressed in a bucket implementation of A*. For computing net-benefits, we propose symbolic branch-and-bound search together with some search refinements. The net-benefit we optimize is the total benefit of satisfying the goals, minus the total action cost to achieve them. This results in an objective function to be minimized that is a linear expression over the violation of the preferences added to the action cost total.

AAAI Conference 2008 Conference Paper

Limits and Possibilities of BDDs in State Space Search

• Stefan Edelkamp

ECAI Conference 2008 Conference Paper

Symbolic Classification of General Multi-Player Games

• Peter Kissmann
• Stefan Edelkamp

For general two-player turn-taking games, first solvers have been contributed. Algorithms for multi-player games like Maxn, however, cannot classify general games robustly, and its extension Soft-Maxn, which can play optimally against unknown and weak opponents, demands large amounts of memory. As RAM is a scarce resource, this paper proposes a memory-efficient implementation of the Soft-Maxnalgorithm, by exploiting the functional representation of state and evaluation sets with BDDs.

ICAPS Conference 2007 Conference Paper

External Memory Value Iteration

• Stefan Edelkamp
• Shahid Jabbar
• Blai Bonet

We propose a unified approach to disk-based search for deterministic, non-deterministic, and probabilistic (MDP) settings. We provide the design of an external Value Iteration algorithm that performs at most O(lG. scan(|E|) + tmax. sort(|E|)) I/Os, where lG is the length of the largest back-edge in the breadth-first search graph G having |E| edges, tmax is the maximum number of iterations, and scan(n) and sort(n) are the I/O complexities for externally scanning and sorting n items. The new algorithm is evaluated over large instances of known benchmark problems. As shown, the proposed algorithm is able to solve very large problems that do not fit into the available RAM and thus out of reach for other exact algorithms.

AAAI Conference 2006 Conference Paper

Cost-Optimal External Planning

• Stefan Edelkamp
• Shahid Jabbar

This paper considers strategies for external memory based optimal planning. An external breadth-first search exploration algorithm is devised that is guaranteed to find the costoptimal solution. We contribute a procedure for finding the upper bound on the locality of the search in planning graphs that dictates the number of layers that have to be kept to avoid re-openings. We also discuss an external variant of Enforced Hill Climbing. Using relaxed-plan heuristic without helpful-action pruning we have been able to perform large explorations on metric planning problems, providing better plan lengths than have been reported earlier. A novel approach to plan reconstruction in external setting with linear I/O complexity is proposed. We provide external exploration results on some recently proposed planning domains.

ECAI Conference 2006 Conference Paper

Cost-Optimal Symbolic Planning with State Trajectory and Preference Constraints

• Stefan Edelkamp

State trajectory and plan preference constraints are the two language features recently introduced to PDDL in the context of the 5 th international planning competition. For planning with soft constraints, an objective function monitors their violation. This paper introduces a symbolic approach for finding cost-optimal plans. The set-based branch-and-bound algorithm exploits an efficient symbolic representation of the objective function. State trajectory constraints are compiled into automata, while ordinary preferences are evaluated on-line for the intersection of the search frontier with the goal.

ICAPS Conference 2006 Conference Paper

On the Compilation of Plan Constraints and Preferences

• Stefan Edelkamp

State trajectory and preference constraints are the two language features introduced in PDDL3 for describing benchmarks of the 5th international planning competition. In this work we make existing solver technology applicable to planning with PDDL3 domains by compiling the new constructs back to PDDL2. State trajectory constraints are translated into LTL formulae and further to Büchi automata, one for each constraint. These automata are compiled to grounded PDDL and the results are merged with the grounded representation of the original problem. Preference constraints are compiled away using numerical state variables. We provide experimental results in heuristic search planning.

AAAI Conference 2005 Conference Paper

Cost-Algebraic Heuristic Search

• Stefan Edelkamp

Heuristic search is used to efficiently solve the single-node shortest path problem in weighted graphs. In practice, however, one is not only interested in finding a short path, but an optimal path, according to a certain cost notion. We propose an algebraic formalism that captures many cost notions, like typical Quality of Service attributes. We thus generalize A*, the popular heuristic search algorithm, for solving optimal-path problem. The paper provides an answer to a fundamental question for AI search, namely to which general notion of cost, heuristic search algorithms can be applied. We proof correctness of the algorithms and provide experimental results that validate the feasibility of the approach.

ICAPS Conference 2005 Conference Paper

External Symbolic Heuristic Search with Pattern Databases

• Stefan Edelkamp

In this paper we propose refinements for optimal search with symbolic pattern databases in deterministic state-space planning. As main memory is limited, external heuristic search is combined with the power of symbolic representation. We start with an external version of symbolic breadth-first search. Then an alternative and external implementation for BDDA* to include different heuristic evaluation functions into the symbolic search process is presented.

LPAR Conference 2002 Conference Paper

Directed Automated Theorem Proving

• Stefan Edelkamp
• Peter Leven

Abstract This paper analyzes the effect of heuristic search algorithms like A * and IDA * to accelerate proof-state based theorem provers. A functional implementation of possibly weighted A * is proposed that extends Dijkstra’s single-source shortest-path algorithm. Efficient implementation issues and possible flaws for both A * and IDA * are discussed in detail. Initial results with first and higher order logic examples in Isabelle indicate that directed automated theorem proving is superior to other known general inference mechanisms and that it can enhance other proof techniques like model elimination.

ICAPS Conference 2002 Conference Paper

Symbolic Pattern Databases in Heuristic Search Planning

• Stefan Edelkamp

This paper invents symbolic pattern databases (SPDB) to combine two influencing aspects for recent progress in domain-independent action planning, namely heuristic search and model checking. SPDBs are off-line computed dictionaries, generated in symbolic backward traversals of automatically inferred planning space abstractions. The entries of SPDBs serve as heuristic estimates to accelerate explicit and symbolic, approximate and optimal heuristic search planners. Selected experiments highlight that the symbolic representation yields much larger and more accurate pattern databases than the ones generated with explicit methods.

AIJ Journal 2001 Journal Article

Time complexity of iterative-deepening-A∗

• Richard E. Korf
• Michael Reid
• Stefan Edelkamp

We analyze the time complexity of iterative-deepening-A ∗ (IDA ∗ ). We first show how to calculate the exact number of nodes at a given depth of a regular search tree, and the asymptotic brute-force branching factor. We then use this result to analyze IDA ∗ with a consistent, admissible heuristic function. Previous analyses relied on an abstract analytic model, and characterized the heuristic function in terms of its accuracy, but do not apply to concrete problems. In contrast, our analysis allows us to accurately predict the performance of IDA ∗ on actual problems such as the sliding-tile puzzles and Rubik's Cube. The heuristic function is characterized by the distribution of heuristic values over the problem space. Contrary to conventional wisdom, our analysis shows that the asymptotic heuristic branching factor is the same as the brute-force branching factor. Thus, the effect of a heuristic function is to reduce the effective depth of search by a constant, relative to a brute-force search, rather than reducing the effective branching factor.

AAAI Conference 2000 Conference Paper

Localizing A*

• Stefan Edelkamp

Heuristic search in large problem spaces inherently calls for algorithms capable of running under restricted memory. This question has been investigated in a number of articles. However, in general the efficient usage of two-layered storage systems is not further discussed. Even if hard-disk capacity is sufficient for the problem instance at hand, the limitation of main memory may still represent the bottleneck for their practical applications. Since breadth-first and best-first strategies do not exhibit any locality of expansion, standard virtual memory management can soon result in thrashing due to excessive page faults. In this paper we propose a new search algorithm and suitable data structures in order to minimize page faults by a local reordering of the sequence of expansions. We prove its correctness and completeness and evaluate it in a real-world scenario of searching a large road map in a commercial route planning system.

AAAI Conference 1998 Conference Paper

The Branching Factor of Regular Search Spaces

• Stefan Edelkamp

Many problems, such as the sliding-tile puzzles, generate searchtrees where different nodeshavedifferent numbers of children, in this case depending on the position of the blank. Weshowhowto calculate the asymptotic branchingfactors of such problems, and how to efficiently compute the exact numbers of nodes at a givendepth. Thisinformation is importantfor determiningthe complexityof various searchalgorithms onthese problems. In additionto the sliding-tile puzzles, wealso apply our technique to Rubik’sCube. Whileour techniquesare fairly straightforward, the literature is full of incorrectbranching factorsfor these problems, andthe errors in several incorrect methods are fairly subtle.

ECAI Conference 1998 Conference Paper

Updating Shortest Paths

• Stefan Edelkamp