Publications

Reasoning about memoryless strategies under partial observability and unconditional fairness constraints

Authors
Simon Busard, Charles Pecheur, Hongyang Qu, Franco Raimondi
Tags
,
Title
Reasoning about memoryless strategies under partial observability and unconditional fairness constraints
Authors
Simon Busard, Charles Pecheur, Hongyang Qu, Franco Raimondi
sr13-journal.pdf Δ   516Kb   28 May 2020
Type
Article
Journal
Information and Computation
Volume
242
Number
0
Pages
128-156
Year
2015

Abstract

Abstract Alternating-time Temporal Logic is a logic to reason about strategies that agents can adopt to achieve a specified collective goal. A number of extensions for this logic exist; some of them combine strategies and partial observability, some others include fairness constraints, but to the best of our knowledge no work provides a unified framework for strategies, partial observability and fairness constraints. Integration of these three concepts is important when reasoning about the capabilities of agents without full knowledge of a system, for instance when the agents can assume that the environment behaves in a fair way. We present \{ATLK\} irF , a logic combining strategies under partial observability in a system with fairness constraints on states. We introduce a model-checking algorithm for \{ATLK\} irF by extending the algorithm for a full-observability variant of the logic and we investigate its complexity. We validate our proposal with an experimental evaluation.

Tags Tags: ,

BibTeX Record
  @ARTICLE{lvl-2015-423232,
    TITLE = {Reasoning about memoryless strategies under partial observability and unconditional fairness constraints},
    AUTHOR = {Simon Busard and Charles Pecheur and Hongyang Qu and Franco Raimondi},
    YEAR = {2015},
    JOURNAL = {Information and Computation},
    VOLUME = {242},
    NUMBER = {0},
    PAGES =  {128-156},
    URL = {https://lvl.info.ucl.ac.be/Publications/ReasoningAboutMemorylessStrategiesUnderPartialObservabilityAndUnconditionalFairnessConstraints},
  }