NDLI: Controller Synthesis for Reward Collecting Markov Processes in Continuous Space

Please wait, while we are loading the content...

Forward Inner-Approximated Reachability of Non-Linear Continuous Systems

Forward Stochastic Reachability Analysis for Uncontrolled Linear Systems using Fourier Transforms

Optimal Data Rate for State Estimation of Switched Nonlinear Systems

Robust Abstractions for Control Synthesis: Completeness via Robustness for Linear-Time Properties

Convex and Combinatorial Optimization for Dynamic Robots in the Real World

Coupling Policy Iterations with Piecewise Quadratic Lyapunov Functions

Dynamic Periodic Event-Triggered Control for Linear Systems

A Small Gain Theorem for Parametric Assume-Guarantee Contracts

Piecewise - Differentiable Trajectory Outcomes in Mechanical Systems Subject to Unilateral Constraints

On the Polytope Escape Problem for Continuous Linear Dynamical Systems

Controller Synthesis for Reward Collecting Markov Processes in Continuous Space

Path-Complete Graphs and Common Lyapunov Functions

Formal Synthesis of Stabilizing Controllers for Switched Systems

Robust Model Checking of Timed Automata under Clock Drifts

On a Class of Maximal Invariance Inducing Control Strategies for Large Collections of Switched Systems

Relaxed Decidability and the Robust Semantics of Metric Temporal Logic

Structural Analysis of Multi-Mode DAE Systems

SMC: Satisfiability Modulo Convex Optimization

Reachability Computation for Switching Diffusions: Finite Abstractions with Certifiable and Tuneable Precision

Invariance Feedback Entropy of Nondeterministic Control Systems

Convex Interpolation Control with Formal Guarantees for Disturbed and Constrained Nonlinear Systems

Safety Verification of Nonlinear Hybrid Systems Based on Invariant Clusters

Sound and Automated Synthesis of Digital Stabilizing Controllers for Continuous Plants

Sampling-based Approximate Optimal Control Under Temporal Logic Constraints

Bipedal Robotic Running with DURUS-2D: Bridging the Gap between Theory and Experiment

Sapo: Reachability Computation and Parameter Synthesis of Polynomial Dynamical Systems

Statistical Verification of the Toyota Powertrain Control Verification Benchmark

Scheduling of Embedded Controllers Under Timing Contracts

HyLAA: A Tool for Computing Simulation-Equivalent Reachability for Linear Systems

Abnormal Data Classification Using Time-Frequency Temporal Logic

Controller Synthesis for Reward Collecting Markov Processes in Continuous Space

Content Provider	ACM Digital Library
Author	Majumdar, Rupak Esmaeil Zadeh Soudjani, Sadegh
Abstract	We propose and analyze a generic mathematical model for optimizing rewards in continuous-space, dynamic environments, called Reward Collecting Markov Processes. Our model is motivated by request-serving applications in robotics, where the objective is to control a dynamical system to respond to stochastically generated environment requests, while minimizing wait times. Our model departs from usual discounted reward Markov decision processes in that the reward function is not determined by the current state and action. Instead, a background process generates rewards whose values depend on the number of steps between generation and collection. For example, a reward is declared whenever there is a new request for a robot and the robot gets higher reward the sooner it is able to serve the request. A policy in this setting is a sequence of control actions which determines a (random) trajectory over the continuous state space. The reward achieved by the trajectory is the cumulative sum of all rewards obtained along the way in the finite horizon case and the long run average of all rewards in the infinite horizon case. We study both the finite horizon and infinite horizon problems for maximizing the expected (respectively, the long run average expected) collected reward. We characterize these problems as solutions to dynamic programs over an augmented hybrid space, which gives history-dependent optimal policies. Second, we provide a computational method for these problems which abstracts the continuous-space problem into a discrete-space collecting reward Markov decision process. Under assumptions of Lipschitz continuity of the Markov process and uniform bounds on the discounting, we show that we can bound the error in computing optimal solutions on the finite-state approximation. Finally, we provide a fixed point characterization of the optimal expected collected reward in the infinite case, and show how the fixed point can be obtained by value iteration.
Starting Page	45
Ending Page	54
Page Count	10
File Format	PDF
ISBN	9781450345903
DOI	10.1145/3049797.3049827
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-04-13
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Continuous-space stochastic systems Formal controller synthesis Reward collecting markov processes
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Viewpoint Development of Stochastic Hybrid Systems

Formal Synthesis of Control Policies for Continuous Time Markov Processes From Time-Bounded Temporal Logic Specifications

A new model of continuous-time Markov processes and impulse stochastic control

Stability analysis and controller synthesis for continuous-time linear stochastic systems

Formal Verification and Synthesis for Discrete-Time Stochastic Systems

Analysis of Nonprocessive Molecular Motor Transport Using Renewal Reward Theory

Adaptive and Sequential Gridding Procedures for the Abstraction and Verification of Stochastic Processes

Backward bisimulation in Markov chain model checking (2006)

Bias Optimality for Continuous-Time Controlled Markov Chains

Controller Synthesis for Reward Collecting Markov Processes in Continuous Space

Similar Documents

Viewpoint Development of Stochastic Hybrid Systems

Formal Synthesis of Control Policies for Continuous Time Markov Processes From Time-Bounded Temporal Logic Specifications

A new model of continuous-time Markov processes and impulse stochastic control

Stability analysis and controller synthesis for continuous-time linear stochastic systems

Formal Verification and Synthesis for Discrete-Time Stochastic Systems

Analysis of Nonprocessive Molecular Motor Transport Using Renewal Reward Theory

Adaptive and Sequential Gridding Procedures for the Abstraction and Verification of Stochastic Processes

Backward bisimulation in Markov chain model checking (2006)

Bias Optimality for Continuous-Time Controlled Markov Chains

Controller Synthesis for Reward Collecting Markov Processes in Continuous Space