Strategy Synthesis for Stochastic Games with Multiple Long-Run Objectives View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2015

AUTHORS

Nicolas Basset , Marta Kwiatkowska , Ufuk Topcu , Clemens Wiltsche

ABSTRACT

We consider turn-based stochastic games whose winning conditions are conjunctions of satisfaction objectives for long-run average rewards, and address the problem of finding a strategy that almost surely maintains the averages above a given multi-dimensional threshold vector. We show that strategies constructed from Pareto set approximations of expected energy objectives are ε-optimal for the corresponding average rewards. We further apply our methods to compositional strategy synthesis for multi-component stochastic games that leverages composition rules for probabilistic automata, which we extend for long-run ratio rewards with fairness. We implement the techniques and illustrate our methods on a case study of automated compositional synthesis of controllers for aircraft primary electric power distribution networks that ensure a given level of reliability. More... »

PAGES

256-271

Book

TITLE

Tools and Algorithms for the Construction and Analysis of Systems

ISBN

978-3-662-46680-3
978-3-662-46681-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-46681-0_22

DOI

http://dx.doi.org/10.1007/978-3-662-46681-0_22

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1017762388


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Oxford, Oxford, UK", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Department of Computer Science, University of Oxford, Oxford, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Basset", 
        "givenName": "Nicolas", 
        "id": "sg:person.014372542370.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014372542370.01"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Oxford, Oxford, UK", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Department of Computer Science, University of Oxford, Oxford, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kwiatkowska", 
        "givenName": "Marta", 
        "id": "sg:person.011375012273.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011375012273.39"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, USA", 
          "id": "http://www.grid.ac/institutes/grid.25879.31", 
          "name": [
            "Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Topcu", 
        "givenName": "Ufuk", 
        "id": "sg:person.011155121742.36", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011155121742.36"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Oxford, Oxford, UK", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Department of Computer Science, University of Oxford, Oxford, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wiltsche", 
        "givenName": "Clemens", 
        "id": "sg:person.013041737446.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013041737446.42"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015", 
    "datePublishedReg": "2015-01-01", 
    "description": "We consider turn-based stochastic games whose winning conditions are conjunctions of satisfaction objectives for long-run average rewards, and address the problem of finding a strategy that almost surely maintains the averages above a given multi-dimensional threshold vector. We show that strategies constructed from Pareto set approximations of expected energy objectives are \u03b5-optimal for the corresponding average rewards. We further apply our methods to compositional strategy synthesis for multi-component stochastic games that leverages composition rules for probabilistic automata, which we extend for long-run ratio rewards with fairness. We implement the techniques and illustrate our methods on a case study of automated compositional synthesis of controllers for aircraft primary electric power distribution networks that ensure a given level of reliability.", 
    "editor": [
      {
        "familyName": "Baier", 
        "givenName": "Christel", 
        "type": "Person"
      }, 
      {
        "familyName": "Tinelli", 
        "givenName": "Cesare", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-46681-0_22", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-662-46680-3", 
        "978-3-662-46681-0"
      ], 
      "name": "Tools and Algorithms for the Construction and Analysis of Systems", 
      "type": "Book"
    }, 
    "keywords": [
      "stochastic games", 
      "turn-based stochastic games", 
      "strategy synthesis", 
      "average reward", 
      "power distribution network", 
      "distribution network", 
      "level of reliability", 
      "threshold vector", 
      "energy objectives", 
      "composition rules", 
      "compositional synthesis", 
      "probabilistic automata", 
      "electric power distribution networks", 
      "controller", 
      "Pareto", 
      "approximation", 
      "game", 
      "problem", 
      "automata", 
      "network", 
      "case study", 
      "objective", 
      "vector", 
      "fairness", 
      "reliability", 
      "rules", 
      "technique", 
      "strategies", 
      "conditions", 
      "conjunction", 
      "average", 
      "reward", 
      "synthesis", 
      "study", 
      "levels", 
      "method", 
      "longer-run objectives", 
      "satisfaction objectives", 
      "multi-dimensional threshold vector", 
      "corresponding average rewards", 
      "compositional strategy synthesis", 
      "multi-component stochastic games", 
      "run ratio rewards", 
      "ratio rewards", 
      "aircraft primary electric power distribution networks", 
      "primary electric power distribution networks", 
      "Multiple Long-Run Objectives"
    ], 
    "name": "Strategy Synthesis for Stochastic Games with Multiple Long-Run Objectives", 
    "pagination": "256-271", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1017762388"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-46681-0_22"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-46681-0_22", 
      "https://app.dimensions.ai/details/publication/pub.1017762388"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:14", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_234.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-46681-0_22"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-46681-0_22'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-46681-0_22'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-46681-0_22'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-46681-0_22'


 

This table displays all metadata directly associated to this object as RDF triples.

136 TRIPLES      23 PREDICATES      73 URIs      66 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-46681-0_22 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author N819c8d2e5bbd41399bf6215f07183ee8
4 schema:datePublished 2015
5 schema:datePublishedReg 2015-01-01
6 schema:description We consider turn-based stochastic games whose winning conditions are conjunctions of satisfaction objectives for long-run average rewards, and address the problem of finding a strategy that almost surely maintains the averages above a given multi-dimensional threshold vector. We show that strategies constructed from Pareto set approximations of expected energy objectives are ε-optimal for the corresponding average rewards. We further apply our methods to compositional strategy synthesis for multi-component stochastic games that leverages composition rules for probabilistic automata, which we extend for long-run ratio rewards with fairness. We implement the techniques and illustrate our methods on a case study of automated compositional synthesis of controllers for aircraft primary electric power distribution networks that ensure a given level of reliability.
7 schema:editor N41e93c8682f140a6bcc2b2bcfd6f12ed
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N6e9901f922c74f23b4d13a043cea0498
12 schema:keywords Multiple Long-Run Objectives
13 Pareto
14 aircraft primary electric power distribution networks
15 approximation
16 automata
17 average
18 average reward
19 case study
20 composition rules
21 compositional strategy synthesis
22 compositional synthesis
23 conditions
24 conjunction
25 controller
26 corresponding average rewards
27 distribution network
28 electric power distribution networks
29 energy objectives
30 fairness
31 game
32 level of reliability
33 levels
34 longer-run objectives
35 method
36 multi-component stochastic games
37 multi-dimensional threshold vector
38 network
39 objective
40 power distribution network
41 primary electric power distribution networks
42 probabilistic automata
43 problem
44 ratio rewards
45 reliability
46 reward
47 rules
48 run ratio rewards
49 satisfaction objectives
50 stochastic games
51 strategies
52 strategy synthesis
53 study
54 synthesis
55 technique
56 threshold vector
57 turn-based stochastic games
58 vector
59 schema:name Strategy Synthesis for Stochastic Games with Multiple Long-Run Objectives
60 schema:pagination 256-271
61 schema:productId N08bf178586bc4a99999301c96474b8e9
62 N440a3e5e496f4e2a97b8b80312bdba6c
63 schema:publisher Ne2b18c1d6d7948a29451e777007df34b
64 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017762388
65 https://doi.org/10.1007/978-3-662-46681-0_22
66 schema:sdDatePublished 2022-01-01T19:14
67 schema:sdLicense https://scigraph.springernature.com/explorer/license/
68 schema:sdPublisher N076f94a8c6c24e539b30da7d76d60a6a
69 schema:url https://doi.org/10.1007/978-3-662-46681-0_22
70 sgo:license sg:explorer/license/
71 sgo:sdDataset chapters
72 rdf:type schema:Chapter
73 N076f94a8c6c24e539b30da7d76d60a6a schema:name Springer Nature - SN SciGraph project
74 rdf:type schema:Organization
75 N08bf178586bc4a99999301c96474b8e9 schema:name dimensions_id
76 schema:value pub.1017762388
77 rdf:type schema:PropertyValue
78 N1a25c92eaf1545e9aa639f4e8fc6bbfa schema:familyName Baier
79 schema:givenName Christel
80 rdf:type schema:Person
81 N2966669d4e714898a4000a297d6c9426 rdf:first sg:person.013041737446.42
82 rdf:rest rdf:nil
83 N41e93c8682f140a6bcc2b2bcfd6f12ed rdf:first N1a25c92eaf1545e9aa639f4e8fc6bbfa
84 rdf:rest N829c1138e1764468841ae187dc0b9e83
85 N440a3e5e496f4e2a97b8b80312bdba6c schema:name doi
86 schema:value 10.1007/978-3-662-46681-0_22
87 rdf:type schema:PropertyValue
88 N4a108ab71b9c40f294f0f884b8e0aec6 rdf:first sg:person.011375012273.39
89 rdf:rest N865366cf1fa04aed800cf3a5ab39e848
90 N6e9901f922c74f23b4d13a043cea0498 schema:isbn 978-3-662-46680-3
91 978-3-662-46681-0
92 schema:name Tools and Algorithms for the Construction and Analysis of Systems
93 rdf:type schema:Book
94 N819c8d2e5bbd41399bf6215f07183ee8 rdf:first sg:person.014372542370.01
95 rdf:rest N4a108ab71b9c40f294f0f884b8e0aec6
96 N829c1138e1764468841ae187dc0b9e83 rdf:first Nbdc0187b8f9448398caaf000016bb44f
97 rdf:rest rdf:nil
98 N865366cf1fa04aed800cf3a5ab39e848 rdf:first sg:person.011155121742.36
99 rdf:rest N2966669d4e714898a4000a297d6c9426
100 Nbdc0187b8f9448398caaf000016bb44f schema:familyName Tinelli
101 schema:givenName Cesare
102 rdf:type schema:Person
103 Ne2b18c1d6d7948a29451e777007df34b schema:name Springer Nature
104 rdf:type schema:Organisation
105 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
106 schema:name Mathematical Sciences
107 rdf:type schema:DefinedTerm
108 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
109 schema:name Applied Mathematics
110 rdf:type schema:DefinedTerm
111 sg:person.011155121742.36 schema:affiliation grid-institutes:grid.25879.31
112 schema:familyName Topcu
113 schema:givenName Ufuk
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011155121742.36
115 rdf:type schema:Person
116 sg:person.011375012273.39 schema:affiliation grid-institutes:grid.4991.5
117 schema:familyName Kwiatkowska
118 schema:givenName Marta
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011375012273.39
120 rdf:type schema:Person
121 sg:person.013041737446.42 schema:affiliation grid-institutes:grid.4991.5
122 schema:familyName Wiltsche
123 schema:givenName Clemens
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013041737446.42
125 rdf:type schema:Person
126 sg:person.014372542370.01 schema:affiliation grid-institutes:grid.4991.5
127 schema:familyName Basset
128 schema:givenName Nicolas
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014372542370.01
130 rdf:type schema:Person
131 grid-institutes:grid.25879.31 schema:alternateName Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, USA
132 schema:name Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, USA
133 rdf:type schema:Organization
134 grid-institutes:grid.4991.5 schema:alternateName Department of Computer Science, University of Oxford, Oxford, UK
135 schema:name Department of Computer Science, University of Oxford, Oxford, UK
136 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...