Active Diagnosis for Probabilistic Systems View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2014

AUTHORS

Nathalie Bertrand , Éric Fabre , Stefan Haar , Serge Haddad , Loïc Hélouët

ABSTRACT

The diagnosis problem amounts to deciding whether some specific “fault” event occurred or not in a system, given the observations collected on a run of this system. This system is then diagnosable if the fault can always be detected, and the active diagnosis problem consists in controlling the system in order to ensure its diagnosability. We consider here a stochastic framework for this problem: once a control is selected, the system becomes a stochastic process. In this setting, the active diagnosis problem consists in deciding whether there exists some observation-based strategy that makes the system diagnosable with probability one. We prove that this problem is EXPTIME-complete, and that the active diagnosis strategies are belief-based. The safe active diagnosis problem is similar, but aims at enforcing diagnosability while preserving a positive probability to non faulty runs, i.e. without enforcing the occurrence of a fault. We prove that this problem requires non belief-based strategies, and that it is undecidable. However, it belongs to NEXPTIME when restricted to belief-based strategies. Our work also refines the decidability/undecidability frontier for verification problems on partially observed Markov decision processes. More... »

PAGES

29-42

References to SciGraph publications

  • 2010. Randomness for Free in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2010
  • 2011. Diagnosability of Pushdown Systems in HARDWARE AND SOFTWARE: VERIFICATION AND TESTING
  • 2007-12. Active Acquisition of Information for Diagnosis and Supervisory Control of Discrete Event Systems in DISCRETE EVENT DYNAMIC SYSTEMS
  • Book

    TITLE

    Foundations of Software Science and Computation Structures

    ISBN

    978-3-642-54829-1
    978-3-642-54830-7

    From Grant

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-54830-7_2

    DOI

    http://dx.doi.org/10.1007/978-3-642-54830-7_2

    DIMENSIONS

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


    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/0104", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Statistics", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "French Institute for Research in Computer Science and Automation", 
              "id": "https://www.grid.ac/institutes/grid.5328.c", 
              "name": [
                "Inria, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Bertrand", 
            "givenName": "Nathalie", 
            "id": "sg:person.012767106631.49", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012767106631.49"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "French Institute for Research in Computer Science and Automation", 
              "id": "https://www.grid.ac/institutes/grid.5328.c", 
              "name": [
                "Inria, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Fabre", 
            "givenName": "\u00c9ric", 
            "id": "sg:person.011362250353.22", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011362250353.22"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "French Institute for Research in Computer Science and Automation", 
              "id": "https://www.grid.ac/institutes/grid.5328.c", 
              "name": [
                "Inria, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Haar", 
            "givenName": "Stefan", 
            "id": "sg:person.015066472515.27", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015066472515.27"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Laboratoire Sp\u00e9cification et V\u00e9rification", 
              "id": "https://www.grid.ac/institutes/grid.464035.0", 
              "name": [
                "LSV, ENS, Cachan & CNRS & Inria, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Haddad", 
            "givenName": "Serge", 
            "id": "sg:person.016552227263.84", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016552227263.84"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "French Institute for Research in Computer Science and Automation", 
              "id": "https://www.grid.ac/institutes/grid.5328.c", 
              "name": [
                "Inria, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "H\u00e9lou\u00ebt", 
            "givenName": "Lo\u00efc", 
            "id": "sg:person.010307042577.01", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010307042577.01"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/2108242.2108243", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007318812"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-15155-2_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010837100", 
              "https://doi.org/10.1007/978-3-642-15155-2_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-15155-2_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010837100", 
              "https://doi.org/10.1007/978-3-642-15155-2_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.3182/20090630-4-es-2003.00252", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015782249"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10626-007-0027-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029318741", 
              "https://doi.org/10.1007/s10626-007-0027-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10626-007-0027-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029318741", 
              "https://doi.org/10.1007/s10626-007-0027-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-19237-1_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029410611", 
              "https://doi.org/10.1007/978-3-642-19237-1_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-19237-1_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029410611", 
              "https://doi.org/10.1007/978-3-642-19237-1_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.3182/20100830-3-de-4013.00039", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043094580"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/9.412626", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061244618"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/9.701089", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061245629"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tac.2002.802763", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061475089"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tac.2005.844722", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061475878"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/cdc.2009.5400608", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094430517"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/lics.2009.31", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094564174"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2014", 
        "datePublishedReg": "2014-01-01", 
        "description": "The diagnosis problem amounts to deciding whether some specific \u201cfault\u201d event occurred or not in a system, given the observations collected on a run of this system. This system is then diagnosable if the fault can always be detected, and the active diagnosis problem consists in controlling the system in order to ensure its diagnosability. We consider here a stochastic framework for this problem: once a control is selected, the system becomes a stochastic process. In this setting, the active diagnosis problem consists in deciding whether there exists some observation-based strategy that makes the system diagnosable with probability one. We prove that this problem is EXPTIME-complete, and that the active diagnosis strategies are belief-based. The safe active diagnosis problem is similar, but aims at enforcing diagnosability while preserving a positive probability to non faulty runs, i.e. without enforcing the occurrence of a fault. We prove that this problem requires non belief-based strategies, and that it is undecidable. However, it belongs to NEXPTIME when restricted to belief-based strategies. Our work also refines the decidability/undecidability frontier for verification problems on partially observed Markov decision processes.", 
        "editor": [
          {
            "familyName": "Muscholl", 
            "givenName": "Anca", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-54830-7_2", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.3785405", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": {
          "isbn": [
            "978-3-642-54829-1", 
            "978-3-642-54830-7"
          ], 
          "name": "Foundations of Software Science and Computation Structures", 
          "type": "Book"
        }, 
        "name": "Active Diagnosis for Probabilistic Systems", 
        "pagination": "29-42", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-54830-7_2"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "420830f39750ae60997d89a4bb0064f697cbb750f27e2f5484bb15b7593df7fb"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1013861280"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-54830-7_2", 
          "https://app.dimensions.ai/details/publication/pub.1013861280"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T22:54", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8695_00000251.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-642-54830-7_2"
      }
    ]
     

    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-54830-7_2'

    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-54830-7_2'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-54830-7_2'

    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-54830-7_2'


     

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

    137 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-54830-7_2 schema:about anzsrc-for:01
    2 anzsrc-for:0104
    3 schema:author N6a442c0b5a5144448929c33cd8f8b98e
    4 schema:citation sg:pub.10.1007/978-3-642-15155-2_23
    5 sg:pub.10.1007/978-3-642-19237-1_6
    6 sg:pub.10.1007/s10626-007-0027-y
    7 https://doi.org/10.1109/9.412626
    8 https://doi.org/10.1109/9.701089
    9 https://doi.org/10.1109/cdc.2009.5400608
    10 https://doi.org/10.1109/lics.2009.31
    11 https://doi.org/10.1109/tac.2002.802763
    12 https://doi.org/10.1109/tac.2005.844722
    13 https://doi.org/10.1145/2108242.2108243
    14 https://doi.org/10.3182/20090630-4-es-2003.00252
    15 https://doi.org/10.3182/20100830-3-de-4013.00039
    16 schema:datePublished 2014
    17 schema:datePublishedReg 2014-01-01
    18 schema:description The diagnosis problem amounts to deciding whether some specific “fault” event occurred or not in a system, given the observations collected on a run of this system. This system is then diagnosable if the fault can always be detected, and the active diagnosis problem consists in controlling the system in order to ensure its diagnosability. We consider here a stochastic framework for this problem: once a control is selected, the system becomes a stochastic process. In this setting, the active diagnosis problem consists in deciding whether there exists some observation-based strategy that makes the system diagnosable with probability one. We prove that this problem is EXPTIME-complete, and that the active diagnosis strategies are belief-based. The safe active diagnosis problem is similar, but aims at enforcing diagnosability while preserving a positive probability to non faulty runs, i.e. without enforcing the occurrence of a fault. We prove that this problem requires non belief-based strategies, and that it is undecidable. However, it belongs to NEXPTIME when restricted to belief-based strategies. Our work also refines the decidability/undecidability frontier for verification problems on partially observed Markov decision processes.
    19 schema:editor N64441b41ab434474a02f113690950972
    20 schema:genre chapter
    21 schema:inLanguage en
    22 schema:isAccessibleForFree true
    23 schema:isPartOf N332d3f4f1e6b4aee842f6ea2057f46ba
    24 schema:name Active Diagnosis for Probabilistic Systems
    25 schema:pagination 29-42
    26 schema:productId N3a11173b56124283a00935ecc806df76
    27 N754a3348bc164126a79340ca40128206
    28 Nc5d0cda655b34b60baab896a86b0f5da
    29 schema:publisher N860d6ef511d844e794d3e2f9a117fc6e
    30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013861280
    31 https://doi.org/10.1007/978-3-642-54830-7_2
    32 schema:sdDatePublished 2019-04-15T22:54
    33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    34 schema:sdPublisher N38bb5aa4bd95464aae444916e3c490a8
    35 schema:url http://link.springer.com/10.1007/978-3-642-54830-7_2
    36 sgo:license sg:explorer/license/
    37 sgo:sdDataset chapters
    38 rdf:type schema:Chapter
    39 N332d3f4f1e6b4aee842f6ea2057f46ba schema:isbn 978-3-642-54829-1
    40 978-3-642-54830-7
    41 schema:name Foundations of Software Science and Computation Structures
    42 rdf:type schema:Book
    43 N38bb5aa4bd95464aae444916e3c490a8 schema:name Springer Nature - SN SciGraph project
    44 rdf:type schema:Organization
    45 N3a11173b56124283a00935ecc806df76 schema:name dimensions_id
    46 schema:value pub.1013861280
    47 rdf:type schema:PropertyValue
    48 N4fe047bc1018485f9dc20741d3bf9209 schema:familyName Muscholl
    49 schema:givenName Anca
    50 rdf:type schema:Person
    51 N64441b41ab434474a02f113690950972 rdf:first N4fe047bc1018485f9dc20741d3bf9209
    52 rdf:rest rdf:nil
    53 N6a442c0b5a5144448929c33cd8f8b98e rdf:first sg:person.012767106631.49
    54 rdf:rest Nb342a7af9653430d94c2f174775c6ae1
    55 N754a3348bc164126a79340ca40128206 schema:name readcube_id
    56 schema:value 420830f39750ae60997d89a4bb0064f697cbb750f27e2f5484bb15b7593df7fb
    57 rdf:type schema:PropertyValue
    58 N860d6ef511d844e794d3e2f9a117fc6e schema:location Berlin, Heidelberg
    59 schema:name Springer Berlin Heidelberg
    60 rdf:type schema:Organisation
    61 Nb342a7af9653430d94c2f174775c6ae1 rdf:first sg:person.011362250353.22
    62 rdf:rest Nd2c0f8cc416546de9f9036db5e23b1a4
    63 Nc5d0cda655b34b60baab896a86b0f5da schema:name doi
    64 schema:value 10.1007/978-3-642-54830-7_2
    65 rdf:type schema:PropertyValue
    66 Nd2c0f8cc416546de9f9036db5e23b1a4 rdf:first sg:person.015066472515.27
    67 rdf:rest Nd36a07a2f85c4ebfbeb464e042669964
    68 Nd36a07a2f85c4ebfbeb464e042669964 rdf:first sg:person.016552227263.84
    69 rdf:rest Nedc89f189d794da981b49dc5db64b2b0
    70 Nedc89f189d794da981b49dc5db64b2b0 rdf:first sg:person.010307042577.01
    71 rdf:rest rdf:nil
    72 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    73 schema:name Mathematical Sciences
    74 rdf:type schema:DefinedTerm
    75 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
    76 schema:name Statistics
    77 rdf:type schema:DefinedTerm
    78 sg:grant.3785405 http://pending.schema.org/fundedItem sg:pub.10.1007/978-3-642-54830-7_2
    79 rdf:type schema:MonetaryGrant
    80 sg:person.010307042577.01 schema:affiliation https://www.grid.ac/institutes/grid.5328.c
    81 schema:familyName Hélouët
    82 schema:givenName Loïc
    83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010307042577.01
    84 rdf:type schema:Person
    85 sg:person.011362250353.22 schema:affiliation https://www.grid.ac/institutes/grid.5328.c
    86 schema:familyName Fabre
    87 schema:givenName Éric
    88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011362250353.22
    89 rdf:type schema:Person
    90 sg:person.012767106631.49 schema:affiliation https://www.grid.ac/institutes/grid.5328.c
    91 schema:familyName Bertrand
    92 schema:givenName Nathalie
    93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012767106631.49
    94 rdf:type schema:Person
    95 sg:person.015066472515.27 schema:affiliation https://www.grid.ac/institutes/grid.5328.c
    96 schema:familyName Haar
    97 schema:givenName Stefan
    98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015066472515.27
    99 rdf:type schema:Person
    100 sg:person.016552227263.84 schema:affiliation https://www.grid.ac/institutes/grid.464035.0
    101 schema:familyName Haddad
    102 schema:givenName Serge
    103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016552227263.84
    104 rdf:type schema:Person
    105 sg:pub.10.1007/978-3-642-15155-2_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010837100
    106 https://doi.org/10.1007/978-3-642-15155-2_23
    107 rdf:type schema:CreativeWork
    108 sg:pub.10.1007/978-3-642-19237-1_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029410611
    109 https://doi.org/10.1007/978-3-642-19237-1_6
    110 rdf:type schema:CreativeWork
    111 sg:pub.10.1007/s10626-007-0027-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1029318741
    112 https://doi.org/10.1007/s10626-007-0027-y
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1109/9.412626 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061244618
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1109/9.701089 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061245629
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1109/cdc.2009.5400608 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094430517
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1109/lics.2009.31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094564174
    121 rdf:type schema:CreativeWork
    122 https://doi.org/10.1109/tac.2002.802763 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061475089
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.1109/tac.2005.844722 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061475878
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1145/2108242.2108243 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007318812
    127 rdf:type schema:CreativeWork
    128 https://doi.org/10.3182/20090630-4-es-2003.00252 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015782249
    129 rdf:type schema:CreativeWork
    130 https://doi.org/10.3182/20100830-3-de-4013.00039 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043094580
    131 rdf:type schema:CreativeWork
    132 https://www.grid.ac/institutes/grid.464035.0 schema:alternateName Laboratoire Spécification et Vérification
    133 schema:name LSV, ENS, Cachan & CNRS & Inria, France
    134 rdf:type schema:Organization
    135 https://www.grid.ac/institutes/grid.5328.c schema:alternateName French Institute for Research in Computer Science and Automation
    136 schema:name Inria, France
    137 rdf:type schema:Organization
     




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


    ...