Manuel Heusner – Publications
(Show all abstracts)
(Hide all abstracts)
2017

Manuel Heusner, Thomas Keller and Malte Helmert.
Understanding the Search Behaviour of Greedy BestFirst Search.
In
Proceedings of the 10th Annual Symposium on Combinatorial Search
(SoCS 2017), pp. 4755.
2017.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
A classical result in optimal search shows that A* with an
admissible and consistent heuristic expands every state whose
fvalue is below the optimal solution cost and no state whose
fvalue is above the optimal solution cost. For satisficing search
algorithms, a similarly clear understanding is currently lacking. We
examine the search behaviour of greedy bestfirst search (GBFS) in
order to make progress towards such an understanding.
We introduce the concept of highwater mark benches, which
separate the search space into areas that are searched by a
GBFS algorithm in sequence. Highwater mark benches allow us to
exactly determine the set of states that are not expanded under any
GBFS tiebreaking strategy. For the remaining states, we show that
some are expanded by all GBFS searches, while others are expanded
only if certain conditions are met.
2014

Manuel Heusner, Martin Wehrle, Florian Pommerening and Malte Helmert.
UnderApproximation Refinement for Classical Planning.
In
Proceedings of the 24th International Conference on Automated
Planning and Scheduling (ICAPS 2014), pp. 365369.
2014.
(Show abstract)
(Hide abstract)
(PDF)
A general and important problem of searchbased planning techniques
is the state explosion problem, which is usually tackled with
approaches to reduce the branching factor of the planning task. Such
approaches often implicitly exploit the observation that the number
of available operators is higher than the number of operators that
are actually needed to find a plan. In this paper, we propose a
simple, but general underapproximation refinement framework for
satisficing planning that explicitly exploits this observation. Our
approach iteratively searches for plans with operator
subsets, which are refined if necessary by adding
operators that appear to be needed. Our evaluation shows that even a
straightforward instantiation of this framework yields a
competitive planner that often finds plans with small operator sets.