Much attention has been devoted in artificial intelligence to the verification of multi-agent systems and different logical formalisms have been proposed, such as Alternating-time Temporal Logic (ATL), Alternating mu-calculus (AMC), and Coalition Logic (CL). Recently, logics able to express bounds on resources have been introduced, such as RB-ATL and PRB-ATL, both of them based on ATL. The main contribution of this paper is the introduction and the study of a new formalism for dealing with bounded resources, based on mu-calculus. Such a formalism, called Priced Resource-Bounded Alternating mu-calculus (PRB-AMC), is an extension of both PRB-ATL and AMC. In analogy with PRB-ATL, we introduce a price for each resource. By considering that the resources have each a price (which may vary during the game) and that agents can buy them only if they have enough money, several real world scenarios can be adequately described. First, we show that the model checking problem for PRB-AMC is in EXPTIME and has a PSPACE lower bound. Then, we solve the problem of determining the minimal cost coalition of agents. Finally, we show that the satisfiability problem of PRB-AMC is undecidable, when the game is played on arenas with only one state.

On a priced resource-bounded alternating mu-calculus

LENZI, Giacomo
2012

Abstract

Much attention has been devoted in artificial intelligence to the verification of multi-agent systems and different logical formalisms have been proposed, such as Alternating-time Temporal Logic (ATL), Alternating mu-calculus (AMC), and Coalition Logic (CL). Recently, logics able to express bounds on resources have been introduced, such as RB-ATL and PRB-ATL, both of them based on ATL. The main contribution of this paper is the introduction and the study of a new formalism for dealing with bounded resources, based on mu-calculus. Such a formalism, called Priced Resource-Bounded Alternating mu-calculus (PRB-AMC), is an extension of both PRB-ATL and AMC. In analogy with PRB-ATL, we introduce a price for each resource. By considering that the resources have each a price (which may vary during the game) and that agents can buy them only if they have enough money, several real world scenarios can be adequately described. First, we show that the model checking problem for PRB-AMC is in EXPTIME and has a PSPACE lower bound. Then, we solve the problem of determining the minimal cost coalition of agents. Finally, we show that the satisfiability problem of PRB-AMC is undecidable, when the game is played on arenas with only one state.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11386/3136920
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact