Reachability in MDPs: Difference between revisions
(Created page with "{{DISPLAYTITLE:Reachability in MDPs (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a Markov Decision Process (MDP), and the objective is reachability: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that visits a vertex in $T$ at least once (i.e. you want to reach some vertex in $T$)....") |
No edit summary |
||
| Line 14: | Line 14: | ||
== Parameters == | == Parameters == | ||
n: number of vertices | |||
m: number of edges | m: number of edges | ||
MEC: O(\min(n^2, m^{1.5})) | |||
MEC: O(\min(n^2, m^{1.5})) | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Currently no algorithms in our database for the given problem. | Currently no algorithms in our database for the given problem. | ||
Revision as of 12:04, 15 February 2023
Description
Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective.
In this case, the model is a Markov Decision Process (MDP), and the objective is reachability: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that visits a vertex in $T$ at least once (i.e. you want to reach some vertex in $T$).
Related Problems
Subproblem: Disjunctive Reachability Queries in MDPs, Conjunctive Reachability Queries in MDPs
Related: Conjunctive Reachability Queries in MDPs, Safety in MDPs, Disjunctive Safety Queries in MDPs, Conjunctive Safety Queries in MDPs, Safety in Graphs, Disjunctive Queries of Safety in Graphs, Disjunctive coBüchi Objectives, Generalized Büchi Games
Parameters
n: number of vertices
m: number of edges
MEC: O(\min(n^2, m^{1.5}))
Table of Algorithms
Currently no algorithms in our database for the given problem.