Введение. О моделировании вероятностных мультиагентных систем Марковскими системами

Мультиагентные системы (МАС) составляют одну из наиболее активно развивающихся областей теории и практики искусственного интеллекта (см., например, [Subrahmanian et al., 2000], [Тарасов, 2002]). При этом значительное место занимает изучение МАС, содержащих агенты, действия которых включают в себя элементы случайности (вероятностных МАС, кратко ВМАС). Уже обычные МАС довольно сложны и включают в себя много разных средств, позволяющих достаточно адекватно моделировать разнообразные практические системы, но затрудняющих их формальное изучение. Для ВМАС последнее обстоятельство еще более усугубляется из-за добавления новых (вероятностных) элементов. Поэтому представляет интерес изучение возможности моделирования ВМАС классическими хорошо изученными марковскими системами (Марковскими цепями или процессами принятия решений).

В этой работе мы приводим краткий обзор наших результатов по такому моделированию (см., в частности, [Dekhtyar et al., 2008], [Валиев и др., 2009]). Заметим, что в общем случае действия агентов ВМАС могут быть не только вероятностными, но и недетерминированными. ВМАС, содержащие такие агенты, будем называть недетерминированными (НВМАС). ВМАС, которые содержат только обычные вероятностные агенты, будем называть (чтобы отличать их от НВМАС) последовательными (ПВМАС).

Наши результаты в раз. 3 ниже показывают, что ПВМАС достаточно эффективно моделируются конечными Марковскими цепями, а НВМАС — конечными Марковскими процессами принятия решений. В разделе 4 приводятся некоторые результаты о сложности верификации динамических свойств ПВМАС и НВМАС, которые следуют из результатов раздела 3 и известных результатов Варди, Куркубетиса-Яннакакиса и др. о верификации Марковских цепей и процессов (соответствующие ссылки см. в разделе 4).