Extending Markov Automata with State and Action Rewards

Dennis Guck, Mark Timmer, Stefan Blom

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This presentation introduces the Markov Reward Automaton (MRA), an extension of the Markov automaton that allows the modelling of systems incorporating rewards in addition to nondeterminism, discrete probabilistic choice and continuous stochastic timing. Our models support both rewards that are acquired instantaneously when taking certain transitions (action rewards) and rewards that are based on the duration that certain conditions hold (state rewards). In addition to introducing the MRA model, we extend the process-algebraic language MAPA to easily specify MRAs. Also, we provide algorithms for computing the expected reward until reaching one of a certain set of goal states, as well as the long-run average reward. We extended the MAMA tool chain (consisting of the tools SCOOP and IMCA) to implement the reward extension of MAPA and these algorithms.
LanguageUndefined
Title of host publicationProceedings of the 12th Workshop on Quantitative Aspects of Programming Languages and Systems (QAPL 2014)
EditorsN. Bertrand, L. Bortolussi
Place of PublicationRennes
PublisherINRIA
Pages-
Number of pages4
ISBN (Print)not assigned
StatePublished - Apr 2014

Keywords

  • EWI-24693
  • IR-91069
  • Expected reward
  • METIS-304085
  • Rewards
  • Process Algebra
  • Long-run average
  • Markov Automata

Cite this

Guck, D., Timmer, M., & Blom, S. (2014). Extending Markov Automata with State and Action Rewards. In N. Bertrand, & L. Bortolussi (Eds.), Proceedings of the 12th Workshop on Quantitative Aspects of Programming Languages and Systems (QAPL 2014) (pp. -). Rennes: INRIA.
Guck, Dennis ; Timmer, Mark ; Blom, Stefan. / Extending Markov Automata with State and Action Rewards. Proceedings of the 12th Workshop on Quantitative Aspects of Programming Languages and Systems (QAPL 2014). editor / N. Bertrand ; L. Bortolussi. Rennes : INRIA, 2014. pp. -
@inproceedings{fa4e6e9813c64d3a946b30dc78850b49,
title = "Extending Markov Automata with State and Action Rewards",
abstract = "This presentation introduces the Markov Reward Automaton (MRA), an extension of the Markov automaton that allows the modelling of systems incorporating rewards in addition to nondeterminism, discrete probabilistic choice and continuous stochastic timing. Our models support both rewards that are acquired instantaneously when taking certain transitions (action rewards) and rewards that are based on the duration that certain conditions hold (state rewards). In addition to introducing the MRA model, we extend the process-algebraic language MAPA to easily specify MRAs. Also, we provide algorithms for computing the expected reward until reaching one of a certain set of goal states, as well as the long-run average reward. We extended the MAMA tool chain (consisting of the tools SCOOP and IMCA) to implement the reward extension of MAPA and these algorithms.",
keywords = "EWI-24693, IR-91069, Expected reward, METIS-304085, Rewards, Process Algebra, Long-run average, Markov Automata",
author = "Dennis Guck and Mark Timmer and Stefan Blom",
year = "2014",
month = "4",
language = "Undefined",
isbn = "not assigned",
pages = "--",
editor = "N. Bertrand and L. Bortolussi",
booktitle = "Proceedings of the 12th Workshop on Quantitative Aspects of Programming Languages and Systems (QAPL 2014)",
publisher = "INRIA",

}

Guck, D, Timmer, M & Blom, S 2014, Extending Markov Automata with State and Action Rewards. in N Bertrand & L Bortolussi (eds), Proceedings of the 12th Workshop on Quantitative Aspects of Programming Languages and Systems (QAPL 2014). INRIA, Rennes, pp. -.

Extending Markov Automata with State and Action Rewards. / Guck, Dennis; Timmer, Mark; Blom, Stefan.

Proceedings of the 12th Workshop on Quantitative Aspects of Programming Languages and Systems (QAPL 2014). ed. / N. Bertrand; L. Bortolussi. Rennes : INRIA, 2014. p. -.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Extending Markov Automata with State and Action Rewards

AU - Guck,Dennis

AU - Timmer,Mark

AU - Blom,Stefan

PY - 2014/4

Y1 - 2014/4

N2 - This presentation introduces the Markov Reward Automaton (MRA), an extension of the Markov automaton that allows the modelling of systems incorporating rewards in addition to nondeterminism, discrete probabilistic choice and continuous stochastic timing. Our models support both rewards that are acquired instantaneously when taking certain transitions (action rewards) and rewards that are based on the duration that certain conditions hold (state rewards). In addition to introducing the MRA model, we extend the process-algebraic language MAPA to easily specify MRAs. Also, we provide algorithms for computing the expected reward until reaching one of a certain set of goal states, as well as the long-run average reward. We extended the MAMA tool chain (consisting of the tools SCOOP and IMCA) to implement the reward extension of MAPA and these algorithms.

AB - This presentation introduces the Markov Reward Automaton (MRA), an extension of the Markov automaton that allows the modelling of systems incorporating rewards in addition to nondeterminism, discrete probabilistic choice and continuous stochastic timing. Our models support both rewards that are acquired instantaneously when taking certain transitions (action rewards) and rewards that are based on the duration that certain conditions hold (state rewards). In addition to introducing the MRA model, we extend the process-algebraic language MAPA to easily specify MRAs. Also, we provide algorithms for computing the expected reward until reaching one of a certain set of goal states, as well as the long-run average reward. We extended the MAMA tool chain (consisting of the tools SCOOP and IMCA) to implement the reward extension of MAPA and these algorithms.

KW - EWI-24693

KW - IR-91069

KW - Expected reward

KW - METIS-304085

KW - Rewards

KW - Process Algebra

KW - Long-run average

KW - Markov Automata

M3 - Conference contribution

SN - not assigned

SP - -

BT - Proceedings of the 12th Workshop on Quantitative Aspects of Programming Languages and Systems (QAPL 2014)

PB - INRIA

CY - Rennes

ER -

Guck D, Timmer M, Blom S. Extending Markov Automata with State and Action Rewards. In Bertrand N, Bortolussi L, editors, Proceedings of the 12th Workshop on Quantitative Aspects of Programming Languages and Systems (QAPL 2014). Rennes: INRIA. 2014. p. -.