Synthesis for Multi-objective Stochastic Games: An Application to Autonomous Urban Driving View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Taolue Chen , Marta Kwiatkowska , Aistis Simaitis , Clemens Wiltsche

ABSTRACT

We study strategy synthesis for stochastic two-player games with multiple objectives expressed as a conjunction of LTL and expected total reward goals. For stopping games, the strategies are constructed from the Pareto frontiers that we compute via value iteration. Since, in general, infinite memory is required for deterministic winning strategies in such games, our construction takes advantage of randomised memory updates in order to provide compact strategies. We implement our methods in PRISM-games, a model checker for stochastic multi-player games, and present a case study motivated by the DARPA Urban Challenge, illustrating how our methods can be used to synthesise strategies for high-level control of autonomous vehicles. More... »

PAGES

322-337

Book

TITLE

Quantitative Evaluation of Systems

ISBN

978-3-642-40195-4
978-3-642-40196-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-40196-1_28

DOI

http://dx.doi.org/10.1007/978-3-642-40196-1_28

DIMENSIONS

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


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/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Oxford, United Kingdom", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Department of Computer Science, University of Oxford, United Kingdom"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Taolue", 
        "id": "sg:person.014034042506.15", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014034042506.15"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Oxford, United Kingdom", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Department of Computer Science, University of Oxford, United Kingdom"
          ], 
          "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 Computer Science, University of Oxford, United Kingdom", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Department of Computer Science, University of Oxford, United Kingdom"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Simaitis", 
        "givenName": "Aistis", 
        "id": "sg:person.010605171167.62", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010605171167.62"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Oxford, United Kingdom", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Department of Computer Science, University of Oxford, United Kingdom"
          ], 
          "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": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "We study strategy synthesis for stochastic two-player games with multiple objectives expressed as a conjunction of LTL and expected total reward goals. For stopping games, the strategies are constructed from the Pareto frontiers that we compute via value iteration. Since, in general, infinite memory is required for deterministic winning strategies in such games, our construction takes advantage of randomised memory updates in order to provide compact strategies. We implement our methods in PRISM-games, a model checker for stochastic multi-player games, and present a case study motivated by the DARPA Urban Challenge, illustrating how our methods can be used to synthesise strategies for high-level control of autonomous vehicles.", 
    "editor": [
      {
        "familyName": "Joshi", 
        "givenName": "Kaustubh", 
        "type": "Person"
      }, 
      {
        "familyName": "Siegle", 
        "givenName": "Markus", 
        "type": "Person"
      }, 
      {
        "familyName": "Stoelinga", 
        "givenName": "Mari\u00eblle", 
        "type": "Person"
      }, 
      {
        "familyName": "D\u2019Argenio", 
        "givenName": "Pedro R.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-40196-1_28", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-40195-4", 
        "978-3-642-40196-1"
      ], 
      "name": "Quantitative Evaluation of Systems", 
      "type": "Book"
    }, 
    "keywords": [
      "stochastic multi-player games", 
      "stochastic games", 
      "value iteration", 
      "Pareto frontier", 
      "infinite memory", 
      "multiple objectives", 
      "compact strategy", 
      "PRISM-games", 
      "two-player game", 
      "strategy synthesis", 
      "multi-player games", 
      "such games", 
      "iteration", 
      "high-level control", 
      "autonomous vehicles", 
      "game", 
      "model checker", 
      "applications", 
      "case study", 
      "construction", 
      "order", 
      "frontier", 
      "advantages", 
      "driving", 
      "conjunction", 
      "control", 
      "urban driving", 
      "vehicles", 
      "strategies", 
      "objective", 
      "goal", 
      "memory", 
      "checker", 
      "LTL", 
      "DARPA Urban Challenge", 
      "challenges", 
      "synthesis", 
      "study", 
      "urban challenges", 
      "method", 
      "autonomous urban driving"
    ], 
    "name": "Synthesis for Multi-objective Stochastic Games: An Application to Autonomous Urban Driving", 
    "pagination": "322-337", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1051989987"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-40196-1_28"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-40196-1_28", 
      "https://app.dimensions.ai/details/publication/pub.1051989987"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:45", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_30.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-40196-1_28"
  }
]
 

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-642-40196-1_28'

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-642-40196-1_28'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-40196-1_28'

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-642-40196-1_28'


 

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

