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": "2021-11-01T18:52", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_251.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 N8dec367386bf4b6da2d02e51ee0652fb
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 N526b99d1e5e149dc80b70fcb87e1dde9
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nbd276c7bc7d1416598dacb96a414cf48
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 N3a84332b73a44dcca4a9735f465ccd8d
62 N5f45c553b0014f71baadcac716cd31fb
63 schema:publisher N23be5ccbca3240f29f077c41c97956fe
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 2021-11-01T18:52
67 schema:sdLicense https://scigraph.springernature.com/explorer/license/
68 schema:sdPublisher N707af04f6bf742a18cc33c28cd5af1aa
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 N09e221db6b64468a924083d13515dd3a rdf:first sg:person.013041737446.42
74 rdf:rest rdf:nil
75 N23be5ccbca3240f29f077c41c97956fe schema:name Springer Nature
76 rdf:type schema:Organisation
77 N2c267dc07175481f84ce8c718405bcd6 schema:familyName Tinelli
78 schema:givenName Cesare
79 rdf:type schema:Person
80 N3a84332b73a44dcca4a9735f465ccd8d schema:name dimensions_id
81 schema:value pub.1017762388
82 rdf:type schema:PropertyValue
83 N526b99d1e5e149dc80b70fcb87e1dde9 rdf:first N720a87be12644a41ada5731c62f73a3e
84 rdf:rest Nd22b6b654feb467da778027b2c6ad8fb
85 N5f45c553b0014f71baadcac716cd31fb schema:name doi
86 schema:value 10.1007/978-3-662-46681-0_22
87 rdf:type schema:PropertyValue
88 N707af04f6bf742a18cc33c28cd5af1aa schema:name Springer Nature - SN SciGraph project
89 rdf:type schema:Organization
90 N720a87be12644a41ada5731c62f73a3e schema:familyName Baier
91 schema:givenName Christel
92 rdf:type schema:Person
93 N8dec367386bf4b6da2d02e51ee0652fb rdf:first sg:person.014372542370.01
94 rdf:rest Nc731cef2d54c43bea74c60a813fde32d
95 N91dd90409a3142b08e315225effd63cc rdf:first sg:person.011155121742.36
96 rdf:rest N09e221db6b64468a924083d13515dd3a
97 Nbd276c7bc7d1416598dacb96a414cf48 schema:isbn 978-3-662-46680-3
98 978-3-662-46681-0
99 schema:name Tools and Algorithms for the Construction and Analysis of Systems
100 rdf:type schema:Book
101 Nc731cef2d54c43bea74c60a813fde32d rdf:first sg:person.011375012273.39
102 rdf:rest N91dd90409a3142b08e315225effd63cc
103 Nd22b6b654feb467da778027b2c6ad8fb rdf:first N2c267dc07175481f84ce8c718405bcd6
104 rdf:rest rdf:nil
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)


...