ON A PRICED RESOURCE-BOUNDED ALTERNATING μ-CALCULUS

Dario Della Monica, Giacomo Lenzi

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 μ-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 μ-calculus. Such a formalism, called Priced Resource-Bounded Alternating μ-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.

Paper Citation

in Harvard Style

Della Monica D. and Lenzi G. (2012). ON A PRICED RESOURCE-BOUNDED ALTERNATING μ-CALCULUS . In Proceedings of the 4th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART, ISBN 978-989-8425-96-6, pages 222-227. DOI: 10.5220/0003750102220227

in Bibtex Style

@conference{icaart12,
author={Dario Della Monica and Giacomo Lenzi},
title={ON A PRICED RESOURCE-BOUNDED ALTERNATING μ-CALCULUS},
booktitle={Proceedings of the 4th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,},
year={2012},
pages={222-227},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003750102220227},
isbn={978-989-8425-96-6},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 4th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,
TI - ON A PRICED RESOURCE-BOUNDED ALTERNATING μ-CALCULUS
SN - 978-989-8425-96-6
AU - Della Monica D.
AU - Lenzi G.
PY - 2012
SP - 222
EP - 227
DO - 10.5220/0003750102220227