maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2013-2-34-53mais-204Research ArticleОригинальные статьиArticlesМультиагентная задача о роботах в пространстве: сложностнóй, информационный и криптографический аспекты“Robots in Space” Multiagent Problem: Complexity, Information and Cryptographic AspectsБернштейнАнтон ЮрьевичBernsteinA. Yu.

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

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

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

 

bahtoh@gmail.comШиловНиколай ВячеславовичShilovN. V.

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

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

канд. физ.-мат. наук, старший научный сотрудник,

prospect Akademika Lavrentjeva, 6, Novosibirsk, 630090, Russia;

доцент Новосибирского государственного университета и Новосибирского государственного технического университета

shilov@iis.nsk.suНовосибирский государственный университетРоссияNovosibirsk State University, Pirogova Str., 2, Novosibirsk, 630090, RussiaRussian FederationИнститут систем информатики им. А.П. Ершова СО РАНРоссияA.P. Ershov Institute of Informatics Systems SB RASRussian Federation2013200420132023453Copyright © Бернштейн А.Ю., Шилов Н.В., 20132013Бернштейн А.Ю., Шилов Н.В.Bernstein A.Y., Shilov N.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/204

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

We study a multiagent algorithmic problem that we call Robot in Space (RinS): There are n ≥ 2 autonomous robots, that need to agree without outside interference on distribution of shelters, so that straight pathes to the shelters will not intersect. The problem is closely related to the assignment problem in Graph Theory, to the convex hull problem in Combinatorial Geometry, or to the path-planning problem in Artificial Intelligence. Our algorithm grew up from a local search solution of the problem suggested by E.W. Dijkstra. We present a multiagent anonymous and scalable algorithm (protocol) solving the problem, give an upper bound for the algorithm, prove (manually) its correctness, and examine two communication aspects of the RinS problem — the informational and cryptographic. We proved that (1) there is no protocol that solves the RinS, which transfers a bounded number of bits, and (2) suggested the protocol that allows robots to check whether their paths intersect, without revealing additional information about their relative positions (with respect to shelters). The present paper continues the research presented in Mars Robot Puzzle (a Multiagent Approach to the Dijkstra Problem) (by E.V. Bodin, N.O. Garanina, and N.V. Shilov), published in Modeling and analysis of information systems, 18(2), 2011.

