Related Experiment Video
Updated: Dec 13, 2025
06:23
Preparation of DMMTAV and DMDTAV Using DMAV for Environmental Applications: Synthesis, Purification, and Confirmation
Published on: March 9, 2018
5.8K
Scenario-Based Verification of Uncertain MDPs
Murat Cubuktepe1, Nils Jansen2, Sebastian Junges3
1The University of Texas at Austin, Austin, USA.
Tools and Algorithms for the Construction and Analysis of Systems : 26Th International Conference, TACAS 2020, Held As Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020, Dublin, Ireland, April 25-30,
|August 6, 2020
Summary
This study addresses uncertainty in Markov decision processes (MDPs) by using scenario optimization to estimate the probability of satisfying specifications, even with unknown parameter distributions.
Area of Science:
- Artificial Intelligence
- Operations Research
- Control Theory
Background:
- Markov decision processes (MDPs) are widely used for decision-making under uncertainty.
- Computing probabilities for temporal logic specifications in MDPs with unknown parameters is generally undecidable.
- Existing methods struggle with unknown probability distributions and complex state spaces.
Purpose of the Study:
- To develop a method for computing the probability of satisfying temporal logic specifications in MDPs with uncertain parameters.
- To address the undecidability of this problem by employing scenario optimization techniques.
- To provide a computationally tractable approach for probabilistic verification of MDPs.
Main Methods:
- Utilizes scenario optimization based on a finite number of samples of uncertain parameters.
- Each sample induces a specific MDP, allowing for problem reformulation.
- Solves a finite-dimensional convex optimization problem to estimate the desired probability.
Main Results:
- The proposed method provides a high-confidence estimate of the probability of satisfying the specification.
- The number of samples required is independent of the number of states and random parameters.
- Experiments demonstrate that a few thousand samples yield high-quality confidence bounds.
Conclusions:
- Scenario optimization offers a viable approach to probabilistic verification of MDPs with unknown parameters.
- The method is computationally efficient and scales well with problem size.
- This work advances the ability to analyze complex systems with inherent uncertainties.
Related Concept Videos
01:16Statically Indeterminate Problem Solving
617
Statically indeterminate problems are those where statics alone can not determine the internal forces or reactions. Consider a structure comprising two cylindrical rods made of steel and brass. These rods are joined at point B and restrained by rigid supports at points A and C. Now, the reactions at points A and C and the deflection at point B are to be determined. This rod structure is classified as statically indeterminate as the structure has more supports than are necessary for maintaining...
617
01:10Propagation of Uncertainty from Systematic Error
1.2K
The atomic mass of an element varies due to the relative ratio of its isotopes. A sample's relative proportion of oxygen isotopes influences its average atomic mass. For instance, if we were to measure the atomic mass of oxygen from a sample, the mass would be a weighted average of the isotopic masses of oxygen in that sample. Since a single sample is not likely to perfectly reflect the true atomic mass of oxygen for all the molecules of oxygen on Earth, the mass we obtain from this...
1.2K
00:59Uncertainty: Overview
1.4K
In analytical chemistry, we often perform repetitive measurements to detect and minimize inaccuracies caused by both determinate and indeterminate errors. Despite the cares we take, the presence of random errors means that repeated measurements almost never have exactly the same magnitude. The collective difference between these measurements - observed values - and the estimated or expected value is called uncertainty. Uncertainty is conventionally written after the estimated or expected value.
1.4K
00:59Propagation of Uncertainty from Random Error
1.5K
An experiment often consists of more than a single step. In this case, measurements at each step give rise to uncertainty. Because the measurements occur in successive steps, the uncertainty in one step necessarily contributes to that in the subsequent step. As we perform statistical analysis on these types of experiments, we must learn to account for the propagation of uncertainty from one step to the next. The propagation of uncertainty depends on the type of arithmetic operation performed on...
1.5K
01:29Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
207
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
207
01:26Constraints and Statical Determinacy
882
In structural engineering, the equilibrium of a system is not only determined by its equations of equilibrium but also with the help of constraints. Constraints refer to restrictions on the motion of a system. The proper combinations of constraints can minimize the total number of constraints needed to maintain a system in mechanical equilibrium. When this happens, the system is said to be statically determinate. For such systems, the unknown reaction supports can be estimated using equilibrium...
882