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

Manuel Heusner.
Search Behavior of Greedy BestFirst Search.
Ph.D. Thesis, University of Basel, Switzerland,
2019.
Date of disputation: 20190510.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
Greedy bestfirst search (GBFS) is a sibling of A* in the
family of bestfirst statespace search algorithms. While A* is
guaranteed to find optimal solutions of search problems, GBFS does
not provide any guarantees but typically finds satisficing solutions
more quickly than A*. A classical result of optimal bestfirst
search shows that A* with 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. Theoretical results of this kind are useful for the analysis
of heuristics in different search domains and for the improvement of
algorithms. For satisficing algorithms a similarly clear
understanding is currently lacking. We examine the search behavior
of 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 GBFS in sequence.
Highwater mark benches allow us to exactly determine the set of
states that GBFS expands under at least one tiebreaking strategy.
We show that benches contain craters. Once GBFS enters a crater,
it has to expand every state in the crater before being able to
escape.
Benches and craters allow us to characterize the bestcase and
worstcase behavior of GBFS in given search instances. We show
that computing the bestcase or worstcase behavior of GBFS is
NPcomplete in general but can be computed in polynomial time for
undirected state spaces.
We present algorithms for extracting the set of states that GBFS
potentially expands and for computing the bestcase and worstcase
behavior. We use the algorithms to analyze GBFS on benchmark tasks
from planning competitions under a stateoftheart heuristic.
Experimental results reveal interesting characteristics of the
heuristic on the given tasks and demonstrate the importance of
tiebreaking in GBFS.
2018

Manuel Heusner, Thomas Keller and Malte Helmert.
BestCase and WorstCase Behavior of Greedy BestFirst Search.
In
Proceedings of the 27th International Joint Conference on Artificial Intelligence
(IJCAI 2018), pp. 14631470.
2018.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
(poster; PDF)
We study the impact of tiebreaking on the behavior of greedy
bestfirst search with a fixed state space and fixed heuristic. We
prove that it is NPcomplete to determine the number of states that
need to be expanded by greedy bestfirst search in the best case or
in the worst case. However, the best and worstcase behavior can
be computed in polynomial time for undirected state spaces. We
perform computational experiments on benchmark tasks from the
International Planning Competitions that compare the best and worst
cases of greedy bestfirst search to FIFO, LIFO and random
tiebreaking. The experiments demonstrate the importance of
tiebreaking in greedy bestfirst search.

Manuel Heusner, Thomas Keller and Malte Helmert.
Search Progress and Potentially Expanded States in Greedy BestFirst Search.
In
Proceedings of the 27th International Joint Conference on Artificial Intelligence
(IJCAI 2018), pp. 52695273.
2018.
Note: This paper was invited for submission to the Best Papers
From Sister Conferences Track, based on a paper that appeared in
the Symposium on Combinatorial Search (SoCS) 2017. When referring to this work,
please cite the SoCS 2017 paper instead of this version.
(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 behavior of greedy bestfirst search (GBFS)
in order to make progress towards such an understanding.
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.