Ralf Wimmer
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Ralf Wimmer has a total of 65 co-authors. Here are the top co-authors by number of shared publications:
Bernd Becker
Albert-Ludwigs-Universität Freiburg
29 shared publicationsHolger Hermanns
Chair for Dependable Systems and Software, Saarland University, Saarbrücken, Germany
10 shared publications- Joost-Pieter Katoen
RWTH Aachen University
9 shared publications Christoph Scholl
8 shared publications- Erika Ábrahám
RWTH Aachen University Aachen Germany
8 shared publications - Bernd Becker
Albert-Ludwigs-Universität Freiburg, Freiburg, Germany
7 shared publications
Latest Publications
- 28 March 2022
- Published by Elsevier in Theoretical Computer Science
- Vol. 925, 1-24
Solving dependency quantified Boolean formulas using quantifier localization
- 28 March 2022
- Published by Elsevier in Theoretical Computer Science
- Vol. 925, 1-24
Solving dependency quantified Boolean formulas using quantifier localization
- 24 April 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 66 (3) , 1040-1054
Strategy Synthesis for POMDPs in Robot Planning via Game-Based Abstractions
We study synthesis problems with constraints in partially observable Markov decision processes (POMDPs), where the objective is to compute a strategy for an agent that is guaranteed to satisfy certain safety and performance specifications. Verification and strategy synthesis for POMDPs are, however, computationally intractable in general. We alleviate this difficulty by focusing on planning applications and exploiting typical structural properties of such scenarios; for instance, we assume that the agent has the ability to observe its own position inside an environment. We propose an abstraction refinement framework which turns such a POMDP model into a (fully observable) probabilistic two-player game (PG). For the obtained PGs, efficient verification and synthesis tools allow to determine strategies with optimal safety and performance measures, which approximate optimal schedulers on the POMDP. If the approximation is too coarse to satisfy the given specifications, an refinement scheme improves the computed strategies. As a running example, we use planning problems where an agent moves inside an environment with randomly moving obstacles and restricted observability. We demonstrate that the proposed method advances the state of the art by solving problems several orders-of-magnitude larger than those that can be handled by existing POMDP solvers. Furthermore, this method gives guarantees on safety constraints, which is not supported by the majority of the existing solvers
- 24 April 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 66 (3) , 1040-1054
Strategy Synthesis for POMDPs in Robot Planning via Game-Based Abstractions
We study synthesis problems with constraints in partially observable Markov decision processes (POMDPs), where the objective is to compute a strategy for an agent that is guaranteed to satisfy certain safety and performance specifications. Verification and strategy synthesis for POMDPs are, however, computationally intractable in general. We alleviate this difficulty by focusing on planning applications and exploiting typical structural properties of such scenarios; for instance, we assume that the agent has the ability to observe its own position inside an environment. We propose an abstraction refinement framework which turns such a POMDP model into a (fully observable) probabilistic two-player game (PG). For the obtained PGs, efficient verification and synthesis tools allow to determine strategies with optimal safety and performance measures, which approximate optimal schedulers on the POMDP. If the approximation is too coarse to satisfy the given specifications, an refinement scheme improves the computed strategies. As a running example, we use planning problems where an agent moves inside an environment with randomly moving obstacles and restricted observability. We demonstrate that the proposed method advances the state of the art by solving problems several orders-of-magnitude larger than those that can be handled by existing POMDP solvers. Furthermore, this method gives guarantees on safety constraints, which is not supported by the majority of the existing solvers
- Open Access
- 1 September 2019
- Published by SAGE Publications in Journal on Satisfiability, Boolean Modeling and Computation
- Vol. 11 (1) , 3-52
The (D)QBF Preprocessor HQSpre – Underlying Theory and Its Implementation1
Preprocessing turned out to be an essential step for SAT, QBF, and DQBF solvers to reduce/modify the number of variables and clauses of the formula, before the formula is passed to the actual solving algorithm. These preprocessing techniques often re
- 1 September 2019
- Published by SAGE Publications in Journal on Satisfiability, Boolean Modeling and Computation
- Vol. 11 (1) , 3-52
Open AccessThe (D)QBF Preprocessor HQSpre – Underlying Theory and Its Implementation1
Preprocessing turned out to be an essential step for SAT, QBF, and DQBF solvers to reduce/modify the number of variables and clauses of the formula, before the formula is passed to the actual solving algorithm. These preprocessing techniques often re
- 16 November 2017
- Published by Springer Nature
- p. 151-168
Analysis of Incomplete Circuits Using Dependency Quantified Boolean Formulas
- 16 November 2017
- Published by Springer Nature
- p. 151-168
Analysis of Incomplete Circuits Using Dependency Quantified Boolean Formulas
- Open Access
- 1 July 2017
- Published by Association for Computing Machinery (ACM) in Formal Aspects of Computing
- Vol. 29 (4) , 629-649
Cost vs. time in stochastic games and Markov automata
Costs and rewards are important tools for analysing quantitative aspects of models like energy consumption and costs of maintenance and repair. Under the assumption of transient costs, this paper considers the computation of expected cost-bounded rewards and cost-bounded reachability for Markov automata and Markov games. We provide a fixed point characterization of this class of properties under early schedulers. Additionally, we give a transformation to expected time-bounded rewards and time-bounded reachability, which can be computed by available algorithms. We prove the correctness of the transformation and show its effectiveness on a number of Markov automata case studies.
- 1 July 2017
- Published by Association for Computing Machinery (ACM) in Formal Aspects of Computing
- Vol. 29 (4) , 629-649
Open AccessCost vs. time in stochastic games and Markov automata
Costs and rewards are important tools for analysing quantitative aspects of models like energy consumption and costs of maintenance and repair. Under the assumption of transient costs, this paper considers the computation of expected cost-bounded rewards and cost-bounded reachability for Markov automata and Markov games. We provide a fixed point characterization of this class of properties under early schedulers. Additionally, we give a transformation to expected time-bounded rewards and time-bounded reachability, which can be computed by available algorithms. We prove the correctness of the transformation and show its effectiveness on a number of Markov automata case studies.
- 31 March 2017
- Published by Springer Nature
- p. 373-390
HQSpre – An Effective Preprocessor for QBF and DQBF
- 31 March 2017
- Published by Springer Nature
- p. 373-390
HQSpre – An Effective Preprocessor for QBF and DQBF