Florian Geißer – Publications

(Show all abstracts) (Hide all abstracts)

2020

David Speck, Florian Geißer and Robert Mattmüller.
When Perfect is not Good Enough: On the Search Behaviour of Symbolic Heuristic Search.
In Proceedings of the 30th International Conference on Automated Planning and Scheduling (ICAPS 2020), pp. 263-271. 2020.
(Show abstract) (Hide abstract) (PDF)

Symbolic search has proven to be a competitive approach to cost-optimal planning, as it compactly represents sets of states by symbolic data structures. While heuristics for symbolic search exist, symbolic bidirectional blind search empirically outperforms its heuristic counterpart and is therefore the dominant search strategy. This prompts the question of why heuristics do not seem to pay off in symbolic search. As a first step in answering this question, we investigate the search behaviour of symbolic heuristic search by means of BDDA*. Previous work identified the partitioning of state sets according to their heuristic values as the main bottleneck. We theoretically and empirically evaluate the search behaviour of BDDA* and reveal another fundamental problem: we prove that the use of a heuristic does not always improve the search performance of BDDA*. In general, even the perfect heuristic can exponentially deteriorate search performance.
Florian Geißer, David Speck and Thomas Keller.
Trial-based Heuristic Tree Search for MDPs with Factored Action Spaces.
In Proceedings of the 13th Annual Symposium on Combinatorial Search (SoCS 2020), pp. 38-47. 2020.
(Show abstract) (Hide abstract) (PDF)

MDPs with factored action spaces, i.e. where actions are described as assignments to a set of action variables, allow reasoning over action variables instead of action states, yet most algorithms only consider a grounded action representation. This includes algorithms that are instantiations of the trial-based heuristic tree search (THTS) framework, such as AO* or UCT. To be able to reason over factored action spaces, we propose a generalisation of THTS where nodes that branch over all applicable actions are replaced with subtrees that consist of nodes that represent the decision for a single action variable. We show that many THTS algorithms retain their theoretical properties under the generalised framework, and show how to approximate any state-action heuristic to a heuristic for partial action assignments. This allows to guide a UCT variant that is able to create exponentially fewer nodes than the same algorithm that considers ground actions. An empirical evaluation on the benchmark set of the probabilistic track of the latest International Planning Competition validates the benefits of the approach.

2019

Sumitra Corraya, Florian Geißer, David Speck and Robert Mattmüller.
An Empirical Study of the Usefulness of State-Dependent Action Costs in Planning.
In Proceedings of the 42nd German Conference on Artificial Intelligence (KI 2019), pp. 123-130. 2019.
(Show abstract) (Hide abstract) (PDF) (PDF; Online)

The vast majority of work in planning to date has focused on state-independent action costs. However, if a planning task features state-dependent costs, using a cost model with state-independent costs means either introducing a modeling error, or potentially sacrificing compactness of the model. In this paper, we investigate the conflicting priorities of modeling accuracy and compactness empirically, with a particular focus on the extent of the negative impact of reduced modeling accuracy on (a) the quality of the resulting plans, and (b) the search guidance provided by heuristics that are fed with inaccurate cost models. Our empirical results show that the plan suboptimality introduced by ignoring state-dependent costs can range, depending on the domain, from inexistent to several orders of magnitude. Furthermore, our results show that the impact on heuristic guidance additionally depends strongly on the heuristic that is used, the specifics of how exactly the costs are represented, and whether one is interested in heuristic accuracy, node expansions, or overall runtime savings.
Florian Geißer, David Speck and Thomas Keller.
An Analysis of the Probabilistic Track of the IPC 2018.
In Proceedings of the ICAPS-2019 Workshop on the International Planning Competition (WIPC 2019), pp. 27-35. 2019.
(Show abstract) (Hide abstract) (PDF)

The International Planning Competition 2018 consisted of several tracks on classical, temporal and probabilistic planning. In this paper, we focus on the discrete MDP track of the probabilistic portion of the competition.

