KR2021Proceedings of the 18th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning

Online event. November 3-12, 2021.

Edited by
  1. Meghyn Bienvenu
  2. Gerhard Lakemeyer
  3. Esra Erdem

ISSN: 2334-1033
ISBN: 978-1-956792-99-7

Sponsored by
Published by

Copyright © 2021 International Joint Conferences on Artificial Intelligence Organization

Strategic Abilities of Asynchronous Agents: Semantic Side Effects and How to Tame Them

  1. Wojciech Jamroga(Institute of Computer Science, Polish Academy of Sciences, Interdisciplinary Centre on Security, Reliability and Trust, SnT, University of Luxembourg)
  2. Wojciech Penczek(Institute of Computer Science, Polish Academy of Sciences)
  3. Teofil Sidoruk(Institute of Computer Science, Polish Academy of Sciences, Faculty of Mathematics and Information Science, Warsaw University of Technology)
PDF
BibTeX
https://doi.org/10.24963/kr.2021/35

Keywords

  1. KR and autonomous agents and multi-agent systems

Abstract

Recently, we have proposed a framework for verification of agents' abilities in asynchronous multi-agent systems (MAS), together with an algorithm for automated reduction of models. The semantics was built on the modeling tradition of distributed systems.

As we show here, this can sometimes lead to counterintuitive interpretation of formulas when reasoning about the outcome of strategies. First, the semantics disregards finite paths, and yields unnatural evaluation of strategies with deadlocks. Secondly, the semantic representations do not allow to capture the asymmetry between proactive agents and the recipients of their choices. We propose how to avoid the problems by a suitable extension of the representations and change of the execution semantics for asynchronous MAS. We also prove that the model reduction scheme still works in the modified framework.