1
$\begingroup$

I am kind of new to timed automaton domain. I am trying to understand in which way they are different to Markov Decision Process. First I know there objectives is to solve the non-determinism of a MDP. However, is there anything else? Are they still memoryless? I am not able to find any information about this topic.

$\endgroup$
1
$\begingroup$

The reason that you do not find any results is thta from a scientific point of view, the well-posed questions for PTAs and MDPs are quite different:

  • MDPs typically have a reward function assigned, while PTAs do not necessarily have to have them.
  • It is a bit imprecise to state that the "objectives is to solve the non-determinism of a MDP" -- it depends on what you want to do. PTAs are foremost models that you can analyse. Resolving the non-determinism means computing a policy, which makes sense if you have some kind of optimization criterion that you want to follow. This could be a temporal logic formula.
  • In MDPs, the classical question is to find a policy that maximizes the limsup average payoff or the discounted payoff. In the latter case, there exist optimal memoryless policies (which is the result that you refer to). In PTAs, asking the same question is kind-of odd as the number of states in PTAs is infinite and there is (by default) nothing to optimize. A state consists of a location and a valuation to the clocks. This is already the case for timed automata, from which PTAs inherit many of their properties (and hardness results).

  • The questions typically asked for PTAs are whether there exist policies that raise the probability of some temporal property holding along a trace over some given limit. A paper my Norman et al. (http://www.prismmodelchecker.org/papers/fmsd-ptas.pdf) contains details. They also define reward structures for PTAs, but the do not need to be concerned with discounted payoff optimization, like it is common in the MDP research case.

$\endgroup$
  • $\begingroup$ Thanks for your answer. So you say that there is by default nothing to optimize using PTAs? But you could still use a finite number of states on a PTA right? I mean, I could model a system using a PTA, and limit the number of states to the number of machines in my system, saying that a machine correspond to a state for example. Then I will have a finite number of states. I am interested on doing optimization on time metrics, thats why PTAs looked OK in my case. $\endgroup$ – Ecterion Jun 26 '18 at 14:58
  • $\begingroup$ @Ecterion Do you mean "States" or "Locations"? The only way to have a final number of states in a PTA is by not having any clocks. But then, you could also just use a non-timed automaton instead. You could do optimization in the sense that you try to find out what the minimal time duration $t$ is for which it is ensured that some specific state is reached at least once with probability >= 0.5 until $t$ time units have passed. $\endgroup$ – DCTLib Jun 26 '18 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.