Author name cluster

Florian Geißer

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.

16 papers

2 author rows

ICAPS Conference 2022 Conference Paper

Admissible Heuristics for Multi-Objective Planning

Florian Geißer
Patrik Haslum
Sylvie Thiébaux
Felipe W. Trevizan

Planning problems of practical relevance commonly include multiple objectives that are difficult to weight a priori. Several heuristic search algorithms computing the Pareto front of non-dominated solutions have been proposed to handle these multi-objective (MO) planning problems. However, the design of informative admissible heuristics to guide these algorithms has not received the same level of attention. The standard practice is to use the so-called ideal point combination, which applies a single-objective heuristic to each objective independently, without capturing any of the trade-offs between them. This paper fills this gap: we extend several classes of classical planning heuristics to the multi-objective case, in such a way as to reflect the tradeoffs underlying the various objectives. We find that MO abstraction heuristics achieve overall the best performance, but that not every MO generalisation pays off.

Details

ICAPS Conference 2022 Conference Paper

Neural Network Heuristic Functions for Classical Planning: Bootstrapping and Comparison to Other Methods

Patrick Ferber
Florian Geißer
Felipe W. Trevizan
Malte Helmert
Jörg Hoffmann 0001

How can we train neural network (NN) heuristic functions for classical planning, using only states as the NN input? Prior work addressed this question by (a) per-instance imitation learning and/or (b) per-domain learning. The former limits the approach to instances small enough for training data generation, the latter to domains where the necessary knowledge generalizes across instances. Here we explore three methods for (a) that make training data generation scalable through bootstrapping and approximate value iteration. In particular, we introduce a new bootstrapping variant that estimates search effort instead of goal distance, which as we show converges to the perfect heuristic under idealized circumstances. We empirically compare these methods to (a) and (b), aligning three different NN heuristic function learning architectures for cross-comparison in an experiment of unprecedented breadth in this context. Key lessons are that our methods and imitation learning are highly complementary; that per-instance learning often yields stronger heuristics than per-domain learning; and the LAMA planner is still dominant but our methods outperform it in one benchmark domain.

Details

UAI Conference 2022 Conference Paper

SymNet 2. 0: Effectively handling Non-Fluents and Actions in Generalized Neural Policies for RDDL Relational MDPs

Vishal Sharma
Daman Arora
Florian Geißer
Mausam
Parag Singla

Relational MDPs (RMDPs) compactly represent an infinite set of MDPs with an unbounded number of objects. Solving an RMDP requires a generalized policy that applies to all instances of a domain. Recently, Garg et al. proposed SymNet for this task– it constructs a graph neural network that shares parameters across all instances in a domain, thus making it applicable to any instance in a zero-shot manner. Our analysis of SymNet reveals that it performs no better than random on 1/4th of planning competition domains. The key reasons are its design choices: it misses important information during graph construction, leading to (1) poor generalizability, and (2) potential non-identifiability of different actions. In response, our solution, SymNet2. 0, substantially augments SymNet’s graph construction approach by introducing additional nodes and edges which allow a better transfer of important information about a domain. It also improves SymNet’s action decoders with relevant information from objects to make different actions identifiable during scoring. Extensive experiments on twelve competition domains, where we use imitation learning over data generated from the PROST planner, demonstrate that SymNet2. 0 performs vastly better than SymNet. Interestingly, even though SymNet2. 0 is trained over data from PROST, it outperforms the planner on several test instances due to former’s ability to scale to large instances in a zero-shot manner.

Details

PRL Workshop 2021 Workshop Paper

Extending Graph Neural Networks for Generalized Stochastic Planning

Ziqi Zhang
Florian Geißer

Probabilistic planning problems are often formulated in terms of a domain class that describes the general problem structure, and in terms of an instantiation of the domain, which yields a particular MDP. Most algorithms in probabilistic planning focus on computing policies for a single MDP. A relational policy represents a solution to any MDP induced from the same domain class. We present a graph neural network architecture that is based on a representation of the relation between types of a given domain and which allows us to generalize from small instances to large instances of the same domain class. Unlike other work, we do not impose restrictions on the structure of the domain. We conduct a preliminary study which compares the relational policies obtained from a network trained on small instances against a policy computed by a state-of-the-art domain-independent planner. The evaluation shows that the network generalizes well across instances of a domain, and is even able to outperform the instance-dependent policy in some of the benchmarks.

PDF Details

PRL Workshop 2021 Workshop Paper

