“Robots in Space” multiagent problem: information and cryptographic aspects

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.