Controller Synthesis by Solving Multi Weighted Games
Studenteropgave: Speciale (inkl. HD afgangsprojekt)
- Søren Moss Nielsen
- Lasse Steen Jensen
- Isabella Kaufmann
3. semester, Datalogi, Kandidat (Kandidatuddannelse)
Controller synthesis is investigated through a game theoretic view. In the context of games, synthesis is the extraction of a winning strategy.
We investigate multi-weighted games, and various strategy types. We hierarchically order these strategy types by expressiveness.
We also present a weighted computation tree logic, for which we provide an undecidability result, and a decidable sub-logic, limited to reachability with upper bounds.
Further more we provide complexity results for the synthesis problem with the reachability sub-logic. We present two methods for synthesis of strategies in 1-weighted games:
We extend the attractor set method with weights giving a global algorithm with polynomial time complexity. And we also show how a strategy can be extracted using
prefixed-point assignment of a symbolic dependency graph.
We investigate multi-weighted games, and various strategy types. We hierarchically order these strategy types by expressiveness.
We also present a weighted computation tree logic, for which we provide an undecidability result, and a decidable sub-logic, limited to reachability with upper bounds.
Further more we provide complexity results for the synthesis problem with the reachability sub-logic. We present two methods for synthesis of strategies in 1-weighted games:
We extend the attractor set method with weights giving a global algorithm with polynomial time complexity. And we also show how a strategy can be extracted using
prefixed-point assignment of a symbolic dependency graph.
Sprog | Engelsk |
---|---|
Udgivelsesdato | 20 dec. 2016 |
Antal sider | 62 |