Geodesic
On complexity of verification of nondeterministic probabilistic multiagent systems
Modelirovanie i analiz informacionnyh sistem, Tome 17 (2010) no. 4, pp. 41-50.

Voir la notice de l'article provenant de la source Math-Net.Ru

Probabilistic systems of interacting nondeterministic intelligent agents are considered. States of the agents in these systems are some probabilistic databases, and the activity of the agents is controlled by some probabilistic logic programs. Moreover, communication channels between agents are also probabilistic. We show how such systems can be polynomially transformed to finite state Markov decision processes. This allows one to transfer the known results on verifying temporal properties of the finite state Markov processes to the probabilistic multi-agent systems of considered type.
Keywords: probabilistic multi-agent systems, Markov chains and decision processes, temporal logics, verification of dynamic properties. 
@article{MAIS_2010_17_4_a4,
     author = {M. K. Valiev and M. I. Dekhtyar'},
     title = {On complexity of verification of nondeterministic probabilistic multiagent systems},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {41--50},
     publisher = {mathdoc},
     volume = {17},
     number = {4},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2010_17_4_a4/}
}
TY  - JOUR
AU  - M. K. Valiev
AU  - M. I. Dekhtyar'
TI  - On complexity of verification of nondeterministic probabilistic multiagent systems
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2010
SP  - 41
EP  - 50
VL  - 17
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2010_17_4_a4/
LA  - ru
ID  - MAIS_2010_17_4_a4
ER  - 
%0 Journal Article
%A M. K. Valiev
%A M. I. Dekhtyar'
%T On complexity of verification of nondeterministic probabilistic multiagent systems
%J Modelirovanie i analiz informacionnyh sistem
%D 2010
%P 41-50
%V 17
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2010_17_4_a4/
%G ru
%F MAIS_2010_17_4_a4
M. K. Valiev; M. I. Dekhtyar'. On complexity of verification of nondeterministic probabilistic multiagent systems. Modelirovanie i analiz informacionnyh sistem, Tome 17 (2010) no. 4, pp. 41-50. http://geodesic.mathdoc.fr/item/MAIS_2010_17_4_a4/

[1] L. De Alfaro, Formal verification of probabilistic systems, PhD Thesis, Stanford Univ., 1998

[2] C. Baier, J. Katoen, Principles of Model Checking, MIT Press, 2008 | MR | Zbl

[3] H. Barringer, M. Fisher, D. Gabbay, G. Gough, R. Owens, “METATEM: An Introduction”, Formal Aspects of Computing, 7 (1995), 533–549 | DOI | Zbl

[4] R. Bordini, M. Fisher, C. Pardavila, M. Wooldridge, “Model checking AgentSpeak”, AAMAS, 2003, 409–416

[5] M. Benerecetti, F. Guinchiglia, L. Serafini, Model checking multiagent systems, Technical Report 9708-07, Instituto Trentino di Cultura, 1998

[6] E. M. Clarke, O. Grumberg, D. Peled, Model checking, MIT Press, 2000

[7] C. Courcoubetis, M. Yannakakis, “The complexity of probabilistic verification”, J. ACM, 42:4 (1995), 857–907 | DOI | MR | Zbl

[8] A. Dekhtyar, M. I. Dekhtyar, “The Theory of Interval Probabilistic Logic Programs”, Annals of Mathematics and Artificial Intelligence, 55:3-4 (2009), 355–388 | DOI | MR | Zbl

[9] M. Dekhtyar, A. Dikovsky, M. Valiev, “On feasible cases of checking multi-agent Systems Behavior”, Theoretical Computer Science, 303:1 (2003), 63–81, Elsevier Science | DOI | MR

[10] M. I. Dekhtyar, A. Ja. Dikovsky, M. K. Valiev, “On complexity of verification of interacting agent's behavior”, Annals of Pure and Applied Logic, 141 (2006), 336–362 | DOI | MR | Zbl

[11] M. I. Dekhtyar, A. Ja. Dikovsky, M. K. Valiev, “Temporal Verification of Probabilistic Multi-Agent Systems”, Pillars of Computer Science, Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday, LNCS, 4800, Springer-Verlag, Berlin, 2008, 256–265 | MR

[12] J. Dix, M. Nanni, V. S. Subrahmanian, “Probabilistic agent reasoning”, ACM Transactions of Computational Logic, 1:2 (2000), 201–245 | MR

[13] H. Hansson, B. Jonsson, “A logic for reasning about time and reliability”, Formal Aspects of Computing, 6:5 (1994), 512–535 | DOI | Zbl

[14] M. K. Valiev, M. I. Dekhtyar, “Veroyatnostnye multiagentnye sistemy: semantika i verifikatsiya”, Vestnik Tverskogo gosuniversiteta, 2008, no. 35(98), 9–22

[15] M. Kwiatkowska, “Model Checking for probability and time: from theory to practice”, Proc. 18th IEEE, Symposium on Logic in Computer Science, 2003, 351–360

[16] R. Ng, V. S. Subrahmanian, “Probabilistic Logic Programming”, Information and Computation, 101:2 (1993), 150–201 | MR

[17] A. S. Rao, M. P. Georgeff, “Modelling rational agents within a BDI architecture”, Proc. 2nd Intern. Conf on Principles of Knowledge Representation and Reasoning, Morgan Kaufman Publisyers, 1991 | MR

[18] V. S. Subrahmanian, P. Bonatti, J. Dix et al., Heterogeneous agent systems, MIT LPess, 2000

[19] W. van der Hoek, M. Wooldridge, “Tractable multiagent planning for epistemic goals”, AAMAS'02 (Bologna, Italy), 2002

[20] M. Y. Vardi, “Automatic verification of probabilistic concurrent finite state programs”, Proceedings of 26th IEEE Symposium on Foundations of Computer Science, IEEE, New York, 327–338

[21] M. Wooldridge, P. E. Dunne, The computational complexity of agent verification, Lecture Notes in AI, 2002

[22] M. Wooldridge, N. Jennings, “Intelligent agents”, Theory and Practice, The Knowledge Engineering Review, 10:2 (1995) | DOI | MR

[23] M. K. Valiev, M. I. Dekhtyar, “Slozhnost verifikatsii multiagentnykh sistem s veroyatnostnymi sostoyaniyami i programmami”, Trudy V Mezhdunarodnoi nauchno-prakticheskoi konferentsii «Integrirovannye modeli i myagkie vychisleniya v iskusstvennom intellekte», v. 1, M., Fizmatlit, 2009, 198–206

[24] V. B. Tarasov, Ot mnogoagentnykh sistem k intellektualnym organizatsiyam, Editorial URSS, M., 2002