мультиагентные (многоагентные) системы и алгоритмыгеометрическая задача о назначенияханонимностьмасштабируемостьсвойства безопасности и прогрессаверификация алгоритмовmultiagent systems and algorithmslocation assignment problemanonymityscalabilitysafety and progress propertiesalgorithm verificationРФФИ, СО РАНReferencesБернштейн А.Ю. Информационный и криптографический аспекты задачи о роботах на Марсе // Ершовская конференция по информатике 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]).Бернштейн А.Ю. Информационный и криптографический аспекты задачи о роботах на Марсе // Ершовская конференция по информатике 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]).Бодин Е.В., Гаранина Н.О., Шилов Н.В. Задача о роботах на Марсе (мультиагентный подход к задаче Дейкстры) // Моделирование и анализ информационных систем. 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]).Бодин Е.В., Гаранина Н.О., Шилов Н.В. Задача о роботах на Марсе (мультиагентный подход к задаче Дейкстры) // Моделирование и анализ информационных систем. 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]).Гаранина Н.О., Шилов Н.В. Верификация комбинированных логик знаний, действий и времени в моделях // Методы и модели современного программирования. Системная информатика, вып. 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]).Гаранина Н.О., Шилов Н.В. Верификация комбинированных логик знаний, действий и времени в моделях // Методы и модели современного программирования. Системная информатика, вып. 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]).Мюллер Д. Общественный выбор III. М.: Гос. ун-т Высшая школа экономики, Институт “Экономическая школа”, 2007 (English trans.: Mueller D.C. Public Choice III. Cambridge: Cambridge University Press, 2003).Мюллер Д. Общественный выбор III. М.: Гос. ун-т Высшая школа экономики, Институт “Экономическая школа”, 2007 (English trans.: Mueller D.C. Public Choice III. Cambridge: Cambridge University Press, 2003).Тель Ж. Введение в распределенные алгоритмы. М.: МЦНМО, 2009 (English trans.: Tel G. Introduction to Distributed Algorithms. Cambridge: Cambridge University Press, 2003).Тель Ж. Введение в распределенные алгоритмы. М.: МЦНМО, 2009 (English trans.: Tel G. Introduction to Distributed Algorithms. Cambridge: Cambridge University Press, 2003).Таненбаум Э., ван Стеен М. Распределенные системы. Принципы и парадигмы. СПб.: Питер, 2003 (English trans.: Andrew S. Tanenbaum A.S., van Steen M. Distributed Systems: Principles and Paradigms. New Jersey: Pearson Prentice Hall, 2007).Таненбаум Э., ван Стеен М. Распределенные системы. Принципы и парадигмы. СПб.: Питер, 2003 (English trans.: Andrew S. Tanenbaum A.S., van Steen M. Distributed Systems: Principles and Paradigms. New Jersey: Pearson Prentice Hall, 2007).Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. М.: Издательство ТРИУМФ, 2002 (English trans.: Schneier B. Applied Cryptography: Protocols, Algorithms, and Source Code in C. New York: John Wiley & Sons, 1996).Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. М.: Издательство ТРИУМФ, 2002 (English trans.: Schneier B. Applied Cryptography: Protocols, Algorithms, and Source Code in C. New York: John Wiley & Sons, 1996).Яковлев К.С. Алгоритмы планирования перемещений на плоскости: Слайды презентации, 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]).Яковлев К.С. Алгоритмы планирования перемещений на плоскости: Слайды презентации, 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]).Fagin R., Halpern J.Y., Moses Y., Vardi M.Y. Reasoning about Knowledge. MIT Press, 1995.Fagin R., Halpern J.Y., Moses Y., Vardi M.Y. Reasoning about Knowledge. MIT Press, 1995.Goldreich O. Foundations of Cryptography — A Primer // Foundations and Trends in Theoretical Computer Science. 2005. V. 1, № 1. P. 1–116.Goldreich O. Foundations of Cryptography — A Primer // Foundations and Trends in Theoretical Computer Science. 2005. V. 1, № 1. P. 1–116.Halpern J., O’Neill K. Anonymity and Information Hiding in Multiagent Systems // Journal of Computer Security. 2005. V. 13, № 3. P. 483–514.Halpern J., O’Neill K. Anonymity and Information Hiding in Multiagent Systems // Journal of Computer Security. 2005. V. 13, № 3. P. 483–514.Hughes D., Shmatikov V. Information Hiding, Anonymity and Privacy: a Modular Approach // Journal of Computer Security. 2004. V. 12, № 1. P. 3–36.Hughes D., Shmatikov V. Information Hiding, Anonymity and Privacy: a Modular Approach // Journal of Computer Security. 2004. V. 12, № 1. P. 3–36.de Jong S., Tuyls K., Verbeeck K. Fairness in Multiagent Systems // The Knowledge Engineering Review. 2008. V. 23, № 2. P. 153–180.de Jong S., Tuyls K., Verbeeck K. Fairness in Multiagent Systems // The Knowledge Engineering Review. 2008. V. 23, № 2. P. 153–180.de Jong S. Fairness in Multi-Agent Systems. PhD Thesis. Maastricht University, 2009. Доступна на http://dl.dropbox.com/u/1505034/website/optima/thesis(17x24).pdf.de Jong S. Fairness in Multi-Agent Systems. PhD Thesis. Maastricht University, 2009. Доступна на http://dl.dropbox.com/u/1505034/website/optima/thesis(17x24).pdf.LaValle S.M. Planning Algorithms. Cambridge University Press, 2006.LaValle S.M. Planning Algorithms. Cambridge University Press, 2006.Manna Z., Pnueli A. The Temporal Logic of Reactive and Concurrent Systems: Specification. Springer, 1992.Manna Z., Pnueli A. The Temporal Logic of Reactive and Concurrent Systems: Specification. Springer, 1992.Shilov N.V., Shilova S.O. Etude on theme of Dijkstra // ACM SIGACT News. 2004. V. 35, № 3. P. 102–108.Shilov N.V., Shilova S.O. Etude on theme of Dijkstra // ACM SIGACT News. 2004. V. 35, № 3. P. 102–108.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.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.Wooldridge M. An Introduction to Multiagent Systems. Jhon Willey & Sons, 2002.Wooldridge M. An Introduction to Multiagent Systems. Jhon Willey & Sons, 2002.

The authors declare that there are no conflicts of interest present.