We discuss the changes to the input language RDDL, which give rise to new challenges for planning systems, and analyze each of the eight competition domains separately and highlight unique properties. We demonstrate flaws of the used evaluation criterion, the IPC score, and discuss the need for optimal upper bounds. An evaluation of the three top-performers, including their post-competition versions, and a brief analysis of their performance highlights the strengths and weaknesses of the individual approaches.
David Speck, Florian Geißer, Robert Mattmüller and Álvaro Torralba.
Symbolic Planning with Axioms.
In Proceedings of the 29th International Conference on Automated Planning and Scheduling (ICAPS 2019), pp. 464-572. 2019.
(Show abstract) (Hide abstract) (PDF)

Axioms are an extension for classical planning models that allow for modeling complex preconditions and goals exponentially more compactly. Although axioms were introduced in planning more than a decade ago, modern planning techniques rarely support axioms, especially in cost-optimal planning. Symbolic search is a popular and competitive optimal planning technique based on the manipulation of sets of states. In this work, we extend symbolic search algorithms to support axioms natively. We analyze different ways of encoding derived variables and axiom rules to evaluate them in a symbolic representation. We prove that all encodings are sound and complete, and empirically show that the presented approach outperforms the previous state of the art in cost-optimal classical planning with axioms.

2018

Florian Geißer.
On planning with state-dependent action costs.
FreiDok plus 2018.
Dissertation Thesis.
(PDF)
David Speck, Florian Geißer and Robert Mattmüller.
Symbolic Planning with Edge-Valued Multi-Valued Decision Diagrams.
In Proceedings of the 28th International Conference on Automated Planning and Scheduling (ICAPS 2018). 2018.
(Show abstract) (Hide abstract) (PDF) (technical report with proofs; PDF)

Symbolic representations have attracted significant attention in optimal planning. Binary Decision Diagrams (BDDs) form the basis for symbolic search algorithms. Closely related are Algebraic Decision Diagrams (ADDs), used to represent heuristic functions.

Also, progress was made in dealing with models that take state-dependent action costs into account. Here, costs are represented as Edge-valued Multi-valued Decision Diagrams (EVMDDs), which can be exponentially more compact than the corresponding ADD representation. However, they were not yet considered for symbolic planning.

In this work, we study EVMDD-based symbolic search for optimal planning. We define EVMDD-based representations of state sets and transition relations, and show how to compute the necessary operations required for EVMDD-A*. This EVMDD-based version of symbolic A* generalizes its BDD variant, and allows to solve planning tasks with state-dependent action costs.

We prove theoretically that our approach is sound, complete and optimal. Additionally, we present an empirical analysis comparing EVMDD-A* to BDD-A* and explicit A* search. Our results underscore the usefulness of symbolic approaches and the feasibility of dealing with models that go beyond unit costs.
Florian Geißer and David Speck.
PROST-DD - Utilizing Symbolic Classical Planning in THTS.
In The 6th International Probabilistic Planning Competition (IPPC 2018), pp. 13-16. 2018.
(Show abstract) (Hide abstract) (PDF)

We describe PROST-DD, our submission to the International Probabilistic Planning Competition 2018. Like its predecessor PROST, which already participated with success at the previous IPPC, PROST-DD is based on the trial-based heuristic tree search framework and applies the UCT* algorithm. The novelty of our submission is the heuristic used to initialize newly encountered decision nodes. We apply an iterative symbolic backward planning approach based on the determinized task. Similarly to the SPUDD approach and recent work in symbolic planning with state-dependent action costs, we encode costs and reachability of states in a single decision diagram. During initialization, these diagrams are then used to query a state for its estimated expected reward. One benefit of this heuristic is that we can optionally interweave the standard heuristic of PROST, the IDS heuristic.
David Speck, Florian Geißer and Robert Mattmüller.
SYMPLE: Symbolic Planning based on EVMDDs.
In The 9th International Planning Competition (IPC 2018), pp. 82-85. 2018.
(Show abstract) (Hide abstract) (PDF)

SYMPLE is a classical planner which performs bidirectional symbolic search. Symbolic search has proven to be a useful approach to optimal classical planning and is usually based on Binary Decision Diagrams (BDDs). Our approach is based on an alternative data structure called Edge-valued Multi-valued Decision Diagrams (EVMDDs), which have some structural advantages over BDDs.
Robert Mattmüller, Florian Geißer, Benedict Wright and Bernhard Nebel.
On the Relationship Between State-Dependent Action Costs and Conditional Effects in Planning.
In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI 2018). 2018.
(Show abstract) (Hide abstract) (PDF)

