Peter Kissmann

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.

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

Focusing on What Really Matters: Irrelevance Pruning in Merge-and-Shrink

• Álvaro Torralba
• Peter Kissmann

Merge-and-shrink (M&S) is a framework to generate abstraction heuristics for cost-optimal planning. A recent approach computes simulation relations on a set of M&S abstractions in order to identify states that are better than others. This relation is then used for pruning states in the search when a "better" state is already known. We propose the usage of simulation relations inside the M&S framework in order to detect irrelevant transitions in abstract state spaces. This potentially simplifies the abstraction allowing M&S to derive more informed heuristics. We also tailor M&S to remove irrelevant operators from the planning task. Experimental results show the potential of our approach to construct well-informed heuristics and simplify the planning tasks prior to the search.

ECAI Conference 2014 Conference Paper

"Distance"? Who Cares? Tailoring Merge-and-Shrink Heuristics to Detect Unsolvability

• Jörg Hoffmann 0001
• Peter Kissmann
• Álvaro Torralba

Research on heuristic functions is all about estimating the length (or cost) of solution paths. But what if there is no such path? Many known heuristics have the ability to detect (some) unsolvable states, but that ability has always been treated as a by-product. No attempt has been made to design heuristics specifically for that purpose, where there is no need to preserve distances. As a case study towards leveraging that advantage, we investigate merge-and-shrink abstractions in classical planning. We identify safe abstraction steps (no information loss regarding solvability) that would not be safe for traditional heuristics. We design practical algorithm configurations, and run extensive experiments showing that our heuristics outperform the state of the art for proving planning tasks unsolvable.

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.

ICAPS Conference 2013 Conference Paper

What's in It for My BDD? On Causal Graphs and Variable Orders in Planning

• Peter Kissmann
• Jörg Hoffmann 0001

One decisive factor for the success of symbolic search using BDDs is whether or not the variable ordering is good. A general intuition is that smaller BDDs result if inter-dependent variables are close together. The most common means to capture variable dependencies in planning are causal graphs, and consequently previous work defined variable orders based on these. Starting from the observation that the two concepts of “dependency” are actually quite different, we introduce a framework for assessing the strength of variable ordering heuristics in sub-classes of planning. It turns out that causal graph based variable orders may be exponentially worse than optimal even for very simple planning tasks. Experiments with a broad range of such variable ordering variants indicate that they are mediocre at best.

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

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.

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.

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.