Geodesic
``Robots in Space'' multiagent problem: information and cryptographic aspects
Prikladnaya Diskretnaya Matematika. Supplement, no. 5 (2012), pp. 61-63.

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

The multiagent problem RinS (Robot in Space) considered here is formulated as follows: there are $n\geq2$ autonomous robots that need to agree without outside on distribution of shelters so that the straight paths to the shelters will not intersect. The problem is closely related to geometry problems, to the assignment problem in Graph Theory, to the convex hull problem in Combinatorial Geometry, and to the path-planning problem in Artificial Intelligence. This paper studies two aspects of the problem – the informational and cryptographic ones: we prove that there is no protocol that solves the RinS transferring a bounded number of bits, and we suggest a protocol that allows robots to check whether their paths intersect, without revealing additional information about their positions. 
@article{PDMA_2012_5_a31,
     author = {A. Yu. Bernstein and N. V. Shilov},
     title = {``Robots in {Space''} multiagent problem: information and cryptographic aspects},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {61--63},
     publisher = {mathdoc},
     number = {5},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2012_5_a31/}
}
TY  - JOUR
AU  - A. Yu. Bernstein
AU  - N. V. Shilov
TI  - ``Robots in Space'' multiagent problem: information and cryptographic aspects
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2012
SP  - 61
EP  - 63
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2012_5_a31/
LA  - ru
ID  - PDMA_2012_5_a31
ER  - 
%0 Journal Article
%A A. Yu. Bernstein
%A N. V. Shilov
%T ``Robots in Space'' multiagent problem: information and cryptographic aspects
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2012
%P 61-63
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2012_5_a31/
%G ru
%F PDMA_2012_5_a31
A. Yu. Bernstein; N. V. Shilov. ``Robots in Space'' multiagent problem: information and cryptographic aspects. Prikladnaya Diskretnaya Matematika. Supplement, no. 5 (2012), pp. 61-63. http://geodesic.mathdoc.fr/item/PDMA_2012_5_a31/

[1] Tanenbaum E., van Steen M., Raspredelënnye sistemy. Printsipy i paradigmy, Piter, SPb., 2003

[2] Tel Zh., Vvedenie v raspredelënnye algoritmy, MTsNMO, M., 2009

[3] Wooldridge M., An Introduction to Multiagent Systems, John Willey Sons Ltd, 2002

[4] Bodin E. V., Garanina N. O., Shilov N. V., “Zadacha o robotakh na Marse (multiagentnyi podkhod k zadache Deikstry)”, Modelirovanie i analiz informatsionnykh sistem, 18:2 (2011), 113–128

[5] Shnaier B., Prikladnaya kriptografiya. Protokoly, algoritmy, iskhodnye teksty na yazyke Si, Triumf, M., 2002

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