Clemens Büchner – Publications

In classical planning, the aim is to find a sequence of deterministic actions leading from the initial to a goal state. In this work, we consider the scenario where a party who knows the solution to a planning task, called the prover, wants to convince a second party, the verifier, that it has the solution without revealing any information about the solution itself. This is relevant in domains where privacy is important, for example when plans contain sensitive information or when the solution should not be revealed upfront. We achieve this by introducing a zero-knowledge protocol for plan existence. By restricting ourselves to tasks with polynomially-bounded plan length, we are able to construct a protocol that can be run efficiently by both prover and verifier. The resulting protocol does not rely on any reduction, has a constant number of rounds, and runs in time polynomial in the size of the task.

Debugging can be a painful task, especially when bugs only occur for large input files. We present Machetli, a tool to help with debugging in such situations. It takes a large input file and cuts away parts of it, while still provoking the bug. The resulting file is much smaller than the original, making the bug easier to find and fix. In our experience, Machetli was able to reduce planning tasks with thousands of actions to trivial tasks that could even be solved by hand. Machetli is an open-source project and it can be extended to other use cases such as debugging SAT solvers or LaTeX compilation bugs.

Since its invention in 1974, the Rubik’s Cube puzzle fascinates people of all ages. Its rules are simple: the player gets a scrambled cube and rotates the six faces until each face contains only stickers of one color. Nevertheless, finding a short sequence of rotations to solve the cube is hard. We present the first model of Rubik’s Cube for general problem solvers. To obtain a concise model, we require conditional effects. Furthermore, we extend counterexample-guided Cartesian abstraction refinement (CEGAR) to support factored effect tasks, a class of planning tasks with a specific kind of conditional effects which includes Rubik’s Cube. Finally, we evaluate how newer types of abstraction heuristics compare against pattern database (PDB) heuristics, the state-of-the-art for solving Rubik’s Cube. We find that PDBs still outperform the more general Cartesian and merge-and-shrink abstractions. However, in contrast to PDBs, Cartesian abstractions yield perfect heuristics up to a certain problem difficulty. These findings raise interesting questions for future research.

Landmarks of a planning task denote properties that must be satisfied by all plans. Existing landmark heuristics exploit that each landmark must be achieved at least once. However, if the orderings between the landmarks induce cyclic dependencies, one of the landmarks in each cycle must be achieved an additional time. We propose two novel heuristics for cost-optimal planning that consider cyclic dependencies between landmarks in addition to the cost for achieving all landmarks once. We show that our heuristics dominate the minimum hitting set solution over any set of landmarks as well as h + if all delete-relaxation landmarks are considered. An experimental evaluation on benchmarks from the International Planning Competition shows that exploiting cyclic dependencies can lead to improved heuristics.

It is usually prohibitively expensive to recompute landmarks in every state of a heuristic search algorithm that bases its heuristic estimate on landmarks. Successful planning systems like LAMA compute landmarks just for the initial state instead and only keep track for each state encountered during search which landmarks of the initial state are accepted or required again. The LM-A* algorithm describes a similar idea for cost-optimal heuristic search. However, it lacks support for reasonable orderings, which have recently been shown to be informative when cyclic dependencies between landmarks are exploited in the heuristic computation. We propose the novel LM-BFS framework for best-first heuristic search with landmark-based heuristics which allows to describe a variety of algorithms in terms of five components: landmark generation, landmark graph progression, landmark graph merging, landmark graph extension, and exploration strategy. We use LM-BFS to show that considering reasonable orderings in the landmark graph progression component leads to flawed landmark graphs in LAMA , and propose a novel landmark graph extension that captures the same information flawlessly. We observe empirically that considering reasonable orderings in the extension rather than the progression component has a positive effect both for LAMA and for cost-optimal planning.