Author name cluster

Thomas Keller

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers

1 author row

IJCAI Conference 2022 Conference Paper

Learning and Exploiting Progress States in Greedy Best-First Search

Patrick Ferber
Liat Cohen
Jendrik Seipp
Thomas Keller

Previous work introduced the concept of progress states. After expanding a progress state, a greedy best-first search (GBFS) will only expand states with lower heuristic values. Current methods can identify progress states only for a single task and only after a solution for the task has been found. We introduce a novel approach that learns a description logic formula characterizing all progress states in a classical planning domain. Using the learned formulas in a GBFS to break ties in favor of progress states often significantly reduces the search effort.

PDF Details DOI

AAAI Conference 2021 Conference Paper

Saturated Post-hoc Optimization for Classical Planning

Jendrik Seipp
Thomas Keller
Malte Helmert

Saturated cost partitioning and post-hoc optimization are two powerful cost partitioning algorithms for optimal classical planning. The main idea of saturated cost partitioning is to give each considered heuristic only the fraction of remaining operator costs that it needs to prove its estimates. We show how to apply this idea to post-hoc optimization and obtain a heuristic that dominates the original both in theory and on the IPC benchmarks.

PDF Details

IJCAI Conference 2020 Conference Paper

Cost-Partitioned Merge-and-Shrink Heuristics for Optimal Classical Planning

Silvan Sievers
Florian Pommerening
Thomas Keller
Malte Helmert

Cost partitioning is a method for admissibly combining admissible heuristics. In this work, we extend this concept to merge-and-shrink (M&S) abstractions that may use labels that do not directly correspond to operators. We investigate how optimal and saturated cost partitioning (SCP) interact with M&S transformations and develop a method to compute SCPs during the computation of M&S. Experiments show that SCP significantly improves M&S on standard planning benchmarks.

PDF Details DOI

JAIR Journal 2020 Journal Article

Saturated Cost Partitioning for Optimal Classical Planning

Jendrik Seipp
Thomas Keller
Malte Helmert

Cost partitioning is a method for admissibly combining a set of admissible heuristic estimators by distributing operator costs among the heuristics. Computing an optimal cost partitioning, i.e., the operator cost distribution that maximizes the heuristic value, is often prohibitively expensive to compute. Saturated cost partitioning is an alternative that is much faster to compute and has been shown to yield high-quality heuristics. However, its greedy nature makes it highly susceptible to the order in which the heuristics are considered. We propose a greedy algorithm to generate orders and show how to use hill-climbing search to optimize a given order. Combining both techniques leads to significantly better heuristic estimates than using the best random order that is generated in the same time. Since there is often no single order that gives good guidance on the whole state space, we use the maximum of multiple orders as a heuristic that is significantly better informed than any single-order heuristic, especially when we actively search for a set of diverse orders.

PDF Details DOI

IJCAI Conference 2018 Conference Paper

Best-Case and Worst-Case Behavior of Greedy Best-First Search

Manuel Heusner
Thomas Keller
Malte Helmert

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.

PDF Details

IJCAI Conference 2018 Conference Paper

Search Progress and Potentially Expanded States in Greedy Best-First Search

Manuel Heusner
Thomas Keller
Malte Helmert

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. 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 expanded by at least one GBFS tie-breaking strategy and give us a clearer understanding of search progress.

PDF Details

AAAI Conference 2017 Conference Paper

Narrowing the Gap Between Saturated and Optimal Cost Partitioning for Classical Planning

Jendrik Seipp
Thomas Keller
Malte Helmert

In classical planning, cost partitioning is a method for admissibly combining a set of heuristic estimators by distributing operator costs among the heuristics. An optimal cost partitioning is often prohibitively expensive to compute. Saturated cost partitioning is an alternative that is much faster to compute and has been shown to offer high-quality heuristic guidance on Cartesian abstractions. However, its greedy nature makes it highly susceptible to the order in which the heuristics are considered. We show that searching in the space of orders leads to signiﬁcantly better heuristic estimates than with previously considered orders. Moreover, using multiple orders leads to a heuristic that is signiﬁcantly better informed than any single-order heuristic. In experiments with Cartesian abstractions, the resulting heuristic approximates the optimal cost partitioning very closely.

PDF Details

IJCAI Conference 2016 Conference Paper

State-Dependent Cost Partitionings for Cartesian Abstractions in Classical Planning

Thomas Keller
Florian Pommerening
Jendrik Seipp
Florian Gei
szlig; er
Robert Mattm
uuml; ller