Neural Network Heuristics for Classical Planning: Reinforcement Learning and Comparison to Other Methods

Patrick Ferber
Florian Geißer
Felipe Trevizan
Malte Helmert
Joerg Hoffmann

How can we train neural network (NN) heuristic functions for classical planning, using only states as the NN input? Prior work addressed this question by (a) supervised learning and/or (b) per-domain learning generalizing over problem instances. The former limits the approach to instances small enough for training data generation, the latter to domains and instance distributions where the necessary knowledge generalizes across instances. Clearly, reinforcement learning (RL) on large instances can potentially avoid both difficulties. We explore this here in terms of three methods drawing on previous ideas relating to bootstrapping and approximate value iteration, including a new bootstrapping variant that estimates search effort instead of goal distance. We empirically compare these methods to (a) and (b), aligning three different NN heuristic function learning architectures for crosscomparison in an experiment of unprecedented breadth in this context. Key lessons from this experiment are that our methods and supervised learning are highly complementary; that per-instance learning often yields stronger heuristics than perdomain learning; and that LAMA is still dominant but is outperformed by our methods in one benchmark domain.

PDF Details

ICAPS Conference 2020 Conference Paper

Optimal and Heuristic Approaches for Constrained Flight Planning under Weather Uncertainty

Florian Geißer
Guillaume Povéda
Felipe W. Trevizan
Manon Bondouy
Florent Teichteil-Königsbuch
Sylvie Thiébaux

Aircraft flight planning is impacted by weather uncertainties. Existing approaches to flight planning are either deterministic and load additional fuel to account for uncertainty, or probabilistic but have to plan in 4D space. If constraints are imposed on the flight plan these methods provide no formal guarantees that the constraints are actually satisfied. We investigate constrained flight planning under weather uncertainty on discrete airways graphs and model this problem as a Constrained Stochastic Shortest Path (C-SSP) problem. Transitions are generated on-the-fly by the underlying aircraft performance model. As this prevents us from using off-the-shelf C-SSP solvers, we generalise column-generation methods stemming from constrained deterministic path planning to the probabilistic case. This results in a novel method which is complete but computationally expensive. We therefore also discuss deterministic and heuristic approaches which average over weather uncertainty and handle constraints by scalarising a multi-objective cost function. We evaluate and compare these approaches on real flight routes subject to real weather forecast data and a realistic aircraft performance model.

Details

SoCS Conference 2020 Conference Paper

Trial-Based Heuristic Tree Search for MDPs with Factored Action Spaces

Florian Geißer
David Speck 0001
Thomas Keller 0001

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 generalization 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.

Details

ICAPS Conference 2020 Conference Paper

When Perfect Is Not Good Enough: On the Search Behaviour of Symbolic Heuristic Search

David Speck 0001
Florian Geißer
Robert Mattmüller

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.

Details

ICAPS Conference 2019 Conference Paper

Symbolic Planning with Axioms

David Speck 0001
Florian Geißer
Robert Mattmüller
Álvaro Torralba

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 costoptimal classical planning with axioms.

Details

AAAI Conference 2018 Conference Paper

On the Relationship Between State-Dependent Action Costs and Conditional Effects in Planning

Robert Mattmüller
Florian Geißer
Benedict Wright
Bernhard Nebel

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 deﬁne relaxed effect semantics in the presence of statedependent action costs and conditional effects, and describe how this semantics can be efﬁciently computed using product EVMDDs. This will form the foundation for informative relaxation heuristics in the setting with state-dependent costs and conditional effects combined.

PDF Details

ICAPS Conference 2018 Conference Paper

Symbolic Planning with Edge-Valued Multi-Valued Decision Diagrams

David Speck 0001
Florian Geißer
Robert Mattmüller

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.

Details

ICAPS Conference 2016 Conference Paper

Abstractions for Planning with State-Dependent Action Costs

Florian Geißer
Thomas Keller 0001
Robert Mattmüller

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.

Details

IROS Conference 2016 Conference Paper

Towards effective localization in dynamic environments

Dali Sun
Florian Geißer
Bernhard Nebel

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.

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

SoCS Conference 2015 Conference Paper

Delete Relaxations for Planning with State-Dependent Action Costs

Florian Geißer
Thomas Keller 0001
Robert Mattmüller

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.

Details

ECAI Conference 2014 Conference Paper

Past, Present, and Future: An Optimal Online Algorithm for Single-Player GDL-II Games

Florian Geißer
Thomas Keller 0001
Robert Mattmüller

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.

Details