“Robots in Space” Multiagent Problem: Complexity, Information and Cryptographic Aspects

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.

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.