Dr. Manuel Heusner
Awards
-
SoCS 2017 Best Paper Award
for the paper
Understanding the Search Behaviour of Greedy Best-First Search
(PDF)
with Thomas Keller and Malte Helmert at the 10th Annual Symposium on Combinatorial Search
(SoCS 2017).
Publications
(Show all abstracts)
(Hide all abstracts)
2019
-
Manuel Heusner.
Search Behavior of Greedy Best-First Search.
Ph.D. Thesis, University of Basel, Switzerland,
2019.
Date of disputation: 2019-05-10.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
Greedy best-first search (GBFS) is a sibling of A* in the
family of best-first state-space 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 best-first
search shows that A* with admissible and consistent heuristic
expands every state whose f-value is below the optimal solution
cost and no state whose f-value 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 high-water mark benches, which separate
the search space into areas that are searched by GBFS in sequence.
High-water mark benches allow us to exactly determine the set of
states that GBFS expands under at least one tie-breaking 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 best-case and
worst-case behavior of GBFS in given search instances. We show
that computing the best-case or worst-case behavior of GBFS is
NP-complete 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 best-case and worst-case
behavior. We use the algorithms to analyze GBFS on benchmark tasks
from planning competitions under a state-of-the-art heuristic.
Experimental results reveal interesting characteristics of the
heuristic on the given tasks and demonstrate the importance of
tie-breaking in GBFS.
2018
-
Manuel Heusner, Thomas Keller and Malte Helmert.
Best-Case and Worst-Case Behavior of Greedy Best-First Search.
In
Proceedings of the 27th International Joint Conference on Artificial Intelligence
(IJCAI 2018), pp. 1463-1470.
2018.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
(poster; PDF)
We study the impact of tie-breaking on the behavior of greedy
best-first search with a fixed state space and fixed heuristic. We
prove that it is NP-complete to determine the number of states that
need to be expanded by greedy best-first search in the best case or
in the worst case. However, the best- and worst-case 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 best-first search to FIFO, LIFO and random
tie-breaking. The experiments demonstrate the importance of
tie-breaking in greedy best-first search.
-
Manuel Heusner, Thomas Keller and Malte Helmert.
Search Progress and Potentially Expanded States in Greedy Best-First Search.
In
Proceedings of the 27th International Joint Conference on Artificial Intelligence
(IJCAI 2018), pp. 5269-5273.
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
f-value is below the optimal solution cost and no state whose
f-value is above the optimal solution cost. For satisficing search
algorithms, a similarly clear understanding is currently lacking.
We examine the search behavior of greedy best-first 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 Best-First Search.
In
Proceedings of the 10th Annual Symposium on Combinatorial Search
(SoCS 2017), pp. 47-55.
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
f-value is below the optimal solution cost and no state whose
f-value is above the optimal solution cost. For satisficing search
algorithms, a similarly clear understanding is currently lacking. We
examine the search behaviour of greedy best-first search (GBFS) in
order to make progress towards such an understanding.
We introduce the concept of high-water mark benches, which
separate the search space into areas that are searched by a
GBFS algorithm in sequence. High-water mark benches allow us to
exactly determine the set of states that are not expanded under any
GBFS tie-breaking 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.
Under-Approximation Refinement for Classical Planning.
In
Proceedings of the 24th International Conference on Automated
Planning and Scheduling (ICAPS 2014), pp. 365-369.
2014.
(Show abstract)
(Hide abstract)
(PDF)
A general and important problem of search-based 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 under-approximation 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
straight-forward instantiation of this framework yields a
competitive planner that often finds plans with small operator sets.