О сложности верификации недетерминированных вероятностных мультиагентных систем

Полный текст:


Аннотация

Рассматриваются вероятностные системы взаимодействующих недетерминированных интеллектуальных агентов. Состояниями агентов в таких системах являются вероятностные базы данных (фактов), а их действия управляются вероятностными логическими программами. Кроме того, каналы взаимодействий между агентами также являются вероятностными. Показано, как таким системам за полиномиальное время могут быть сопоставлены моделирующие их конечные Марковские процессы принятия решений. Это позволяет перенести известные результаты о верификации динамических свойств конечных Марковских процессов на вероятностные мультиагентные системы рассматриваемого типа.

Об авторах

М. К. Валиев
Институт прикладной математики им. М.В. Келдыша РАН
Россия


М. И. Дехтярь
Тверской государственный университет
Россия


Список литературы

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

2. Baier C., Katoen J. Principles of Model Checking. MIT Press, 2008.

3. Barringer, H., Fisher, M., Gabbay, D., Gough, G., and Owens R. METATEM: An Introduction // Formal Aspects of Computing. 1995. 7. P. 533-549.

4. Bordini R., FisherM., Pardavila C., and Wooldridge M. Model checking AgentSpeak. AAMAS. 2003. P. 409-416.

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

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

7. Courcoubetis C., Yannakakis M. The complexity of probabilistic verification // J. ACM. 1995. V. 42, 4. P. 857-907.

8. Dekhtyar A., Dekhtyar M.I. The Theory of Interval Probabilistic Logic Programs // Annals of Mathematics and Artificial Intelligence. 2009. 55, N 3-4. P. 355-388.

9. Dekhtyar M., Dikovsky A., and Valiev M. On feasible cases of checking multi-agent Systems Behavior // Theoretical Computer Science, Elsevier Science. 2003. V. 303, N 1. P. 63-81.

10. Dekhtyar M.I., Dikovsky A.Ja., Valiev M.K. On complexity of verification of interacting agent's behavior // Annals of Pure and Applied Logic. 2006. 141. P. 336- 362.

11. Dekhtyar M,I., Dikovsky A.Ja., Valiev M.K. 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. V. 4800. Springer- Verlag, Berlin, 2008. P. 256-265.

12. Dix J., Nanni M., and Subrahmanian V. S. Probabilistic agent reasoning // ACM Transactions of Computational Logic. 2000. 1(2). P. 201-245.

13. Hansson H., Jonsson B. A logic for reasning about time and reliability // Formal Aspects of Computing. 1994. 6(5). P. 512-535.

14. Kwiatkowska M. Model Checking for probability and time: from theory to practice // Proc. 18th IEEE Symposium on Logic in Computer Science. 2003. P. 351-360.

15. Ng R., Subrahmanian V.S. Probabilistic Logic Programming // Information and Computation. 1993. 101, N 2. P. 150-201.

16. Rao A.S., Georgeff M.P. Modelling rational agents within a BDI architecture // Proc. 2nd Intern. Conf on Principles of Knowledge Representation and Reasoning, Morgan Kaufman Publisyers, 1991.

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

18. van der Hoek W., Wooldridge M. Tractable multiagent planning for epistemic goals. AAMAS'02, Bologna, Italy, 2002.

19. Vardi M.Y. Automatic verification of probabilistic concurrent finite state programs // Proceedings of 26th IEEE Symposium on Foundations of Computer Science. IEEE, New York. P. 327-338.

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

21. Wooldridge M., Jennings N. Intelligent agents. Theory and Practice // The Knowledge Engineering Review. 1995. 10(2).

22. Валиев М.К., Дехтярь М.И. Вероятностные мультиагентные системы: семантика и верификация // Вестник Тверского госуниверситета. 2008. № 35(98). С. 9-22.

23. Валиев М.К., Дехтярь М.И. Сложность верификации мультиагентных систем с вероятностными состояниями и программами // Труды V Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте». Т. 1. М.: Физматлит, 2009. С. 198-206

24. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям. Эдиториал УРСС. М., 2002.


Дополнительные файлы

Для цитирования: Валиев М.К., Дехтярь М.И. О сложности верификации недетерминированных вероятностных мультиагентных систем. Моделирование и анализ информационных систем. 2010;17(4):41-51.

For citation: Valiev M.K., Dekhtyar M.I. On complexity of veri¯cation of nondeterministic probabilistic multiagent systems. Modeling and Analysis of Information Systems. 2010;17(4):41-51. (In Russ.)

Просмотров: 10

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)