Abstraction heuristics are a popular method to guide optimal search algorithms in classical planning. Cost partitionings allow to sum heuristic estimates admissibly by distributing action costs among the heuristics. We introduce state-dependent cost partitionings which take context information of actions into account, and show that an optimal state-dependent cost partitioning dominates its state-independent counterpart. We demonstrate the potential of our idea with a state-dependent variant of the recently proposed saturated cost partitioning, and show that it has the potential to improve not only over its state-independent counterpart, but even over the optimal state-independent cost partitioning. Our empirical results give evidence that ignoring the context of actions in the computation of a cost partitioning leads to a significant loss of information.

PDF Details

AAAI Conference 2015 Conference Paper

Better Be Lucky than Good: Exceeding Expectations in MDP Evaluation

Thomas Keller
Florian Geißer

We introduce the MDP-Evaluation Stopping Problem, the optimization problem faced by participants of the International Probabilistic Planning Competition 2014 that focus on their own performance. It can be constructed as a meta-MDP where actions correspond to the application of a policy on a base-MDP, which is intractable in practice. Our theoretical analysis reveals that there are tractable special cases where the problem can be reduced to an optimal stopping problem. We derive approximate strategies of high quality by relaxing the general problem to an optimal stopping problem, and show both theoretically and experimentally that it not only pays off to pursue luck in the execution of the optimal policy, but that there are even cases where it is better to be lucky than good as the execution of a suboptimal base policy is part of an optimal strategy in the meta-MDP.

PDF Details

IJCAI Conference 2015 Conference Paper

Delete Relaxations for Planning with State-Dependent Action Costs

Florian Gei
szlig; er
Thomas Keller
Robert Mattm
uuml; ller

Most work in planning focuses on tasks with stateindependent or even uniform action costs. However, supporting state-dependent action costs admits a more compact representation of many tasks. We investigate how to solve such tasks using heuristic search, with a focus on delete-relaxation heuristics. We first define a generalization of the additive heuristic hadd to such tasks and then discuss different ways of computing it via compilations to tasks with state-independent action costs and more directly by modifying the relaxed planning graph. We evaluate these approaches theoretically and present an implementation of hadd for planning with state-dependent action costs. To our knowledge, this gives rise to the first approach able to handle even the hardest instances of the combinatorial ACADEMIC ADVISING domain from the International Probabilistic Planning Competition (IPPC) 2014.

PDF Details

RLDM Conference 2013 Conference Abstract

Trial-based Heuristic Tree Search for Finite Horizon MDPs

Thomas Keller
Malte Helmert

Dynamic programming is a well-known approach for solving MDPs. In large state spaces, asyn- chronous versions like Real-Time Dynamic Programming (RTDP) have been applied successfully. If unfold- ed into equivalent trees, Monte-Carlo Tree Search algorithms are a valid alternative. UCT, the most popular representative, obtains good anytime behavior by guiding the search towards promising areas of the search tree and supporting non-admissible heuristics. The global Heuristic Search algorithm AO* finds optimal solutions for MDPs that can be represented as acyclic AND/OR graphs. Despite the differences, these approaches actually have much in common. We present the Trial-based Heuris- tic Tree Search (THTS) framework that subsumes these approaches and distinguishes them based on only five ingredients: heuristic function, backup function, action selection, outcome selection, and trial length. We describe the ingredients that model RTDP, AO* and UCT within this framework, and use THTS to com- bine attributes of these algorithms step by step in order to derive novel algorithms with superior theoretical properties. We merge Full Bellman and Monte-Carlo backup functions to Partial Bellman backups, and gain a function that both allows partial updates and a procedure that labels states when they are solved. DP-UCT combines attributes and theoretical properties from RTDP and UCT even though it differs from the latter only in the used Partial Bellman backups. Our main algorithm, UCT* adds a limited trial length to DP-UCT to inherit the global search behavior of AO*, which ensures that parts of the state space that are closer to the root are investigated more thoroughly. The experimental evaluation shows that both DP-UCT and UCT* are not only superior to UCT, but also outperform Prost, the winner of the International Probabilistic Planning Competition (IPPC) 2011 on the benchmarks of IPPC 2011.

PDF Details

AAAI Conference 2010 Conference Paper

High-Quality Policies for the Canadian Traveler’s Problem

Patrick Eyerich
Thomas Keller
Malte Helmert

We consider the stochastic variant of the Canadian Traveler’s Problem, a path planning problem where adverse weather can cause some roads to be untraversable. The agent does not initially know which roads can be used. However, it knows a probability distribution for the weather, and it can observe the status of roads incident to its location. The objective is to find a policy with low expected travel cost. We introduce and compare several algorithms for the stochastic CTP. Unlike the optimistic approach most commonly considered in the literature, the new approaches we propose take uncertainty into account explicitly. We show that this property enables them to generate policies of much higher quality than the optimistic one, both theoretically and experimentally.

PDF Details