When planning for tasks that feature both state-dependent action costs and conditional effects using relaxation heuristics, the following problem appears: handling costs and effects separately leads to worse-than-necessary heuristic values, since we may get the more useful effect at the lower cost by choosing different values of a relaxed variable when determining relaxed costs and relaxed active effects.

In this paper, we show how this issue can be avoided by representing state-dependent costs and conditional effects uniformly, both as edge-valued multi-valued decision diagrams (EVMDDs) over different sets of edge values, and then working with their product diagram. We develop a theory of EVMDDs that is general enough to encompass state-dependent action costs, conditional effects, and even their combination.

We define relaxed effect semantics in the presence of state-dependent action costs and conditional effects, and describe how this semantics can be efficiently computed using product EVMDDs. This will form the foundation for informative relaxation heuristics in the setting with state-dependent costs and conditional effects combined.

2017

Robert Mattmüller, Florian Geißer, Benedict Wright and Bernhard Nebel.
On the Relationship Between State-Dependent Action Costs and Conditional Effects in Planning.
In Proceedings of the 9th Workshop on Heuristics and Search for Domain-Independent Planning (HSDIP 2017). 2017.
Superseded by the AAAI 2018 paper by the same name.
(Show abstract) (Hide abstract) (PDF)

When planning for tasks that feature both state-dependent action costs and conditional effects using relaxation heuristics, the following problem appears: handling costs and effects separately leads to worse-than-necessary heuristic values, since we may get the more useful effect at the lower cost by choosing different values of a relaxed variable when determining relaxed costs and relaxed active effects.

In this paper, we show how this issue can be avoided by representing state-dependent costs and conditional effects uniformly, both as edge-valued multi-valued decision diagrams (EVMDDs) over different sets of edge values, and then working with their product diagram. We develop a theory of EVMDDs that is general enough to encompass state-dependent action costs, conditional effects, and even their combination.

We define relaxed effect semantics in the presence of state-dependent action costs and conditional effects, and describe how this semantics can be efficiently computed using product EVMDDs. This will form the foundation for informative relaxation heuristics in the setting with state-dependent costs and conditional effects combined.

2016

Dali Sun, Florian Geißer and Bernhard Nebel.
Towards Effective Localization in Dynamic Environments.
In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2016). 2016.
(Show abstract) (Hide abstract) (PDF)

Localization in dynamic environments is still a challenging problem in robotics – especially if rapid and large changes occur irregularly. Inspired by SLAM algorithms, our Bayesian approach to this so-called dynamic localization problem divides it into a localization problem and a mapping problem, respectively. To tackle the localization problem we use a particle filter, coupled with a distance filter and a scan matching method, which achieves a more robust localization against dynamic obstacles. For the mapping problem we use an extended sensor model which results in an effective and precise map update effect. We compare our approach against other localization methods and evaluate the impact the map update effect has on the localization in dynamic environments.
Thomas Keller, Florian Pommerening, Jendrik Seipp, Florian Geißer and Robert Mattmüller.
State-dependent Cost Partitionings for Cartesian Abstractions in Classical Planning (Extended Abstract).
In Proceedings of the 39th German Conference on Artificial Intelligence (KI 2016). 2016.
(Show abstract) (Hide abstract) (PDF)

Abstraction heuristics are a popular method to guide optimal search algorithms in classical planning. Cost partitionings allow to sum heuristic estimates admissibly by partitioning action costs among the abstractions. 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 state-dependent cost partitionings with a state-dependent variant of the recently proposed saturated cost partitioning, and show that it can sometimes improve not only over its state-independent counterpart, but even over the optimal state-independent cost partitioning.
Thomas Keller, Florian Pommerening, Jendrik Seipp, Florian Geißer and Robert Mattmüller.
State-dependent Cost Partitionings for Cartesian Abstractions in Classical Planning:Full Proofs.
Technical Report CS-2016-002, University of Basel, 2016.
(Show abstract) (Hide abstract) (PDF)

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. This technical report contains the full proofs for Theorem 1, Theorem 3 and Lemma 1.
Thomas Keller, Florian Pommerening, Jendrik Seipp, Florian Geißer and Robert Mattmüller.
State-dependent Cost Partitionings for Cartesian Abstractions in Classical Planning.
In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016). 2016.
(Show abstract) (Hide abstract) (PDF)

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.
Florian Geißer, Thomas Keller and Robert Mattmüller.
Abstractions for Planning with State-Dependent Action Costs.
In Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS 2016). 2016.
(Show abstract) (Hide abstract) (PDF)

