Подход к верификации семейства мультиагентных систем разрешения конфликтов


https://doi.org/10.18255/1818-1015-2016-6-703-714

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


Аннотация

В данной работе мы описываем метод верификации для семейств распределенных систем, которые порождаются контекстно-зависимой сетевой грамматикой специального вида. Эта грамматика содержит специальные нетерминальные символы ䷘ квази-терминалы. Квази-терминалы однозначно соответствуют терминалам грамматики и могут задавать процессы,
которые определяются слиянием базовых процессов системы, в то время как нетерминалы задают сети параллельных композиций этих процессов. Данный метод верификации основан на техниках верификации моделей и абстракции. Абстрактная репрезентативная модель семейства систем зависит от задающей их грамматики и верифицируемых свойств системы. Эта модель симулирует поведение заданных систем таким образом, что свойства, которые выполняются в репрезентативной модели, также выполняются и во всех заданных системах. Проверку свойств репрезентативной модели можно осуществлять с помощью метода проверки моделей. Свойства порождаемых систем специфицируются с помощью универсальной логики ветвящегося времени ∀CTL с конечными детерминированными автоматами в качестве атомарных формул. Мы показываем, что предложенный метод верификации можно применять для проверки некоторых свойств мультиагентных систем разрешения конфликтов, в частности, систем разрешения неоднозначностей при пополнении онтологий. Также показано, что этот подход можно использовать для верификации вычислений на подрешетках, являющихся подграфами решеток вычислений, например, для вычисления четности числа работающих процессов.


Об авторах

Н. О. Гаранина
Институт систем информатики им. А.П. Ершова СО РАН
Россия
канд. физ.-мат. наук, проспект Лаврентьева, 6, г. Новосибирск, 630090 Россия


Е. А. Сидорова
Институт систем информатики им. А.П. Ершова СО РАН
Россия

канд. физ.-мат. наук, проспект Лаврентьева, 6, г. Новосибирск, 630090 Россия



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

1. Bergenti F., Franchi E., Poggi A., “Selected models for agent-based simulation of social networks”, Proc. of 3rd Symposium on Social Networks and Multiagent Systems (SNAMAS 2011), 2011, 27–32.

2. Clarke E. M., Grumberg O., Jha S., “Verifying Parameterized Networks”, ACM Transactions on Programming Languages and Systems, 19:5 (1997), 726–750.

3. Clarke E. M., Grumberg O., Peled D., Model Checking, MIT Press, 1999.

4. Dassow J., “Grammars With Regulated Rewriting”, Formal Languages and Applications, Studies in Fuzziness and Soft Computing, 148, 2004, 249–273.

5. De Gennaro M. C., Jadbabaie A., “Decentralized Control of Connectivity for Multi-Agent Systems”, Proc. of 45th IEEE Conference on Decision and Control, 2006, 3628–3633.

6. Fagin R., Halpern J. Y., Moses Y., Vardi M. Y., Reasoning about Knowledge, MIT Press, 1995.

7. Garanina N. O., Sidorova E .A., “Ontology Population as Algebraic Information System Processing Based on Multi-agent Natural Language Text Analysis Algorithms”, Programming and Computer Software, 41:3 (2015), 140–148.

8. Garanina N., Sidorova E., “An Approach to Ambiguity Resolution for Ontology Population”, Proc. of 24th International Workshop on Concurrency, Specification, and Programming, (CS&P 2015) (Rzeszow, Poland, 2015, Sep. 28–30), 1, 2015, 27–32.

9. Garanina N. O., Sidorova E. A., Anokhin S. A., “Conflict Resolution in Multi-agent Systems with Typed Connections for Ontology Population”, Perspectives of System Informatics, Lecture Notes in Computer Science, 9609, 2016, 116–129.

10. Hopcroft J. E., Ullman J. D., Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.

11. Huhns M. N., Stephens L. M., “Multiagent Systems and Societies of Agents”, Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence, MIT Press, 1999, 79– 120.

12. Tel G., Introduction to Distributed Algorithms, Cambridge University Press, 2000.

13. Wooldridge M., An Introduction to Multiagent Systems, Willey&Sons Ltd, 2002.


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

Для цитирования: Гаранина Н.О., Сидорова Е.А. Подход к верификации семейства мультиагентных систем разрешения конфликтов. Моделирование и анализ информационных систем. 2016;23(6):703-714. https://doi.org/10.18255/1818-1015-2016-6-703-714

For citation: Garanina N.O., Sidorova E.A. An Approach to Verification of a Family of Multi- agent Systems for Conflict Resolution. Modeling and Analysis of Information Systems. 2016;23(6):703-714. (In Russ.) https://doi.org/10.18255/1818-1015-2016-6-703-714

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

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

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


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


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