Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Logic-based specification and verification of homogeneous dynamic multi-agent systems
Stockholms universitet, Humanistiska fakulteten, Filosofiska institutionen.
Stockholms universitet, Humanistiska fakulteten, Filosofiska institutionen. University of Johannesburg, South Africa.
Antal upphovsmän: 22020 (Engelska)Ingår i: Autonomous Agents and Multi-Agent Systems, ISSN 1387-2532, E-ISSN 1573-7454, Vol. 34, nr 2, artikel-id 34Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We develop a logic-based framework for formal specification and algorithmic verification of homogeneous and dynamic concurrent multi-agent transition systems. Homogeneity means that all agents have the same available actions at any given state and the actions have the same effects regardless of which agents perform them. The state transitions are therefore determined only by the vector of numbers of agents performing each action and are specified symbolically, by means of conditions on these numbers definable in Presburger arithmetic. The agents are divided into controllable (by the system supervisor/controller) and uncontrollable, representing the environment or adversary. Dynamicity means that the numbers of controllable and uncontrollable agents may vary throughout the system evolution, possibly at every transition. As a language for formal specification we use a suitably extended version of Alternating-time Temporal Logic, where one can specify properties of the type a coalition of (at least) n controllable agents can ensure against (at most) m uncontrollable agents that any possible evolution of the system satisfies a given objective ., where is specified again as a formula of that language and each of n and m is either a fixed number or a variable that can be quantified over. We provide formal semantics to our logic L HDMAS and define normal form of its formulae. We then prove that every formula in L HDMAS is equivalent in the finite to one in a normal form and develop an algorithm for global model checking of formulae in normal form in finite HDMAS models, which invokes model checking truth of Presburger formulae. We establish worst case complexity estimates for the model checking algorithm and illustrate it on a running example.

Ort, förlag, år, upplaga, sidor
2020. Vol. 34, nr 2, artikel-id 34
Nyckelord [en]
Dynamic multi-agent systems, Logics for multi-agent systems, Logics for strategic reasoning, Model-checking
Nationell ämneskategori
Data- och informationsvetenskap Filosofi, etik och religion
Identifikatorer
URN: urn:nbn:se:su:diva-181800DOI: 10.1007/s10458-020-09457-8ISI: 000529337600001OAI: oai:DiVA.org:su-181800DiVA, id: diva2:1441212
Tillgänglig från: 2020-06-15 Skapad: 2020-06-15 Senast uppdaterad: 2022-03-23Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Person

De Masellis, RiccardoGoranko, Valentin

Sök vidare i DiVA

Av författaren/redaktören
De Masellis, RiccardoGoranko, Valentin
Av organisationen
Filosofiska institutionen
I samma tidskrift
Autonomous Agents and Multi-Agent Systems
Data- och informationsvetenskapFilosofi, etik och religion

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 83 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf