Abstract
A continuous-time Markov decision process (CTMDP) is a generalization of a continuous-time Markov chain in which both probabilistic and nondeterministic choices co-exist. This paper presents an efficient algorithm to compute the maximum (or minimum) probability to reach a set of goal states within a given time bound in a uniform CTMDP, i.e., a CTMDP in which the delay time distribution per state visit is the same for all states. It furthermore proves that these probabilities coincide for (time-abstract) history-dependent and Markovian schedulers that resolve nondeterminism either deterministically or in a randomized way.
Original language | English |
---|---|
Pages (from-to) | 2-26 |
Number of pages | 25 |
Journal | Theoretical Computer Science |
Volume | 345 |
Issue number | 1 |
DOIs | |
Publication status | Published - 2005 |
Externally published | Yes |
Keywords
- EWI-1431
- METIS-225905
- IR-54792