Extending the classical planning formalism with state-dependent action costs (SDAC) allows an up to exponentially more compact task encoding. Recent work proposed to use edge-valued multi-valued decision diagrams (EVMDDs) to represent cost functions, which allows to automatically detect and exhibit structure in cost functions and to make heuristic estimators accurately reflect SDAC. However, so far only the inadmissible additive heuristic has been considered in this context. In this paper, we define informative admissible abstraction heuristics which enable optimal planning with SDAC. We discuss how abstract cost values can be extracted from EVMDDs that represent concrete cost functions without adjusting them to the selected abstraction. Our theoretical analysis shows that this is efficiently possible for abstractions that are Cartesian or coarser. We adapt the counterexample-guided abstraction refinement approach to derive such abstractions. An empirical evaluation of the resulting heuristic shows that highly accurate values can be computed quickly.

2015

Florian Geißer, Thomas Keller and Robert Mattmüller.
Delete Relaxations for Planning with State-Dependent Action Costs.
In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015). 2015.
(Show abstract) (Hide abstract) (PDF) (BIB)

Most work in planning focuses on tasks with state-independent 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 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 the generalized additive heuristic 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.
Florian Geißer, Thomas Keller and Robert Mattmüller.
Delete Relaxations for Planning with State-Dependent Action Costs.
In Proceedings of the 8th Annual Symposium on Combinatorial Search (SoCS 2015). 2015.
Extended abstract of the IJCAI 2015 paper by the same name.
(Show abstract) (Hide abstract) (PDF) (BIB)

Supporting state-dependent action costs in planning admits a more compact representation of many tasks. We generalize the additive heuristic and compute it by embedding decision-diagram representations of action cost functions into the RPG. We give a theoretical evaluation and present an implementation of the generalized additive heuristic. This allows us to handle even the hardest instances of the combinatorial Academic Advising domain from the IPPC 2014.
Thomas Keller and Florian Geißer.
Better Be Lucky Than Good: Exceeding Expectations in MDP Evaluation.
In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015). AAAI Press 2015.
Erratum: On page 7, we mention that the results at IPPC would have differed by "-0.09", "+0.04" and "+0.05", which should read "-0.009", "+0.004" and "+0.005" instead.
(Show abstract) (Hide abstract) (PDF)

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.

2014

Florian Geißer, Thomas Keller and Robert Mattmüller.
Past, Present, and Future: An Optimal Online Algorithm for Single-Player GDL-II Games.
In Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014), pp. 357-362. 2014.
(Show abstract) (Hide abstract) (PDF) (BIB)

In General Game Playing, a player receives the rules of an unknown game and attempts to maximize his expected reward. Since 2011, the GDL-II rule language extension allows the formulation of nondeterministic and partially observable games. In this paper, we present an algorithm for such games, with a focus on the single-player case. Conceptually, at each stage, the proposed Norns algorithm distinguishes between the past, present and future steps of the game. More specifically, a belief state tree is used to simulate a potential past that leads to a present that is consistent with received observations. Unlike other related methods, our method is asymptotically optimal. Moreover, augmenting the belief state tree with iteratively improved probabilities speeds up the process over time significantly. As this allows a true picture of the present, we additionally present an optimal version of the well-known UCT algorithm for partially observable single-player games. Instead of performing hindsight optimization on a simplified, fully observable tree, the true future is simulated on an action-observation tree that takes partial observability into account. The expected reward estimates of applicable actions converge towards the true expected rewards even for moves that are only used to gather information. We prove that our algorithm is asymptotically optimal for single-player games and POMDPs and support our claim with an empirical evaluation.