Reasoning about memoryless strategies under partial observability and unconditional fairness constraints
(2015) Information and Computation — Vol. 242, p. 128-156 (2015)
Files
sr13-journal.pdf
Open Access - Adobe PDF
- 516.04 KB
Details
- Authors
- 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 ATLKirF, a logic combining strategies under partial observability in a system with fairness constraints on states. We introduce a model-checking algorithm for ATLKirF 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.
- Affiliations
Citations
Busard, S., Pecheur, C., Qu, H., & Raimondi, F. (2015). Reasoning about memoryless strategies under partial observability and unconditional fairness constraints. Information and Computation, 242, 128-156. https://doi.org/10.1016/j.ic.2015.03.014 (Original work published 2015)