4 Search Results for "Auer, Peter"

Exploring large-scale networks is a time consuming and expensive task which is usually operated in a complex and uncertain environment. A crucial aspect of network exploration is the development of suitable strategies that decide which nodes and edges to probe at each stage of the process. To model this process, we introduce the stochastic graph exploration problem. The input is an undirected graph G=(V,E) with a source vertex s, stochastic edge costs drawn from a distribution pi_e, e in E, and rewards on vertices of maximum value R. The goal is to find a set F of edges of total cost at most B such that the subgraph of G induced by F is connected, contains s, and maximizes the total reward. This problem generalizes the stochastic knapsack problem and other stochastic probing problems recently studied. Our focus is on the development of efficient nonadaptive strategies that are competitive against the optimal adaptive strategy. A major challenge is the fact that the problem has an Omega(n) adaptivity gap even on a tree of n vertices. This is in sharp contrast with O(1) adaptivity gap of the stochastic knapsack problem, which is a special case of our problem. We circumvent this negative result by showing that O(log nR) resource augmentation suffices to obtain O(1) approximation on trees and O(log nR) approximation on general graphs. To achieve this result, we reduce stochastic graph exploration to a memoryless process - the minesweeper problem - which assigns to every edge a probability that the process terminates when the edge is probed. For this problem, interesting in its own, we present an optimal polynomial time algorithm on trees and an O(log nR) approximation for general graphs. We study also the problem in which the maximum cost of an edge is a logarithmic fraction of the budget. We show that under this condition, there exist polynomial-time oblivious strategies that use 1+epsilon budget, whose adaptivity gaps on trees and general graphs are 1+epsilon and 8+epsilon, respectively. Finally, we provide additional results on the structure and the complexity of nonadaptive and adaptive strategies.

This Dagstuhl Seminar also stood as the 11th European Workshop on Reinforcement Learning (EWRL11). Reinforcement learning gains more and more attention each year, as can be seen at the various conferences (ECML, ICML, IJCAI, ...). EWRL, and in particular this Dagstuhl Seminar, aimed at gathering people interested in reinforcement learning from all around the globe. This unusual format for EWRL helped viewing the field and discussing topics differently.

In this paper, we present several aspects of the recent project PROREOP, in which a new prognosis system is developed for optimizing patient-specific preoperative surgical planning for the human skeletal system. We address verification and validation assessment in PROREOP with special emphasis on numerical accuracy and performance. To assess numerical accuracy, we propose to employ graded instruments, including accuracy tests and error analysis. The use of such instruments is exemplified for the process of accurate femur reconstruction. Moreover, we show how to verify the simulation results and take into account measurement uncertainties for a part of this process using tools and techniques developed in the project TellHIM&S.

Modern techniques for the design and analysis of control strategies for nonlinear dynamical systems are often based on the simulation of the open-loop as well as the closed-loop dynamical behavior of suitable mathematical models. In control engineering, continuous-time and discrete-time state-space representations are widely used which are given by sets of ordinary differential equations and difference equations, respectively. In addition to these representations, sets of differential algebraic equations are commonly used. Since we will focus on computational techniques which are applied for the design and mathematical verification of controllers for lumped parameter systems, i.e., systems which do not contain elements with distributed parameters, partial differential equations will not be considered in this talk. The prerequisite for the design and robustness analysis of each control system is the identification of mathematical models which describe the dynamics of the plant to be controlled as well as the available measurement devices with a sufficient accuracy. The model identification task comprises the derivation of physically motivated state equations, their parameterization based on measured data, as well as simplifications to apply specific approaches for controller design. In the design stage, both open-loop and closed-loop control strategies can be considered. Since dynamical system models are subject to uncertain parameters and uncertain initial conditions in most practical applications, detailed mathematical formulations of the desired dynamics of the controlled system are necessary. These specifications involve the definition of robustness with respect to the above-mentioned uncertainties. For linear system representations, robustness is commonly specified in terms of regions in the complex domain containing all admissible poles of the closed-loop transfer functions ($Gamma$-stability) or in terms of specifications of worst-case bounds for the frequency response ($mathcal{B}$-stability) [1]. However, these specifications do not allow for inclusion of bounds for the state variables which are often available in the time domain if controllers are designed for safety critical applications. Especially for nonlinear dynamical systems, pole assignment based on the linearization of nonlinear mathematical models generally leads to the necessity for the analysis of asymptotic stability of the resulting closed-loop dynamics. In this presentation, we will give an overview of the potential use of validated techniques for the analysis and design of controllers for nonlinear dynamical systems with uncertainties, where the systems under consideration will be subject to constraints for both state and control variables. As an application scenario the design of robust control strategies for a biological wastewater treatment process will be discussed. In the design and the verification process, constraints for both state and control variables which are given by guaranteed interval bounds in the time domain are taken into account. Suitable computational techniques are, for example, based on an extension of the validated initial value problem solver {sc ValEncIA-IVP} [2,6]. For that purpose, differential sensitivities of the trajectories of all state variables with respect to variations of the parameters of the mathematical system model as well as the adaptation of controller parameters are computed. This information can then be used for online identification and adaptation of parameters during the operation of a closed-loop controller as well as in offline design, verification, and optimization. Here, the interval arithmetic routines for sensitivity analysis allow to compute guaranteed differential sensitivity measures for system models with both nominal parameters and interval uncertainties. The presented interval arithmetic techniques are the basis for a general purpose tool for the analysis and the design of robust and optimal control strategies for uncertain dynamical systems. The presentation is concluded with an outlook on the formulation of control problems using sets of differential algebraic equations. Possibilities for the extension of {sc ValEncIA-IVP} to this type of system representation will be summarized. Relations between the presented interval arithmetic approach and methods for stabilizing control of nonlinear dynamical systems which make use of structural system properties such as differential flatness [3] and exact feedback linearization are highlighted [4,5]. In the latter case, input-output linearization as well as (in special cases) input-to-state linearization are of practical importance. References: [1] J. Ackermann, P. Blue, T. B"unte, L. G"uvenc, D. Kaesbauer, M. Kordt, M. Muhler, and D. Odenthal, {it{Robust Control: The Parameter Space Approach}}, Springer--Verlag, London, 2nd edition, 2002. [2] E. Auer, A. Rauh, E. P. Hofer, and W. Luther, {it{Validated Modeling of Mechanical Systems with {sc SmartMOBILE}: Improvement of Performance by {sc ValEncIA-IVP}}}, In Proceedings of Dagstuhl Seminar 06021: Reliable Implementation of Real Number Algorithms: Theory and Practice, Lecture Notes in Computer Science, Dagstuhl, Germany, 2006. In print. [3] M. Fliess, J. Lévine, P. Martin, and P. Rouchon, {it{Flatness and Defect of Nonlinear Systems: Introductory Theory and Examples}}, International Journal of Control, vol. 61, pp. 1327--1361, 1995. [4] H. K. Khalil, {it{Nonlinear Systems}}, Prentice-Hall, Upper Saddle River, New Jersey, 3rd edition, 2002. [5] H. J. Marquez, {it{Nonlinear Control Systems}}, John Wiley & Sons, Inc., New Jersey, 2003. [6] A. Rauh and E. Auer, {{www.valencia-ivp.com}}.