Precomputing reconfiguration strategies based on stochastic timed game automata

Abstract

Many modern software systems continuously reconfigure themselves to (self-)adapt to ever-changing environmental contexts. Selecting presumably best-fitting next configurations is, however, very challenging, depending on functional and non-functional criteria like real-time constraints as well as inherently uncertain future contexts which makes greedy one-step decision heuristics ineffective. In addition, the computational overhead caused by reconfiguration planning at run-time should not outweigh its benefits. On the other hand, completely pre-planning reconfiguration decisions at design time is also infeasible due to the lack of knowledge about the context behavior. In this paper, we propose a game-theoretic setting for precomputing reconfiguration decisions under partially uncertain real-time behavior. We employ stochastic timed game automata as reconfiguration model to derive winning strategies which enable the first player (the system) to make fast look-ups for presumably best-fitting reconfiguration decisions satisfying the second player (the context). To cope with the high computational complexity of finding winning strategies, our tool implementation1 utilizes the statistical model-checker Uppaal Stratego to approximate near-optimal solutions. In our evaluation, we investigate efficiency/effectiveness trade-offs by considering a real-world example consisting of a reconfigurable robot support system for the construction of aircraft fuselages.