Geodesic
``Robots in Space'' Multiagent Problem: Complexity, Information and Cryptographic Aspects
Modelirovanie i analiz informacionnyh sistem, Tome 20 (2013) no. 2, pp. 34-53.

Voir la notice de l'article provenant de la source Math-Net.Ru

We study a multiagent algorithmic problem that we call Robot in Space (RinS): There are $n\geq 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.
Keywords: multiagent systems and algorithms, location assignment problem, anonymity, scalability, safety and progress properties, algorithm verification. 
@article{MAIS_2013_20_2_a2,
     author = {A. Yu. Bernstein and N. V. Shilov},
     title = {``Robots in {Space''} {Multiagent} {Problem:} {Complexity,} {Information} and {Cryptographic} {Aspects}},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {34--53},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2013_20_2_a2/}
}
TY  - JOUR
AU  - A. Yu. Bernstein
AU  - N. V. Shilov
TI  - ``Robots in Space'' Multiagent Problem: Complexity, Information and Cryptographic Aspects
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2013
SP  - 34
EP  - 53
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2013_20_2_a2/
LA  - ru
ID  - MAIS_2013_20_2_a2
ER  - 
%0 Journal Article
%A A. Yu. Bernstein
%A N. V. Shilov
%T ``Robots in Space'' Multiagent Problem: Complexity, Information and Cryptographic Aspects
%J Modelirovanie i analiz informacionnyh sistem
%D 2013
%P 34-53
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2013_20_2_a2/
%G ru
%F MAIS_2013_20_2_a2
A. Yu. Bernstein; N. V. Shilov. ``Robots in Space'' Multiagent Problem: Complexity, Information and Cryptographic Aspects. Modelirovanie i analiz informacionnyh sistem, Tome 20 (2013) no. 2, pp. 34-53. http://geodesic.mathdoc.fr/item/MAIS_2013_20_2_a2/

[1] A. Yu. Bernstein, “Informatsyonny i kriptografichesky aspekty zadachi o robotah na Marse”, Trudy tretego seminara Znaniya i Ontologiya *ELSEWHERE*, Ershovskaya konferentsiya po informatike 2011, Prais-Kurer, Novosibirsk, 2011, 35–46 (in Russian)

[2] E. V. Bodin, N. O. Garanina, N. V. Shilov, “Mars Robot Puzzle (a Multiagent Approach to the Dijkstra Problem)”, Modeling and analysis of information systems, 18:2 (2011), 111–126 (in Russian)

[3] N. O. Garanina, N. V. Shilov, “Verifikatsiya kombinirovannyh logic znany, deistvy i vremeny v modelyah”, Metody i modeli sovremennogo programmirovaniay, Sistemnaya informatica, 10, Izdatelstvo Sibirskogo Otdelenya RAN, Novosibirsk, 2006, 114–173 (in Russian)

[4] D. C. Mueller, Public Choice III, Cambridge University Press, Cambridge, 2003

[5] G. Tel, Introduction to Distributed Algorithms, Cambridge University Press, Cambridge, 2003 | MR

[6] A. S. Tanenbaum, M. van Steen, Distributed Systems: Principles and Paradigms, Pearson Prentice Hall, New Jersey, 2007 | Zbl

[7] B. Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, John Wiley Sons, New York, 1996

[8] Yakovlev K. S., Algorithmy planyrovanya peremescheny na ploskosti: Presentation, , 2010 www.raai.org/news/pii/ppt/yakovlev.ppt

[9] R. Fagin, J. Y. Halpern, Y. Moses, M. Y. Vardi, Reasoning about Knowledge, MIT Press, 1995 | MR | Zbl

[10] O. Goldreich, “Foundations of Cryptography — A Primer”, Foundations and Trends in Theoretical Computer Science, 1:1 (2005), 1–116 | DOI | MR

[11] J. Halpern, K. O'Neill, “Anonymity and Information Hiding in Multiagent Systems”, Journal of Computer Security, 13:3 (2005), 483–514

[12] D. Hughes, V. Shmatikov, “Information Hiding, Anonymity and Privacy: a Modular Approach”, Journal of Computer Security, 12:1 (2004), 3–36

[13] S. de Jong, K. Tuyls, K. Verbeeck, “Fairness in Multiagent Systems”, The Knowledge Engineering Review, 23:2 (2008), 153–180 | DOI | MR

[14] S. de Jong, Fairness in Multi-Agent Systems, PhD Thesis, Maastricht University, 2009 http://dl.dropbox.com/u/1505034/website/optima/thesis(17x24).pdf | Zbl

[15] S. M. LaValle, Planning Algorithms, Cambridge University Press, 2006 | MR | Zbl

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

[17] N. V. Shilov, S. O. Shilova, “Etude on theme of Dijkstra”, ACM SIGACT News, 35:3 (2004), 102–108 | DOI

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

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