137 TRIPLES      23 PREDICATES      67 URIs      60 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-40196-1_28 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author N5b5f1e8f0bc448c5a6314f5f15228d2f
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description We study strategy synthesis for stochastic two-player games with multiple objectives expressed as a conjunction of LTL and expected total reward goals. For stopping games, the strategies are constructed from the Pareto frontiers that we compute via value iteration. Since, in general, infinite memory is required for deterministic winning strategies in such games, our construction takes advantage of randomised memory updates in order to provide compact strategies. We implement our methods in PRISM-games, a model checker for stochastic multi-player games, and present a case study motivated by the DARPA Urban Challenge, illustrating how our methods can be used to synthesise strategies for high-level control of autonomous vehicles.
7 schema:editor N3ef5d7c300714cf7a6f00d7a09b2f5d6
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N8c9d33827b6440d6ae891d5e3f5515b3
12 schema:keywords DARPA Urban Challenge
13 LTL
14 PRISM-games
15 Pareto frontier
16 advantages
17 applications
18 autonomous urban driving
19 autonomous vehicles
20 case study
21 challenges
22 checker
23 compact strategy
24 conjunction
25 construction
26 control
27 driving
28 frontier
29 game
30 goal
31 high-level control
32 infinite memory
33 iteration
34 memory
35 method
36 model checker
37 multi-player games
38 multiple objectives
39 objective
40 order
41 stochastic games
42 stochastic multi-player games
43 strategies
44 strategy synthesis
45 study
46 such games
47 synthesis
48 two-player game
49 urban challenges
50 urban driving
51 value iteration
52 vehicles
53 schema:name Synthesis for Multi-objective Stochastic Games: An Application to Autonomous Urban Driving
54 schema:pagination 322-337
55 schema:productId N7bbf999e77334a85a3f2c782df632108
56 Nffa0461d21da4a189d5ca219dba87913
57 schema:publisher Nf20ce8eb93814cfb98089c2ecff18ad0
58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051989987
59 https://doi.org/10.1007/978-3-642-40196-1_28
60 schema:sdDatePublished 2022-05-10T10:45
61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
62 schema:sdPublisher N52bd8d8099cd41c38c78ce9f08dfe8f7
63 schema:url https://doi.org/10.1007/978-3-642-40196-1_28
64 sgo:license sg:explorer/license/
65 sgo:sdDataset chapters
66 rdf:type schema:Chapter
67 N184ed342437442b48218255da1573b64 rdf:first sg:person.013041737446.42
68 rdf:rest rdf:nil
69 N2563068fc0bd4ded84422a78a242fb17 schema:familyName D’Argenio
70 schema:givenName Pedro R.
71 rdf:type schema:Person
72 N3ef5d7c300714cf7a6f00d7a09b2f5d6 rdf:first Ne10e31e1177f41f49c4bf54b5ac06312
73 rdf:rest N8270c28088bd48e8b66fc4e2de16501d
74 N4917820432de436b9d21d3b58a1af802 schema:familyName Stoelinga
75 schema:givenName Mariëlle
76 rdf:type schema:Person
77 N52bd8d8099cd41c38c78ce9f08dfe8f7 schema:name Springer Nature - SN SciGraph project
78 rdf:type schema:Organization
79 N5b5f1e8f0bc448c5a6314f5f15228d2f rdf:first sg:person.014034042506.15
80 rdf:rest Ne4b1d03dc91c49e3877ddc17f033286f
81 N6e5f67622b3446468efdfe2b36ce215f rdf:first N2563068fc0bd4ded84422a78a242fb17
82 rdf:rest rdf:nil
83 N7bbf999e77334a85a3f2c782df632108 schema:name dimensions_id
84 schema:value pub.1051989987
85 rdf:type schema:PropertyValue
86 N8270c28088bd48e8b66fc4e2de16501d rdf:first Ne6e157bec9774f4e941d0215250e5aff
87 rdf:rest Nf6c40b4e2ae24f8daf7042d08b20694d
88 N8c9d33827b6440d6ae891d5e3f5515b3 schema:isbn 978-3-642-40195-4
89 978-3-642-40196-1
90 schema:name Quantitative Evaluation of Systems
91 rdf:type schema:Book
92 Ne10e31e1177f41f49c4bf54b5ac06312 schema:familyName Joshi
93 schema:givenName Kaustubh
94 rdf:type schema:Person
95 Ne4b1d03dc91c49e3877ddc17f033286f rdf:first sg:person.011375012273.39
96 rdf:rest Nfd40747591de4de890aede96e08db08e
97 Ne6e157bec9774f4e941d0215250e5aff schema:familyName Siegle
98 schema:givenName Markus
99 rdf:type schema:Person
100 Nf20ce8eb93814cfb98089c2ecff18ad0 schema:name Springer Nature
101 rdf:type schema:Organisation
102 Nf6c40b4e2ae24f8daf7042d08b20694d rdf:first N4917820432de436b9d21d3b58a1af802
103 rdf:rest N6e5f67622b3446468efdfe2b36ce215f
104 Nfd40747591de4de890aede96e08db08e rdf:first sg:person.010605171167.62
105 rdf:rest N184ed342437442b48218255da1573b64
106 Nffa0461d21da4a189d5ca219dba87913 schema:name doi
107 schema:value 10.1007/978-3-642-40196-1_28
108 rdf:type schema:PropertyValue
109 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
110 schema:name Mathematical Sciences
111 rdf:type schema:DefinedTerm
112 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
113 schema:name Statistics
114 rdf:type schema:DefinedTerm
115 sg:person.010605171167.62 schema:affiliation grid-institutes:grid.4991.5
116 schema:familyName Simaitis
117 schema:givenName Aistis
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010605171167.62
119 rdf:type schema:Person
120 sg:person.011375012273.39 schema:affiliation grid-institutes:grid.4991.5
121 schema:familyName Kwiatkowska
122 schema:givenName Marta
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011375012273.39
124 rdf:type schema:Person
125 sg:person.013041737446.42 schema:affiliation grid-institutes:grid.4991.5
126 schema:familyName Wiltsche
127 schema:givenName Clemens
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013041737446.42
129 rdf:type schema:Person
130 sg:person.014034042506.15 schema:affiliation grid-institutes:grid.4991.5
131 schema:familyName Chen
132 schema:givenName Taolue
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014034042506.15
134 rdf:type schema:Person
135 grid-institutes:grid.4991.5 schema:alternateName Department of Computer Science, University of Oxford, United Kingdom
136 schema:name Department of Computer Science, University of Oxford, United Kingdom
137 rdf:type schema:Organization
 




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


...