Мультиагентная задача о роботах в пространстве: сложностнóй, информационный и криптографический аспекты


https://doi.org/10.18255/1818-1015-2013-2-34-53

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


Аннотация

В статье изучается следующая мультиагентная алгоритмическая задача о роботах в пространстве (Robot in Space — RinS): В пространстве есть n ≥ 2 автономных робота, которым необходимо самостоятельно договориться о выборе индивидуальных укрытий так, чтобы прямолинейные маршруты к этим укрытиям не пересекались. Эта задача имеет отношение к задаче о назначениях в теории графов, задаче построения выпуклой оболочки в ком- бинаторной геометрии и задаче планирования перемещений в искусственном интеллекте. Предлагаемый в статье мультиагентный алгоритм (протокол) ос- нован на централизованном локальном алгоритме Э.В. Дейкстры. Наш алго- ритм обладает свойствами анонимности и масштабируемости, мы доказываем его корректность и верхнюю оценку сложности. Кроме того, мы исследуем два коммуникационных аспекта задачи о роботах в пространстве — инфор- мационный и криптографический. В статье показано, что (1) не существует протокола, решающего задачу RinS, передающего ограниченное число битов, но (2) существует протокол для решения этой задачи, который позволяет ро- ботам не раскрывать информацию о своём положении относительно укрытий. Настоящая статья является продолжением исследований, представленных в статье Е.В. Бодина, Н.О. Гараниной и Н.В. Шилова "Задача о роботах на Марсе (мультиагентный подход к задаче Дейкстры)" опубликованной в № 2 за 2011 г. журнала "Моделирование и анализ информационных систем".


Об авторах

Антон Юрьевич Бернштейн
Новосибирский государственный университет
Россия

студент механико-математического факультета,

630090, г. Новосибирск, ул. Пирогова, д. 2



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

канд. физ.-мат. наук, старший научный сотрудник, доцент Новосибирского государственного университета и Новосибирского государственного технического университета,

630090, г. Новосибирск, проспект Лаврентьева, 6



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

1. Бернштейн А.Ю. Информационный и криптографический аспекты задачи о роботах на Марсе // Ершовская конференция по информатике 2011: Труды третьего семинара “Знания и Онтология *ELSEWHERE* 2011”. Новосибирск: Прайс-Курьер, 2011. С. 35–46 (Bernstein A.Yu. Informatsyonny i kriptografichesky aspekty zadachi o robotah na Marse // Ershovskaya konferentsiya po informatike 2011: Trudy tretego seminara Znaniya i Ontologiya *ELSEWHERE*. Novosibirsk: Prais-Kurer, 2011. P. 35–46 [in Russian]).

2. Бодин Е.В., Гаранина Н.О., Шилов Н.В. Задача о роботах на Марсе (мультиагентный подход к задаче Дейкстры) // Моделирование и анализ информационных систем. 2011. Т. 18, №2. С. 111–126 (Bodin E.V., Garanina N.O., Shilov N.V. Mars Robot Puzzle (a Multiagent Approach to the Dijkstra Problem) // Modeling and analysis of information systems. 2011. V. 18, №2. P. 111–126 [in Russian]).

3. Гаранина Н.О., Шилов Н.В. Верификация комбинированных логик знаний, действий и времени в моделях // Методы и модели современного программирования. Системная информатика, вып. 10. Новосибирск: изд-во Сибирского Отделения РАН, 2006. С. 114–173 (Garanina N.O., Shilov N.V. Verifikatsiya kombinirovannyh logic znany, deistvy i vremeny v modelyah // Metody i modeli sovremennogo programmirovaniay. Sistemnaya informatica. № 10. Novosibirsk: izdatelstvo Sibirskogo Otdelenya RAN, 2006. P. 114–173 [in Russian]).

4. Мюллер Д. Общественный выбор III. М.: Гос. ун-т Высшая школа экономики, Институт “Экономическая школа”, 2007 (English trans.: Mueller D.C. Public Choice III. Cambridge: Cambridge University Press, 2003).

5. Тель Ж. Введение в распределенные алгоритмы. М.: МЦНМО, 2009 (English trans.: Tel G. Introduction to Distributed Algorithms. Cambridge: Cambridge University Press, 2003).

6. Таненбаум Э., ван Стеен М. Распределенные системы. Принципы и парадигмы. СПб.: Питер, 2003 (English trans.: Andrew S. Tanenbaum A.S., van Steen M. Distributed Systems: Principles and Paradigms. New Jersey: Pearson Prentice Hall, 2007).

7. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. М.: Издательство ТРИУМФ, 2002 (English trans.: Schneier B. Applied Cryptography: Protocols, Algorithms, and Source Code in C. New York: John Wiley & Sons, 1996).

8. Яковлев К.С. Алгоритмы планирования перемещений на плоскости: Слайды презентации, 2010. Доступна на www.raai.org/news/pii/ppt/yakovlev.ppt. (Yakovlev K.S. Algorithmy planyrovanya peremescheny na ploskosti: Presentation, 2010. Available at www.raai.org/news/pii/ppt/yakovlev.ppt [in Russian]).

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

10. Goldreich O. Foundations of Cryptography — A Primer // Foundations and Trends in Theoretical Computer Science. 2005. V. 1, № 1. P. 1–116.

11. Halpern J., O’Neill K. Anonymity and Information Hiding in Multiagent Systems // Journal of Computer Security. 2005. V. 13, № 3. P. 483–514.

12. Hughes D., Shmatikov V. Information Hiding, Anonymity and Privacy: a Modular Approach // Journal of Computer Security. 2004. V. 12, № 1. P. 3–36.

13. de Jong S., Tuyls K., Verbeeck K. Fairness in Multiagent Systems // The Knowledge Engineering Review. 2008. V. 23, № 2. P. 153–180.

14. de Jong S. Fairness in Multi-Agent Systems. PhD Thesis. Maastricht University, 2009. Доступна на http://dl.dropbox.com/u/1505034/website/optima/thesis(17x24).pdf.

15. LaValle S.M. Planning Algorithms. Cambridge University Press, 2006.

16. Manna Z., Pnueli A. The Temporal Logic of Reactive and Concurrent Systems: Specification. Springer, 1992.

17. Shilov N.V., Shilova S.O. Etude on theme of Dijkstra // ACM SIGACT News. 2004. V. 35, № 3. P. 102–108.

18. Shilov N.V., Garanina N.O. Rational Agents at the Marketplace // Proceedings of Workshop on Concurrency, Specification and Programming CS&P’2011 (Pultusk, Poland, September 28-30, 2011). Bialystok University of Technology, 2011. P. 465–476.

19. Wooldridge M. An Introduction to Multiagent Systems. Jhon Willey & Sons, 2002.


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

Для цитирования: Бернштейн А.Ю., Шилов Н.В. Мультиагентная задача о роботах в пространстве: сложностнóй, информационный и криптографический аспекты. Моделирование и анализ информационных систем. 2013;20(2):34-53. https://doi.org/10.18255/1818-1015-2013-2-34-53

For citation: Bernstein A.Y., Shilov N.V. “Robots in Space” Multiagent Problem: Complexity, Information and Cryptographic Aspects. Modeling and Analysis of Information Systems. 2013;20(2):34-53. (In Russ.) https://doi.org/10.18255/1818-1015-2013-2-34-53

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

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

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


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


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